An introduction to the hardness versus randomness paradigm (Part 2) @SimonsInstitute
An introduction to the hardness versus randomness paradigm (Part 2)  @SimonsInstitute
Uploaded September 2026 | Updated November 2026, 4 days ago
Ronen Shaltiel (University of Haifa)
https://simons.berkeley.edu/talks/ronen-shaltiel-university-haifa-2026-09-02
Joint Boot Camp: Spectral Theory Beyond Graphs + Pseudorandomness and High-Dimensional Expansion

The hardness versus randomness paradigm (initiated by Blum, Micali, Yao, Nisan and Wigderson) aims to show that randomized complexity classes can be derandomized assuming that certain complexity theoretic hardness assumptions hold. The key concept in this research is that of a pseudorandom generator, which stretches a short seed of random bits into a long string of pseudorandom bits that cannot be distinguished from uniform bits by any efficient algorithm. In the talk I will survey classical constructions of pseudorandom generators based on hardness assumptions, as well as implications of these constructions. I will also try to broadly survey some of the more recent work in this area.
An introduction to the hardness versus randomness paradigm (Part 2)A new class of algorithms for trajectory inferenceRandom Hyperbolic Surfaces (Part 1)A 3D Self-Correcting Quantum MemoryWhat Kind of Hallucination Is This? Decomposing Uncertainty for Generative ModelsGlobal selection, local completion: a probabilistic anatomy of diffusion U-NetUnderstanding and enhancing diffusion model: a quantification of its generalizability, and a...Spectrum of Brownian Motions on the General Linear GroupThe Polynomial Method and Random MatricesWindowed thinning and query complexity for the bouncy particle and Zigzag samplersClassical algorithms for quantum Gibbs statesAn introduction to the hardness versus randomness paradigm (Part 1)
Simons Institute for the Theory of Computing |

An introduction to the hardness versus randomness paradigm (Part 2)

SHARE TO X SHARE TO REDDIT SHARE TO FACEBOOK WALLPAPER