Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR22-148 | 11th November 2022 15:56

#### Efficient resilient functions

TR22-148
Authors: Peter Ivanov, Raghu Meka, Emanuele Viola
Publication: 11th November 2022 15:56
Keywords:

Abstract:

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