Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Richard J. Lipton:

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

TR02-057 | 19th September 2002
Richard J. Lipton, Anastasios Viglas

Non-uniform Depth of Polynomial Time and Space Simulations

We discuss some connections between polynomial time and non-uniform, small depth circuits. A connection is shown with simulating deterministic time in small space. The well known result of Hopcroft, Paul and Valiant showing that space is more powerful than time can be improved, by making an assumption about the connection ... more >>>

ISSN 1433-8092 | Imprint