A Quadratic Size-Hierarchy Theorem for Small-Depth Multilinear Formulas
From MaRDI portal
Publication:5002707
DOI10.4230/LIPIcs.ICALP.2018.36zbMath1499.68103OpenAlexW2887782098MaRDI QIDQ5002707
Srikanth Srinivasan, Suryajith Chillara, Nutan Limaye
Publication date: 28 July 2021
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/9040/pdf/LIPIcs-ICALP-2018-36.pdf/
Related Items (2)
Unbalancing sets and an almost quadratic lower bound for syntactically multilinear arithmetic circuits ⋮ Slightly improved lower bounds for homogeneous formulas of bounded depth and bounded individual degree
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Lower bounds and separations for constant depth multilinear circuits
- \(k\)-subgraph isomorphism on \(\text{AC}^{0}\) circuits
- Homogeneous formulas and symmetric polynomials
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- Size-depth tradeoffs for Boolean formulae
- Lower bounds on arithmetic circuits via partial derivatives
- Balancing syntactically multilinear arithmetic circuits
- Arithmetic Circuits: A survey of recent results and open questions
- Small-Bias Probability Spaces: Efficient Constructions and Applications
- Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications.
- Parity, circuits, and the polynomial-time hierarchy
- A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits
- Improved Pseudorandom Generators for Depth 2 Circuits
- Constructive Proofs of Concentration Bounds
- Simple Constructions of Almost k-wise Independent Random Variables
- The Parallel Evaluation of General Arithmetic Expressions
- Separation Between Read-once Oblivious Algebraic Branching Programs (ROABPs) and Multilinear Depth Three Circuits
- On the Computational Complexity of Algorithms
- Subspace evasive sets
- Separating multilinear branching programs and formulas
This page was built for publication: A Quadratic Size-Hierarchy Theorem for Small-Depth Multilinear Formulas
