Theory Seminar, Wednesday Nov 26: Ilan Newman (Haifa) - Query complexity of Debate
2 views
Skip to first unread message
Arnold Filtser
Nov 19, 2025, 8:47:22 AMNov 19
to BIU Theory Seminar, Ilan Newman
Hi all,
Next week (Wed Nov 19, at 12) we will meet for our theory seminar.
Location: Building 503 room 226.
Looking forward to seeing you all there,
Speaker: Ilan Newman (Haifa)
Title: Query complexity of Debate
Abstract: AI safety via debate uses two competing models to help a human judge verify complex computational tasks. Previous work has established what problems debate can solve in principle, but has not analysed the practical cost of human oversight: how many queries must the judge make to the debate transcript? We introduce \emph{Debate Query Complexity} (DQC), the minimum number of bits a verifier must inspect to correctly decide a debate.
Surprisingly, we find that $\mathsf{PSPACE/poly}$ (the class of problems which debate can efficiently decide) is precisely the class of functions decidable with $O(\log n)$ queries. This characterisation shows that debate is remarkably query-efficient: even for highly complex problems, logarithmic oversight suffices. We also establish that functions depending on all their input bits require $\Omega(\log n)$ queries, and that any function computable by a circuit of size $s$ satisfies $DQC(f) \leq \log(s) + 3$. Interestingly, this last result implies that proving DQC lower bounds of $\log(n) + 6$ for languages in $\mathsf{P}$ would yield new circuit lower bounds, connecting debate query complexity to central questions in circuit complexity.
This is joint work with Jonah Brown-Cohen, Geoffrey Irving, Simon C. Marshall, Georgios Piliouras and Mario Szegedy.
Title: Query complexity of Debate
Abstract: AI safety via debate uses two competing models to help a human judge verify complex computational tasks. Previous work has established what problems debate can solve in principle, but has not analysed the practical cost of human oversight: how many queries must the judge make to the debate transcript? We introduce \emph{Debate Query Complexity} (DQC), the minimum number of bits a verifier must inspect to correctly decide a debate.
Surprisingly, we find that $\mathsf{PSPACE/poly}$ (the class of problems which debate can efficiently decide) is precisely the class of functions decidable with $O(\log n)$ queries. This characterisation shows that debate is remarkably query-efficient: even for highly complex problems, logarithmic oversight suffices. We also establish that functions depending on all their input bits require $\Omega(\log n)$ queries, and that any function computable by a circuit of size $s$ satisfies $DQC(f) \leq \log(s) + 3$. Interestingly, this last result implies that proving DQC lower bounds of $\log(n) + 6$ for languages in $\mathsf{P}$ would yield new circuit lower bounds, connecting debate query complexity to central questions in circuit complexity.
This is joint work with Jonah Brown-Cohen, Geoffrey Irving, Simon C. Marshall, Georgios Piliouras and Mario Szegedy.
Arnold Filtser
Nov 26, 2025, 4:00:25 AM (12 days ago) Nov 26
to BIU Theory Seminar, Ilan Newman
The seminar starts in one hour!
Reply all
Reply to author
Forward
0 new messages