Lower bounds for matrix factorization

DOI10.4230/LIPICS.CCC.2020.5OpenAlexW2964003194MaRDI QIDQ5092452FDOQ5092452

Mrinal Kumar, Ben Lee Volk

Publication date: 21 July 2022

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

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

zbMATH Keywords

matrix factorizationlower boundsalgebraic complexitylinear circuits

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites Work

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

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)