Pseudorandomness
6Explicit SoS lower bounds from high-dimensional expanders
Irit Dinur (Weizmann Institute of Science), Yuval Filmus (Technion), Prahladh Harsha (TIFR), Madhur Tulsiani (Toyota Technological Institute at Chicago)
Block Rigidity: Strong Multiplayer Parallel Repetition implies Super-Linear Lower Bounds for Turing Machines
Kunal Mittal (Princeton University), Ran Raz (Princeton University)
Pseudorandom Generators for Unbounded-Width Permutation Branching Programs
William Hoza (University of Texas at Austin), Edward Pyne (Harvard University), Salil Vadhan (Harvard University)
Comparing computational entropies below majority (or: When is the dense model theorem false?)
Russell Impagliazzo (University of California, San Diego), Sam McGuire (University of California, San Diego)
Shrinkage under random projections, and cubic formula lower bounds in AC^0
Yuval Filmus (Technion), Or Meir (University of Haifa), Avishay Tal (UC Berkeley)
ITCS 2021
Other Videos By Simons Institute for the Theory of Computing
| 2021-01-11 | Circuits and communication |
| 2021-01-10 | Graph algorithms |
| 2021-01-10 | Algorithms |
| 2021-01-10 | GRADUATING BITS |
| 2021-01-10 | Algorithmic game theory |
| 2021-01-10 | Quantum information |
| 2021-01-10 | Quantum |
| 2021-01-09 | Analytic methods |
| 2021-01-09 | Computational complexity |
| 2021-01-08 | Distributed models |
| 2021-01-08 | Pseudorandomness |
| 2021-01-08 | Crypto and Privacy |
| 2021-01-08 | Matchings |
| 2021-01-08 | Introductory Remarks |
| 2020-12-28 | David Harold Blackwell Summer Research Institute | Interview with Jelani Nelson |
| 2020-12-19 | Recent Developments in Supervised Learning With Noise |
| 2020-12-19 | Testing and Reconstruction via Decision Trees |
| 2020-12-18 | An Equivalence Between Private Classification and Online Prediction |
| 2020-12-18 | Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models |
| 2020-12-18 | Hardness of Identity Testing for Potts models and RBMs |
| 2020-12-18 | Near-Optimal Learning of Tree-Structured Distributions by Chow-Liu |