Lower bounds for matrix factorization

DOI10.4230/LIPICS.CCC.2020.5MaRDI QIDQ5092452zbMATH OpenOpenAlexFDO

Authors Mrinal Kumar, Ben Lee Volk

Publication date 21 July 2022

Full work available at URL https://doi.org/10.4230/LIPIcs.CCC.2020.5

zbMATH Keywords

matrix factorizationlower boundsalgebraic complexitylinear circuits

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Lower bounds for matrix factorization
• Lower bounds for the low-rank matrix approximation
• Lower bounds on matrix factorization ranks via noncommutative polynomial optimization
• Randomized algorithms for low-rank matrix factorizations: sharp performance bounds
• Bounded matrix low rank approximation
• Lower bounds for matrices
• Lower bounds for some factorable matrices
• Lower bounds of matrices
• A matrix lower bound
• Lower bounds in minimum rank problems

Cites work

• scientific article; zbMATH DE number 5485435 (Why is no real title available?)
• scientific article; zbMATH DE number 3566171 (Why is no real title available?)
• scientific article; zbMATH DE number 3597878 (Why is no real title available?)
• scientific article; zbMATH DE number 976329 (Why is no real title available?)
• scientific article; zbMATH DE number 1528185 (Why is no real title available?)
• A note on matrix rigidity
• A note on the use of determinant for proving lower bounds on the size of linear circuits
• A remark on matrix rigidity
• An efficient reduction from two-source to non-malleable extractors: achieving near-logarithmic min-entropy
• Arithmetic circuits: a chasm at depth 3
• Arithmetic circuits: a survey of recent results and open questions
• Arithmetic circuits: the chasm at depth four gets wider
• Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators
• Communication in bounded depth circuits
• Complexity Lower Bounds using Linear Algebra
• Complexity of Linear Boolean Operators
• Crossing the logarithmic barrier for dynamic Boolean data structure lower bounds
• Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten
• Elusive functions and lower bounds for arithmetic circuits
• Explicit two-source extractors and resilient functions
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits
• Improved bounds for reduction to depth 4 and depth 3
• Logarithmic Lower Bounds in the Cell-Probe Model
• Lower bounds for polynomial evaluation and interpolation problems
• Matrix rigidity and the Croot-Lev-Pach lemma
• New Algorithms for Finding Irreducible Polynomials Over Finite Fields
• Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform
• On identity testing of tensors, low-rank recovery and compressed sensing
• On range searching in the group model and combinatorial discrepancy
• Probabilistic rank and matrix rigidity
• Static data structure lower bounds imply rigidity
• Superconcentrators
• Superconcentrators of depth 2
• Superconcentrators of depths 2 and 3; odd levels help (rarely)
• Testers and their applications
• The Complexity of Maintaining an Array and Computing Its Partial Sums
• The cell probe complexity of dynamic range counting
• The cell probe complexity of succinct data structures
• The complexity of partial derivatives
• Tight Bounds on Computing Error-Correcting Codes by Bounded-Depth Circuits With Arbitrary Gates
• Towards optimal two-source extractors and Ramsey graphs

Cited in

(3)

• Lower bounds for matrix factorization
• From-below approximations in Boolean matrix factorization: geometry and new algorithm
• A combinatorial approach to \(L_1\)-matrix factorization

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5092452)