Johan Håstad

We prove that the correlation of a depth-$d$

unbounded fanin circuit of size $S$ with parity

of $n$ variables is at most $2^{-\Omega(n/(\log S)^{d-1})}$.

Andrej Bogdanov, Chin Ho Lee

We show that secure homomorphic evaluation of any non-trivial functionality of sufficiently many inputs with respect to any CPA secure encryption scheme cannot be implemented by constant depth, polynomial size circuits, i.e. in the class AC0. In contrast, we observe that certain previously studied encryption schemes (with quasipolynomial security) can ... more >>>

Johan Håstad

We extend the recent hierarchy results of Rossman, Servedio and

Tan \cite{rst15} to any $d \leq \frac {c \log n}{\log {\log n}}$

for an explicit constant $c$.

To be more precise, we prove that for any such $d$ there is a function

$F_d$ that is computable by a read-once formula ...
more >>>