Ph.D Thesis of R. Uehara

Title

Probabilistic Algorithms and Complexity Classes

University

Department of Computer Science and Information Mathematics, The University of Electro-Communications

Date

March 1998

PostScript file

gzipped PostScript file of all of them (gzipped, 276480bytes) is splitted as follows;

• Title, Abstract, Acknowledgement, and Contents (gzipped PostScript file, 31905bytes).
• Chapter 1: Introduction (gzipped PostScript file, 37978bytes).
• Chapter 2: Preliminaries (gzipped PostScript file, 56038bytes).
• Chapter 3: Efficient Simulations by a Biased Coin (gzipped PostScript file, 31344bytes).
• Chapter 4: Complexity Classes Characterized by Semi-Random Sources (gzipped PostScript file, 56758bytes).
• Chapter 5: Optimal Attribute-Efficient Learning of Disjunction, Parity, and Threshold Functions (gzipped PostScript file, 60302bytes).
• Chapter 6: Fast NC and RNC Algorithms for Finding a Maximal Set of Paths (gzipped PostScript file, 105460bytes).
• Chapter 7: NP-completeness of the problems on a simple structure (gzipped PostScript file, 47487bytes).
• Index, Bibliography, and List of publications (gzipped PostScript file, 38586bytes).

Note

Original dissertation contains Japanese abstract, which is omitted from this presented version.

Last modified: Wed Nov 6 11:20:16 EST 2002 by R.Uehara (uehara@jaist.ac.jp)