ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > AUTHORS > PERIKLIS PAPAKONSTANTINOU:
All reports by Author Periklis Papakonstantinou:

TR09-039 | 6th April 2009
Matei David, Periklis Papakonstantinou, Anastasios Sidiropoulos

Polynomial Time with Restricted Use of Randomness

We define a hierarchy of complexity classes that lie between P and RP, yielding a new way of quantifying partial progress towards the derandomization of RP. A standard approach in derandomization is to reduce the number of random bits an algorithm uses. We instead focus on a model of computation ... more >>>



ISSN 1433-8092 | Imprint