Computer Science and Discrete Mathematics (CSDM)

The celebrated Brascamp-Lieb (BL) inequalities are an important mathematical tool, unifying and generalizing numerous inequalities in analysis, convex geometry and information theory, with many used in computer science. I will survey the well...

The Minimum Circuit Size Problem (MCSP) and a related problem (MKTP) that deals with time-bounded Kolmogorov complexity are prominent candidates for NP-intermediate status. We present new results relating the complexity of various approximation...

We provide a duality framework for Bayesian Mechanism Design. Specifically, we show that the dual problem to revenue maximization is a search over virtual transformations. This approach yields a unified view of several recent breakthroughs in...

I will show a new efficient approximate nearest neighbor search (ANN) algorithm over an arbitrary high-dimensional *symmetric* norm. Traditionally, the ANN problem in high dimensions has been studied over the $\ell_1$ and $\ell_2$ distances with a...

In recent years, there has been a surge of exciting research activity at the interface of optimization (in particular polynomial, semidefinite, and sum of squares optimization) and the theory of dynamical systems. In this talk, we focus on two...

Random constraint satisfaction problems (CSPs) are known to exhibit threshold phenomena: given a uniformly random instance of a CSP with $n$ variables and $m$ clauses, there is a value of $m = \Omega(n)$ beyond which the CSP will be unsatisfiable...

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