Cubic Formula Size Lower Bounds Based on Compositions with Majority (Q5090412): Difference between revisions

@@ label / en / label / en @@
+Cubic Formula Size Lower Bounds Based on Compositions with Majority
@@ Property / cites work @@
+A method for obtaining more than quadratic effective lower estimates of complexity of \(\pi\) schemes
+Normal rank
@@ Property / cites work @@
+Q5002692
@@ Property / cites work: Q5002692 / rank @@
+Normal rank
@@ Property / cites work @@
+Mining circuit lower bound proofs for meta-algorithms
+Normal rank
@@ Property / cites work @@
+Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity
+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 @@
+Probability Inequalities for Sums of Bounded Random Variables
+Normal rank
@@ Property / cites work @@
+The effect of random restrictions on formula size
@@ Property / cites work: The effect of random restrictions on formula size / rank @@
+Normal rank
@@ Property / cites work @@
+Super-logarithmic depth lower bounds via the direct sum in communication complexity
+Normal rank
@@ Property / cites work @@
+Complexity of the realization of a linear function in the class of \(\Pi\)-circuits
+Normal rank
@@ Property / cites work @@
+Average-case lower bounds for formula size
@@ Property / cites work: Average-case lower bounds for formula size / rank @@
+Normal rank
@@ Property / cites work @@
+Improved Average-Case Lower Bounds for De Morgan Formula Size: Matching Worst-Case Lower Bound
+Normal rank
@@ Property / cites work @@
+Shrinkage of de Morgan formulae under restriction
@@ Property / cites work: Shrinkage of de Morgan formulae under restriction / rank @@
+Normal rank
@@ Property / cites work @@
+Complexity and depth of formulas for symmetric Boolean functions
+Normal rank
@@ Property / cites work @@
+Q3281059
@@ Property / cites work: Q3281059 / rank @@
+Normal rank
@@ Property / cites work @@
+Formula lower bounds via the quantum method
@@ Property / cites work: Formula lower bounds via the quantum method / 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
@@ Property / cites work @@
+The critical complexity of all (monotone) boolean functions and monotone graph properties
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.4230/LIPIcs.ITCS.2019.35
+Normal rank
@@ Property / OpenAlex ID @@
+W2913244533
@@ Property / OpenAlex ID: W2913244533 / rank @@
+Normal rank
@@ Property / title @@
+Cubic Formula Size Lower Bounds Based on Compositions with Majority (English)
+Normal rank