Using elimination theory to construct rigid matrices

DOI10.1007/s00037-013-0061-0zbMath1366.68076arXiv0910.5301OpenAlexW2053068069MaRDI QIDQ475335

M. N. Jayalal Sarma, Abhinav Kumar, Satyanarayana V. Lokam, Vijay M. Patankar

Publication date: 26 November 2014

Published in: Computational Complexity (Search for Journal in Brave)

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

zbMATH Keywords

elimination theorylower boundsmatrix rigidity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Determinants, permanents, traces, other special matrix functions (15A15) Computational aspects of algebraic surfaces (14Q10) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vector spaces, linear dependence, rank, lineability (15A03)

Related Items (5)

Fourier and Circulant Matrices are Not Rigid ⋮ New applications of the polynomial method: The cap set conjecture and beyond ⋮ Matrix Rigidity from the Viewpoint of Parameterized Complexity ⋮ Fourier and circulant matrices are not rigid ⋮ Matrix Rigidity and the Ill-Posedness of Robust PCA and Matrix Completion

Cites Work

• A remark on matrix rigidity
• A note on matrix rigidity
• Definability and fast quantifier elimination in algebraically closed fields
• Bounds for the degrees in the Nullstellensatz
• The membership problem for unmixed polynomial ideals is solvable in single exponential time
• Determinantal rings
• On the rigidity of Vandermonde matrices
• Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity
• A linear lower bound on the unbounded error probabilistic communication complexity.
• Matrix rigidity
• Complexity Lower Bounds using Linear Algebra
• Learning Complexity vs Communication Complexity
• The Geometry of Schemes
• Sharp Effective Nullstellensatz
• Cohen-Macaulay Rings, Invariant Theory, and the Generic Perfection of Determinantal Loci
• Theory and Applications of Models of Computation
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Using elimination theory to construct rigid matrices