Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Nisan-Wigderson:
TR10-186 | 2nd December 2010
Bill Fefferman, Ronen Shaltiel, Chris Umans, Emanuele Viola

On beating the hybrid argument

The {\em hybrid argument}
allows one to relate
the {\em distinguishability} of a distribution (from
uniform) to the {\em
predictability} of individual bits given a prefix. The
argument incurs a loss of a factor $k$ equal to the
bit-length of the
distributions: $\epsilon$-distinguishability implies only
$\epsilon/k$-predictability. ... more >>>

ISSN 1433-8092 | Imprint