Using Elimination Theory to construct Rigid Matrices

DOI10.4230/LIPIcs.FSTTCS.2009.2327zbMath1248.68221OpenAlexW2286151938MaRDI QIDQ2920137

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

Publication date: 24 October 2012

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

zbMATH Keywords

elimination theorylower boundseffective Nullstellensatzcircuit complexitymatrix 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 (4)

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

This page was built for publication: Using Elimination Theory to construct Rigid Matrices