Lower Bounds on Matrix Rigidity Via a Quantum Argument
From MaRDI portal
Publication:3613749
DOI10.1007/11786986_7zbMath1223.68050arXivquant-ph/0505188OpenAlexW1668966671MaRDI QIDQ3613749
Publication date: 12 March 2009
Published in: Automata, Languages and Programming (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/quant-ph/0505188
Quantum computation (81P68) Miscellaneous inequalities involving matrices (15A45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (4)
Complexity of linear circuits and geometry ⋮ On a theorem of Razborov ⋮ Min-rank conjecture for log-depth circuits ⋮ Quantum multiparty communication complexity and circuit lower bounds
This page was built for publication: Lower Bounds on Matrix Rigidity Via a Quantum Argument
