Lower Bounds on Matrix Rigidity via a Quantum Argument

Details Lower Bounds on Matrix Rigidity via a Quantum Argument Lower Bounds on Matrix Rigidity via a Quantum Argument

2005-05-25

arxiv.org/abs/quant-ph/0505188v2

Physics

Quantum Physics

10 pages LaTeX, 2nd version: some discussion added. This version to appear in ICALP 2006 conference

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Lower Bounds on Matrix Rigidity via a Quantum Argument does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Lower Bounds on Matrix Rigidity via a Quantum Argument, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Lower Bounds on Matrix Rigidity via a Quantum Argument will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-642166