Computer Science/Discrete Mathematics

We present a general framework for derandomizing random linear codes with respect to a broad class of properties, known as local properties, which encompass several standard notions such as minimum distance, list-decoding, list-recovery, and perfect...

Why is it so hard to prove P != NP, or even to prove super-linear circuit lower bounds? While we often blame a lack of combinatorial ingenuity, the bottleneck might be more fundamental: the logical strength of our mathematical tools.

This series of...

We define and study an extension of the notion of the VC-dimension of a hypergraph and apply it to establish a Tverberg type theorem for unions of convex sets. We also prove a new Radon type theorem for unions of convex sets, settling an open...

Note: This talk will involve quantum computing, cryptography, and representation theory, but no background in any of these will be necessary to understand it. I'll introduce everything from the basics.

Aaronson, Atia, and Susskind (2020) established...