Quadratic lower bounds for algebraic branching programs and formulas
From MaRDI portal
Publication:2159469
DOI10.1007/s00037-022-00223-8OpenAlexW4283819639WikidataQ113906237 ScholiaQ113906237MaRDI QIDQ2159469
Ben lee Volk, Mrinal Kumar, Prerona Chatterjee, Adrian She
Publication date: 1 August 2022
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1911.11793
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Networks and circuits as models of computation; circuit complexity (68Q06)
Related Items (1)
Uses Software
Cites Work
- Quadratic lower bound for permanent vs. determinant in any characteristic
- Boolean function complexity. Advances and frontiers.
- The complexity of partial derivatives
- On sparse graphs with dense long paths
- Easy lower bound for a strange computational model
- Lower bounds on arithmetic circuits via partial derivatives
- Balancing syntactically multilinear arithmetic circuits
- A quadratic lower bound for homogeneous algebraic branching programs
- Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten
- Arithmetic Circuits: A Chasm at Depth 3
- Arithmetic Circuits: A survey of recent results and open questions
- A Lower Bound for the Formula Size of Rational Functions
- A quadratic lower bound for algebraic branching programs
- Separating multilinear branching programs and formulas
- Depth-3 arithmetic circuits over fields of characteristic zero
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Quadratic lower bounds for algebraic branching programs and formulas
