Narrow Proofs May Be Maximally Long (Q5277920): Difference between revisions

@@ Property / cites work @@
+Mutilated chessboard problem is exponentially hard for resolution
+Normal rank
@@ Property / cites work @@
+Space Complexity in Propositional Calculus
@@ Property / cites work: Space Complexity in Propositional Calculus / rank @@
+Normal rank
@@ Property / cites work @@
+A combinatorial characterization of resolution width
+Normal rank
@@ Property / cites work @@
+Clause-Learning Algorithms with Many Restarts and Bounded-Width Resolution
+Normal rank
@@ Property / cites work @@
+LOWER BOUNDS FOR DNF-REFUTATIONS OF A RELATIVIZED WEAK PIGEONHOLE PRINCIPLE
+Normal rank
@@ Property / cites work @@
+Hypercontractivity, sum-of-squares proofs, and their applications
+Normal rank
@@ Property / cites work @@
+Q4399249
@@ Property / cites work: Q4399249 / rank @@
+Normal rank
@@ Property / cites work @@
+Time-space tradeoffs in resolution
@@ Property / cites work: Time-space tradeoffs in resolution / 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 @@
+Some trade-off results for polynomial calculus
@@ Property / cites work: Some trade-off results for polynomial calculus / rank @@
+Normal rank
@@ Property / cites work @@
+Size-Space Tradeoffs for Resolution
@@ Property / cites work: Size-Space Tradeoffs for Resolution / rank @@
+Normal rank
@@ Property / cites work @@
+Space complexity of random formulae in resolution
@@ Property / cites work: Space complexity of random formulae in resolution / rank @@
+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 @@
+Parameterized Complexity of DPLL Search Procedures
+Normal rank
@@ Property / cites work @@
+Parameterized Bounded-Depth Frege Is not Optimal
@@ Property / cites work: Parameterized Bounded-Depth Frege Is not Optimal / rank @@
+Normal rank
@@ Property / cites work @@
+Q5769706
@@ Property / cites work: Q5769706 / rank @@
+Normal rank
@@ Property / cites work @@
+A Framework for Space Complexity in Algebraic Proof Systems
+Normal rank
@@ Property / cites work @@
+Space proof complexity for random 3-CNFs
@@ Property / cites work: Space proof complexity for random 3-CNFs / rank @@
+Normal rank
@@ Property / cites work @@
+Total Space in Resolution
@@ Property / cites work: Total Space in Resolution / rank @@
+Normal rank
@@ Property / cites work @@
+Optimality of size-width tradeoffs for resolution
@@ Property / cites work: Optimality of size-width tradeoffs for resolution / rank @@
+Normal rank
@@ Property / cites work @@
+Polybori: A framework for Gröbner-basis computations with Boolean polynomials
+Normal rank
@@ Property / cites work @@
+New developments in the theory of Gröbner bases and applications to formal verification
+Normal rank
@@ Property / cites work @@
+Convex Relaxations and Integrality Gaps
@@ Property / cites work: Convex Relaxations and Integrality Gaps / rank @@
+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 @@
+Relativization makes contradictions harder for resolution
+Normal rank
@@ Property / cites work @@
+Tight rank lower bounds for the Sherali-Adams proof system
+Normal rank
@@ Property / cites work @@
+Towards an Understanding of Polynomial Calculus: New Separations and Lower Bounds
+Normal rank
@@ Property / cites work @@
+Parity, circuits, and the polynomial-time hierarchy
+Normal rank
@@ Property / cites work @@
+On Resolution with Clauses of Bounded Size
@@ Property / cites work: On Resolution with Clauses of Bounded Size / rank @@
+Normal rank
@@ Property / cites work @@
+Q5645210
@@ Property / cites work: Q5645210 / rank @@
+Normal rank
@@ Property / cites work @@
+Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
+Normal rank
@@ Property / cites work @@
+Q4807964
@@ Property / cites work: Q4807964 / rank @@
+Normal rank
@@ Property / cites work @@
+Complexity of Null- and Positivstellensatz proofs
@@ Property / cites work: Complexity of Null- and Positivstellensatz proofs / rank @@
+Normal rank
@@ Property / cites work @@
+Communication lower bounds via critical block sensitivity
+Normal rank
@@ Property / cites work @@
+The intractability of resolution
@@ Property / cites work: The intractability of resolution / rank @@
+Normal rank
@@ Property / cites work @@
+Lower bounds for the polynomial calculus and the Gröbner basis algorithm
+Normal rank
@@ Property / cites work @@
+Q4537750
@@ Property / cites work: Q4537750 / rank @@
+Normal rank
@@ Property / cites work @@
+A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
+Normal rank
@@ Property / cites work @@
+Q4601842
@@ Property / cites work: Q4601842 / rank @@
+Normal rank
@@ Property / cites work @@
+Cones of Matrices and Set-Functions and 0–1 Optimization
+Normal rank
@@ Property / cites work @@
+GRASP: a search algorithm for propositional satisfiability
+Normal rank
@@ Property / cites work @@
+A Generalized Method for Proving Polynomial Calculus Degree Lower Bounds
+Normal rank
@@ Property / cites work @@
+Q4934563
@@ Property / cites work: Q4934563 / rank @@
+Normal rank
@@ Property / cites work @@
+Proofs as Games
@@ Property / cites work: Proofs as Games / rank @@
+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 @@
+A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
+Normal rank
@@ Property / cites work @@
+Q2816413
@@ Property / cites work: Q2816413 / rank @@
+Normal rank
@@ Property / cites work @@
+Hard examples for resolution
@@ Property / cites work: Hard examples for resolution / rank @@
+Normal rank