Lower Bounds on Matrix Rigidity Via a Quantum Argument
From MaRDI portal
Publication:3613749
DOI10.1007/11786986_7zbMath1223.68050arXivquant-ph/0505188MaRDI 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
81P68: Quantum computation
15A45: Miscellaneous inequalities involving matrices
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
On a theorem of Razborov, Min-rank conjecture for log-depth circuits, Quantum multiparty communication complexity and circuit lower bounds
