Reproduce “Debate is efficient with your time” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Jonah Brown-Cohen, Geoffrey Irving, Simon C. Marshall, Ilan Newman, Georgios Piliouras, Mario Szegedy
The paper introduces Debate Query Complexity, measuring the worst-case bits a deterministic verifier queries from an input and debate transcript when two provers compete. Cross-examination checks a challenged computation gate, yielding at most log(m)+3 queries for an m-gate circuit. The authors prove logarithmic DQC characterizes PSPACE/poly, with lower bounds near log(n); human practicality remains untested.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.