| |
|
|
| |
| |
|
Date Reviewed |
|
| |
1 - 10 of 16
reviews
|
|
|
 |
|
|
|
|
The complexity theory companion
Hemaspaandra L., Ogihara M., Springer-Verlag New York, Inc., New York, NY, 2002. 369 pp. Type: Book
I used this book as a companion text for a graduate-level course in complexity theory last semester, and I found it quite useful. You should be warned, however, that this is not a standalone complexity textbook. Many of the basic theorems (such...
|
Sep 5 2002 |
|
|
|
|
|
|
Parallel RAMs with owned global memory and deterministic context-free language recognition
Dymond P., Ruzzo W. Journal of the ACM 47(1): 16-45, 2000. Type: Article
This paper proves a gem of a theorem--one that provides an unexpectedly close connection between a class of formal languages and one type of architecture for parallel algorithms....
|
Jun 1 2000 |
|
|
|
|
|
|
Succinct representation, leaf languages, and projection reductions
Veith H. Information and Computation 142(2): 207-236, 1998. Type: Article
Problems that are complete for complexity classes usually turn out
to be complete under very restrictive types of reducibility. Although
this has frequently been observed informally, only very recently has
there been work proving that this must...
|
Aug 1 1999 |
|
|
|
|
|
|
Space-efficient deterministic simulation of probabilistic automata
Macarie I. SIAM Journal on Computing 27(2): 448-465, 1998. Type: Article
Elegant number-theoretic techniques are used to answer a very natural, decades-old open problem regarding probabilistic finite automata. The author shows that the languages recognized by probabilistic finite automata can be recognized in...
|
Mar 1 1999 |
|
|
|
|
|
|
The isomorphism conjecture fails relative to a random oracle
Kurtz S., Mahaney S., Royer J. Journal of the ACM 42(2): 401-420, 1995. Type: Article
The central premise of the theory of NP-completeness asserts that it is no coincidence that most important problems fall into two categories: those with efficient algorithms, and those that are NP-complete. (If P = NP, then these two are but one...
|
Oct 1 1996 |
|
|
|
|
|
|
Limits to parallel computation
Greenlaw R., Hoover H., Ruzzo W., Oxford University Press, Inc., New York, NY, 1995.Type: Book
Anyone who has used Garey and Johnson’s famous reference [1] will agree that it is indispensable to any computer science library because the theory of NP-completeness is a useful tool, and the book has become this area’s standard...
|
Jul 1 1996 |
|
|
|
|
|
|
Hard promise problems and nonuniform complexity
Longpré L., Selman A. (ed) Theoretical Computer Science 115(2): 277-290, 1993. Type: Article
The term “promise problem” refers to computational problems for which a solution must be found only on certain inputs (that is, on inputs for which the “promise” holds). Promise problems arise, among other places, in the...
|
Nov 1 1994 |
|
|
|
|
|
|
Extensions to Barrington’s M-program model
Bédard F., Lemieux F., McKenzie P. (ed) Theoretical Computer Science 107(1): 31-61, 1993. Type: Article
When Barrington gave his characterization of NC1 in terms of branching programs, it became clear that circuit classes have surprisingly strong connections to algebraic structures. The M-program model (for programs over a monoid...
|
May 1 1994 |
|
|
|
|
|
|
Separating the eraser Turing machine classes Le, NLe, co-NLe and Pe
Krause M., Meinel C., Waack S. Theoretical Computer Science 86(2): 267-275, 1991. Type: Article
The authors have studied many variants of branching programs in a series of papers. Here, they study read-once branching programs, corresponding to logarithmic space-bounded Turing machines that erase each input bit after reading it (eraser...
|
Jul 1 1992 |
|
|
|
|
|
|
PP is closed under intersection
Beigel R., Reingold N., Spielman D. Theory of computing (Proceedings of the twenty-third annual ACM symposium, New Orleans, Louisiana, United States, May 5-8, 1991) 1-9, 1991. Type: Proceedings
PP (probabilistic polynomial time) was first studied in the 1970s, and basic properties of the class have been known since then (for instance, NP ⊆ PP, and PP is closed under complement). It had remained an open question whether PP is closed ...
|
Oct 1 1991 |
|
|
|
|
|
| |
|
|
| |
|
|
