On fixed-polynomial size circuit lower bounds for uniform polynomials in the sense of Valiant
From MaRDI portal
Publication:2514144
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
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