The pointer function of G{\"{o}}{\"{o}}s, Pitassi and Watson
\cite{DBLP:journals/eccc/GoosP015a} and its variants have recently
been used to prove separation results among various measures of
complexity such as deterministic, randomized and quantum query
complexities, exact and approximate polynomial degrees, etc. In
particular, the widest possible (quadratic) separations between
deterministic and zero-error ... more >>>

Let $k=k(n)$ be the largest integer such that there
exists a $k$-wise uniform distribution over $\zo^n$ that
is supported on the set $S_m := \{x \in \zo^n : \sum_i
x_i \equiv 0 \bmod m\}$, where $m$ is any integer. We
show that $\Omega(n/m^2 \log m) \le k \le 2n/m + ... more >>>

We survey recent progress in the proof complexity of strong proof systems and its connection to algebraic circuit complexity, showing how the synergy between the two gives rise to new approaches to fundamental open questions, solutions to old problems, and new directions of research. In particular, we focus on tight ... more >>>