David Eppstein - Publications

Theory of Computing Systems (formerly Mathematical Systems Theory)

• Simultaneous strong separations of probabilistic and unambiguous complexity classes.
  D. Eppstein, L. Hemachandra, J. Tisdall, and B. Yener.
  Int. Conf. Computing and Information, Toronto, North-Holland, 1989, pp. 65-70.
  Tech. Rep. 335, Dept. Comp. Sci., U. Rochester, 1990.
  Mathematical Systems Theory 25(1):23-36, 1992.

  Structural complexity theory. Constructs oracles in which BPP (a probabilistic complexity class) and UP (the class of problems with a unique "witness") contain languages that in a very strong sense are not contained in the other class. The conference version used the title "Probabilistic and unambiguous computation are incomparable".

  (BibTeX: ICCI, MST -- Citations: ICCI, MST -- CiteSeer)

Journals -- Publications -- David Eppstein -- Theory Group -- Inf. & Comp. Sci. -- UC Irvine

Semi-automatically filtered from a common source file.