Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > JOHNS THEOREM:
Reports tagged with Johns Theorem:
TR16-093 | 4th June 2016
Cyrus Rashtchian

Bounded Matrix Rigidity and John's Theorem

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 ... more >>>




ISSN 1433-8092 | Imprint