Lower bounds for matrix factorization
From MaRDI portal
Publication:5092452
DOI10.4230/LIPIcs.CCC.2020.5OpenAlexW2964003194MaRDI QIDQ5092452
Publication date: 21 July 2022
Full work available at URL: https://doi.org/10.4230/LIPIcs.CCC.2020.5
Related Items (1)
Cites Work
- 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
- The cell probe complexity of succinct data structures
- 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
- 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
- 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
- Explicit two-source extractors and resilient functions
- 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
- FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
This page was built for publication: Lower bounds for matrix factorization
