Lower Bounds on Matrix Rigidity Via a Quantum Argument

DOI10.1007/11786986_7MaRDI QIDQ3613749zbMATH OpenOpenAlexFDO

Authors Ronald de Wolf

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

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum computation (81P68) Miscellaneous inequalities involving matrices (15A45)

Abstract: The rigidity of a matrix measures how many of its entries need to be changed in order to reduce its rank to some value. Good lower bounds on the rigidity of an explicit matrix would imply good lower bounds for arithmetic circuits as well as for communication complexity. Here we reprove the best known bounds on the rigidity of Hadamard matrices, due to Kashin and Razborov, using tools from quantum computing. Our proofs are somewhat simpler than earlier ones (at least for those familiar with quantum) and give slightly better constants. More importantly, they give a new approach to attack this longstanding open problem.

Recommendations

• Theory and Applications of Models of Computation
• Improved lower bounds on the rigidity of Hadamard matrices
• A matrix convexity approach to some celebrated quantum inequalities
• Rigidity of eigenvalues of generalized Wigner matrices
• A note on matrix rigidity
• Lower bounds for matrices
• Matrix Rigidity from the Viewpoint of Parameterized Complexity
• Matrix Rigidity from the Viewpoint of Parameterized Complexity
• A remark on matrix rigidity
• Lower bounds of matrices

Cited in

(8)

• Complexity of linear circuits and geometry
• On matrix rigidity and locally self-correctable codes
• Rigidity of a simple extended lower triangular matrix
• On a theorem of Razborov
• Matrix Rigidity from the Viewpoint of Parameterized Complexity
• On approximate symmetric polynomials and tightness of homogenization results
• 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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3613749)