All reports by Author Anastasios Sidiropoulos:

__
TR09-039
| 6th April 2009
__

Matei David, Periklis Papakonstantinou, Anastasios Sidiropoulos#### Polynomial Time with Restricted Use of Randomness

Matei David, Periklis Papakonstantinou, Anastasios Sidiropoulos

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 >>>