Dr. Robert Robere | Polynomial Interpolation for Sherali-Adams Lower Bounds Part I

Dr. Robert Robere | Polynomial Interpolation for Sherali-Adams Lower Bounds Part I

Title history
  • Dr. Robert Robere | Polynomial Interpolation for Sherali-Adams Lower Bounds Part I — observed on 20261028-1135 UTC (YouTube)

by Robert Robere · View the channel on PSI

Formal & Physical Sciences Computing & Cybersecurity UYComputer scienceUYAMathematical theory of computation
🎙 Robert Robere 👥 2K 📅 October 28, 2026 ⏱ 60 min 👁 1 📄 original study 🧭 2026-10-28
Available in: English (current) Français

Keywords

Sherali-Adamsproof complexitylower boundspolynomial interpolationautomatability

Summary

This seminar by Dr. Robert Robere presents new lower-bound techniques for the Sherali-Adams proof system using polynomial interpolation. The talk begins with a review of the Sherali-Adams system, defining its algebraic representation as a system of polynomial equations over the reals, and the notion of a conical hint term. The speaker then introduces the key concept of pseudo-expectations and pseudo-distributions, which are central to proving degree lower bounds. Two main results are announced: first, a formula that has polynomial-size resolution-2 proofs but requires exponential size for Sherali-Adams, and second, that Sherali-Adams is not automatable unless P equals NP, a result that was previously claimed but retracted. The technical core involves constructing pseudo-distributions that agree on local marginals and never falsify clauses, using matching-based distributions for the pigeonhole principle as an illustration. The talk also discusses the distinction between size and degree, the use of dual variables, and why random restriction arguments are needed to convert degree lower bounds into size lower bounds. Throughout, the presentation is interactive with audience questions, and the speaker emphasizes the difficulty of these constructions due to the positivity requirement for the conical hint term.

189 words

Critical Evaluation

Value of the Information & Strength of the Argument

The talk delivers significant new results in proof complexity, filling a gap in the understanding of Sherali-Adams lower bounds. The argumentation is rigorous and well-structured, starting from fundamental definitions and building up to the technical arguments. The speaker clearly motivates each step, explains the barriers encountered, and gives intuitive examples such as the pseudo-distribution for the pigeonhole principle. The interaction with the audience clarifies subtle points about degree and size, and the speaker candidly discusses a previously retracted result, enhancing the credibility of the presentation.

Scientific Rigor, Source Quality, Title Accuracy

The talk adheres to a high standard of scientific rigor, with precise definitions and careful explanations. While the transcript does not explicitly cite external papers, the context of the Isaac Newton Institute and the speaker’s affiliation (McGill University) add authority. The title accurately reflects the content, focusing on polynomial interpolation as a tool for Sherali-Adams lower bounds, and the talk indeed spends effort on introducing and using this technique. The description provides links to the institute and the specific event page, which serve as reliable references for the seminar context.

190 words

Title / Content Match

The title accurately describes the talk, which focuses on using polynomial interpolation to establish lower bounds for the Sherali-Adams proof system.

Quality & Reliability

9/10

Talk by a recognized researcher at a prestigious institute, presenting original results with rigorous technical detail.

Key Moments

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

Cited Sources

Contribution & Novelties

The talk presents original contributions: an exponential separation between Sherali-Adams and resolution-2, and the non-automatability of Sherali-Adams unless P=NP. These results extend the known landscape of proof complexity and solve a problem that had been previously claimed but retracted. The novel use of polynomial interpolation in constructing pseudo-distributions represents a methodological advance.

Pour aller plus loin :

  • Sherali-Adams hierarchy — Relevant framework for linear programming relaxations, directly related to the proof system discussed.
  • Proof complexity — The field in which the results are situated, covering various proof systems and lower bounds.
  • Polynomial interpolation — The mathematical technique that underpins the new lower-bound method.

103 words

Radar Profile

The profile shows a very high technical level and strong quality and reliability, reflecting a rigorous academic talk. The quantity of information is slightly lower, as the one-hour format limits the depth, but the content is dense and significant.

Reliability 9/10