Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Karp-Lipton collapse:
TR12-080 | 18th June 2012
Baris Aydinlioglu, Dieter van Melkebeek

Nondeterministic Circuit Lower Bounds from Mildly Derandomizing Arthur-Merlin Games

In several settings derandomization is known to follow from circuit lower bounds that themselves are equivalent to the existence of pseudorandom generators. This leaves open the question whether derandomization implies the circuit lower bounds that are known to imply it, i.e., whether the ability to derandomize in *any* way implies ... more >>>

ISSN 1433-8092 | Imprint