On defining integers and proving arithmetic circuit lower bounds

DOI10.1007/s00037-009-0260-xzbMath1213.68308OpenAlexW2153575169MaRDI QIDQ626611

Peter Bürgisser

Publication date: 18 February 2011

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

Full work available at URL: https://doi.org/10.1007/s00037-009-0260-x

zbMATH Keywords

permanentalgebraic complexityfactorialsinteger roots of univariate polynomials

Mathematics Subject Classification ID

Counting solutions of Diophantine equations (11D45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (10)

Counting arithmetic formulas ⋮ Towards a tight hardness-randomness connection between permanent and arithmetic circuit identity testing ⋮ Interpolation in Valiant's theory ⋮ Permanent Does Not Have Succinct Polynomial Size Arithmetic Circuits of Constant Depth ⋮ Unnamed Item ⋮ Algebraic Complexity Classes ⋮ Malod and the Pascaline ⋮ A \(\tau \)-conjecture for Newton polygons ⋮ Monomials in arithmetic circuits: complete problems in the counting hierarchy ⋮ Real \(\tau \)-conjecture for sum-of-squares: a unified approach to lower bound and derandomization

This page was built for publication: On defining integers and proving arithmetic circuit lower bounds