David Eppstein - Publications
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.
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.
Tech. Rep. CUCS-440-89, Computer Science Dept., Columbia University, 1989.
- Parallel algorithmic techniques for combinatorial computation.
D. Eppstein and
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.
ACM DL (ARCS) –
ACM DL (ICALP))
- Simultaneous strong separations of
probabilistic and unambiguous complexity classes.
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
The conference version used the title
"Probabilistic and unambiguous computation are incomparable".
David Eppstein –
Theory Group –
Inf. & Comp. Sci. –
from a common source file.