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

Co-authors – Publications – David Eppstein – Theory Group – Inf. & Comp. Sci. – UC Irvine

Semi-automatically filtered from a common source file.