A quadratic lower bound for homogeneous algebraic branching programs

DOI10.1007/s00037-019-00186-3zbMath1429.68072OpenAlexW2954888688WikidataQ127717074 ScholiaQ127717074MaRDI QIDQ2323359

Mrinal Kumar

Publication date: 30 August 2019

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

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/7513/

zbMATH Keywords

lower boundsalgebraic complexityalgebraic branching programsarithmetic circuitsdeterminantal complexity

Mathematics Subject Classification ID

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

Related Items

Quadratic lower bounds for algebraic branching programs and formulas ⋮ Unnamed Item ⋮ A quadratic lower bound for algebraic branching programs ⋮ A lower bound on determinantal complexity ⋮ Limitations of sums of bounded read formulas and ABPs

Uses Software

• GitHub
• lowerbounds-survey

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Quadratic lower bound for permanent vs. determinant in any characteristic
• The complexity of partial derivatives
• Easy lower bound for a strange computational model
• A combinatorial formula for principal minors of a matrix with tree-metric exponents and its applications
• Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten
• Arithmetic Circuits: A survey of recent results and open questions
• Affine Dispersers from Subspace Polynomials
• A Lower Bound for the Formula Size of Rational Functions
• Representations and Parallel Computations for Rational Functions
• Identity testing and lower bounds for read- k oblivious algebraic branching programs