“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.”

Read the paper and see the full list of authors at SIAM.