Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Amplification:
TR98-074 | 16th December 1998
Madhu Sudan, Luca Trevisan, Salil Vadhan

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