Determinants vs. algebraic branching programs

DOI10.1007/s00037-024-00258-zMaRDI QIDQ6624427

Mrinal Kumar, Abhranil Chatterjee, Ben lee Volk

Publication date: 25 October 2024

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

zbMATH Keywords

lower boundsalgebraic branching programsalgebraic 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)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Quadratic lower bound for permanent vs. determinant in any characteristic
• On computing the determinant in small parallel time using a small number of processors
• Permanent and determinant
• The complexity of partial derivatives
• Lower bounds for polynomial evaluation and interpolation problems
• Permanent v. determinant: an exponential lower bound assuming symmetry and a potential path towards Valiant's conjecture
• A lower bound on determinantal complexity
• Quadratic lower bounds for algebraic branching programs and formulas
• A quadratic lower bound for homogeneous algebraic branching programs
• A lower bound for the determinantal complexity of a hypersurface
• Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten
• Complexity Lower Bounds using Linear Algebra
• A Lower Bound for the Formula Size of Rational Functions

This page was built for publication: Determinants vs. algebraic branching programs