Reflections on Proof Complexity and Counting Principles (Q5027248): Difference between revisions

@@ Property / cites work @@
+On the power and limitations of branch and cut
@@ Property / cites work: On the power and limitations of branch and cut / rank @@
+Normal rank
@@ Property / cites work @@
+The Complexity of Propositional                                                   Proofs
@@ Property / cites work: The Complexity of Propositional Proofs / rank @@
+Normal rank
@@ Property / cites work @@
+Hard examples for resolution
@@ Property / cites work: Hard examples for resolution / rank @@
+Normal rank
@@ Property / cites work @@
+Q5593816
@@ Property / cites work: Q5593816 / rank @@
+Normal rank
@@ Property / cites work @@
+Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
+Normal rank
@@ Property / cites work @@
+Regular Resolution Versus Unrestricted Resolution
@@ Property / cites work: Regular Resolution Versus Unrestricted Resolution / rank @@
+Normal rank
@@ Property / cites work @@
+Davis-Putnam resolution versus unrestricted resolution
+Normal rank
@@ Property / cites work @@
+Cops-robber games and the resolution of Tseitin formulas
+Normal rank
@@ Property / cites work @@
+Bounded-Depth Frege Complexity of Tseitin Formulas for All Graphs
+Normal rank
@@ Property / cites work @@
+Q3002781
@@ Property / cites work: Q3002781 / rank @@
+Normal rank
@@ Property / cites work @@
+Satisfiability, branch-width and Tseitin tautologies
+Normal rank
@@ Property / cites work @@
+Q4993273
@@ Property / cites work: Q4993273 / rank @@
+Normal rank
@@ Property / cites work @@
+Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs
+Normal rank
@@ Property / cites work @@
+Q4399249
@@ Property / cites work: Q4399249 / rank @@
+Normal rank
@@ Property / cites work @@
+Lower Bounds for Lovász–Schrijver Systems and Beyond Follow from Multiparty Communication Complexity
+Normal rank
@@ Property / cites work @@
+Approximation and Small-Depth Frege Proofs
@@ Property / cites work: Approximation and Small-Depth Frege Proofs / rank @@
+Normal rank
@@ Property / cites work @@
+Hard examples for the bounded depth Frege proof system
+Normal rank
@@ Property / cites work @@
+Short proofs are narrow—resolution made simple
@@ Property / cites work: Short proofs are narrow—resolution made simple / rank @@
+Normal rank
@@ Property / cites work @@
+Lower bounds for cutting planes proofs with small coefficients
+Normal rank
@@ Property / cites work @@
+Approximate Constraint Satisfaction Requires Large LP Relaxations
+Normal rank
@@ Property / cites work @@
+Edmonds polytopes and a hierarchy of combinatorial problems
+Normal rank
@@ Property / cites work @@
+Many hard examples for resolution
@@ Property / cites work: Many hard examples for resolution / rank @@
+Normal rank
@@ Property / cites work @@
+Q4228469
@@ Property / cites work: Q4228469 / rank @@
+Normal rank
@@ Property / cites work @@
+The relative efficiency of propositional proof systems
+Normal rank
@@ Property / cites work @@
+On the complexity of cutting-plane proofs
@@ Property / cites work: On the complexity of cutting-plane proofs / rank @@
+Normal rank
@@ Property / cites work @@
+A machine program for theorem-proving
@@ Property / cites work: A machine program for theorem-proving / rank @@
+Normal rank
@@ Property / cites work @@
+A Computing Procedure for Quantification Theory
@@ Property / cites work: A Computing Procedure for Quantification Theory / rank @@
+Normal rank
@@ Property / cites work @@
+Semialgebraic Proofs and Efficient Algorithm Design
+Normal rank
@@ Property / cites work @@
+Explicit constructions of linear-sized superconcentrators
+Normal rank
@@ Property / cites work @@
+On the complexity of regular resolution and the Davis-Putnam procedure
+Normal rank
@@ Property / cites work @@
+Monotone circuit lower bounds from resolution
@@ Property / cites work: Monotone circuit lower bounds from resolution / rank @@
+Normal rank
@@ Property / cites work @@
+Outline of an Algorithm for Integer Solutions to Linear Programs and An Algorithm for the Mixed Integer Problem
+Normal rank
@@ Property / cites work @@
+Extension Complexity of Independent Set Polytopes
@@ Property / cites work: Extension Complexity of Independent Set Polytopes / rank @@
+Normal rank
@@ Property / cites work @@
+Communication lower bounds via critical block sensitivity
+Normal rank
@@ Property / cites work @@
+Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
+Normal rank
@@ Property / cites work @@
+The intractability of resolution
@@ Property / cites work: The intractability of resolution / rank @@
+Normal rank
@@ Property / cites work @@
+An Average-Case Depth Hierarchy Theorem for Boolean Circuits
+Normal rank
@@ Property / cites work @@
+Expander graphs and their applications
@@ Property / cites work: Expander graphs and their applications / rank @@
+Normal rank
@@ Property / cites work @@
+A DNF without Regular Shortest Consensus Path
@@ Property / cites work: A DNF without Regular Shortest Consensus Path / rank @@
+Normal rank
@@ Property / cites work @@
+Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs
+Normal rank
@@ Property / cites work @@
+Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
+Normal rank
@@ Property / cites work @@
+An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
+Normal rank
@@ Property / cites work @@
+Exponential lower bounds for the pigeonhole principle
+Normal rank
@@ Property / cites work @@
+Poly-logarithmic Frege depth lower bounds via an expander switching lemma
+Normal rank
@@ Property / cites work @@
+Communication Complexity
@@ Property / cites work: Communication Complexity / rank @@
+Normal rank
@@ Property / cites work @@
+Monotone circuits for matching require linear depth
+Normal rank
@@ Property / cites work @@
+Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic
+Normal rank
@@ Property / cites work @@
+Lower bounds for the polynomial calculus
@@ Property / cites work: Lower bounds for the polynomial calculus / rank @@
+Normal rank
@@ Property / cites work @@
+Resolution lower bounds for perfect matching principles
+Normal rank
@@ Property / cites work @@
+On Cutting Planes
@@ Property / cites work: On Cutting Planes / rank @@
+Normal rank
@@ Property / cites work @@
+The Complexity of Propositional Proofs
@@ Property / cites work: The Complexity of Propositional Proofs / rank @@
+Normal rank
@@ Property / cites work @@
+Dag-like communication and its applications
@@ Property / cites work: Dag-like communication and its applications / rank @@
+Normal rank
@@ Property / cites work @@
+A Near-Optimal Separation of Regular and General Resolution
+Normal rank
@@ Property / cites work @@
+Simplified lower bounds for propositional proofs
@@ Property / cites work: Simplified lower bounds for propositional proofs / rank @@
+Normal rank
@@ Property / cites work @@
+Lower bounds for resolution and cutting plane proofs and monotone computations
+Normal rank
@@ Property / cites work @@
+Near-optimal lower bounds on regular resolution refutations of Tseitin formulas for all constant-degree graphs
+Normal rank
@@ Property / cites work @@
+Linear gaps between degrees for the polynomial calculus modulo distinct primes
+Normal rank