Determinants vs. algebraic branching programs

DOI10.4230/LIPICS.ITCS.2024.27MaRDI QIDQ6906409zbMATH OpenFDO

Authors Abhranil Chatterjee, Mrinal Kumar, Ben Lee Volk

Publication date 4 November 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.27

zbMATH Keywords

algebraic branching programdeterminantlower boundssingular variety

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A lower bound for the determinantal complexity of a hypersurface
• A Lower Bound for the Formula Size of Rational Functions
• A lower bound on determinantal complexity
• A quadratic lower bound for homogeneous algebraic branching programs
• Complexity Lower Bounds using Linear Algebra
• Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten
• Elusive functions and lower bounds for arithmetic circuits
• scientific article; zbMATH DE number 3566171 (Why is no real title available?)
• scientific article; zbMATH DE number 3597878 (Why is no real title available?)
• scientific article; zbMATH DE number 2151804 (Why is no real title available?)
• scientific article; zbMATH DE number 6472651 (Why is no real title available?)
• Lower bounds for polynomial evaluation and interpolation problems
• On computing the determinant in small parallel time using a small number of processors
• Permanent and determinant
• Permanent v. determinant: an exponential lower bound assuming symmetry and a potential path towards Valiant's conjecture
• Quadratic lower bound for permanent vs. determinant in any characteristic
• Quadratic lower bounds for algebraic branching programs and formulas
• The complexity of partial derivatives

Cited in

(1)

• Lower bounds for planar arithmetic circuits

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

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