A Quadratic Size-Hierarchy Theorem for Small-Depth Multilinear Formulas (Q5002707): Difference between revisions

@@ label / en / label / en @@
+A Quadratic Size-Hierarchy Theorem for Small-Depth Multilinear Formulas
@@ Property / describes a project that uses @@
+lowerbounds-survey
@@ Property / describes a project that uses: lowerbounds-survey / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / cites work @@
+\(\Sigma_ 1^ 1\)-formulae on finite structures
@@ Property / cites work: \(\Sigma_ 1^ 1\)-formulae on finite structures / rank @@
+Normal rank
@@ Property / cites work @@
+Simple Constructions of Almost k-wise Independent Random Variables
+Normal rank
@@ Property / cites work @@
+\(k\)-subgraph isomorphism on \(\text{AC}^{0}\) circuits
+Normal rank
@@ Property / cites work @@
+Size-depth tradeoffs for Boolean formulae
@@ Property / cites work: Size-depth tradeoffs for Boolean formulae / rank @@
+Normal rank
@@ Property / cites work @@
+The Parallel Evaluation of General Arithmetic Expressions
+Normal rank
@@ Property / cites work @@
+Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications.
+Normal rank
@@ Property / cites work @@
+Improved Pseudorandom Generators for Depth 2 Circuits
+Normal rank
@@ Property / cites work @@
+Subspace evasive sets
@@ Property / cites work: Subspace evasive sets / rank @@
+Normal rank
@@ Property / cites work @@
+Separating multilinear branching programs and formulas
+Normal rank
@@ Property / cites work @@
+Parity, circuits, and the polynomial-time hierarchy
+Normal rank
@@ Property / cites work @@
+On the Computational Complexity of Algorithms
@@ Property / cites work: On the Computational Complexity of Algorithms / rank @@
+Normal rank
@@ Property / cites work @@
+Homogeneous formulas and symmetric polynomials
@@ Property / cites work: Homogeneous formulas and symmetric polynomials / rank @@
+Normal rank
@@ Property / cites work @@
+Constructive Proofs of Concentration Bounds
@@ Property / cites work: Constructive Proofs of Concentration Bounds / rank @@
+Normal rank
@@ Property / cites work @@
+Separation Between Read-once Oblivious Algebraic Branching Programs (ROABPs) and Multilinear Depth Three Circuits
+Normal rank
@@ Property / cites work @@
+Q5636862
@@ Property / cites work: Q5636862 / rank @@
+Normal rank
@@ Property / cites work @@
+Small-Bias Probability Spaces: Efficient Constructions and Applications
+Normal rank
@@ Property / cites work @@
+Lower bounds on arithmetic circuits via partial derivatives
+Normal rank
@@ Property / cites work @@
+Q3002768
@@ Property / cites work: Q3002768 / rank @@
+Normal rank
@@ Property / cites work @@
+A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits
+Normal rank
@@ Property / cites work @@
+Balancing syntactically multilinear arithmetic circuits
+Normal rank
@@ Property / cites work @@
+Lower bounds and separations for constant depth multilinear circuits
+Normal rank
@@ Property / cites work @@
+Arithmetic Circuits: A survey of recent results and open questions
+Normal rank
@@ Property / full work available at URL @@
+https://drops.dagstuhl.de/opus/volltexte/2018/9040/pdf/LIPIcs-ICALP-2018-36.pdf/
+Normal rank
@@ Property / OpenAlex ID @@
+W2887782098
@@ Property / OpenAlex ID: W2887782098 / rank @@
+Normal rank
@@ Property / title @@
+A Quadratic Size-Hierarchy Theorem for Small-Depth Multilinear Formulas (English)
+Normal rank