Stronger lower bounds and randomness-hardness trade-offs using associated algebraic complexity classes

DOI10.4230/LIPICS.STACS.2012.519MaRDI QIDQ2904790zbMATH OpenFDO

Authors Maurice Jansen, Rahul Santhanam

Publication date 23 August 2012

Full work available at URL https://doi.org/10.4230/LIPICS.STACS.2012.519

zbMATH Keywords

circuit lower boundscomputational complexityderandomizationpolynomial identity testing

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Hardness-randomness tradeoffs for bounded depth arithmetic circuits
• Tighter connections between derandomization and circuit lower bounds
• scientific article; zbMATH DE number 7250153
• Derandomizing polynomial identity tests means proving circuit lower bounds
• scientific article; zbMATH DE number 7150624

Cited in

(6)

• Proving that \(\mathrm{prBPP}=\mathrm{prP}\) is as hard as proving that ``almost NP is not contained in P/poly
• On fixed-polynomial size circuit lower bounds for uniform polynomials in the sense of Valiant
• Hardness-randomness tradeoffs for bounded depth arithmetic circuits
• scientific article; zbMATH DE number 7250153 (Why is no real title available?)
• scientific article; zbMATH DE number 7150624 (Why is no real title available?)
• Tighter connections between derandomization and circuit lower bounds

This page was built for publication: Stronger lower bounds and randomness-hardness trade-offs using associated algebraic complexity classes

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