Past Events

I will prove that the block length of every linear 3-query Locally Correctable Code (LCC) with a constant distance over any small field grows exponentially with k, the dimension of

The Unfriendly Partition Conjecture posits that every countable graph can be bipartitioned in such a way that each vertex has more neighbours outside its own part (i.e., has an unfriendly

We consider the sparsification of sums $F : \mathbb{R}^n \to \mathbb{R}_+$ where $F(x) = f_1(\langle a_1,x \rangle) + ... + f_m(\langle a_m,x \rangle)$ for vectors $a_1, ..., a_m \in \mathbb{R}^n$

I will present some of the late Allen Tannenbaum's fundamental contributions to image processing and computer vision, concentrating on our collaborative research. Topics include use of symmetry groups and nonlinear

I will give a survey/tutorial-style talk on the query complexity of log-concave sampling, eventually covering some recent developments and open questions.

I'll be talking about tree decompositions and their relation to spanning trees. A tree decomposition is a way to represent a graph as a tree; generally, a good tree decomposition

In fair partition results, we aim to distribute resources among several competing players. One family of problems, known as mass partition problems, studies scenarios where we can guarantee that every

We study graph spanners for point-set in the high-dimensional Euclidean space. On the one hand, we prove that spanners with stretch <\sqrt{2} and subquadratic size are not possible, even if

This is a cute problem me and some friends overanalyzed a while back. Suppose there is a dentist who wants to examine 3 patients, but only has 2 pairs of

Given a closed set on the plane and two probability distributions on the real line, when are there random variables with the given distributions whose joint distribution is supported by

If I'm proctoring an exam and write on the board that students may not sit adjacent to another student, what should I expect the density of students to be in

In this talk I will present a new locally consistent decomposition of strings with applications to sketching of edit distance and approximate pattern matching. Edit distance is a string similarity

I’ll explain what the hook-length formula is and present a cool proof using volumes of polytopes. If there’s time, I’ll also present a probabilistic proof. No background will be needed

Endow the edges of the Z^D lattice with independent and identically distributed random capacities (e.g., uniformly distributed on [a,b] for some b>a>0). We wish to study the minimal cuts in

We study the problem of chasing positive bodies in \ell_1: given a sequence of bodies K_t = {x \in R^n_+ | C^t x ≥ 1,P^t x ≤ 1} revealed online,

Every partially ordered set has a linear extension (usually many). If two elements, x and y, are not comparable in a partially ordered set, one may ask what the probability

We propose an efficient ε-differentially private (DP) algorithm, that given a simple weighted n-vertex, m-edge graph G with a maximum unweighted degree Δ(G), outputs a synthetic graph which approximates the

Bernhard Riemann gave an exact formula for the number of primes below given bound via a particular sum over the zeros of zeta function. In the course of large scale

Agreement testing (aka direct product testing) is a main component in most PCP constructions and in many locally testable codes. We will introduce these tests and see how they can

The multi-armed bandits (MABs) model has been studied extensively in theoretical computer science and machine learning. Motivated by modern large-scale applications, a recent line of work has focused on streaming