Efficient resilient functions

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) = n1-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 = n0.63… can be computed by linear-size circuits [BL85], and functions resilient to coalitions of size q = Θ(n/ log2 n) can be computed by quadratic-size circuits [AL93]. One component of our proofs is a new composition theorem for resilient functions. * This paper subsumes an unpublished work by Meka. PI and EV are partially supported by NSF grant CCF-2114116.