Computer Science and Discrete Mathematics (CSDM)

Theoretical Computer Science and Discrete Mathematics

Sum-of-squares lower bounds for the planted clique problem

Avi Wigderson
Herbert H. Maass Professor, School of Mathematics
November 25, 2014
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 best known polynomial-time algorithms only solve the problem for \(k = \Theta(\sqrt{n})\). In this paper we study the complexity of the planted clique problem under algorithms from the Sum-Of-Squares hierarchy.

Computational fair division

Ariel Procaccia
Carnegie Mellon University
November 24, 2014
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 other things, I will talk about a complexity-theoretic approach to the question of why envy-free cake cutting has been so elusive; and will explain how the notion of worst-case approximation gives rise to a provably feasible notion of fairness in the context of the allocation of indivisible goods.

Toric origami manifolds and origami templates

Tara Holm
Cornell University; von Neumann Fellow, School of Mathematics
November 18, 2014
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 classified by their moment polytope, and their topology (equivariant cohomology) can be read directly from the polytope.

Asymptotic expansions of the central limit theorem and its applications

Anindya De
Center for Discrete Mathematics and Theoretical Computer Science; Visitor, School of Mathematics
November 11, 2014
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 prove an extension of this theorem where we achieve error bounds of \(O(n^{-(s-1)/2})\) by matching \(s\) moments (for any \(s > 0\)). While similar results were known in literature before this, the only explicit error bounds were known when the summands are continuous i.i.d. variables.

Talagrand's convolution conjecture and geometry via coupling

James Lee
University of Washington
November 10, 2014
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 we apply enough blur, the whole picture will be a dull grey. But can this happen for a very light shade of grey? That seems preposterous--certainly the colors should fade gracefully from light to dark. Talagrand conjectured in 1989 that we should see at least 50 shades of grey. We will prove it.

Sign rank, spectral gap and VC dimension

Noga Alon
Tel Aviv University; Visiting Professor, School of Mathematics
November 4, 2014
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 columns \(I\) of \(A\) so that for every subset \(J\) of \(I\) there is a row \(i\) of \(A\) so that \(A_{ij}=+1\) for all \(j\) in \(J\) and \(A_{ij}=-1\) for all \(j\) in \(I-J\). I will describe explicit examples of \(N \times N\) matrices with VC-dimension 2 and signrank \(\Omega(N^{1/4})\).

Information percolation for the Ising model

Eyal Lubetzky
New York University
November 3, 2014
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'' clusters in the space-time slab, shows that total-variation mixing exhibits cutoff with an \(O(1)\)-window around the time at which the magnetization is the square-root of the volume.

Exponential separation of information and communication

Gillat Kol
Member, School of Mathematics
October 28, 2014
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 message \(x\) can be compressed to roughly \(H(X)\) bits, the information content of the message. Can one prove similar results in the interactive setting, where Alice and Bob engage in an interactive communication protocol?

Cool with a Gaussian: an \(O^*(n^3)\) volume algorithm

Santosh Vempala
Georgia Institute of Technology
October 13, 2014
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 complexity grows as \(n^3\) for any well-rounded convex body (any body can be rounded by an affine transformation). This improves the previous best Lo-Ve algorithm from 2003 by a factor of \(n\), and bypasses the famous KLS hyperplane conjecture, which appeared essential to achieving such complexity.

Monotone submodular maximization over a matroid

Yuval Filmus
Member, School of Mathematics
October 7, 2014
Monotone submodular maximization over a matroid (MSMM) is a fundamental optimization problem generalizing Maximum Coverage and MAX-SAT. Maximum Coverage is NP-hard to approximate better than \(1-1/e\), an approximation ratio obtained by the greedy algorithm. The performance of the greedy algorithm deteriorates to \(1/2\) on the more general problem of MAX-SAT. Recently, Vondrak et al. designed a sophisticated algorithm attaining the optimal approximation ratio \(1-1/e\) for MSMM.