Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Browse by topic Browse by titles Authors Reviewers Browse by issue Browse Help
Allender, Eric
Rutgers University
Piscataway, New Jersey
  Follow this Reviewer
Date Reviewed  
- 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 (9783540674191)

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

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

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 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): 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 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 NP-completeness 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): 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 st...

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

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

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  
Display per column
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright © 2000-2018 ThinkLoud, Inc.
Terms of Use
| Privacy Policy