Search
w/in this Reviewer
for Reviewers
All Reviews
Allender, Eric
Rutgers University
Piscataway, New Jersey
Options:
All Media Types
Journals
Proceedings
Div Books
Whole Books
Other
Date Reviewed
Title
Author
Publisher
Published Date
Descending
Ascending
Date Reviewed
1

10
of
16
reviews
The complexity theory companion
Hemaspaandra L., Ogihara M., SpringerVerlag New York, Inc., New York, NY, 2002. 369 pp. Type: Book (9783540674191)
I used this book as a companion text for a graduatelevel 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 a...
Sep 5 2002
Parallel RAMs with owned global memory and deterministic contextfree language recognition
Dymond P., Ruzzo W. Journal of the ACM 47(1): 1645, 2000. Type: Article
This paper proves a gem of a theoremone 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): 207236, 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 so...
Aug 1 1999
Spaceefficient deterministic simulation of probabilistic automata
Macarie I. SIAM Journal on Computing 27(2): 448465, 1998. Type: Article
Elegant numbertheoretic techniques are used to answer a very natural, decadesold open problem regarding probabilistic finite automata. The author shows that the languages recognized by probabilistic finite automata can be recognized in determini...
Mar 1 1999
The isomorphism conjecture fails relative to a random oracle
Kurtz S., Mahaney S., Royer J. Journal of the ACM 42(2): 401420, 1995. Type: Article
The central premise of the theory of NPcompleteness asserts that it is no coincidence that most important problems fall into two categories: those with efficient algorithms, and those that are NPcomplete. (If P = NP, then these two are but one c...
Oct 1 1996
Limits to parallel computation
Greenlaw R., Hoover H., Ruzzo W., Oxford University Press, Inc., New York, NY, 1995.Type: Book (9780195085914)
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 NPcompleteness is a useful tool, and the book has become this area’s standard manu...
Jul 1 1996
Hard promise problems and nonuniform complexity
Longpré L., Selman A. (ed) Theoretical Computer Science 115(2): 277290, 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 st...
Nov 1 1994
Extensions to Barrington’s Mprogram model
Bédard F., Lemieux F., McKenzie P. (ed) Theoretical Computer Science 107(1): 3161, 1993. Type: Article
When Barrington gave his characterization of NC
^{1}
in terms of branching programs, it became clear that circuit classes have surprisingly strong connections to algebraic structures. The Mprogram model (for programs over a monoid
M
...
May 1 1994
Separating the eraser Turing machine classes
L
_{e}
,
NL
_{e}
,
coNL
_{e}
and
P
_{e}
Krause M., Meinel C., Waack S. Theoretical Computer Science 86(2): 267275, 1991. Type: Article
The authors have studied many variants of branching programs in a series of papers. Here, they study readonce branching programs, corresponding to logarithmic spacebounded Turing machines that erase each input bit after reading it (eraser machin...
Jul 1 1992
PP is closed under intersection
Beigel R., Reingold N., Spielman D. Theory of computing (Proceedings of the twentythird annual ACM symposium, New Orleans, Louisiana, United States, May 58, 1991) 19, 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
Display
5
10
15
25
50
100
per column
Reproduction in whole or in part without permission is prohibited. Copyright © 20002018 ThinkLoud, Inc.
Terms of Use

Privacy Policy