Seminars

Finding large cliques in random graphs and the closely related "planted" clique variant, where a clique of size \(k\) is planted in a random \(G(n,1/2)\) graph, have been the focus of substantial study in algorithm design. Despite much effort, the...

I will present an exciting new interaction between computer science and fair division theory, with the goal of giving the audience a taste of different fair division challenges and the role computational thinking plays in addressing them. Among...

A folded symplectic form on a manifold is a closed 2-form with the mildest possible degeneracy along a hypersurface. A special class of folded symplectic manifolds are the origami manifolds. In the classical case, toric symplectic manifolds can...

The computational worldview is relevant to multiple fields of investigation beyond computer science, including evolutionary theory. Evolution is a creative process that generates organisms as well as behavioral programs, which can be thought of as...

In its simplest form, the central limit theorem states that a sum of n independent random variables can be approximated with error \(O(n^{-1/2})\) by a Gaussian with matching mean and second moment (given these variables are not too dissimilar). We...

Consider an image with two colors--black and white--and where only 1% of the pixels are white. If we apply a Gaussian blur, can it be that the non-black pixels of the (now greyscale) image are largely concentrated on a single shade of grey? Sure, if...

The signrank of an \(N \times N\) matrix \(A\) of signs is the minimum possible rank of a real matrix \(B\) in which every entry has the same sign as the corresponding entry of \(A\). The VC-dimension of \(A\) is the maximum cardinality of a set of...

We introduce a new method of obtaining sharp estimates on mixing for Glauber dynamics for the Ising model, which, in particular, establishes cutoff in three dimensions up to criticality. The new framework, which considers ``information percolation''...

In profoundly influential works, Shannon and Huffman show that if Alice wants to send a message \(X\) to Bob, it's sufficient for her to send roughly \(H(X)\) bits (in expectation), where \(H\) denotes Shannon's entropy function. In other words, the...

Geometric questions for discrete objects (e.g. isoperimetry, integrality gaps, embeddings) are often easier to understand by first considering an appropriate continuous analogue, using additional structure that is available in the continuous setting...