A lower bound on determinantal complexity

DOI10.1007/s00037-022-00228-3OpenAlexW3083374753MaRDI QIDQ2087768

Mrinal Kumar, Ben lee Volk

Publication date: 21 October 2022

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

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

zbMATH Keywords

lower boundsalgebraic complexity theoryalgebraic circuitsdeterminantal complexity

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Networks and circuits as models of computation; circuit complexity (68Q06)

Uses Software

• GitHub
• lowerbounds-survey

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Quadratic lower bound for permanent vs. determinant in any characteristic
• On the relation between the determinant and the permanent
• Permanent and determinant
• On two extremal matrix problems
• A note on the determinant and permanent problem
• Permanent v. determinant: an exponential lower bound assuming symmetry and a potential path towards Valiant's conjecture
• Hypersurfaces with degenerate duals and the geometric complexity theory program
• On the complexity of the permanent in various computational models
• Quadratic lower bounds for algebraic branching programs and formulas
• A quadratic lower bound for homogeneous algebraic branching programs
• A combinatorial formula for principal minors of a matrix with tree-metric exponents and its applications
• A lower bound for the determinantal complexity of a hypersurface
• Arithmetic Circuits: A survey of recent results and open questions
• A Lower Bound for the Formula Size of Rational Functions
• An Improved Lower Bound on Polynomial Multiplication
• Lower Bounds for Matrix Product

This page was built for publication: A lower bound on determinantal complexity