scientific article; zbMATH DE number 2019636

zbMATH Open1028.68225MaRDI QIDQ4440439FDOQ4440439

Authors: Oded Goldreich, A. Wigderson 

Publication date: 17 December 2003

Full work available at URL: http://link.springer.de/link/service/series/0558/bibs/2483/24830209.htm

Title of this publication is not available (Why is that?)

Recommendations

• Can every randomized algorithm be derandomized?
• On derandomizing algorithms that err extremely rarely
• Pseudorandom generators, typically-correct derandomization, and circuit lower bounds
• Derandomizing isolation in space-bounded settings
• Pseudorandom Generators and Typically-Correct Derandomization

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20)

Cited In (13)

• Worst-Case to Average-Case Reductions for Subclasses of P
• Pseudorandom generators, typically-correct derandomization, and circuit lower bounds
• Incompressible functions, relative-error extractors, and the power of nondeterministic reductions
• Derandomizing isolation in space-bounded settings
• Weak derandomization of weak algorithms: explicit versions of Yao's lemma
• (Nondeterministic) hardness vs. non-malleability
• Non-malleable codes with optimal rate for poly-size circuits
• On uniformity and circuit lower bounds
• Derandomizing isolation in space-bounded settings
• Fine-grained derandomization: from problem-centric to resource-centric complexity
• Typically-correct derandomization for small time and space
• On the average-case complexity of property testing
• Nearly optimal pseudorandomness from hardness

This page was built for publication:

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