Lower bounds for matrix factorization
type: Item
instance of: scholarly article
title: Lower bounds for matrix factorization
author: Ben Lee Volk
author: Mrinal Kumar
published in: Computational Complexity
publication date: 2021-07-16T00:00:00Z
full work available at URL: https://arxiv.org/abs/1904.01182
Mathematics Subject Classification ID: 68Q04
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 7372271
zbMATH Keywords: algebraic complexity
zbMATH Keywords: linear circuits
zbMATH Keywords: matrix factorization
zbMATH Keywords: lower bounds
MaRDI profile type: Publication
OpenAlex ID: W3141479212
cites work: FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
cites work: Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits
cites work: Probabilistic rank and matrix rigidity
cites work: Superconcentrators of depths 2 and 3; odd levels help (rarely)
cites work: Descartes' Rule of Signs Revisited
cites work: The complexity of partial derivatives
cites work: An efficient reduction from two-source to non-malleable extractors: achieving near-logarithmic min-entropy
cites work: Testers and their applications
cites work: Q4331740
cites work: Explicit two-source extractors and resilient functions
cites work: Q4515159
cites work: Towards optimal two-source extractors and Ramsey graphs
cites work: Matrix rigidity and the Croot-Lev-Pach lemma
cites work: Static data structure lower bounds imply rigidity
cites work: Fourier and Circulant Matrices are Not Rigid
cites work: On identity testing of tensors, low-rank recovery and compressed sensing
cites work: The Complexity of Maintaining an Array and Computing Its Partial Sums
cites work: A note on matrix rigidity
cites work: Tight Bounds on Computing Error-Correcting Codes by Bounded-Depth Circuits With Arbitrary Gates
cites work: Arithmetic circuits: a chasm at depth 3
cites work: Complexity of Linear Boolean Operators
cites work: Arithmetic circuits: the chasm at depth four gets wider
cites work: Lower bounds for matrix factorization
cites work: The cell probe complexity of dynamic range counting
cites work: On Range Searching in the Group Model and Combinatorial Discrepancy
cites work: Crossing the logarithmic barrier for dynamic Boolean data structure lower bounds
cites work: Q5091780
cites work: Complexity Lower Bounds using Linear Algebra
cites work: Online learning for matrix factorization and sparse coding
cites work: Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform
cites work: Q3549595
cites work: Logarithmic Lower Bounds in the Cell-Probe Model
cites work: Superconcentrators
cites work: Superconcentrators of depth 2
cites work: Communication in bounded depth circuits
cites work: A note on the use of determinant for proving lower bounds on the size of linear circuits
cites work: Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators
cites work: Q3002820
cites work: Lower Bounds for Matrix Product in Bounded Depth Circuits with Arbitrary Gates
cites work: A remark on matrix rigidity
cites work: New Algorithms for Finding Irreducible Polynomials Over Finite Fields
cites work: Lower bounds for polynomial evaluation and interpolation problems
cites work: Arithmetic Circuits: A survey of recent results and open questions
cites work: Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten
cites work: Improved bounds for reduction to depth 4 and depth 3
cites work: Q4138137
cites work: Q4164821
DOI: 10.1007/S00037-021-00205-2
Recommended article: Lower bounds for matrix factorization
Recommended article: Lower bounds for the low-rank matrix approximation
Recommended article: Lower bounds on matrix factorization ranks via noncommutative polynomial optimization
Recommended article: Randomized algorithms for low-rank matrix factorizations: sharp performance bounds
Recommended article: Bounded Matrix Low Rank Approximation
Recommended article: Lower bounds for matrices
Recommended article: Lower bounds for some factorable matrices
Recommended article: Lower bounds of matrices
Recommended article: A matrix lower bound
Recommended article: Lower bounds in minimum rank problems
description: scientific article; zbMATH DE number 7372271