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

__
TR02-057
| 19th September 2002
__

Richard J. Lipton, Anastasios Viglas#### Non-uniform Depth of Polynomial Time and Space Simulations

Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton

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

Richard J. Lipton, Anastasios Viglas

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