期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2011
卷号：2011
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We consider a system of linear constraints over any finite Abelian group G of the following form: i(x1xn)i1x1++inxnAi for i=1t and each AiG, ij is an element of G and xi's are Boolean variables. Our main result shows that the subset of the Boolean cube that satisfies these constraints has exponentially small correlation with the MODq boolean function, when the order of G and q are co-prime numbers.
Our work extends the recent result of Chattopadhyay and Wigderson (FOCS'09) who obtain such a correlation bound for linear systems over cyclic groups whose order is a product of two distinct primes or has at most one prime factor. Our result also immediately yields the first exponential bounds on the size of boolean depth-four circuits of the form MAJANDANYO(1)MODm for computing the MODq function, when mq are co-prime. No superpolynomial lower bounds were known for such circuits for computing any explicit function.%, when m had three or more distinct prime factors.
This completely solves an open problem posed by Beigel and Maciel (Complexity'97).
