Fourier and Circulant Matrices are Not Rigid

DOI10.4086/toc.2020.v016a020zbMath1477.68117arXiv1902.07334OpenAlexW3118907271MaRDI QIDQ5857612

Allen P. Liu, Zeev Dvir

Publication date: 1 April 2021

Published in: Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1902.07334

zbMATH Keywords

circulant matrixmatrix rigidity

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Special matrices (15B99) Networks and circuits as models of computation; circuit complexity (68Q06)

Related Items (2)

Arithmetic circuits, structured matrices and (not so) deep learning ⋮ Lower bounds for matrix factorization

Cites Work

• Using elimination theory to construct rigid matrices
• A note on matrix rigidity
• Tutorial on large deviations for the binomial distribution
• On the rigidity of Vandermonde matrices
• Matrix rigidity of random Toeplitz matrices
• Complexity Lower Bounds using Linear Algebra
• Shifted primes without large prime factors
• Unnamed Item
• Unnamed Item

This page was built for publication: Fourier and Circulant Matrices are Not Rigid