David Eppstein – Publications

Publications with Lane Hemachandra

• 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 \(\mathsf{BPP}\) (a probabilistic complexity class) and \(\mathsf{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".