Cover Image

Proof Systems Based on Structured Circuits

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Micun, Matthäus, Berkholz, Christoph
Format:	Preprint
Published:	2026
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

A characterization of efficiently compilable constraint languages
by: Berkholz, Christoph, et al.
Published: (2023)

Supercritical Size-Width Tree-Like Resolution Trade-Offs for Graph Isomorphism
by: Berkholz, Christoph, et al.
Published: (2024)

From Proof Complexity to Circuit Complexity via Interactive Protocols
by: Arteche, Noel, et al.
Published: (2024)

Symmetric Proofs in the Ideal Proof System
by: Dawar, Anuj, et al.
Published: (2025)

Recursive Jump Operators and Optimal Proof Systems
by: Egidy, Fabian
Published: (2026)

Hard CNF Instances for Ideal Proof Systems
by: Hakoniemi, Tuomas, et al.
Published: (2026)

The SPARSE-Relativization Framework and Applications to Optimal Proof Systems
by: Egidy, Fabian
Published: (2026)

Optimal Proof Systems for Complex Sets are Hard to Find
by: Egidy, Fabian, et al.
Published: (2024)

Lower Bounds against the Ideal Proof System in Finite Fields
by: Elbaz, Tal, et al.
Published: (2025)

Heuristics Optimization of Boolean Circuits with application in Attribute Based Encryption
by: Ionita, Alexandru, et al.
Published: (2023)

Distribution-Free Proofs of Proximity
by: Aaronson, Hugo, et al.
Published: (2023)

Separations in Proof Complexity and TFNP
by: Göös, Mika, et al.
Published: (2022)

On the Existence of Algebraic Natural Proofs
by: Chatterjee, Prerona, et al.
Published: (2020)

Multi-Prover Interactive Proof Systems with Leakage
by: Asadi, Vahid R., et al.
Published: (2026)

The Collapse of Unentangled Stoquastic Merlin-Arthur Proof Systems
by: Gay, William, et al.
Published: (2026)

Arithmetic Circuits with Division
by: Sacher, Silas Cato
Published: (2025)

On the Interplay of Cube Learning and Dependency Schemes in QCDCL Proof Systems
by: Choudhury, Abhimanyu, et al.
Published: (2025)

On the Bit Size of Sum-of-Squares Proofs for Symmetric Formulations
by: Bortolotti, Alex, et al.
Published: (2025)

Proof Complexity and Feasible Interpolation
by: Tabatabai, Amirhossein Akbar
Published: (2025)

Symmetric Distributions from Shallow Circuits
by: Kane, Daniel M., et al.
Published: (2025)

Symmetric Algebraic Circuits and Homomorphism Polynomials
by: Dawar, Anuj, et al.
Published: (2025)

Simple Circuit Extensions for XOR in PTIME
by: Carmosino, Marco, et al.
Published: (2025)

Lower bounds for planar Arithmetic Circuits
by: Ramya, C., et al.
Published: (2025)

Circuits and Backdoors: Five Shades of the SETH
by: Lampis, Michael
Published: (2024)

Nearest Neighbor Complexity and Boolean Circuits
by: DiCicco, Mason, et al.
Published: (2024)

Proof complexity of Mal'tsev CSP
by: Gaysin, Azza
Published: (2025)

A Quadratic Lower Bound for Noncommutative Circuits
by: Shastri, Pratik
Published: (2026)

Optimal Depth-Three Circuits for Inner Product
by: Gurumukhani, Mohit, et al.
Published: (2026)

Improved Bounds on the Space Complexity of Circuit Evaluation
by: Shalunov, Yakov
Published: (2025)

Average-Case Hardness of Binary-Encoded Clique in Proof and Communication Complexity
by: de Rezende, Susanna F., et al.
Published: (2026)

Convergent Gate Elimination and Constructive Circuit Lower Bounds
by: Carmosino, Marco, et al.
Published: (2026)

Exponential Lower Bounds on the Size of ResLin Proofs of Nearly Quadratic Depth
by: Bhattacharya, Sreejata Kishor, et al.
Published: (2025)

Top-Down Lower Bounds for Depth-Four Circuits
by: Göös, Mika, et al.
Published: (2023)

Boolean Circuit Complexity and Two-Dimensional Cover Problems
by: Cavalar, Bruno P., et al.
Published: (2025)

Interactive Proofs For Distribution Testing With Conditional Oracles
by: Biswas, Ari, et al.
Published: (2025)

Separation Results for Constant-Depth and Multilinear Ideal Proof Systems
by: Behera, Amik Raj, et al.
Published: (2026)

Tight Lower Bounds for Block-Structured Integer Programs
by: Hunkenschröder, Christoph, et al.
Published: (2024)

Monotone Circuit Complexity of Matching
by: Cavalar, Bruno, et al.
Published: (2025)

Optimal Monotone Depth-Three Circuit Lower Bounds for Majority
by: Gurumukhani, Mohit, et al.
Published: (2026)

Exponential-Size Circuit Complexity is Comeager in Symmetric Exponential Time
by: Hitchcock, John M.
Published: (2026)