Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR16-093 | 4th June 2016 01:28

Bounded Matrix Rigidity and John's Theorem

RSS-Feed




TR16-093
Authors: Cyrus Rashtchian
Publication: 5th June 2016 07:24
Downloads: 589
Keywords: 


Abstract:

Using John's Theorem, we prove a lower bound on the bounded rigidity of a sign matrix, defined as the Hamming distance between this matrix and the set of low-rank, real-valued matrices with entries bounded in absolute value. For Hadamard matrices, our asymptotic leading constant is tighter than known results by a factor of two whenever the approximating matrix has sufficiently small entries.



ISSN 1433-8092 | Imprint