Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR22-148 | 11th November 2022 15:56

Efficient resilient functions

RSS-Feed




TR22-148
Authors: Peter Ivanov, Raghu Meka, Emanuele Viola
Publication: 11th November 2022 15:56
Downloads: 143
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
by quadratic-size circuits \cite{AL93}.

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



ISSN 1433-8092 | Imprint