Derandomizing complexity classes

Research output: Contribution to book/anthology/report/proceedingBook chapterResearch

  • Peter Bro Miltersen
  • Sanguthevar Rajasekaran, Denmark
  • Panos Miltiades Pardalos, Denmark
  • John Henry Reif, Denmark
  • José Diaulas Palazzo Rolim, Denmark
  • Department of Computer Science

Consider a randomized algorithm, such as the Rabin primality test of Rabin, 1976. This algorithm is given as input an integer n, and as auxiliary input, a sequence of coin tosses, i.e., a vector of unbiased independent random bits. The test gives as output either "n is a prime" or "n is not a prime". For every input n, the probability that the output is a false statement is bounded form above by a small constant say ¼.

The test runs in time polynomial in the size of the binary representation of n. In particular, the number r of random bits needed is polynomial in log n.

Original languageEnglish
Title of host publicationHandbook on Randomized Computing : Combinatorial Optimization, Vol. 9
Number of pages92
VolumeII, chapter 19
PublisherKluwer Academic Publishers (Springer)
Publication year2001
Editionchapter 19
Pages843-935
ISBN (print)978-0-7923-6959-9
ISBN (Electronic)0-7923-6957-9
Publication statusPublished - 2001

See relations at Aarhus University Citationformats

ID: 282850