Dimitrios Tsintsilidas | Rounds vs. Parallel Queries in Student-Teacher Witnessing

Dimitrios Tsintsilidas | Rounds vs. Parallel Queries in Student-Teacher Witnessing

Title history
  • Dimitrios Tsintsilidas | Rounds vs. Parallel Queries in Student-Teacher Witnessing — observed on 20261025-1504 UTC (YouTube)

by Dimitrios Tsintsilidas · View the channel on PSI

Formal & Physical Sciences Computing & Cybersecurity UYComputer scienceUYAMathematical theory of computation
🎙 Dimitrios Tsintsilidas 👥 8K 📅 October 23, 2026 ⏱ 42 min 👁 136 📄 original study 🧭 2026-10-25
Available in: English (current) Français

Keywords

student-teacher gamesparallel queriesbounded arithmeticwitnessing theoremscomplexity classes

Summary

The talk by Dimitrios Tsintsilidas presents recent work on student-teacher games in computational complexity, focusing on the comparison between adaptive rounds and parallel queries. He introduces the concept of total search problems and the complexity classes TFΣP, then formally defines student-teacher games as interactive processes where a student proposes solutions and a teacher provides counterexamples. Motivated by previous work of Grädel, Pudlák, and Skal, the talk addresses the question of whether the separation between classes defined by number of rounds and number of parallel queries is due to interaction or just the quantity of counterexamples. New results show that adaptivity matters: even one more round with a single query per round yields strictly more power than polynomial parallel queries with fewer rounds. Conversely, parallelism is also essential in certain settings. These separations are proven under the assumption NP ⊄ P/poly and generalize to higher levels of the polynomial hierarchy. The talk then connects these results to bounded arithmetic, specifically to length induction and sharply bounded collection axioms. Fine-grained versions of these axioms are studied, leading to witnessing theorems that exactly match the student-teacher game complexity. This yields separations between theories like PV1 and S12, along with intermediate theories defined by BB axioms. The speaker also discusses open problems and implications for unprovability results, including those for circuit lower bounds.

219 words

Critical Evaluation

Value of the Information & Strength of the Argument

The talk provides substantial value by delivering new separation results that clarify the interplay between rounds and parallel queries in student-teacher games. The argumentation is rigorous: the speaker presents formal definitions, states theorems, and outlines proof techniques without hand-waving. The use of illustrative examples (e.g., prime factorization) helps comprehension. The connection to bounded arithmetic is well-motivated and ties together two areas, showing how complexity-theoretic separations imply logical theory separations. The speaker acknowledges limitations (e.g., assumptions like NP ⊄ P/poly) and points out open questions, demonstrating a balanced and honest scientific approach. The overall reasoning is solid and contributes to the field.

Scientific Rigor, Source Quality, Title Accuracy

The scientific rigor is high: the talk is delivered at the Isaac Newton Institute, a respected venue, and the speaker clearly references foundational papers (e.g., by Buss, Cook, Neil, Krajíček, Pudlák, Skal) and discusses prior results accurately. The description provides official links to the institute and the seminar page, which serve as verifiable sources. The title accurately describes the content—focusing on rounds vs. parallel queries in student-teacher witnessing—and no discrepancy between title and material was observed. The audience questions during the talk also indicate engagement and peer scrutiny, further enhancing credibility.

207 words

Title / Content Match

The title accurately reflects the content, which compares the power of rounds and parallel queries in student-teacher witnessing.

Quality & Reliability

8/10

The talk is given by a researcher at an established institute, presents new results with proofs, and references prior work, indicating high reliability.

Key Moments

Markers derived by PSI from the transcript: the creator did not define chapters.

Cited Sources

Contribution & Novelties

The talk presents original contributions that sharpen our understanding of student-teacher games in computational complexity. Specifically, the speaker and his co-author prove structural separations showing that both adaptivity (rounds) and parallelism (queries) are essential resources, and these separations are robust across the polynomial hierarchy. Moreover, the work establishes tight witnessing theorems for fine-grained bounded arithmetic axioms, enabling the separation of several theories that were previously unknown to be distinct. This bridges complexity theory and proof theory, offering new tools for future research.

Pour aller plus loin :

120 words

Radar Profile

The profile shows high scores across all dimensions, with technical level being the highest (9), indicating a specialized and rigorous presentation that is rich in content and reliable.

Reliability 8/10