Computer Science and Discrete Mathematics (CSDM)

Sketching for distance estimation is the problem where we need to design a possibly randomized function $F$ from a metric space to short strings, such that for any points $x,y$ from the metric space, the "sketches" $F(x)$ and $F(y)$ are sufficient...

In this talk, I will discuss our recent efforts to formalize a particular notion of “fairness” in online decision making problems, and study its costs on the achievable learning rate of the algorithm. Our focus for most of the talk will be on the...

The sensitivity conjecture is a famous open problem in the theory of boolean functions. Let $f$ be a boolean function defined on the hypercube. The sensitivity of a node $x$ is the number of its neighbours in the hypercube, for which $f$ give the...

An active learning algorithm for a classification problem has access to many unlabelled samples. The algorithm asks for the labels of a small number of samples, carefully chosen, such that that it can leverage this information to correctly label...

The "cap set problem" asks for the size of the largest subset $S$ of the vector space $\mathbb F_3^n$ containing no three elements summing to 0. Progress on this problem was slow for many years, until the spring of 2016, when a very short argument...

Let $P:\{0,1\}^k \to \{0,1\}$ be a $k$-ary predicate. A random instance of a constraint satisfaction problem (CSP(P)) where each of the $\Delta n$ constraints is $P$ applied to $k$ literals on $n$ variables chosen at random is unsatisfiable with...

The motivating question for this talk is: What does a sparse Erdős–Rényi random graph, conditioned to have twice the number of triangles than the expected number, typically look like? Motivated by this question, In 2014, Chatterjee and Dembo...

We show that for constraint satisfaction problems (CSPs), sub-exponential size linear programming relaxations are as powerful as $n^{\Omega(1)}$-rounds of the Sherali-Adams linear programming hierarchy. As a corollary, we obtain sub-exponential size...

Consider a set of $n$ points in $\mathbb R^d$. The classical theorem of Sylvester-Gallai says that, if the points are not all collinear then there must be a line through exactly two of the points. Let us call such a line an "ordinary line". In a...

In this talk I will review some of the classical (and fundamental) results in the theory of graph rigidity.