Computer Science and Discrete Mathematics (CSDM)

The Parallel Repetition Theorem upper-bounds the value of a repeated (tensored) two prover game in terms of the value of the base game and the number of repetitions. In this work we give a simple transformation on games -- "fortification" -- and...

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

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

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

Computing the volume of a convex body in n-dimensional space is an ancient, basic and difficult problem (#P-hard for explicit polytopes and exponential lower bounds for deterministic algorithms in the oracle model). We present a new algorithm, whose...