A super-quadratic lower bound for depth four arithmetic circuits
From MaRDI portal
Cites work
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- A \(5n - o(n)\) lower bound on the circuit size over \(U _{2}\) of a linear Boolean function
- A Boolean function requiring 3n network size
- A Lower Bound for the Formula Size of Rational Functions
- A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits
- A method for obtaining more than quadratic effective lower estimates of complexity of schemes
- A note on the use of determinant for proving lower bounds on the size of linear circuits
- A super-polynomial lower bound for regular arithmetic formulas
- Amplifying lower bounds by means of self-reducibility
- An almost cubic lower bound for depth three arithmetic circuits
- An exponential lower bound for homogeneous depth four arithmetic formulas
- Applications of approximation algorithms to cooperative games
- Approaching the chasm at depth four
- Arithmetic circuits: a chasm at depth 3
- Arithmetic circuits: a survey of recent results and open questions
- Arithmetic circuits: the chasm at depth four gets wider
- Arithmetic complexity in ring extensions
- Balancing syntactically multilinear arithmetic circuits
- Boolean circuits versus arithmetic circuits
- Bootstrapping results for threshold circuits ``just beyond known lower bounds
- Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQP
- Communication in bounded depth circuits
- Completeness and reduction in algebraic complexity theory
- Computing polynomials with few multiplications
- Depth-3 arithmetic circuits over fields of characteristic zero
- Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten
- Elusive functions and lower bounds for arithmetic circuits
- Explicit lower bound of 4.5n - o(n) for boolena circuits
- Exponential lower bounds for depth 3 arithmetic circuits in algebras of functions over finite fields.
- Fast Parallel Computation of Polynomials Using Few Processors
- scientific article; zbMATH DE number 4008289 (Why is no real title available?)
- scientific article; zbMATH DE number 3461412 (Why is no real title available?)
- scientific article; zbMATH DE number 3566171 (Why is no real title available?)
- scientific article; zbMATH DE number 3597878 (Why is no real title available?)
- scientific article; zbMATH DE number 976329 (Why is no real title available?)
- scientific article; zbMATH DE number 1775446 (Why is no real title available?)
- scientific article; zbMATH DE number 1929951 (Why is no real title available?)
- scientific article; zbMATH DE number 7250151 (Why is no real title available?)
- scientific article; zbMATH DE number 7250152 (Why is no real title available?)
- scientific article; zbMATH DE number 2193958 (Why is no real title available?)
- Identity testing and lower bounds for read-\(k\) oblivious algebraic branching programs
- Improved bounds for reduction to depth 4 and depth 3
- Jacobian hits circuits: hitting sets, lower bounds for depth-D occur-k formulas and depth-3 transcendence degree-k circuits
- Lower bounds and separations for constant depth multilinear circuits
- Lower bounds for depth three arithmetic circuits with small bottom fanin
- Lower bounds for depth-4 formulas computing iterated matrix multiplication
- Lower bounds for depth-three arithmetic circuits with small bottom fanin
- Lower Bounds for Matrix Product in Bounded Depth Circuits with Arbitrary Gates
- Lower bounds for polynomial evaluation and interpolation problems
- Lower bounds on arithmetic circuits via partial derivatives
- Lower bounds on monotone complexity of the logical permanent
- Monotone Circuits for Connectivity Require Super-Logarithmic Depth
- Monotone separation of logarithmic space from logarithmic depth
- Multi-linear formulas for permanent and determinant are of super-polynomial size
- Negation can be exponentially powerful
- Non-commutative circuits and the sum-of-squares problem
- Nonuniform ACC circuit lower bounds
- Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform
- On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits
- On lower bounds for read-\(k\)-times branching programs
- On the Complexity of Matrix Product
- On the hardness of the noncommutative determinant
- On the power of homogeneous depth 4 arithmetic circuits
- On Threshold Circuits and Polynomial Computation
- Parity, circuits, and the polynomial-time hierarchy
- Partial derivatives in arithmetic complexity and beyond
- Separating monotone VP and VNP
- Separating multilinear branching programs and formulas
- Separation of multilinear circuit and formula size
- Separation of the monotone NC hierarchy
- Size--Depth Tradeoffs for Threshold Circuits
- Small-depth multilinear formula lower bounds for iterated matrix multiplication with applications
- Some Exact Complexity Results for Straight-Line Computations over Semirings
- Sums of products of polynomials in few variables: lower bounds and polynomial identity testing
- Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits
- Superpolynomial lower bounds for general homogeneous depth 4 arithmetic circuits
- Tensor-rank and lower bounds for arithmetic formulas
- The complexity of partial derivatives
- The design of approximation algorithms
- The gap between monotone and non-monotone circuit complexity is exponential
- The monotone circuit complexity of Boolean functions
- The Shrinkage Exponent of de Morgan Formulas is 2
- Uniform constant-depth threshold circuits for division and iterated multiplication.
Cited in
(2)
This page was built for publication: A super-quadratic lower bound for depth four arithmetic circuits
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5092474)
