Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > SIMULTANEOUS PROTOCOLS:
Reports tagged with Simultaneous Protocols:
TR03-047 | 22nd June 2003
Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton

Symmetric Polynomials over Z_m and Simultaneous Communication Protocols

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 ... more >>>


TR04-022 | 31st March 2004
Nayantara Bhatnagar, Parikshit Gopalan

The Degree of Threshold Mod 6 and Diophantine Equations

We continue the study of the degree of polynomials representing threshold functions modulo 6 initiated by Barrington, Beigel and Rudich. We use the framework established by the authors relating representations by symmetric polynomials to simultaneous protocols. We show that proving bounds on the degree of Threshold functions is equivalent to ... more >>>




ISSN 1433-8092 | Imprint