A super-quadratic lower bound for depth four arithmetic circuits
From MaRDI portal
Publication:5092474
DOI10.4230/LIPIcs.CCC.2020.23OpenAlexW3013403809MaRDI QIDQ5092474
Bhargav Thankey, N. Gupta, Chandan Saha
Publication date: 21 July 2022
Full work available at URL: https://doi.org/10.4230/LIPIcs.CCC.2020.23
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A note on the use of determinant for proving lower bounds on the size of linear circuits
- Lower bounds for depth-three arithmetic circuits with small bottom fanin
- Arithmetic circuits: the chasm at depth four gets wider
- Lower bounds and separations for constant depth multilinear circuits
- A Boolean function requiring 3n network size
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- Lower bounds on monotone complexity of the logical permanent
- The monotone circuit complexity of Boolean functions
- A method for obtaining more than quadratic effective lower estimates of complexity of \(\pi\) schemes
- Negation can be exponentially powerful
- The complexity of partial derivatives
- Communication in bounded depth circuits
- Lower bounds on arithmetic circuits via partial derivatives
- Lower bounds for polynomial evaluation and interpolation problems
- On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits
- Completeness and reduction in algebraic complexity theory
- Exponential lower bounds for depth 3 arithmetic circuits in algebras of functions over finite fields.
- The gap between monotone and non-monotone circuit complexity is exponential
- Uniform constant-depth threshold circuits for division and iterated multiplication.
- Monotone separation of logarithmic space from logarithmic depth
- Separation of the monotone NC hierarchy
- Balancing syntactically multilinear arithmetic circuits
- On lower bounds for read-\(k\)-times branching programs
- Improved bounds for reduction to depth 4 and depth 3
- Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten
- Boolean circuits versus arithmetic circuits
- Arithmetic Circuits: A Chasm at Depth 3
- Jacobian Hits Circuits: Hitting Sets, Lower Bounds for Depth-$D$ Occur-$k$ Formulas and Depth-3 Transcendence Degree-$k$ Circuits
- Partial Derivatives in Arithmetic Complexity and Beyond
- A 5n − o(n) Lower Bound on the Circuit Size over U 2 of a Linear Boolean Function
- Lower Bounds for Depth-4 Formulas Computing Iterated Matrix Multiplication
- An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas
- On the Power of Homogeneous Depth 4 Arithmetic Circuits
- The Design of Approximation Algorithms
- Fast Parallel Computation of Polynomials Using Few Processors
- Arithmetic Circuits: A survey of recent results and open questions
- Nonuniform ACC Circuit Lower Bounds
- Parity, circuits, and the polynomial-time hierarchy
- A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits
- Monotone Circuits for Connectivity Require Super-Logarithmic Depth
- Amplifying lower bounds by means of self-reducibility
- A Lower Bound for the Formula Size of Rational Functions
- Some Exact Complexity Results for Straight-Line Computations over Semirings
- On Threshold Circuits and Polynomial Computation
- Size--Depth Tradeoffs for Threshold Circuits
- The Shrinkage Exponent of de Morgan Formulas is 2
- On the Complexity of Matrix Product
- Small-Depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication with Applications
- Lower Bounds for Matrix Product in Bounded Depth Circuits with Arbitrary Gates
- Identity Testing and Lower Bounds for Read- k Oblivious Algebraic Branching Programs
- Superpolynomial Lower Bounds for General Homogeneous Depth 4 Arithmetic Circuits
- Applications of approximation algorithms to cooperative games
- Explicit lower bound of 4.5n - o(n) for boolena circuits
- Bootstrapping results for threshold circuits “just beyond” known lower bounds
- Separating monotone VP and VNP
- Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQP
- A super-polynomial lower bound for regular arithmetic formulas
- Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits
- Tensor-Rank and Lower Bounds for Arithmetic Formulas
- Separating multilinear branching programs and formulas
- Approaching the Chasm at Depth Four
- Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform
- Non-commutative circuits and the sum-of-squares problem
- Multi-linear formulas for permanent and determinant are of super-polynomial size
- On the hardness of the noncommutative determinant
- Depth-3 arithmetic circuits over fields of characteristic zero
This page was built for publication: A super-quadratic lower bound for depth four arithmetic circuits
