Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits

DOI10.1137/080735850zbMath1205.68170OpenAlexW2000108234MaRDI QIDQ3586180

Zeev Dvir, Amir Shpilka, Amir Yehudayoff

Publication date: 6 September 2010

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/080735850

zbMATH Keywords

derandomizationpolynomial factoringhardnessrandomnesspolynomial identity testing

Mathematics Subject Classification ID

Related Items (22)

Discovering the Roots: Uniform Closure Results for Algebraic Classes Under Factoring ⋮ Algebraic independence over positive characteristic: new criterion and applications to locally low-algebraic-rank circuits ⋮ Subexponential size hitting sets for bounded depth multilinear formulas ⋮ Factors of low individual degree polynomials ⋮ Uniform derandomization from pathetic lower bounds ⋮ Sums of read-once formulas: how many summands are necessary? ⋮ Schur polynomials do not have small formulas if the determinant does not ⋮ Unnamed Item ⋮ Deterministic polynomial identity tests for multilinear bounded-read formulae ⋮ Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds ⋮ Sylvester-Gallai type theorems for quadratic polynomials ⋮ Unnamed Item ⋮ Read-once polynomial identity testing ⋮ Recent Results on Polynomial Identity Testing ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the Size of Homogeneous and of Depth-Four Formulas with Low Individual Degree ⋮ Unnamed Item ⋮ A generalized sylvester-gallai type theorem for quadratic polynomials ⋮ Unnamed Item ⋮ Improved hitting set for orbit of ROABPs ⋮ Equivalence of polynomial identity testing and polynomial factorization

This page was built for publication: Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits