1989
Note that a paper may appear in listings for multiple years due to multiple publication (of tech. report, conference, and journal versions).- Efficient algorithms for sequence analysis with concave and convex gap costs.
D. Eppstein.
Ph.D. thesis, Columbia University, 1989.Includes results from "Speeding up dynamic programming", "Sequence comparison with mixed convex and concave costs", and "Sparse dynamic programming".
- Parallel algorithmic techniques for combinatorial computation.
D. Eppstein and Z. Galil.
Ann. Rev. Comput. Sci. 3: 233–283, 1988.
Invited talk by Z. Galil, 16th Int. Coll. Automata, Languages and Programming, Stresa, Italy, 1989.
Springer, Lecture Notes in Comp. Sci. 372, 1989, pp. 304–318.This survey on parallel algorithms emphasized the use of basic subroutines such as prefix sums, Euler tours, ear decomposition, and matrix multiplication for solving more complicated graph problems.
- 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".