Computer Science and Discrete Mathematics (CSDM)

Is randomness ever necessary for space-efficient computation? It is commonly conjectured that L = BPL, meaning that halting decision algorithms can always be derandomized without increasing their space complexity by more than a constant factor. In...

Consider a function on Rn that can be written as a sum of functions f=f1 + f2 + ... + fm, for m greater than n.

The question of approximating f by a reweighted sum using only a small number of summands has many applications in CS theory, mathematical...

Strong spatial mixing (SSM) is an important and widely studied quantitative notion of "correlation decay" for a variety of natural distributions arising in statistical physics, probability theory, and theoretical computer science. One of the most...

Explicit constructions of "random-like" objects play an important role in complexity theory and pseudorandomness. For many important objects such as prime numbers and rigid matrices, it remains elusive to find fast deterministic algorithms for...

High dimensional expanders are an exciting generalization of expander graphs to hypergraphs and other set systems.  Loosely speaking, high dimensional expanders are sparse approximation to the complete hypergraph.  In this talk, we’ll give a gentle...

In this work we prove a high dimensional analogue of the beloved Goldreich-Levin  theorem (STOC 1989), which is the first local list-decoding algorithm.  We consider the following algorithmic problem: given oracle access to a function f:Zmq⟶Znq such...

I will give an introduction to the problem of sampling from a strongly log-concave density on Euclidean space through the lens of convex optimization.  In particular, I will focus on the interpretation, due to Jordan, Kinderlehrer, and Otto, of the...

In 1948, Shannon used a probabilistic argument to show the existence of codes achieving channel capacity. In 1954, Muller and Reed introduced a simple deterministic code construction, conjectured shortly after to achieve channel capacity. Major...

Recent years have seen remarkable progress in the field of Machine Learning (ML). 

However recent breakthroughs exhibit phenomena that remain unexplained and at times contradict conventional wisdom.  A primary reason for this discrepancy is that...