Computer Science and Discrete Mathematics (CSDM)

One of the major open problems in complexity theory is proving super-logarithmic lower bounds on the depth of circuits. Karchmer, Raz, and Wigderson (Computational Complexity 5(3/4), 1995) suggested approaching this problem by proving that depth...

A weighted pseudorandom generator (WPRG) is a generalization of a pseudorandom generator (PRG) in which, roughly speaking, probabilities are replaced with weights that are permitted to be positive or negative. In this talk, we present new explicit...

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