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.