The Proof Analysis Problem for Constant-Depth Frege
summary
The gist
The paper presents a parallel algorithm for solving the Proof Analysis Problem (PAP) of Arteche, Atserias, de Rezende, and Khaniki (FOCS 2025)…
In short
The paper presents a parallel algorithm for solving the Proof Analysis Problem (PAP) for Constant-Depth Frege systems, which involves extracting a satisfying assignment from a Resolution lower bound proof. The main contribution is an assignment extraction algorithm computable by polynomial-size TC$^0$ circuits and quasipolynomial-size AC$^0$ circuits, proving correctness within quasipolynomial-size AC$^0$-Frege. This shows that automating proof search on Resolution lower bounds suffices for all formulas.
Key concepts
- Proof Analysis Problem (PAP)
- This is the task of finding a satisfying assignment for a given CNF formula by analyzing its Resolution lower bound proof. Essentially, it asks: can we efficiently extract an answer from the structure of a proof that shows a formula is unsatisfiable?
- Resolution Lower Bound Proof ($ ext{Ref}_s(\varphi)$)
- This is the specific type of proof used in this problem. It's a formal derivation showing that a CNF formula $\varphi$ cannot be satisfied, based on the Resolution rule. The length or structure of this proof is what the algorithm analyzes to extract an assignment.
- AC$^0$-Frege
- This refers to a specific class of propositional proof systems. AC$^0$ is a very restricted class of circuits (constant depth), and Frege systems are general proof systems. The paper proves that the assignment extraction can be done using quasipolynomial-size AC$^0$-Frege proofs, which relates the complexity of the problem to this system.
- Atserias–Müller Lower Bound
- This is a key concept formalized in bounded arithmetic theories (T42($\alpha$)). It provides a lower bound on the complexity or structure of Resolution proofs. The paper uses a new formalization of this bound to establish proof systems' hardness results.
Terminology used across episodes
This episode discusses
- The Proof Analysis Problem for Constant-Depth Frege · Paper Radio
- The Proof Analysis Problem
- Proof complexity of CSP
- Feasibility of Primality in Bounded Arithmetic
- Parallelism and Adaptivity in Student-Teacher Witnessing
- Models of Bounded Arithmetic and variants of Pigeonhole Principle
- An independence of the MIN principle from the PHP principle
- Towards P not equal to NP from Extended Frege lower bounds
The paper
The Proof Analysis Problem for Constant-Depth Frege · Read on arXiv
Noel Arteche, Susanna F. de Rezende, Erfan Khaniki, Kilian Risse
Lund University · University of Copenhagen · University of Oxford · ETH Zürich
We give a parallel algorithm for the Proof Analysis Problem of Arteche, Atserias, de Rezende, and Khaniki (FOCS 2025). The problem asks, given a CNF formula φ on n variables and a proof π of a size- s Resolution lower bound on φ, encoded as Ref s(φ), to extract a satisfying assignment for φ when one exists. The original work gave a polynomial-time extraction algorithm for Resolution refutations that enabled a formalization of the Atserias-Müller lower bound (FOCS 2019) in Extended Frege, but it appeared inherently sequential. We devise a new algorithm that performs assignment extraction in low-depth circuit classes. Specifically, we give an assignment extraction algorithm computable by polynomial-size TC 0 circuits and by quasipolynomial-size AC 0 circuits, and we prove the correctness of the latter within quasipolynomial-size AC 0-Frege. This is thanks to a new formalization of the Atserias-Müller lower bound in the relativized theory 4 2(α) of bounded arithmetic, which corresponds to depth- 4 Frege systems. This yields quasipolynomial-size AC 0-Frege proofs for a broad class of Resolution lower bounds, making progress on a question of Pudlák. A key feature of our approach is an improved parameter regime where we get AC 0-Frege formalizations of Resolution lower bounds Ref s(φ) for all s, including s = n O(1). W also show that the Proof Analysis Problem for AC 0-Frege is NP-hard under quasipolynomial-time reductions, which rules out certain Atserias-Müller-type approaches to the hardness of automating constant-depth Frege. Furthermore, automating AC 0-Frege on Resolution lower bound formulas suffices to automate it on all formulas.
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: We're looking at the paper: "The Proof Analysis Problem for Constant-Depth Frege".
Jane: Here's the gist of the paper. The paper presents a parallel algorithm for solving the Proof Analysis Problem (PAP) of Arteche, Atserias, de Rezende, and Khaniki (FOCS 2025), which asks to extract a satisfying assignment for a CNF formula phi given its Resolution lower bound proof Ref s(phi).
Tom: The primary contribution is an assignment extraction algorithm computable by polynomial-size TC 0 circuits and quasipolynomial-size AC 0 circuits, with the correctness of the latter proven within quasipolynomial-size AC 0-Frege.
Jane: This achievement stems from a novel formalization of the Atserias–Müller lower bound within the relativized theory T42(alpha) of bounded arithmetic, which corresponds to depth-4 Frege systems.
Tom: This new approach yields quasipolynomial-size AC 0-Frege proofs for a broad class of Resolution lower bounds, advancing Pudlák's question.
Paper summary: Tom: So to wrap up, we've seen this paper, "The Proof Analysis Problem for Constant-Depth Frege," and it really focuses on finding a way to extract satisfying assignments from proof size lower bounds in Resolution.
Jane: It’s about giving us an assignment extraction algorithm that works using polynomial size TC0 circuits or quasipolynomial size AC0 circuits >
Lu: The authors achieved this by formalizing the Atserias–Müller lower bound within the theory T42 alpha of bounded arithmetic which links it to depth-four Frege systems >
Meng: For practical terms, this means we have a method for extracting those assignments in low-depth circuit classes without needing impossibly large resources >
Lalam: The paper also shows that while they can solve the extraction problem efficiently for Resolution, the Proof Analysis Problem remains NP-hard under quasipolynomial time reductions for systems that p-simulate depth-two Frege > <ref:2611.08305#pg1>
Tom: It means there are still hard problems when you look at broader classes of logic or larger proof sizes, but we have better tools to navigate those specific lower bounds >
Jane: The authors proved that automating the search just on Resolution lower bounds is enough to automate proof systems over all formulas in quasipolynomial time if the system has a depth greater than or equal to three >
Lu: It's a lot of machinery, but they’re showing how these deep formalizations help us understand exactly where things fall on the complexity spectrum between what's easy and what's computationally intractable >
Conclusion: Tom: So we're wrapping up this talk on "The Proof Analysis Problem for Constant-Depth Frege." Basically, these authors showed that you can actually build an algorithm to find satisfying assignments from Resolution lower bounds using very efficient circuit sizes.
Jane: So, what does that mean for us? Like, if a proof system is shallow—constant depth—we have a better way to analyze its proofs without needing an impossibly big search space.
Lu: Exactly. They’ve done this by finding a new way to look at those lower bounds using bounded arithmetic, which is basically a formal math language for describing the universe. This lets them prove their extraction algorithm works with quasipolynomial size circuits in a setting that's deeper than what was possible before.
Meng: I'm interested in the practical side here. If this works for constant-depth systems, does it mean we can actually automate proof search for those kinds of logic systems on real data? What are the actual resource costs they’re talking about?
Lalam: The paper shows that automating the search just on these Resolution lower bounds is enough to automate proof systems over all formulas if their depth is three or more. This suggests that if you can efficiently find assignments for Resolution proofs, you can actually handle most other proof systems on all possible formulas with reasonable time.
Tom: It means we’re getting tighter constraints on what’s computationally hard in logic. The authors also highlighted that the basic way they used to approach Resolution lower bounds doesn't apply to constant-depth systems because there are NP-hard problems still lurking there.
Jane: So, while this is great for Resolution and bounded arithmetic, it also tells us where the real complexity lies when we move beyond those specific structures. It’s a map of what’s solvable versus what remains hard across different proof systems.
Lu: Right. The next thing we should look at is how these results connect to the broader landscape of proof systems and their limitations, especially when considering those NP-hard cases they mentioned for constant-depth Frege itself.
More episodes
- 2505.16254-Human-AI Writing as Distributed Cognition: Reassessing Collaborative Writing Theories in the Age of LLMs
- 2506.10913-Choreographic Quick Changes: First-Class Location (Set) Polymorphism
- 2507.14812-A Black-Box Approach for Exogenous Replenishment in Online Resource Allocation
- 2507.15448-Frames over finite fields with respect to the Galois inner product and their connections to self-orthogonal and LCD codes
- 2508.21572-NewsReX: An Open-Source Multi-Framework for Neural News Recommendation
- 2509.17028-Impact of Packetization on Network Calculus Analysis
- 2510.17342-AoA Services in 5G Networks: A Framework for Real-World Implementation and Systematic Testing
- 2511.04088-Efficient and rate-optimal list-decoding in the presence of minimal feedback
- 2511.17264-Notes on Stack Machines and Quantum Stack Machines
- 2601.15318-On the closest balanced game