Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton
Symmetric Polynomials over Z_m and Simultaneous Communication Protocols

Abstract: In this paper, we study the problem of representing Boolean functions as symmetric polynomials over Z_m. This problem is motivated by the surprising result of Barrington, Beigel and Rudich that over Z₆ the OR function requires degree only n^1/2. We show an equivalence between strong and weak representations by polynomials over Z_m and simultaneous communication protocols. We show that a polynomial of degree d which computes a function f on 0-1 inputs over Z_pq is equivalent to a two-player simultaneous protocol for computing f, where Player1 is given the least significant log_pd digits of the weight in base p, and Player2 is given the  least significant log_qd 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 Mod_r and Threshold functions. For strong representations, we show that there exist symmetric polynomials over Z_pq 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 (see also [1]).