Lower bounds for matrix factorization

DOI10.1007/s00037-021-00205-2OpenAlexW3141479212MaRDI QIDQ2041242

Mrinal Kumar, Ben lee Volk

Publication date: 16 July 2021

Published in: Computational Complexity (Search for Journal in Brave)

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

zbMATH Keywords

lower boundsalgebraic complexitymatrix factorizationlinear circuits

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Classical models of computation (Turing machines, etc.) (68Q04)

Related Items (2)

Efficient Construction of Rigid Matrices Using an NP Oracle ⋮ Real \(\tau \)-conjecture for sum-of-squares: a unified approach to lower bound and derandomization

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A remark on matrix rigidity
• A note on the use of determinant for proving lower bounds on the size of linear circuits
• Arithmetic circuits: the chasm at depth four gets wider
• A note on matrix rigidity
• Superconcentrators of depth 2
• The complexity of partial derivatives
• Superconcentrators of depths 2 and 3; odd levels help (rarely)
• Communication in bounded depth circuits
• Lower bounds for polynomial evaluation and interpolation problems
• Explicit two-source extractors and resilient functions
• Improved bounds for reduction to depth 4 and depth 3
• Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten
• Arithmetic Circuits: A Chasm at Depth 3
• Testers and their applications
• Arithmetic Circuits: A survey of recent results and open questions
• Complexity Lower Bounds using Linear Algebra
• New Algorithms for Finding Irreducible Polynomials Over Finite Fields
• The Complexity of Maintaining an Array and Computing Its Partial Sums
• Superconcentrators
• Descartes' Rule of Signs Revisited
• Lower Bounds for Matrix Product in Bounded Depth Circuits with Arbitrary Gates
• Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators
• Probabilistic rank and matrix rigidity
• Towards optimal two-source extractors and Ramsey graphs
• An efficient reduction from two-source to non-malleable extractors: achieving near-logarithmic min-entropy
• Lower bounds for matrix factorization
• Matrix rigidity and the Croot-Lev-Pach lemma
• Static data structure lower bounds imply rigidity
• Crossing the logarithmic barrier for dynamic Boolean data structure lower bounds
• Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits
• Tight Bounds on Computing Error-Correcting Codes by Bounded-Depth Circuits With Arbitrary Gates
• Complexity of Linear Boolean Operators
• The cell probe complexity of dynamic range counting
• On identity testing of tensors, low-rank recovery and compressed sensing
• Logarithmic Lower Bounds in the Cell-Probe Model
• On Range Searching in the Group Model and Combinatorial Discrepancy
• Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform
• Fourier and Circulant Matrices are Not Rigid
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science

This page was built for publication: Lower bounds for matrix factorization