2012-2013 Seminars

I will describe some recent results and problems regarding influence of sets of variables on Boolean functions: In 1989 Benny Chor conjectured that a balanced Boolean function with n variables has a subset S of size 0.4n with influence (1-c^n) where...

A linear property of Banach spaces is called "local" if it depends on finite number of vectors and is invariant under renorming (i.e., distorting the norm by a finite factor). A famous theorem of Ribe states that local properties are invariant under...

We study the problem of constructing extractors for independent weak random sources. The probabilistic method shows that such an extractor exists for two sources on n bits with min-entropy k >= 2 log n. On the other hand, explicit constructions are...

Abstract: We give near-tight lower bounds for the sparsity required in several dimensionality reducing linear maps. In particular, we show: (1) The sparsity achieved by [Kane-Nelson, SODA 2012] in the sparse Johnson-Lindenstrauss lemma is optimal up...

In small dimension a random geometric graph behaves very differently from a standard Erdös-Rényi random graph. On the other hand, when the dimension tends to infinity (with the number of vertices being fixed) both models coincide. In this talk we...

An “oblivious subspace embedding” (OSE) is a distribution over matrices S such that for any low-dimensional subspace $V$, with high probability over the choice of $S$, $\|Sx\|_2$ approximately equals $\|x\|_2$ (up to $1 + \epsilon$ multiplicative...

For a set of polynomials F, we define their bilinear complexity as the smallest k so that F lies in an ideal generated by k bilinear polynomials. The main open problem is to estimate the bilinear complexity of the single polynomial $\sum_{i,j}x_i^2...

We will give an overview of this system, which has been at the center of recent algorithmic and proof complexity developments. We will give the definitions of the system (as a proof system for polynomial inequalities, and as an SDP-based algorithm)...

The PCP theorem (Arora et. al., J. ACM 45(1,3)) asserts the existence of proofs that can be verified by reading a very small part of the proof. Since the discovery of the theorem, there has been a considerable work on improving the theorem in terms...