A stronger LP bound for formula size lower bounds via clique constraints (Q428879): Difference between revisions

@@ Property / cites work @@
+Quantum lower bounds by quantum arguments
@@ Property / cites work: Quantum lower bounds by quantum arguments / rank @@
+Normal rank
@@ Property / cites work @@
+Any AND-OR Formula of Size <i>N</i> Can Be Evaluated in Time $N^{1/2+o(1)}$ on a Quantum Computer
+Normal rank
@@ Property / cites work @@
+Decompositions of positive self-dual Boolean functions
+Normal rank
@@ Property / cites work @@
+Minimum self-dual decompositions of positive dual-minor Boolean functions
+Normal rank
@@ Property / cites work @@
+Geometric algorithms and combinatorial optimization
+Normal rank
@@ Property / cites work @@
+The Shrinkage Exponent of de Morgan Formulas is 2
@@ Property / cites work: The Shrinkage Exponent of de Morgan Formulas is 2 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3549652
@@ Property / cites work: Q3549652 / rank @@
+Normal rank
@@ Property / cites work @@
+Two applications of information complexity
@@ Property / cites work: Two applications of information complexity / rank @@
+Normal rank
@@ Property / cites work @@
+Fractional Covers and Communication Complexity
@@ Property / cites work: Fractional Covers and Communication Complexity / rank @@
+Normal rank
@@ Property / cites work @@
+Monotone Circuits for Connectivity Require Super-Logarithmic Depth
+Normal rank
@@ Property / cites work @@
+Complexity of the realization of a linear function in the class of \(\Pi\)-circuits
+Normal rank
@@ Property / cites work @@
+Improvements on Khrapchenko's theorem
@@ Property / cites work: Improvements on Khrapchenko's theorem / rank @@
+Normal rank
@@ Property / cites work @@
+The quantum adversary method and classical formula size power bounds
+Normal rank
@@ Property / cites work @@
+A New Rank Technique for Formula Size Lower Bounds
+Normal rank
@@ Property / cites work @@
+On the noise sensitivity of monotone functions
@@ Property / cites work: On the noise sensitivity of monotone functions / rank @@
+Normal rank
@@ Property / cites work @@
+Lower Bounds on Formula Size of Boolean Functions Using Hypergraph Entropy
+Normal rank
@@ Property / cites work @@
+Hardness amplification within NP
@@ Property / cites work: Hardness amplification within NP / rank @@
+Normal rank
@@ Property / cites work @@
+On the facial structure of set packing polyhedra
@@ Property / cites work: On the facial structure of set packing polyhedra / rank @@
+Normal rank
@@ Property / cites work @@
+Almost integral polyhedra related to certain combinatorial optimization problems
+Normal rank
@@ Property / cites work @@
+Q4036708
@@ Property / cites work: Q4036708 / rank @@
+Normal rank
@@ Property / cites work @@
+The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
+Normal rank
@@ Property / cites work @@
+Better lower bounds for monotone threshold formulas
+Normal rank
@@ Property / cites work @@
+Applications of matrix methods to the theory of lower bounds in computational complexity
+Normal rank
@@ Property / cites work @@
+Q5365063
@@ Property / cites work: Q5365063 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3549690
@@ Property / cites work: Q3549690 / rank @@
+Normal rank
@@ Property / cites work @@
+Short monotone formulae for the majority function
@@ Property / cites work: Short monotone formulae for the majority function / rank @@
+Normal rank