Approaching the chasm at depth four
From MaRDI portal
Publication:5501936
Recommendations
- Arithmetic circuits: the chasm at depth four gets wider
- Superpolynomial lower bounds for general homogeneous depth 4 arithmetic circuits
- On the power of homogeneous depth 4 arithmetic circuits
- Arithmetic circuits: a chasm at depth 3
- Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas
Cites work
- A super-polynomial lower bound for regular arithmetic formulas
- Affine projections of polynomials (extended abstract)
- Arithmetic circuits: the chasm at depth four gets wider
- Depth-3 arithmetic circuits over fields of characteristic zero
- Exponential lower bounds for depth 3 arithmetic circuits in algebras of functions over finite fields.
- Gröbner bases and Stanley decompositions of determinantal ideals
- scientific article; zbMATH DE number 1775446 (Why is no real title available?)
- Ideals of generic minors
- Ideals, varieties, and algorithms. An introduction to computational algebraic geometry and commutative algebra
- Improved Bounds for Reduction to Depth 4 and Depth 3
- Lower bounds and separations for constant depth multilinear circuits
- Lower bounds for depth 4 formulas computing iterated matrix multiplication
- Lower bounds on arithmetic circuits via partial derivatives
- Multi-linear formulas for permanent and determinant are of super-polynomial size
- Random arithmetic formulas can be reconstructed efficiently
- Stirling's Approximation for n!: The Ultimate Short Proof?
- Superpolynomial lower bounds for general homogeneous depth 4 arithmetic circuits
- The irreducibility of ladder determinantal varieties
Cited in
(37)- Multi-k-ic depth three circuit lower bound
- On the complexity of the permanent in various computational models
- Lower bounds for arithmetic circuits via the Hankel matrix
- Unbalancing sets and an almost quadratic lower bound for syntactically multilinear arithmetic circuits
- Depth-4 lower bounds, determinantal complexity: a unified approach
- Average-case linear matrix factorization and reconstruction of low width algebraic branching programs
- Lower bounds and PIT for non-commutative arithmetic circuits with restricted parse trees
- Unifying known lower bounds via geometric complexity theory
- Improved bounds for reduction to depth 4 and depth 3
- Arithmetic circuits: a chasm at depth 3
- Algebraic complexity classes
- A Selection of Lower Bounds for Arithmetic Circuits
- The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials
- 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
- Lower bounds for depth-three arithmetic circuits with small bottom fanin
- Lower bounds for sums of powers of low degree univariates
- The limits of depth reduction for arithmetic formulas: it's all about the top fan-in
- Arithmetic circuits: the chasm at depth four gets wider
- On the Size of Homogeneous and of Depth-Four Formulas with Low Individual Degree
- scientific article; zbMATH DE number 7009617 (Why is no real title available?)
- The computational power of depth five arithmetic circuits
- Random arithmetic formulas can be reconstructed efficiently
- Barriers for rank methods in arithmetic complexity
- scientific article; zbMATH DE number 7471587 (Why is no real title available?)
- Towards Optimal Depth Reductions for Syntactically Multilinear Circuits
- On the Symmetries of and Equivalence Test for Design Polynomials.
- A super-quadratic lower bound for depth four arithmetic circuits
- Lower bounds by Birkhoff interpolation
- scientific article; zbMATH DE number 7204375 (Why is no real title available?)
- scientific article; zbMATH DE number 7250151 (Why is no real title available?)
- scientific article; zbMATH DE number 7250153 (Why is no real title available?)
- Depth-4 identity testing and Noether's normalization lemma
- Young flattenings in the Schur module basis
- Superpolynomial lower bounds against low-depth algebraic circuits
- Improved lower bound, and proof barrier, for constant depth algebraic circuits
This page was built for publication: Approaching the chasm at depth four
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5501936)
