文章基本信息

标题：On the Complexity of Boolean Functions in Different Characteristics
本地全文：下载
作者：Parikshit Gopalan ; Shachar Lovett ; Amir Shpilka 等
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2009
卷号：2009
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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 : \begin{itemize} \item 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 only one characteristic. This result is essentially tight as there exist functions that have degree log n in every characteristic. \item If f has degree d = o ( log n ) modulo p , it cannot be computed correctly on more than 1 − p − O ( d ) fraction of the hypercube by polynomials of degree n 2 1 − \eps modulo q . \end{itemize} 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.
关键词：Boolean Functions , polynomials