http://www.lifelong-navigation.eu/images/ERC_logo.png

ERC Starting Grant: Randomness and Computation

 

Ronen Shaltiel

 

Professor, Department of Computer Science. University of Haifa.

Scientific Background and Goals

This is a theoretical research project aimed at promoting our understanding of the interplay between randomness and computation in Complexity Theory.

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.

Open positions

Postdocs

We are offering postdoc positions for applicants with a strong track record in Theoretical Computer Science (and preferably in Complexity Theory and Derandomization).

Starting date and period of postdoc is flexible.

The application should contain:

o   A CV with a list of relevant publications in Theory of Computer Science (preferably in Complexity Theory).

o   Two letters of recommendation.

o   A short letter describing the applicant's background and relevance to the specific research project (optional).

Only relevant applications will be considered.

Contact: ronen@cs.haifa.ac.il   

Funding

      This project is funded by the European Research Council under the European Union's Seventh Framework Programme (FP7/2007-2013)/ERC grant agreement no. 279559.