Seminars

Nov
25
2014

Computer Science/Discrete Mathematics Seminar II

Sum-of-squares lower bounds for the planted clique problem
10:30am|S-101

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

Nov
24
2014

Computer Science/Discrete Mathematics Seminar I

Computational fair division
Ariel Procaccia
11:15am|S-101

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

Nov
18
2014

Computer Science/Discrete Mathematics Seminar II

Toric origami manifolds and origami templates
10:30am|S-101

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

Nov
17
2014

Computer Science/Discrete Mathematics Seminar I

Mutation as a computational event
Adi Livnat
11:15am|S-101

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

Nov
11
2014

Computer Science/Discrete Mathematics Seminar II

Asymptotic expansions of the central limit theorem and its applications
10:30am|S-101

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

Nov
10
2014

Computer Science/Discrete Mathematics Seminar I

Talagrand's convolution conjecture and geometry via coupling
11:15am|S-101

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

Nov
04
2014

Computer Science/Discrete Mathematics Seminar II

Sign rank, spectral gap and VC dimension
10:30am|S-101

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

Nov
03
2014

Computer Science/Discrete Mathematics Seminar I

Information percolation for the Ising model
Eyal Lubetzky
11:15am|S-101

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

Oct
28
2014

Computer Science/Discrete Mathematics Seminar II

Exponential separation of information and communication
10:30am|S-101

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

Oct
27
2014

Computer Science/Discrete Mathematics Seminar I

Discretization and quantitative differentiation
11:15am|S-101

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