期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2003
卷号：2003
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We study the problem of representing symmetric Boolean functions as symmetric polynomials over Z_m. We show an equivalence between such representations and simultaneous communication protocols. Computing a function with a polynomial of degree d modulo m=pq is equivalent to a two player protocol where one player is given the first log_p(d) digits of the weight in base p and the other is given the first log_q(d) digits of the weight in base q. The players can decide on a protocol beforehand but they cannot communicate directly with each other. If m has t distinct prime factors, the protocols involve t players. This reduces the problem of proving bounds on the degree of symmetric polynomials to proving bounds on simultaneous communication protocols. We use this equivalence to prove linear lower bounds on the degree of symmetric polynomials weakly representing Mod_r over Z_m for sufficiently large r and for the degree of symmetric polynomials weakly representing some threshold functions. The best previously known lower bound for symmetric polynomials representing any function over Z_m was n^(1/t). We show an equivalence between the existence of finitely many solutions to certain Diophantine equations and the existence of strong protocols for constant threshold functions. We use this to show a degree bound of o(n) for symmetric polynomials strongly representing constant threshold.We also study classes of randomized protocols which are equivalent to choosing randomly from a sample space of symmetric polynomials. Our results give simplifications of some previously known results and provide a simple explanation for why some functions have lower degree over composites than over primes.
