Resilient functions: Optimized, simplified, and generalized
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909232847126528 |
|---|---|
| author | Ivanov, Peter Viola, Emanuele |
| author_facet | Ivanov, Peter Viola, Emanuele |
| contents | An $n$-bit boolean function is resilient to coalitions of size $q$ if any fixed set of $q$ bits is unlikely to influence the function when the other $n-q$ bits are chosen uniformly. We give explicit constructions of depth-$3$ circuits that are resilient to coalitions of size $cn/\log^{2}n$ with bias $n^{-c}$. Previous explicit constructions with the same resilience had constant bias. Our construction is simpler and we generalize it to biased product distributions.
Our proof builds on previous work; the main differences are the use of a tail bound for expander walks in combination with a refined analysis based on Janson's inequality. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_19467 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Resilient functions: Optimized, simplified, and generalized Ivanov, Peter Viola, Emanuele Computational Complexity Data Structures and Algorithms An $n$-bit boolean function is resilient to coalitions of size $q$ if any fixed set of $q$ bits is unlikely to influence the function when the other $n-q$ bits are chosen uniformly. We give explicit constructions of depth-$3$ circuits that are resilient to coalitions of size $cn/\log^{2}n$ with bias $n^{-c}$. Previous explicit constructions with the same resilience had constant bias. Our construction is simpler and we generalize it to biased product distributions. Our proof builds on previous work; the main differences are the use of a tail bound for expander walks in combination with a refined analysis based on Janson's inequality. |
| title | Resilient functions: Optimized, simplified, and generalized |
| topic | Computational Complexity Data Structures and Algorithms |
| url | https://arxiv.org/abs/2406.19467 |