Computer Science and Discrete Mathematics (CSDM)

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...

I plan to survey the many ways we have today of constructing expanding Cayley graphs of finite groups, and the ideas behind their analysis (some useful beyond that purpose). I want to highlight that despite a comprehensive understanding of achieving...

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...

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 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 revisit the question of whether it is possible to build succinct non-interactive arguments (SNARGs) for all of NP under standard cryptographic assumptions. In particular, we give a candidate non-adaptive SNARG for NP and prove its soundness under...

The regularity lemma says that every discrete object can be partitioned into a small number of random-like subobjects. But how small is small? And can we make small smaller if we assume that our given object is simple? And what does it mean for a...

The very first result ever proved about tournaments is due to Rédei, who nearly 100 years ago proved that every tournament contains a Hamiltonian directed path. Since then, questions and results about directed paths in tournaments have become a...

In the theory of error-correcting codes, list decoding allows a decoder to output a list of candidates when attempting to remove noise from a corrupted input. The constructions and algorithms for such list decodable codes has had numerous...