Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > ALLEN LIU:
All reports by Author Allen Liu:

TR19-129 | 27th September 2019
Zeev Dvir, Allen Liu

Fourier and Circulant Matrices are Not Rigid

The concept of matrix rigidity was first introduced by Valiant in [Val77]. Roughly speaking, a matrix is rigid if its rank cannot be reduced significantly by changing a small number of entries. There has been extensive interest in rigid matrices as Valiant showed that rigidity can be used to prove ... more >>>




ISSN 1433-8092 | Imprint