Parallelism and Adaptivity in Student-Teacher Witnessing

Ondřej Ježil, Dimitrios Tsintsilidas · 2026

Read Parallelism and Adaptivity in Student-Teacher Witnessing by Ondřej Ježil, Dimitrios Tsintsilidas (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-19934.txt.

Description

Student-teacher games model a restricted student trying to produce a string with a property that can be refuted. An all-powerful teacher refutes wrong candidates with counterexamples. A 2026 arXiv paper by Ondřej Ježil and Dimitrios Tsintsilidas introduces subclasses of total search problems sorted by rounds and answers per round.

By a classical result, such games capture how certain formulas are witnessed in bounded arithmetic. Assuming the polynomial hierarchy does not collapse, the authors separate the new classes for different round and query counts. Applications include a general witnessing theorem for theories built on fine-grained induction and collection principles. They also include separations of those theories, resolutions of two open problems in bounded arithmetic, and extensions of results showing certain circuit bounds cannot be proved in stronger theories.

Catalog record

CREATOROndřej Ježil, Dimitrios Tsintsilidas
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE130 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-19934

Browse the full library · About the Tower of Babel