Fourier and circulant matrices are not rigid

DOI10.4230/LIPIcs.CCC.2019.17OpenAlexW2965353432MaRDI QIDQ5091768

Allen P. Liu, Zeev Dvir

Publication date: 27 July 2022

Full work available at URL: https://doi.org/10.4230/lipics.ccc.2019.17

zbMATH Keywords

rigiditycirculant matrixFourier matrix

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

Matrix and tensor rigidity and \(L_p\)-approximation ⋮ Unnamed Item ⋮ On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions

Cites Work

• Unnamed Item
• A remark on matrix rigidity
• Using elimination theory to construct rigid matrices
• A note on matrix rigidity
• On the rigidity of Vandermonde matrices
• Complexity Lower Bounds using Linear Algebra
• Quasirandom Groups
• Shifted primes without large prime factors
• Probabilistic rank and matrix rigidity
• Matrix rigidity and the Croot-Lev-Pach lemma
• Matrix rigidity of random toeplitz matrices
• Theory and Applications of Models of Computation