Seminars

We use critical block sensitivity, a new complexity measure introduced by Huynh and Nordstrom (STOC 2012) to study the communication complexity of search problems. Our main result is a simple proof that if \(S\) is a search problem with high...

We introduce and study a new type of learning problem for probability distributions over the Boolean hypercube \(\{-1,1\}^n\). As in the standard PAC learning model, a learning problem in our framework is defined by a class \(C\) of Boolean...

Given data stream \(D = \{p_1,p_2,...,p_m\}\) of size \(m\) of numbers from \(\{1,..., n\}\), the frequency of \(i\) is defined as \(f_i = |\{j: p_j = i\}|\). The \(k\)-th frequency moment of \(D\) is defined as \(F_k = \sum_{i=1}^n f_i^k\). We...

Classical matrix perturbation bounds, such as Weyl (for eigenvalues) and David-Kahan (for eigenvectors) have, for a long time, been playing an important role in various areas: numerical analysis, combinatorics, theoretical computer science...

Let \(K\) and \(T\) be convex bodies in the \(n\)-dimensional Euclidean space. The covering number of \(K\) by \(T\) is the minimal number of translates of \(T\) required to cover \(K\) entirely. One open question regarding this classical notion is...

Motivated by questions in Social Choice Theory I will consider the following extremal problem in Combinatorial Geometry. Call a sequence of vectors of length \(n\) with \(-1\), \(1\) entries feasible if it contains a subset whose sum is positive in...

The goal of (general-purpose) program obfuscation is to make an arbitrary computer program "unintelligible" while preserving its functionality. The problem of program obfuscation is well studied both in theory and in practice. Though despite its...

In this lecture, I will talk about moment based SDP hierarchies (which are duals of SOS relaxations for polynomial optimization) in the context of graph partitioning. The focus will be on a certain way of rounding such hierarchies, whose quality is...