A lower bound for the determinantal complexity of a hypersurface

DOI10.1007/s10208-015-9300-xzbMath1375.14201arXiv1505.02205OpenAlexW2963573981MaRDI QIDQ2362290

Jarod Alper, Mauricio Velasco, Tristram C. Bogart

Publication date: 7 July 2017

Published in: Foundations of Computational Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

permanentscubic surfacesdeterminantal complexityaffine linear projections

Mathematics Subject Classification ID

Determinantal varieties (14M12) Computational aspects of higher-dimensional varieties (14Q15) Singularities of surfaces or higher-dimensional varieties (14J17) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Effectivity, complexity and computational aspects of algebraic geometry (14Q20) Hypersurfaces and algebraic geometry (14J70)

Related Items

Ulrich complexity ⋮ Permanent v. determinant: an exponential lower bound assuming symmetry and a potential path towards Valiant's conjecture ⋮ Permanent versus determinant: Not via saturations ⋮ On the complexity of the permanent in various computational models ⋮ Unnamed Item ⋮ No occurrence obstructions in geometric complexity theory ⋮ A lower bound on determinantal complexity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Binary determinantal complexity
• The complexity of computing the permanent
• Permanent and determinant
• On two extremal matrix problems
• Parametrization of the orbits of cubic surfaces
• Determinantal hypersurfaces.