Pseudorandomness

Explicit 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