Seminars

The sensitivity conjecture is a major outstanding foundational problems about boolean functions is the sensitivity conjecture. In one of its many forms, it asserts that the degree of a boolean function (i.e. the minimum degree of a real polynomial...

Let $S$ and $T$ be two dense subsets of $G^n$, where $G$ is the special linear group $\mathrm{SL}(2,q)$ for a prime power $q$. If you sample uniformly a tuple $(s_1,\ldots,s_n)$ from $S$ and a tuple $(t_1,\ldots,t_n)$ from $T$ then their interleaved...

In the last few years, there has been a significant interest in the computational abilities of Physarum Polycephalum (a slime mold). This drew from a remarkable experiment which showed that this organism can compute shortest paths in a maze...

A square matrix $V$ is called rigid if every matrix obtained by altering a small number of entries of $V$ has sufficiently high rank. While random matrices are rigid with high probability, no explicit constructions of rigid matrices are known to...

During last fifty years a strong machine learning theory has been developed. This theory includes: 1. The necessary and sufficient conditions for consistency of learning processes. 2. The bounds on the rate of convergence which in general cannot be...

Given a collection of constraints over a collection of variables consider the following generic constraint satisfaction algorithm: start with a random assignment of values to the variables; while violated constraints exist, select a random such...

At the heart of every local search algorithm is a directed graph on candidate solutions (states) such that every unsatisfactory state has at least one outgoing arc. In stochastic local search the hope is that a random walk will reach a satisfactory...

We give an explicit example for a Boolean function $f : \{0,1\}^n \to \{0,1\}$, such that every Boolean formula of size at most $n^{2.999}$, with gates AND, OR and NOT, computes $f$ correctly on at most $1/2 + \epsilon$ fraction of the inputs, where...

We prove that for any $\epsilon > 0$ it is NP-hard to approximate the non-commutative Grothendieck problem to within a factor $1/2 + \epsilon$, which matches the approximation ratio of the algorithm of Naor, Regev, and Vidick (STOC'13). Our proof...

Expander walk sampling is an important tool for derandomization. For any bounded function, sampling inputs from a random walk on an expander graph yields a sample average which is quite close to the true mean, and moreover the deviations obtained...