Dr. Susanna de Rezende | The Proof Analysis Problem for Constant-Depth Frege

Item: Dr. Susanna de Rezende | The Proof Analysis Problem for Constant-Depth Frege
Rating: 5
Author: PostSingularity Institute

by Susanna de Rezende · View the channel on PSI

Formal & Physical Sciences Mathematics PBCMathematical foundations PBCDMathematical logic

🎙 Susanna de Rezende 👥 8K 📅 October 19, 2026 ⏱ 37 min 👁 181 📄 original study 🧭 2026-10-20

Available in: English (current) Français

Keywords

proof analysisconstant-depth Fregeresolutionassignment extractionproof complexity

Summary

The talk by Dr. Susanna de Rezende addresses the proof analysis problem for constant-depth Frege systems. She begins with a hypothetical scenario where a machine produces an extended Frege lower bound, raising the question of whether the bound is trivial or meaningful. The problem is formalized as determining whether a given lower bound proof for a formula implies the formula is unsatisfiable, and if so, extracting a satisfying assignment. The talk focuses on resolution as the target proof system, varying the proof system Q that proves the lower bounds. She reviews Pudlák’s result that resolution itself can prove trivial lower bounds, leading to a corollary about the consequences of automizability and analyzability. She discusses the work of Atserias and others on non-automatability and the analyzability of resolution. The main contribution is a new algorithm that extracts satisfying assignments from resolution refutations of lower bound formulas, achieving quasi-polynomial size AC0 circuits, which can be parallelized. The correctness of this algorithm is formalizable in a bounded arithmetic theory corresponding to quasi-polynomial size constant-depth circuits. This implies that constant-depth Frege systems are hard to analyze under quasi-polynomial reductions, and provides a connection between automizability and analyzability for these systems. The talk concludes with open problems, notably whether constant-depth Frege can prove resolution lower bounds in polynomial size.

214 words

Critical Evaluation

Value of the Information & Strength of the Argument

The talk presents significant new results in proof complexity, particularly the parallel extraction of satisfying assignments from resolution lower bound proofs, and the formalization of these results in bounded arithmetic. The argumentation is rigorous, with clear definitions, stated theorems, and proofs sketched. The speaker carefully explains the intuition behind the algorithms and the technical challenges, addressing audience questions effectively. The value of the work is high, as it advances our understanding of the relationship between proof systems and their analyzability, with potential implications for the automizability of weaker proof systems.

Scientific Rigor, Source Quality, Title Accuracy

The talk is scientifically rigorous, conforming to high standards of mathematical exposition. The speaker builds on prior results (Pudlák, Atserias et al.) and clearly delineates new contributions. The sources are primarily the presented research and the references therein, though the description provides links to the institute and seminar page. The title accurately mirrors the content, and the talk itself is a cohesive presentation of original research.

171 words

Title / Content Match

The title accurately describes the talk's focus on the proof analysis problem for constant-depth Frege systems.

Quality & Reliability

9/10

The talk presents rigorous research results in proof complexity, featuring formal definitions, proofs, and discussions with the audience. It is delivered by a recognized researcher from a reputable institution, and the content is highly technical and appears reliable.

Key Moments

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

Cited Sources

Isaac Newton Institute for Mathematical Sciences — Main website of the hosting institution.
Seminar page for the talk — Official seminar page with details of the event.

Contribution & Novelties

The talk introduces a novel parallel algorithm for extracting satisfying assignments from resolution refutations of lower bound formulas, achieving quasi-polynomial size AC0 circuits. This improves on previous sequential algorithms and is formalizable in a bounded arithmetic theory, leading to hardness results for constant-depth Frege systems. The work also provides a new reduction showing that analyzing AC0 lower bounds is NP-hard under quasi-polynomial reductions, and establishes a connection between automizability and analyzability on resolution refutations.

Pour aller plus loin :

Proof complexity — Overview of the field.
Resolution (logic) — The proof system central to the talk.
Bounded arithmetic — Theories used for formalizing the results.

105 words

Radar Profile

The radar profile shows a very high technical level (10) with high quality and quantity of information (9), and equally high reliability (9), indicating a deeply technical and trustworthy talk.

Reliability 9/10