Uniform Derandomization from Pathetic Lower Bounds

DOI10.1007/978-3-642-15369-3_29MaRDI QIDQ3588422zbMATH OpenOpenAlexFDO

Authors Vikraman Arvind, Fengming Wang, Eric Allender

Publication date 10 September 2010

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-15369-3_29

zbMATH Keywords

circuit complexityderandomizationpolynomial identity testing

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Formal languages and automata (68Q45) Randomized algorithms (68W20)

Recommendations

• Uniform derandomization from pathetic lower bounds
• On circuit lower bounds from derandomization
• Strong average-case lower bounds from non-trivial derandomization
• scientific article; zbMATH DE number 1775407
• Some results on derandomization
• scientific article; zbMATH DE number 1962815
• Pseudorandomness and average-case complexity via uniform reductions
• On uniformity and circuit lower bounds
• On derandomizing algorithms that err extremely rarely
• Tighter connections between derandomization and circuit lower bounds

Cited in

(4)

• Uniform derandomization from pathetic lower bounds
• Coin flipping in dynamic programming is almost useless
• On derandomizing algorithms that err extremely rarely
• Majority vs. approximate linear sum and average-case complexity below NC^1

This page was built for publication: Uniform Derandomization from Pathetic Lower Bounds

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