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

**On reset sequence length**.

D. Eppstein.

Tech. Rep. CUCS-440-89, Computer Science Dept., Columbia University, 1989.**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 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".

Years – Publications – David Eppstein – Theory Group – Inf. & Comp. Sci. – UC Irvine

Semi-automatically filtered from a common source file.