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.