2023-2024 Seminars

Over the last two decades we have developed good understanding how to quantify the impact of strategic user behavior on outcomes in many games (including traffic routing and online auctions) and showed that the resulting bounds extend to repeated...

I will discuss recent progress on approximating the metric traveling salesperson problem, focusing on a line of work beginning in 2011 that studies the behavior of the max entropy algorithm. This algorithm is a randomized variant of the beautiful...

Consider the process where a signal propagates downward an infinite rooted tree. On every edge some independent noise is applied to the signal. The reconstruction problem asks whether it is possible to reconstruct the original signal given...

Consider an oracle which takes a point $x$ and returns the minimizer of a convex function $f$ in an $\ell_2$ ball of radius $r$ around $x$. While it is straightforward to show that $\approx r^{-1}$ queries to this oracle suffice to minimize $f$ to...

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 code. This result gives the first separation between LCCs and...

In this talk, I will discuss progress on showing hardness of the Minimum Circuit Size Problem (MCSP). The computational complexity of MCSP is a longstanding mystery, dating back as far as Levin's seminal work on NP-completeness in 1973. Over the...

Consider a scenario where we are learning a predictor, whose predictions will be evaluated by their expected loss. What if we do not know the precise loss at the time of learning, beyond some generic properties (like convexity)? What if the same...

The Tree Evaluation Problem has emerged in the past decade as a leading candidate for separating logspace from polynomial time. In this talk we will introduce the problem, as well as the context behind its introduction and conjectured hardness. We...

The online discrepancy minimization problem asks, given unit vectors v_1, ..., v_t arriving one at a time, for online signs x_1 ..., x_t4 in {-1, 1} so that the signed sum x_1 v_1 + ... + x_t v_t has small coordinates in absolute value. 

In the first...

A function $f : \mathbb{F}_2^n \to \mathbb{F}_2^n$ is linear if $f(x+y)=f(x)+f(y)$ for all pairs $(x,y)$.

Suppose $f$ is "a bit linear" -- say, $f(x+y)=f(x)+f(y)$ for 1% of pairs $(x,y)$.  Must $f$ agree with a truly linear function a positive...