On the rigidity of Vandermonde matrices

DOI10.1016/S0304-3975(00)00008-6zbMath0943.68072MaRDI QIDQ1566747

Satyanarayana V. Lokam

Publication date: 4 June 2000

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

Vandermonde matrixarithmetic circuitsmatrix rigidity

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (11)

Complexity of linear circuits and geometry ⋮ Fourier and Circulant Matrices are Not Rigid ⋮ New applications of the polynomial method: The cap set conjecture and beyond ⋮ On a theorem of Razborov ⋮ Min-rank conjecture for log-depth circuits ⋮ Using elimination theory to construct rigid matrices ⋮ Matrix Rigidity from the Viewpoint of Parameterized Complexity ⋮ Rigidity of a simple extended lower triangular matrix ⋮ Fourier and circulant matrices are not rigid ⋮ Efficient Construction of Rigid Matrices Using an NP Oracle ⋮ Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A remark on matrix rigidity
• A note on matrix rigidity
• On the ratio of optimal integral and fractional covers
• Improved lower bounds on the rigidity of Hadamard matrices
• Communication in bounded depth circuits
• Lower bounds for polynomial evaluation and interpolation problems

This page was built for publication: On the rigidity of Vandermonde matrices