Noel Arteche | Automating constant-depth Frege on CNF formulas is ETH-Hard, assuming no short...

Noel Arteche | Automating constant-depth Frege on CNF formulas is ETH-Hard, assuming no short...

Title history
  • Noel Arteche | Automating constant-depth Frege on CNF formulas is ETH-Hard, assuming no short... — observed on 20261025-1506 UTC (YouTube)

by Noel Arteche · View the channel on PSI

Formal & Physical Sciences Computing & Cybersecurity UYComputer scienceUYAMathematical theory of computation
🎙 Noel Arteche 👥 8K 📅 October 22, 2026 ⏱ 38 min 👁 214 📄 original study 🧭 2026-10-25
Available in: English (current) Français

Keywords

proof complexityFrege systemsautomationETHpigeonhole principle

Summary

The talk presents a complexity-theoretic result on automated proof search in propositional logic. It shows that automating constant-depth Frege (ACC0-Frege) on CNF formulas is ETH-hard under the assumption that there are no shorter proofs of the weak pigeonhole principle. The speaker reviews the background on automatability, discusses prior results, and introduces a new reduction from SAT to the propositional formula encoding a refutation of the input, adapting the Atserias-Müller argument. He also discusses the necessity and sufficiency of the weak pigeonhole principle for proving tight resolution lower bounds in this setting. The talk details the technical steps, including a parallel compression argument and the formalization in bounded arithmetic theories, and highlights implications for the proof analysis problem.

117 words

Critical Evaluation

Value of the Information & Strength of the Argument

The argument is rigorous and well-structured, building on prior work by Atserias and Müller and addressing the role of the weak pigeonhole principle. The speaker clearly explains the limitations of previous approaches and the novelty of the new reduction. The technical details are presented with precision, making a strong case for the main theorem.

Scientific Rigor, Source Quality, Title Accuracy

The talk is delivered at the Isaac Newton Institute, a reputable venue for mathematical sciences. The speaker cites specific papers (e.g., Atserias-Müller 2020, Li-Ren, etc.) and uses them appropriately. The title is accurate and descriptive, matching the content precisely. No public comments were provided for analysis.

115 words

Title / Content Match

The title accurately reflects the content: the talk presents a proof that automating constant-depth Frege is ETH-hard under an assumption about the weak pigeonhole principle.

Quality & Reliability

9/10

Presentation of original research at a recognized institute, with rigorous mathematical content and references to known results.

Key Moments

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

Cited Sources

Contribution & Novelties

The talk contributes a new reduction showing that automating constant-depth Frege is ETH-hard under the assumption that weak pigeonhole principle has no short proofs. It also clarifies the necessity and sufficiency of the weak pigeonhole principle for proving tight resolution lower bounds, providing a clean formalization in bounded arithmetic.

Pour aller plus loin :

  • Frege system — A formal proof system used in propositional logic; the talk deals with constant-depth variants.
  • Exponential Time Hypothesis — The complexity assumption used to establish hardness results in the talk.
  • Pigeonhole principle — A combinatorial principle central to the talk, specifically the weak pigeonhole principle.

101 words

Radar Profile

The radar profile shows very high scores in quality, technical level, and reliability, with a slightly lower quantity of information, reflecting a dense but focused presentation.

Reliability 9/10