Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Matei David:

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

TR08-014 | 26th February 2008
Matei David

Separating NOF communication complexity classes RP and NP

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

ISSN 1433-8092 | Imprint