Two Comments on Targeted Canonical Derandomizers

DOI10.1007/978-3-030-43662-9_4MaRDI QIDQ5098768zbMATH OpenOpenAlexFDO

Authors Oded Goldreich

Publication date 30 August 2022

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.422.3697

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Recommendations

• Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace
• Targeted pseudorandom generators, simulation advice generators, and derandomizing logspace
• In a world of \(\mathrm{P}=\mathrm{BPP}\)
• Can every randomized algorithm be derandomized?
• Pseudorandom generators, typically-correct derandomization, and circuit lower bounds

Cites work

• An Unconditional Study of Computational Zero Knowledge
• Computational Complexity
• Hardness vs randomness
• How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
• In a world of \(\mathrm{P}=\mathrm{BPP}\)
• Randomness vs time: Derandomization under a uniform assumption
• The complexity of promise problems with applications to public-key cryptography

Cited in

(3)

• Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games
• Instance-wise hardness and refutation versus derandomization for Arthur-Merlin protocols
• Leakage resilience, targeted pseudorandom generators, and mild derandomization of Arthur-Merlin protocols

This page was built for publication: Two Comments on Targeted Canonical Derandomizers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5098768)