CSDM Seminars

The INDEX problem is one of a handful of fundamental problems in communication complexity: Alice has an n-bit string x, Bob has an index k in [n], and the players wish to determine the k-th bit of x. It is easy to show that the problem is "hard"...

The complexity of simple stochastic games (SSGs) has been open since they were defined by Condon in 1992. Such a game is played by two players, Min and Max, on a graph consisting of max nodes, min nodes, and average nodes. The goal of Max is to...

Recently there has been much interest in polynomial threshold functions in the context of learning theory, structural results and pseudorandomness. A crucial ingredient in these works is the understanding of the distribution of low-degree...

The Unique Games conjecture (UGC) has emerged in recent years as the starting point for several optimal inapproximability results. While for none of these results a reverse reduction to Unique Games is known, the assumption of bijective projections...

The Johnson-Lindenstrauss lemma (also known as Random Projections) states that any set of n points in Euclidian space can be embedded almost isometrically into another Euclidian space of dimension O(log(n)). The talk will focus on the efficiency of...

We study the complexity of computing some basic arithmetic operations over GF(2^n), namely computing q-th root and q-th residuosity, by constant depth arithmetic circuits over GF(2) (also known as AC^0(parity)). Our main result is that these...

The Johnson-Lindenstrauss lemma states that for any n points in Euclidean space and error parameter 0

Boolean Threshold Functions (BTF) arise in many contexts, ranging from computer science and learning theory to theoretical neurobiology. In this talk, I will present non-rigorous approaches developed in the statistical physics of disordered systems...

This paper revisits the construction of Universally One-Way Hash Functions (UOWHFs) from any one-way function due to Rompel (STOC 1990). We give a simpler construction of UOWHFs which also obtains better efficiency and security. The construction...

Given data drawn from a mixture of multivariate Gaussians, a basic problem is to accurately estimate the mixture parameters. We provide a polynomial-time algorithm for this problem for any fixed number ($k$) of Gaussians in $n$ dimensions (even if...