Abstract.
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 Ω(n1−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 \(n^{\frac{1}{2}-\in}\) 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 AC0[q] circuits. This gives a lower bound for a broad and natural class of functions.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Corresponding author
Additional information
Manuscript received 17 September 2009
Rights and permissions
About this article
Cite this article
Gopalan, P., Shpilka, A. & Lovett, S. The Complexity of Boolean Functions in Different Characteristics. comput. complex. 19, 235–263 (2010). https://doi.org/10.1007/s00037-010-0290-4
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00037-010-0290-4