Proof Complexity
From MaRDI portal
Publication:4629797
Recommendations
Cited in
(73)- Algorithm analysis through proof complexity
- Proof complexity of substructural logics
- On the proof complexity of logics of bounded branching
- Lower bounds for QCDCL via formula gauge
- On the complexity of finding shortest variable disjunction branch-and-bound proofs
- The canonical pairs of bounded depth Frege systems
- Mathematical logic: proof theory, constructive mathematics. Abstracts from the workshop held November 8--14, 2020 (hybrid meeting)
- A simple proof of QBF hardness
- Proof Complexity and the Kneser-Lovász Theorem
- Twelve Problems in Proof Complexity
- scientific article; zbMATH DE number 4095440 (Why is no real title available?)
- Proof Complexity Meets Algebra
- scientific article; zbMATH DE number 2161249 (Why is no real title available?)
- scientific article; zbMATH DE number 1916823 (Why is no real title available?)
- The Complexity of Propositional Proofs
- Substitution and Propositional Proof Complexity
- A separator theorem for hypergraphs and a CSP-SAT algorithm
- INFORMATION IN PROPOSITIONAL PROOFS AND ALGORITHMIC PROOF SEARCH
- scientific article; zbMATH DE number 7561740 (Why is no real title available?)
- NEW RELATIONS AND SEPARATIONS OF CONJECTURES ABOUT INCOMPLETENESS IN THE FINITE DOMAIN
- Short refutations for an equivalence-chain principle for constant-depth formulas
- scientific article; zbMATH DE number 2212138 (Why is no real title available?)
- Propositional proof complexity
- scientific article; zbMATH DE number 7753415 (Why is no real title available?)
- Understanding the Relative Strength of QBF CDCL Solvers and QBF Resolution
- Towards Uniform Certification in QBF
- Space characterizations of complexity measures and size-space trade-offs in propositional proof systems
- INTERLEAVING LOGIC AND COUNTING
- ON THE EXISTENCE OF STRONG PROOF COMPLEXITY GENERATORS
- Unprovability of strong complexity lower bounds in bounded arithmetic
- Indistinguishability obfuscation, range avoidance, and bounded arithmetic
- Equivalence checking for orthocomplemented bisemilattices in log-linear time
- Perfect matching in random graphs is as hard as Tseitin
- Constructive separations and their consequences
- On computing small variable disjunction branch-and-bound trees
- Extended Nullstellensatz proof systems
- QBF merge resolution is powerful but unnatural
- On the strength of Sherali-Adams and Nullstellensatz as propositional proof systems
- Towards an understanding of polynomial calculus: new separations and lower bounds
- The strength of the dominance rule
- The relative strength of \#SAT proof systems
- Failure of feasible disjunction property for k-DNF resolution and NP-hardness of automating it
- Depth-d Frege systems are not automatable unless P\,=\,NP
- Quantum automating TC^0-Frege is LWE-hard
- From proof complexity to circuit complexity via interactive protocols
- A proof complexity conjecture and the incompleteness theorem
- Bounded Henkin quantifiers and the exponential time hierarchy
- Quantum automating \(\mathrm{TC}^0\)-Frege is LWE-hard
- Runtime vs. extracted proof size: an exponential gap for CDCL on QBFs
- A simplified lower bound for implicational logic
- A generalized method for proving polynomial calculus degree lower bounds
- Separations in proof complexity and TFNP
- Learning algorithms from circuit lower bounds
- Proof complexity of positive branching programs
- On protocols for monotone feasible interpolation
- On some \(\boldsymbol{\Sigma}^B_0\)-formulae generalizing counting principles over \(V^0\)
- QCDCL with cube learning or pure literal elimination -- what is best?
- Near-optimal lower bounds on quantifier depth and Weisfeiler-Leman refinement steps
- Strength and limitations of Sherali-Adams and nullstellensatz proof systems
- Understanding the relative strength of QBF CDCL solvers and QBF resolution
- Polynomial calculus for quantified Boolean logic: lower bounds through circuits and degree
- Kernelization, proof complexity and social choice
- On \(\mathrm{NP} \cap \mathrm{coNP}\) proof complexity generators
- Prover-adversary games for systems over (non-deterministic) branching programs
- Towards PNP from extended Frege lower bounds
- A classical proof system for quantum unsatisfiability, based on a matrix Nullstellensatz
- Tropical proof systems: between R(CP) and resolution
- Symmetric proofs in the ideal proof system
- The relative strength of \#SAT proof systems
- Iterated lower bound formulas: a diagonalization-based approach to proof complexity
- New bounds for the ideal proof system in positive characteristic
- A non-uniform view of Craig interpolation in modal logics with linear frames
- Proof complexity of modal resolution
This page was built for publication: Proof Complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4629797)
