Symmetric Polynomials over Z m and Simultaneous Communication Protocols
Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton · 2003
In this paper, we study the problem of representing Boolean functions as symmetric polynomials over Zm. We show an equivalence between strong and weak representations by polynomials over Zm and simultaneous communication protocols. We show that a polynomial of degree d which computes a function f on 0-1 inputs over Zpq is equivalent to a two-player simultaneous protocol for computing f, where Player1 is given the least significant logpd digits of the weight in base p, and Player2 is given the least significant logqd digits of the weight in base q. This reduces showing bounds on the degree of symmetric polynomials representing f to proving bounds on simultaneous communication protocols. We use this equivalence to show lower bounds of Ω (n) on the degree of symmetric polynomials weakly representing classes of Modr and Threshold functions. For strong representations, we show that there exist symmetric polynomials over Zpq of degree o (n) for Threshold c, where c is a constant. This result uses the fact that there are only finitely many solutions to certain exponential Diophantine equations. Conversely, a bound on the degree for Threshold c implies that certain classes of Diophantine equations have only finitely many solutions.