TR22-148 Authors: Peter Ivanov, Raghu Meka, Emanuele Viola

Publication: 11th November 2022 15:56

Downloads: 243

Keywords:

An $n$-bit boolean function is resilient to coalitions of size $q$

if no fixed set of $q$ bits is likely to influence the value of the

function when the other $n-q$ bits are chosen uniformly at random,

even though the function is nearly balanced. We construct explicit

functions resilient to coalitions of size $q=n/(\log n)^{O(\log\log n)}=n^{1-o(1)}$

computable by linear-size circuits and linear-time algorithms. We

also obtain a tight size-depth tradeoff for computing such resilient

functions.

Constructions such as ours were not available even non-explicitly.

It was known that functions resilient to coalitions of size $q=n^{0.63...}$

can be computed by linear-size circuits \cite{Ben-OrLi85}, and functions

resilient to coalitions of size $q=\Theta(n/\log^{2}n)$ can be computed

by quadratic-size circuits \cite{AL93}.

One component of our proofs is a new composition theorem for resilient

functions.