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
| CREATOR | Ondřej Ježil, Dimitrios Tsintsilidas |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 130 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-19934