Using elimination theory to construct rigid matrices

DOI10.4230/LIPICS.FSTTCS.2009.2327zbMATH Open1248.68221OpenAlexW2286151938MaRDI QIDQ2920137FDOQ2920137

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

Publication date: 24 October 2012

Full work available at URL: http://subs.emis.de/LIPIcs/frontdoor_a04f.html

zbMATH Keywords

lower boundscircuit complexitymatrix rigidityelimination theoryeffective Nullstellensatz

Mathematics Subject Classification ID

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

Cited In (5)

• On the geometry of tensor network states of \(2\times N\) grids
• Complexity of linear circuits and geometry
• Unifying known lower bounds via geometric complexity theory
• Matrix Rigidity from the Viewpoint of Parameterized Complexity
• Geometric complexity theory: an introduction for geometers

Recommendations

• A remark on matrix rigidity 👍 👎
• A note on matrix rigidity 👍 👎
• Explicit constructions of RIP matrices and related problems 👍 👎
• Rigidity of a simple extended lower triangular matrix 👍 👎
• Using elimination theory to construct rigid matrices 👍 👎
• Matrices in elimination theory 👍 👎
• A simple construction of elliptic \(R\)-matrices 👍 👎
• Efficient Construction of Rigid Matrices Using an NP Oracle 👍 👎
• Some Elimination Problems for Matrices 👍 👎
• Computation of hybrid element matrices by elimination techniques 👍 👎

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2920137)