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²n with bias n⁻ᶜ. 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.
No takes yet. Share an insight, caveat, or question.
Ivanov et al. (2024) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: