Separations above TFNP from Sherali-Adams Lower Bounds by Deniz Imrek

Value of the Information & Strength of the Argument

The value of the talk lies in its demonstration that proof complexity methods, traditionally used for TFNP separations, can be extended to the more expressive class TF-sigma-2. The argumentation is solid: the speaker carefully defines sigma-2 proof systems, shows how they characterize problems in TF-sigma-2, and then derives separations by proving lower bounds on the degree of Sherali-Adams proofs. The proof sketch is coherent, progressing from an abstract expectation-based argument to a concrete combinatorial covering problem. The results are non-trivial and answer open questions about the dominance of Strong Avoid in TF-sigma-2. The presentation is well-structured, though dense, making it suitable for an expert audience.

Scientific Rigor, Source Quality, Title Accuracy

The talk is scientifically rigorous, grounded in prior work by the speaker and collaborators, as well as classical results in proof complexity and total function problems. The sources are not explicitly cited inline, but the talk references key papers and constructs (e.g., the works of Kleinberg et al., Feige et al., and the speaker’s own recent papers). The provided description includes a link to the ICTS program page, which serves as a reference for the workshop context. The title accurately reflects the content. The talk does not go beyond well-established theoretical frameworks, and the technical details appear correct. The main limitation is that, without seeing the slides, some visual details are lost, but the transcript conveys the core arguments effectively.

The title accurately reflects the talk's central contribution: proving separations above TFNP using Sherali-Adams lower bounds.

9/10

The talk presents rigorous results in computational complexity, with clear methodology and a detailed proof sketch, built on established frameworks.

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

• 01:00Introduction to TFNP and the blackbox model, and the link between TFNP and proof complexity.
• 04:00Introduction of TF-sigma-2 and examples like Strong Avoid, LOP, and List Number.
• 10:00Explanation of sigma-2 proof systems and the preprocessing step of sigma-2 weakenings.
• 15:00Statement of main results: LOP does not reduce to Strong Avoid or List Number.
• 20:00Proof sketch: reducing the problem to a combinatorial covering question and presenting the covering lower bound.
• 25:00Discussion of the decomposition lemma and its role in deriving the separations.

• ICTS Program: Circuits, Communication, and Proofs — Workshop where this talk was presented, providing background on the program.