We're sorry but this page doesn't work properly without JavaScript enabled. Please enable it to continue.
Feedback

Nearly Optimal Pseudorandomness From Hardness

Formale Metadaten

Titel
Nearly Optimal Pseudorandomness From Hardness
Serientitel
Anzahl der Teile
12
Autor
Lizenz
CC-Namensnennung - keine kommerzielle Nutzung - keine Bearbeitung 4.0 International:
Sie dürfen das Werk bzw. den Inhalt in unveränderter Form zu jedem legalen und nicht-kommerziellen Zweck nutzen, vervielfältigen, verbreiten und öffentlich zugänglich machen, sofern Sie den Namen des Autors/Rechteinhabers in der von ihm festgelegten Weise nennen.
Identifikatoren
Herausgeber
Erscheinungsjahr
Sprache

Inhaltliche Metadaten

Fachgebiet
Genre
Abstract
Existing proofs that deduce BPP=P from circuit lower bounds convert randomized algorithms into deterministic algorithms with a large polynomial slowdown. We convert randomized algorithms into deterministic ones with little slowdown. Specifically, assuming exponential lower bounds against nondeterministic circuits, we convert any randomized algorithm that errs rarely into a deterministic algorithm with a similar running time (with pre-processing), and any general randomized algorithm into a deterministic algorithm whose runtime is slower by a nearly linear multiplicative factor. Our results follow from a new, nearly optimal, explicit pseudorandom generator fooling circuits of size s with seed length (1+alpha)log s for an arbitrarily small constant alpha>0, under the assumption that there exists a function f in E that requires nondeterministic circuits of size at least 2^{(1-alpha')n}, where alpha = O(alpha'). The construction uses, among other ideas, a new connection between pseudoentropy generators and locally list recoverable codes.