On fixed-polynomial size circuit lower bounds for uniform polynomials in the sense of Valiant

DOI10.1016/j.ic.2014.09.006zbMath1312.68091OpenAlexW2140459707MaRDI QIDQ2514144

Hervé Fournier, Rémi de Joannis de Verclos, Sylvain Perifel

Publication date: 30 January 2015

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2014.09.006

zbMATH Keywords

arithmetic circuitsValiant's classescircuit lower boundscomplex fieldArthur-Merlin classes

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)

Cites Work

• The complexity of combinatorial problems with succinct input representation
• The complexity of partial derivatives
• Improved lower bounds on the number of multiplications/divisions which are necessary to evaluate polynomials
• Completeness and reduction in algebraic complexity theory
• Hilbert's Nullstellensatz is in the polynomial hierarchy
• Circuit-size lower bounds and non-reducibility to sparse sets
• PP is as Hard as the Polynomial-Time Hierarchy
• Circuit Lower Bounds for Merlin–Arthur Classes
• On the Complexity of Numerical Analysis
• Algebraic methods for interactive proof systems
• Polynomials with Rational Coefficients Which are Hard to Compute
• Derandomizing polynomial identity tests means proving circuit lower bounds
• The complexity theory companion
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On fixed-polynomial size circuit lower bounds for uniform polynomials in the sense of Valiant