Hardness-randomness tradeoffs for bounded depth arithmetic circuits

DOI10.1137/080735850MaRDI QIDQ3586180zbMATH OpenOpenAlexFDO

Authors 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

derandomizationhardnesspolynomial factoringpolynomial identity testingrandomness

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 7250153
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Stronger lower bounds and randomness-hardness trade-offs using associated algebraic complexity classes
• scientific article; zbMATH DE number 7150624

Cited in

(39)

• Algebraic independence over positive characteristic: new criterion and applications to locally low-algebraic-rank circuits
• Sums of read-once formulas: how many summands are necessary?
• Towards a tight hardness-randomness connection between permanent and arithmetic circuit identity testing
• Improved hitting set for orbit of ROABPs
• Improved bounds for quantified derandomization of constant-depth circuits and polynomials
• Equivalence of polynomial identity testing and polynomial factorization
• Strong Turing degrees for additive BSS RAM's
• Stronger lower bounds and randomness-hardness trade-offs using associated algebraic complexity classes
• Uniform derandomization from pathetic lower bounds
• Recent results on polynomial identity testing
• Subexponential size hitting sets for bounded depth multilinear formulas
• Factors of low individual degree polynomials
• ON THE HARDNESS AGAINST CONSTANT-DEPTH LINEAR-SIZE CIRCUITS
• Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size
• On the Size of Homogeneous and of Depth-Four Formulas with Low Individual Degree
• scientific article; zbMATH DE number 7009617 (Why is no real title available?)
• scientific article; zbMATH DE number 7029312 (Why is no real title available?)
• Read-once polynomial identity testing
• On some computations on sparse polynomials
• scientific article; zbMATH DE number 7471587 (Why is no real title available?)
• A generalized sylvester-gallai type theorem for quadratic polynomials
• scientific article; zbMATH DE number 7561742 (Why is no real title available?)
• scientific article; zbMATH DE number 7561765 (Why is no real title available?)
• scientific article; zbMATH DE number 7250153 (Why is no real title available?)
• scientific article; zbMATH DE number 7150624 (Why is no real title available?)
• scientific article; zbMATH DE number 5044336 (Why is no real title available?)
• Discovering the Roots: Uniform Closure Results for Algebraic Classes Under Factoring
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Schur polynomials do not have small formulas if the determinant does not
• Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds
• Complexity theory. Abstracts from the workshop held June 2--7, 2024
• On matrix multiplication and polynomial identity testing
• Superpolynomial lower bounds against low-depth algebraic circuits
• Bounded-depth circuits cannot sample good codes
• Hitting sets for orbits of circuit classes and polynomial families
• Towards deterministic algorithms for constant-depth factors of constant-depth circuits
• Deterministic polynomial identity tests for multilinear bounded-read formulae
• Hardness hypotheses, derandomization, and circuit complexity

This page was built for publication: Hardness-randomness tradeoffs for bounded depth arithmetic circuits

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