On Defining Integers in the Counting Hierarchy and Proving Arithmetic Circuit Lower Bounds

DOI10.1007/978-3-540-70918-3_12zbMATH Open1186.68208OpenAlexW1487480175MaRDI QIDQ3590929FDOQ3590929

Authors: Peter Bürgisser 

Publication date: 3 September 2007

Published in: STACS 2007 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-70918-3_12

Recommendations

• On defining integers and proving arithmetic circuit lower bounds
• Valiant's model and the cost of computing integers
• Permanent does not have succinct polynomial size arithmetic circuits of constant depth
• Permanent does not have succinct polynomial size arithmetic circuits of constant depth
• Upper bounds on real roots and lower bounds for the permanent

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cited In (4)

• On defining integers and proving arithmetic circuit lower bounds
• Valiant's model and the cost of computing integers
• Kolmogorov Complexity Theory over the Reals
• The complexity of two problems on arithmetic circuits

This page was built for publication: On Defining Integers in the Counting Hierarchy and Proving Arithmetic Circuit Lower Bounds

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