Pseudorandomness when the odds are against you

DOI10.4230/LIPICS.CCC.2016.9MaRDI QIDQ5368743zbMATH OpenOpenAlexFDO

Authors Sergei Artemenko, Russell Impagliazzo, Valentine Kabanets, Ronen Shaltiel

Publication date 10 October 2017

Full work available at URL https://doi.org/10.4230/lipics.ccc.2016.9

zbMATH Keywords

derandomizationhitting-set generatorpseudorandom generatorrelative error

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Recommendations

• Hardness vs randomness
• Can every randomized algorithm be derandomized?
• scientific article; zbMATH DE number 1559537
• Simple extractors for all min-entropies and a new pseudorandom generator
• Pseudorandom generators without the XOR lemma (extended abstract)

Cited in

(9)

• Incompressible functions, relative-error extractors, and the power of nondeterministic reductions
• Bad and Good Ways of Post-processing Biased Physical Random Numbers
• Pseudorandom generators, typically-correct derandomization, and circuit lower bounds
• The journey from NP to TFNP hardness
• Improving on Gutfreund, Shaltiel, and Ta-Shma's paper ``If NP languages are hard on the worst-case, then it is easy to find their hard instances
• Pseudodeterministic constructions in subexponential time
• Derandomizing Knockoffs
• Nearly optimal pseudorandomness from hardness
• Non-malleable codes with optimal rate for poly-size circuits

This page was built for publication: Pseudorandomness when the odds are against you

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