The Complexity of Boolean Functions in Different Characteristics

• Published in: Computational complexity 2010-05, Vol.19 (2), p.235-263
• Main Authors: Gopalan, Parikshit, Shpilka, Amir, Lovett, Shachar
• Format: Article
• Language: English
• Subjects: Algorithm Analysis and Problem Complexity; Computational Mathematics and Numerical Analysis; Computer Science
• ISSN: 1016-3328; 1420-8954
• DOI: 10.1007/s00037-010-0290-4

. Every Boolean function on n variables can be expressed as a unique multivariate polynomial modulo p for every prime p . In this work, we study how the degree of a function in one characteristic affects its complexity in other characteristics. We establish the following general principle: functions with low degree modulo p must have high complexity in every other characteristic q . More precisely, we show the following results about Boolean functions f : {0, 1} n → {0, 1} which depend on all n variables, and distinct primes p ,  q : º If f has degree o (log n ) modulo p , then it must have degree Ω( n 1− o (1) ) modulo q . Thus a Boolean function has degree o (log n ) in at most one characteristic. This result is essentially tight as there exist functions that have degree log n in every characteristic. º If f has degree d = o (log n ) modulo p , then it cannot be computed correctly on more than 1 −  p − O ( d ) fraction of the hypercube by polynomials of degree modulo q . As a corollary of the above results it follows that if f has degree o (log n ) modulo p , then it requires super-polynomial size AC 0 [q] circuits. This gives a lower bound for a broad and natural class of functions.