Theory Seminar, Wednesday Dec 03: Roy Schwartz (Technion) - On Approximating Cutwidth and Pathwidth
0 views
Skip to first unread message
Arnold Filtser
Nov 26, 2025, 8:29:09 AM (11 days ago) Nov 26
to BIU Theory Seminar, Roy Schwartz
Hi all,
Next week (Wed Dec 03, at 12) we will meet for our theory seminar.
Location: Building 503 room 226.
Looking forward to seeing you all there,
Speaker: Roy Schwartz (Technion)
Title: On Approximating Cutwidth and Pathwidth
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: On Approximating Cutwidth and Pathwidth
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, 9:07:01 AM (11 days ago) Nov 26
to BIU Theory Seminar, Roy Schwartz
Iv'e sent the title+abstract of the previous talk by mistake.
The correct details of the talk next week by Roy Schwartz appear below.
See you next week,
Arnold
Speaker: Roy Schwartz (Technion)
Title: On Approximating Cutwidth and Pathwidth
Title: On Approximating Cutwidth and Pathwidth
Abstract: We study graph ordering problems with a min-max objective.
A classical problem of this type is cutwidth, where given a graph we want to order its vertices such that the number of edges crossing any point is minimized.
We give a $ \log^{1+o(1)}(n)$ approximation for the problem, improving upon the previous poly-logarithmic guarantees based on the standard recursive balanced partitioning approach of Leighton and Rao (FOCS'88).
Our key idea is a new metric decomposition procedure that is suitable for handling min-max objectives, which could be of independent interest.
We give a $ \log^{1+o(1)}(n)$ approximation for the problem, improving upon the previous poly-logarithmic guarantees based on the standard recursive balanced partitioning approach of Leighton and Rao (FOCS'88).
Our key idea is a new metric decomposition procedure that is suitable for handling min-max objectives, which could be of independent interest.
We also use this to show other results, including an improved $ \log^{1+o(1)}(n)$ approximation for computing the pathwidth of a graph.
Joint work with Nikhil Bansal and Dor Katzelnick
Arnold Filtser
Dec 3, 2025, 4:01:05 AM (5 days ago) Dec 3
to BIU Theory Seminar, Roy Schwartz
The talk starts in one hour!
Reply all
Reply to author
Forward
0 new messages