|
ERC Starting
Grant: Randomness and Computation Professor, Department of Computer Science. University of Haifa. |
Randomized algorithms and
Protocols play an important role in many areas of Computer Science. The “theory
of derandomization” is an active sub-field of
Complexity Theory that focuses on studying randomness as a computational
resource. It is concerned with two fundamental questions on randomness and
computation:
Necessity of randomness: Which randomized algorithms
can be simulated by efficient deterministic ones?
Availability of randomness: How can computers obtain
random bits?
We are interested explicitly
constructing efficient pseudorandom generators against various
complexity classes, or alternatively in proving limitations on such
constructions. We would like to explicitly construct randomness extractors
(and related objects) that come close to meeting the known existential bounds.
We plan to explore applications of such objects in various areas of Theoretical
Computer Science, Combinatorics and Cryptography.