2024/06/27 by Ivanov, Peter, Viola, Emanuele
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2406.19467
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/log2n 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.