An introduction to the hardness versus randomness paradigm (Part 1) @SimonsInstitute
An introduction to the hardness versus randomness paradigm (Part 1)  @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-08-31
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 1)The Truth About Your Lying Calibrated Forecaster: How to Design Truthful Calibration MeasuresRandom hyperbolic surfacesRandomness Extractors and Related Objects (Part 1)Derandomizing Matrix Concentration Inequalities from Free ProbabilityBinary code rate bounds via classical quantum channelsSpectral Diversity as a Paradigm for Trustworthy AIHallucination Rates in Language GenerationExplicit Almost-Optimal ε-Balanced Codes via Free Expander WalksKikuchi Graphs: A Spectral Method for HypergraphsA survey on PIT for read-once algebraic branching programsNew directions in catalytic derandomizationPolar Codes I
Simons Institute for the Theory of Computing |

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

SHARE TO X SHARE TO REDDIT SHARE TO FACEBOOK WALLPAPER