All reports by Author Matei David:

__
TR09-039
| 6th April 2009
__

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

__
TR08-014
| 26th February 2008
__

Matei David#### Separating NOF communication complexity classes RP and NP

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

Matei David

We provide a non-explicit separation of the number-on-forehead communication complexity classes RP and NP when the number of players is up to \delta log(n) for any \delta<1. Recent lower bounds on Set-Disjointness [LS08,CA08] provide an explicit separation between these classes when the number of players is only up to o(loglog(n)).

... more >>>