Barriers for rank methods in arithmetic complexity

DOI10.4230/LIPICS.ITCS.2018.1zbMATH Open1462.68069arXiv1710.09502OpenAlexW2964049658MaRDI QIDQ4993264FDOQ4993264

Authors:

Publication date: 15 June 2021

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 $Omeg{a}_d(n^{lfloord/2floor})$ lower bound on the tensor rank of any $d$-dimensional tensor of side $n$. (In particular, they cannot prove super-linear, indeed even $>8n$ tensor rank lower bounds for any 3-dimensional tensors.) 2. Rank methods cannot prove $Omeg{a}_d(n^{lfloord/2floor})$ on the Waring rank of any $n$-variate polynomial of degree $d$. (In particular, they cannot prove such lower bounds on stronger models, including depth-3 circuits.)

Full work available at URL: https://arxiv.org/abs/1710.09502

Recommendations

• Tensor-rank and lower bounds for arithmetic formulas
• Tensor-rank and lower bounds for arithmetic formulas
• Arithmetic circuit lower bounds via MaxRank
• Arithmetic circuit lower bounds via maximum-rank of partial derivative matrices
• The complexity of tensor rank

zbMATH Keywords

partial derivativeslower boundsbarriersflattenings

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Polynomials, factorization in commutative rings (13P05) Secant varieties, tensor rank, varieties of sums of powers (14N07)

Cites Work

• A probabilistic remark on algebraic program testing
• Title not available (Why is that?)
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Title not available (Why is that?)
• The solution to the Waring problem for monomials and the sum of coprime monomials
• Applications of matrix methods to the theory of lower bounds in computational complexity
• Title not available (Why is that?)
• Title not available (Why is that?)
• Hitting sets for multilinear read-once algebraic branching programs, in any order
• Geometric complexity theory and tensor rank
• Modern computer algebra
• Full reconstruction of Markov models on evolutionary trees: identifiability and consistency.
• Lower bounds on arithmetic circuits via partial derivatives
• Arithmetic circuits: a survey of recent results and open questions
• Tensor rank is NP-complete
• Superpolynomial lower bounds for general homogeneous depth 4 arithmetic circuits
• Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas
• Geometry and complexity theory
• Affine projections of polynomials (extended abstract)
• Approaching the chasm at depth four
• Multi-linear formulas for permanent and determinant are of super-polynomial size
• Lower bounds and separations for constant depth multilinear circuits
• On the Parallel Evaluation of Multivariate Polynomials
• Algebrization: a new barrier in complexity theory
• New lower bounds for the border rank of matrix multiplication
• Title not available (Why is that?)
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• Partial derivatives in arithmetic complexity and beyond
• Taking turns
• Natural proofs
• Tensor-rank and lower bounds for arithmetic formulas
• Bounds on the norms of uniform low degree graph matrices
• A spectral algorithm for latent Dirichlet allocation
• Non-commutative circuits and the sum-of-squares problem
• Finer separations between shallow arithmetic circuits
• Learning mixtures of spherical Gaussians: moment methods and spectral decompositions (extended abstract)
• Unifying known lower bounds via geometric complexity theory
• Decomposing overcomplete 3rd order tensors using sum-of-squares algorithms
• Succinct hitting sets and barriers to proving algebraic circuits lower bounds
• Lower bounds for depth-4 formulas computing iterated matrix multiplication
• 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\)

Cited In (14)

• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• 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)