Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > AMPLIFICATION:
Reports tagged with Amplification:
TR98-074 | 16th December 1998

#### Pseudorandom generators without the XOR Lemma

Revisions: 2

Impagliazzo and Wigderson have recently shown that
if there exists a decision problem solvable in time \$2^{O(n)}\$
and having circuit complexity \$2^{\Omega(n)}\$
(for all but finitely many \$n\$) then \$\p=\bpp\$. This result
is a culmination of a series of works showing
connections between the existence of hard predicates
and ... more >>>

TR15-158 | 27th September 2015
Ofer Grossman, Dana Moshkovitz

#### Amplification and Derandomization Without Slowdown

We present techniques for decreasing the error probability of randomized algorithms and for converting randomized algorithms to deterministic (non-uniform) algorithms. Unlike most existing techniques that involve repetition of the randomized algorithm, and hence a slowdown, our techniques produce algorithms with a similar run-time to the original randomized algorithms.

The ... more >>>

ISSN 1433-8092 | Imprint