The FOCS and Positano versions of this paper merged my results on a dynamic program used for RNA secondary structure prediction, with Raffaele's on sequence comparison. The Bethesda talk and the TR version both used the longer title "Speeding up dynamic programming with application to the computation of RNA structure", and included only the RNA result, which used a mild convexity assumption on certain costs to save two orders of magnitude in total time. This work incited a boom in computational biology within the theory community that is still going strong. But the RNA results were quickly improved by a log factor [Aggarwal et al. at the same FOCS] and never made it into a journal paper.
(Bibtex: Positano, FOCS -- Citations -- Citations of "Efficient algorithms..." -- MIT hypertext bibliography -- CiteSeer)
Gives an algorithm for finding the minimum number of mutations needed to transform one input string into another, in a general model in which substrings may be inserted or deleted at a cost depending nonlinearly on the substring length. The time bound depends on the number of times the second derivative of the cost function changes sign.
(BibTeX -- Citations -- ACM DL)
Automata theory. A reset sequence for a DFA is an input such that, no matter which state the DFA starts in, it ends up after the input in a known state. These have been used by Natarajan and Goldberg for certain robot motion planning problems (in fact the conference version of this paper used the title "Reset sequences for finite automata with application to design of parts orienters"), and also in coding theory where they arise in the design of self-synchronizing codes. This paper considers DFAs in which the transition functions respect a given cyclic ordering of the states, and shows that their shortest reset sequences can be found quickly. It also considers parallel algorithms for the problem. There remains open a gap between n2 and n3 in the maximum length of reset sequences for general automata.
(BibTeX -- Citations -- CiteSeer -- ACM DL (ICALP) -- ACM DL (SJC))
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".
(BibTeX: ICCI, MST -- Citations: ICCI, MST -- CiteSeer)
The complement of a minimum spanning tree is a maximum spanning tree in the dual graph. By applying this fact we can use a modified form of Sleator and Tarjan's dynamic tree data structure to update the MST in logarithmic time per update.
(BibTeX -- Citations -- CiteSeer -- ACM DL)
Given a collection of points in convex position, the sharpest angle determined by any triple can be found as a corner of a triangle in the farthest point Delaunay triangulation.
(BibTeX -- Citations -- CiteSeer -- ACM DL)
By removing edges not involved in some solution, and contracting edges involved in all solutions, we reduce the problem to one in a graph with O(k) edges and vertices. This simplification step transforms any time bound involving m or n to one involving min(m, k) or min(n, k) respectively. This paper also introduces the geometric version of the k smallest spanning trees problem (the graph version was long known) which it solves using order (k+1) Voronoi diagrams.
(BibTeX -- Citations -- ACM DL (SWAT) -- ACM DL (BIT))
Considers sequence alignment and RNA structure problems in which the solution is constructed by piecing together some initial set of fragments (e.g. short sequences that match exactly). The method is to consider a planar point set formed by the fragment positions in the two input sequences, and use plane sweep to construct a cellular decomposition of the plane similar to the rectilinear Voronoi diagram.
An investigation of 3d visibility problems in which the viewing position moves along a straight flight path, with various assumptions on the complexity of the viewed scene.
Uses quadtrees to construct triangulations with extra Steiner vertices added to the original input. Triangulates planar point sets and polygons, with all angles bounded away from zero, using a number of triangles within a constant of optimal. Triangulates planar point sets with all angles non-obtuse, using linearly many triangles. Triangulates higher dimensional point sets with no small solid angles and a number of simplices within a constant of optimal. Augments any higher dimensional point set so the Delaunay triangulation has linear complexity.
(BibTeX -- Citations -- Preliminary copy of journal version -- MIT hypertext bibliography -- CiteSeer -- ACM DL (JCSS))
Years -- Publications -- David Eppstein -- Theory Group -- Inf. & Comp. Sci. -- UC Irvine
Semi-automatically filtered from a common source file.