Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with typically-correct derandomization:
TR10-129 | 16th August 2010
Jeff Kinne, Dieter van Melkebeek, Ronen Shaltiel

Pseudorandom Generators, Typically-Correct Derandomization, and Circuit Lower Bounds

The area of derandomization attempts to provide efficient deterministic simulations of randomized algorithms in various algorithmic settings. Goldreich and Wigderson introduced a notion of "typically-correct" deterministic simulations, which are allowed to err on few inputs. In this paper we further the study of typically-correct derandomization in two ways.

First, we ... more >>>

ISSN 1433-8092 | Imprint