Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes (Q5889793): Difference between revisions

@@ Property / cites work @@
+Lower bounds for k-DNF resolution on random 3-CNFs
+Normal rank
@@ Property / cites work @@
+Q4004078
@@ Property / cites work: Q4004078 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4993273
@@ Property / cites work: Q4993273 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4542576
@@ Property / cites work: Q4542576 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4790380
@@ Property / cites work: Q4790380 / rank @@
+Normal rank
@@ Property / cites work @@
+Random CNF's are hard for the polynomial calculus
@@ Property / cites work: Random CNF's are hard for the polynomial calculus / rank @@
+Normal rank
@@ Property / cites work @@
+Symmetric approximation arguments for monotone lower bounds without sunflowers
+Normal rank
@@ Property / cites work @@
+Lower bounds for cutting planes proofs with small coefficients
+Normal rank
@@ Property / cites work @@
+Edmonds polytopes and a hierarchy of combinatorial problems
+Normal rank
@@ Property / cites work @@
+Q4228436
@@ Property / cites work: Q4228436 / rank @@
+Normal rank
@@ Property / cites work @@
+Many hard examples for resolution
@@ Property / cites work: Many hard examples for resolution / rank @@
+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 @@
+Q5092485
@@ Property / cites work: Q5092485 / rank @@
+Normal rank
@@ Property / cites work @@
+Proof of the Satisfiability Conjecture for Large k
+Normal rank
@@ Property / cites work @@
+Relations between average case complexity and approximation complexity
+Normal rank
@@ Property / cites work @@
+Semantic Versus Syntactic Cutting Planes
@@ Property / cites work: Semantic Versus Syntactic Cutting Planes / rank @@
+Normal rank
@@ Property / cites work @@
+Random  \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes
+Normal rank
@@ Property / cites work @@
+Parametrized complexity theory.
@@ Property / cites work: Parametrized complexity theory. / rank @@
+Normal rank
@@ Property / cites work @@
+A threshold for unsatisfiability
@@ Property / cites work: A threshold for unsatisfiability / rank @@
+Normal rank
@@ Property / cites work @@
+Outline of an algorithm for integer solutions to linear programs
+Normal rank
@@ Property / cites work @@
+Communication lower bounds via critical block sensitivity
+Normal rank
@@ Property / cites work @@
+An exponential lower bound for the size of monotone real circuits
+Normal rank
@@ Property / cites work @@
+A note on monotone real circuits
@@ Property / cites work: A note on monotone real circuits / rank @@
+Normal rank
@@ Property / cites work @@
+Boolean function complexity. Advances and frontiers.
+Normal rank
@@ Property / cites work @@
+Monotone Circuits for Connectivity Require Super-Logarithmic Depth
+Normal rank
@@ Property / cites work @@
+Critical Behavior in the Satisfiability of Random Boolean Expressions
+Normal rank
@@ Property / cites work @@
+Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
+Normal rank
@@ Property / cites work @@
+Interpolation by a Game
@@ Property / cites work: Interpolation by a Game / rank @@
+Normal rank
@@ Property / cites work @@
+Communication Complexity
@@ Property / cites work: Communication Complexity / rank @@
+Normal rank
@@ Property / cites work @@
+On semantic cutting planes with very small coefficients
+Normal rank
@@ Property / cites work @@
+Search Problems in the Decision Tree Model
@@ Property / cites work: Search Problems in the Decision Tree Model / rank @@
+Normal rank
@@ Property / cites work @@
+Probability and Computing
@@ Property / cites work: Probability and Computing / rank @@
+Normal rank
@@ Property / cites work @@
+Lower bounds for resolution and cutting plane proofs and monotone computations
+Normal rank
@@ Property / cites work @@
+Separation of the monotone NC hierarchy
@@ Property / cites work: Separation of the monotone NC hierarchy / rank @@
+Normal rank
@@ Property / cites work @@
+Q3758729
@@ Property / cites work: Q3758729 / rank @@
+Normal rank
@@ Property / cites work @@
+Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic
+Normal rank
@@ Property / cites work @@
+Generating hard satisfiability problems
@@ Property / cites work: Generating hard satisfiability problems / rank @@
+Normal rank