Randomization is an important tool in the design of algorithms,
and the ability of randomization to provide enhanced power is a
major research topic in complexity theory. Noam Nisan continues the
investigation into the power of randomization and the relationships
between randomized and deterministic complexity classes by pursuing
the idea of emulating randomness, or pseudorandom
generation.Pseudorandom generators reduce the number of random bits
required by randomized algorithms, enable the construction of
certain cryptographic protocols, and shed light on the difficulty
of simulating randomized algorithms by deterministic ones. The
research described here deals with two methods of constructing
pseudorandom generators from hard problems and demonstrates some
surprising connections between pseudorandom generators and
seemingly unrelated topics such as multiparty communication
complexity and random oracles.Nisan first establishes a precise
connection between computational complexity and pseudorandom number
generation, revealing that efficient deterministic simulation of
randomized algorithms is possible under much weaker assumptions
than was previously known, and bringing to light new consequences
concerning the power of random oracles. Using a remarkable argument
based on multiparty communication complexity, Nisan then constructs
a generator that is good against all tests computable in
logarithmic space. A consequence of this result is a new
construction of universal traversal sequences.Noam Nisan is
Lecturer in the Department of Computer Science at Hebrew University
in Jerusalem. He received his doctoral degree from the University
of California, Berkeley.Contents: Introduction. Hardness vs.
Randomness. Pseudorandom Generators for Logspace and Multiparty
Protocols.
General
Is the information for this product incomplete, wrong or inappropriate?
Let us know about it.
Does this product have an incorrect or missing image?
Send us a new image.
Is this product missing categories?
Add more categories.
Review This Product
No reviews yet - be the first to create one!