Arithmetic circuits: a chasm at depth 3
From MaRDI portal
Recommendations
Cites work
- \({\mathcal P}\), \({\mathcal{NP}}\) and mathematics -- a computational complexity perspective
- A super-polynomial lower bound for regular arithmetic formulas
- Affine projections of symmetric polynomials.
- Approaching the chasm at depth four
- Arithmetic circuits: a survey of recent results and open questions
- Arithmetic circuits: the chasm at depth four gets wider
- Characterizing Valiant's algebraic complexity classes
- Depth-3 arithmetic circuits over fields of characteristic zero
- Derandomizing polynomial identity tests means proving circuit lower bounds
- Diagonal Circuit Identity Testing and Lower Bounds
- Exponential lower bounds for depth 3 arithmetic circuits in algebras of functions over finite fields.
- Fast Parallel Computation of Polynomials Using Few Processors
- Fast Parallel Matrix Inversion Algorithms
- FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
- scientific article; zbMATH DE number 5995471 (Why is no real title available?)
- scientific article; zbMATH DE number 3182201 (Why is no real title available?)
- scientific article; zbMATH DE number 3759547 (Why is no real title available?)
- scientific article; zbMATH DE number 1775446 (Why is no real title available?)
- scientific article; zbMATH DE number 6472651 (Why is no real title available?)
- scientific article; zbMATH DE number 3333392 (Why is no real title available?)
- Improved Bounds for Reduction to Depth 4 and Depth 3
- Improved rank bounds for design matrices and a new proof of Kelly's theorem
- Lower bounds for depth 4 formulas computing iterated matrix multiplication
- Lower bounds on arithmetic circuits via partial derivatives
- On computing the determinant in small parallel time using a small number of processors
- Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes
- Sums of Like Powers of Multivariate Linear Forms
- Tensor-rank and lower bounds for arithmetic formulas
- The power of depth 2 circuits over algebras
Cited in
(74)- Algebraic independence over positive characteristic: new criterion and applications to locally low-algebraic-rank circuits
- On \(\varSigma\wedge\varSigma\wedge\varSigma\) circuits: the role of middle \(\varSigma\) fan-in, homogeneity and bottom degree
- Deterministic identity testing for sum of read-once oblivious arithmetic branching programs
- Multi-k-ic depth three circuit lower bound
- Affine projections of symmetric polynomials.
- Permanent does not have succinct polynomial size arithmetic circuits of constant depth
- Lower bounds for matrix factorization
- Real \(\tau \)-conjecture for sum-of-squares: a unified approach to lower bound and derandomization
- Quadratic lower bounds for algebraic branching programs and formulas
- Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants
- Average-case linear matrix factorization and reconstruction of low width algebraic branching programs
- A \(\tau \)-conjecture for Newton polygons
- Geometric complexity theory: an introduction for geometers
- Equivalence of polynomial identity testing and polynomial factorization
- Unifying known lower bounds via geometric complexity theory
- On the limits of depth reduction at depth 3 over small finite fields
- Improved bounds for reduction to depth 4 and depth 3
- Algebraic geometry and representation theory in the study of matrix multiplication complexity and other problems in theoretical computer science
- Jacobian hits circuits: hitting sets, lower bounds for depth-D occur-k formulas and depth-3 transcendence degree-k circuits
- Algebraic complexity classes
- Arithmetic circuits and the Hadamard product of polynomials
- On the limits of depth reduction at depth 3 over small finite fields
- An exponential lower bound for homogeneous depth four arithmetic formulas
- On the power of homogeneous depth 4 arithmetic circuits
- Elusive functions and lower bounds for arithmetic circuits
- Permanent does not have succinct polynomial size arithmetic circuits of constant depth
- Lower bounds for depth-three arithmetic circuits with small bottom fanin
- Subexponential size hitting sets for bounded depth multilinear formulas
- Arithmetic circuits: a survey of recent results and open questions
- Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications.
- Lower bounds for sums of powers of low degree univariates
- Arithmetic circuits: the chasm at depth four gets wider
- scientific article; zbMATH DE number 1775446 (Why is no real title available?)
- An almost cubic lower bound for depth three arithmetic circuits
- Equations for secant varieties of Chow varieties
- 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
- The method of shifted partial derivatives cannot separate the permanent from the determinant
- Small-depth multilinear formula lower bounds for iterated matrix multiplication with applications
- Arithmetic circuit lower bounds via maximum-rank of partial derivative matrices
- On proving parameterized size lower bounds for multilinear algebraic models
- Towards blackbox identity testing of log-variate circuits
- scientific article; zbMATH DE number 7471587 (Why is no real title available?)
- A quadratic lower bound for algebraic branching programs
- Lower bounds for matrix factorization
- scientific article; zbMATH DE number 7561742 (Why is no real title available?)
- A super-quadratic lower bound for depth four arithmetic circuits
- scientific article; zbMATH DE number 7561765 (Why is no real title available?)
- Lower bounds by Birkhoff interpolation
- scientific article; zbMATH DE number 7250152 (Why is no real title available?)
- scientific article; zbMATH DE number 7250153 (Why is no real title available?)
- A unified method for placing problems in polylogarithmic depth
- Fundamental invariants of orbit closures
- Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits
- Arithmetic circuit lower bounds via MaxRank
- Approaching the chasm at depth four
- Depth-4 identity testing and Noether's normalization lemma
- Arithmetic circuits, structured matrices and (not so) deep learning
- Schur polynomials do not have small formulas if the determinant does not
- Testing the satisfiability of algebraic formulas over the field of two elements
- Lower bounds and separations for constant depth multilinear circuits
- Linear independence, alternants, and applications
- Lower bounds for the sum of small-size algebraic branching programs
- Complexity theory. Abstracts from the workshop held June 2--7, 2024
- NP-hardness of testing equivalence to sparse polynomials and to constant-support polynomials
- Tensor reconstruction beyond constant rank
- Superpolynomial lower bounds against low-depth algebraic circuits
- Improved lower bound, and proof barrier, for constant depth algebraic circuits
- Lower bounds for the sum of small-size algebraic branching programs
- Hitting sets for orbits of circuit classes and polynomial families
- Building above read-once polynomials: identity testing and hardness of representation
- Uniform bounds on product Sylvester-Gallai configurations
- Deterministic polynomial identity tests for multilinear bounded-read formulae
This page was built for publication: Arithmetic circuits: a chasm at depth 3
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2816300)
