Lower Bounds for Matrix Factorization

Mrinal Kumar, Ben Lee Volk

Type: Preprint

Publication Date: 2019-04-02

Citations: 2

Locations

arXiv (Cornell University) - View

Similar Works

Action	Title	Year	Authors
+	Lower Bounds for Matrix Factorization	2019	Mrinal Kumar Ben Lee Volk
+	Lower bounds for matrix factorization	2020	Mrinal Kumar Ben Lee Volk
+	Lower Bounds for Matrix Factorization.	2019	Mrinal Kumar Ben Lee Volk
+	A Polynomial Degree Bound on Equations of Non-rigid Matrices and Small Linear Circuits	2020	Mrinal Kumar Ben Lee Volk
+	Static Data Structure Lower Bounds Imply Rigidity	2018	Zeev Dvir Alexander Golovnev Omri Weinstein
+ PDF Chat	A Polynomial Degree Bound on Equations for Non-rigid Matrices and Small Linear Circuits	2022	Ben Lee Volk Mrinal Kumar
+	New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms	2023	Amir Abboud Nick Fischer Zander Kelley Shachar Lovett Raghu Meka
+ PDF Chat	Kronecker products, low-depth circuits, and matrix rigidity	2021	Josh Alman
+	Kronecker Products, Low-Depth Circuits, and Matrix Rigidity	2021	Josh Alman
+ PDF Chat	Low-Bandwidth Matrix Multiplication: Faster Algorithms and More General Forms of Sparsity	2024	Chetan Gupta Janne H. Korhonen Jan Studený Jukka Suomela Hossein Vahidi
+	Static data structure lower bounds imply rigidity	2019	Zeev Dvir Alexander Golovnev Omri Weinstein
+	Recent Progress on Matrix Rigidity -- A Survey	2020	C. Ramya
+	Matrix Multiplication Verification Using Coding Theory	2023	Huck Bennett Karthik Gajulapalli Alexander Golovnev Philip G. Warton
+	Lower Bounds on Matrix Rigidity via a Quantum Argument	2005	Ronald de Wolf
+	Complexity Lower Bounds using Linear Algebra	2007	Satyanarayana V. Lokam
+	Symmetric Sparse Boolean Matrix Factorization and Applications	2021	Sitan Chen Zhao Song Runzhou Tao Ruizhe Zhang
+	Deterministic Factorization of Sparse Polynomials with Bounded Individual Degree	2018	Vishwas Bhargava Shubhangi Saraf Ilya Volkovich
+	Low-Rank Approximation from Communication Complexity	2019	Cameron Musco Christopher Musco David P. Woodruff
+	Improved upper bounds for the rigidity of Kronecker products	2021	Bohdan Kivva
+	Efficient Removal Lemmas for Matrices	2016	Noga Alon Omri Ben‐Eliezer

Works That Cite This (0)

Action	Title	Year	Authors

Works Cited by This (19)

Action	Title	Year	Authors
+	The discrepancy method: randomness and complexity	2002	Bernard Chazelle
+ PDF Chat	Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits	2015	Manindra Agrawal Rohit Gurjar Arpita Korwar Nitin Saxena
+ PDF Chat	Logarithmic Lower Bounds in the Cell-Probe Model	2006	Mihai Pătraşcu Erik D. Demaine
+	The complexity of partial derivatives	1983	Walter Bäur Volker Strassen
+ PDF Chat	The cell probe complexity of dynamic range counting	2012	Kasper Green Larsen
+	Arithmetic circuits: The chasm at depth four gets wider	2012	Pascal Koiran
+ PDF Chat	Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform	1973	Jacques Morgenstern
+ PDF Chat	Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators	2000	Jaikumar Radhakrishnan Amnon Ta‐Shma
+	Superconcentrators of depths 2 and 3; odd levels help (rarely)	1994	Noga Alon Pavel Pudlák
+	On Range Searching in the Group Model and Combinatorial Discrepancy	2014	Kasper Green Larsen