Barriers for rank methods in arithmetic complexity
From MaRDI portal
Publication:4993264
Abstract: Arithmetic complexity is considered simpler to understand than Boolean complexity, namely computing Boolean functions via logical gates. And indeed, we seem to have significantly more lower bound techniques and results in arithmetic complexity than in Boolean complexity. Despite many successes and rapid progress, however, challenges like proving super-polynomial lower bounds on circuit or formula size for explicit polynomials, or super-linear lower bounds on explicit 3-dimensional tensors, remain elusive. At the same time, we have plenty more "barrier results" for failing to prove basic lower bounds in Boolean complexity than in arithmetic complexity. Finding barriers to arithmetic lower bound techniques seem harder, and despite some attempts we have no excuses of similar quality for these failures in arithmetic complexity. This paper aims to add to this study. We address rank methods, which were long recognized as encompassing and abstracting almost all known arithmetic lower bounds to-date, including the most recent impressive successes. Rank methods (or flattenings) are also in wide use in algebraic geometry for proving tensor rank and symmetric tensor rank lower bounds. Our main results are barriers to these methods. In particular, 1. Rank methods cannot prove better than lower bound on the tensor rank of any -dimensional tensor of side . (In particular, they cannot prove super-linear, indeed even tensor rank lower bounds for any 3-dimensional tensors.) 2. Rank methods cannot prove on the Waring rank of any -variate polynomial of degree . (In particular, they cannot prove such lower bounds on stronger models, including depth-3 circuits.)
Recommendations
Cites work
- scientific article; zbMATH DE number 5968745 (Why is no real title available?)
- scientific article; zbMATH DE number 3651744 (Why is no real title available?)
- scientific article; zbMATH DE number 176870 (Why is no real title available?)
- scientific article; zbMATH DE number 976329 (Why is no real title available?)
- scientific article; zbMATH DE number 773851 (Why is no real title available?)
- A probabilistic remark on algebraic program testing
- A spectral algorithm for latent Dirichlet allocation
- Affine projections of polynomials (extended abstract)
- Algebrization: a new barrier in complexity theory
- Applications of matrix methods to the theory of lower bounds in computational complexity
- Approaching the chasm at depth four
- Arithmetic circuits: a survey of recent results and open questions
- Bounds on the norms of uniform low degree graph matrices
- Decomposing overcomplete 3rd order tensors using sum-of-squares algorithms
- Fast Probabilistic Algorithms for Verification of Polynomial Identities
- Finer separations between shallow arithmetic circuits
- Full reconstruction of Markov models on evolutionary trees: identifiability and consistency.
- Geometric complexity theory and tensor rank
- Geometry and complexity theory
- Hitting sets for multilinear read-once algebraic branching programs, in any order
- Learning mixtures of spherical Gaussians: moment methods and spectral decompositions (extended abstract)
- 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
- Modern computer algebra
- Multi-linear formulas for permanent and determinant are of super-polynomial size
- Natural proofs
- New lower bounds for the border rank of matrix multiplication
- Non-commutative circuits and the sum-of-squares problem
- Nontriviality of equations and explicit tensors in \(\mathbb{C}^m \otimes \mathbb{C}^m \otimes \mathbb{C}^m\) of border rank at least \(2m - 2\)
- On the Parallel Evaluation of Multivariate Polynomials
- Partial derivatives in arithmetic complexity and beyond
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- Succinct hitting sets and barriers to proving algebraic circuits lower bounds
- Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas
- Superpolynomial lower bounds for general homogeneous depth 4 arithmetic circuits
- Taking turns
- Tensor rank is NP-complete
- Tensor-rank and lower bounds for arithmetic formulas
- The solution to the Waring problem for monomials and the sum of coprime monomials
- Unifying known lower bounds via geometric complexity theory
Cited in
(14)- scientific article; zbMATH DE number 7689792 (Why is no real title available?)
- On the Symmetries of and Equivalence Test for Design Polynomials.
- On the tensor rank of the \(3 \times 3\) permanent and determinant
- Bad and good news for Strassen's laser method: border rank of \(\mathrm{Perm}_3\) and strict submultiplicativity
- Rank and border rank of Kronecker powers of tensors and Strassen's laser method
- scientific article; zbMATH DE number 7758331 (Why is no real title available?)
- Comparing barrier algorithms
- Lower bounds and PIT for non-commutative arithmetic circuits with restricted parse trees
- Average-case linear matrix factorization and reconstruction of low width algebraic branching programs
- Border rank is not multiplicative under the tensor product
- Algebraic geometry and representation theory in the study of matrix multiplication complexity and other problems in theoretical computer science
- New lower bounds for matrix multiplication and
- Concise tensors of minimal border rank
- Novel arithmetic operations on IVIFNs and their properties on ranking functions
This page was built for publication: Barriers for rank methods in arithmetic complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4993264)
