Noam Nisan's Online Papers on Theoretical Computer Science
My more recent papers in the border of computer science, game-theory, and economics can be found
here.
Communication Complexity
On One-Round Randomized Communication Complexity
by I. Kremer, N. Nisan and D. Ron.
Data Structures and Asymmetric Communication
Complexity
by P. B. Miltersen, N. Nisan, S. Safra and A. Wigderson.
On Rank vs. Communication Complexity
by N. Nisan
and A. Wigderson.
The Communication Complexity of Threshold Gates
by N. Nisan.
Derandomization and SL
Symmetric Logspace is Closed Under Complement
by
N. Nisan and A. Ta-Shma.
Undiercted Connectivity in log^1.5(n) space
by N. Nisan E. Szemeredi and A. Wigderson.
Pseudorandomness for Network Algorithms
by
R. Impagliazzo, N. Nisan, and A. Wigderson.
Randomness is Linear in Space
by
N. Nisan and D. Zuckerman.
Hardness vs. Randomness
by N. Nisan and
A. Wigderson.
RL is contained in SC
by N. Nisan.
On Read-once vs. Multiple Access to Randomness
in Logspace
by N. Nisan.
Extracting Randomness: How and Why -- A survey
by N. Nisan.
Other
Pointer Jumping Requires Concurrent Read
by Z. Bar-Yossef and N. Nisan.
On the Complexity of Bilinear Forms
by
N. Nisan and A. Wigderson.
Products and Help Bits in Decision Trees
by
N. Nisan, S. Rudich, and M. Saks.
On The Degree of Boolean Functions as Real
Polynomials
by N. Nisan and M. Szegedy.
CREW PRAMs and Decision Trees
by N. Nisan.
Tradeoffs Between Communication Throughput and
Parallel Time
by Y. Mansour, N. Nisan, and U. Vishkin.
Lower Bounds for Arithmetic Circuits via Partial
Deriovatives
by N. Nisan and A. Wigderson.
Lower Bounds for Noncommutative Computation
by N. Nisan.
A Parallel Approximation Algorithm for Positive Linear
Programs
by M. Luby and N. Nisan.