Author name cluster
Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.
MFCS Conference 2006 Invited Paper
Abstract We will talk about three ideas from theoretical computer science that have actually been successfully used in real world applications in bioinformatics. From these ideas, we hope to inspire more theoretical research that are applicable to real world bioinformatics problems.
SODA Conference 2006 Conference Paper
SODA Conference 2003 Conference Paper
SODA Conference 2000 Conference Paper
SODA Conference 2000 Conference Paper
SODA Conference 2000 Conference Paper
STOC Conference 2000 Conference Paper
SODA Conference 1999 Conference Paper
STOC Conference 1999 Conference Paper
SODA Conference 1999 Conference Paper
SODA Conference 1998 Conference Paper
FOCS Conference 1998 Conference Paper
Inferring evolutionary trees has long been a challenging problem both for biologists and computer scientists. In recent years research has concentrated on the quartet method paradigm for inferring evolutionary trees. Quartet methods proceed by first inferring the evolutionary history for every set of four species (resulting in a set Q of inferred quarter topologies) and then recombining these inferred quarter topologies to form an evolutionary tree. This paper presents two results on the quartet method paradigm. The first is a polynomial time approximation scheme (PTAS) for recombining the inferred quartet topologies optimally. This is an important result since, to date, there have been no polynomial time algorithms with performance guarantees for quartet methods. In fact, this is the first known PTAS for inferring evolutionary trees under any paradigm. To achieve this result the natural denseness of the set Q is exploited. The second result is a new technique, called quartet cleaning, that detects and corrects errors in the set Q with performance guarantees. This result has particular significance since quartet methods are usually very sensitive to errors in the data. It is shown how quartet cleaning can dramatically increase the accuracy of quartet methods.
SODA Conference 1997 Conference Paper
STOC Conference 1993 Conference Paper
STOC Conference 1993 Conference Paper
STOC Conference 1991 Conference Paper
FOCS Conference 1990 Conference Paper
Mathematical frameworks suitable for massive automated DNA sequencing and for analyzing DNA sequencing algorithms are studied under plausible assumptions. The DNA sequencing problem is modeled as learning a superstring from its randomly drawn substrings. Under certain restrictions, this may be viewed as learning a superstring in L. G. Valiant's (1984) learning model, and in this case the author gives an efficient algorithm for learning a superstring and a quantitative bound on how many samples suffice. A major obstacle to the approach turns out to be a quite well-known open question on how to approximate the shortest common superstring of a set of strings. The author presents the first provably good algorithm that approximates the shortest superstring of length n by a superstring of length O(n log n). >
FOCS Conference 1989 Conference Paper
It is pointed out that in L. G. Valiant's learning model (Commun. ACM, vol. 27, p. 1134-42, 1984) many concepts turn out to be too hard to learn, whereas in practice, almost nothing we care to learn appears to be not learnable. To model the intuitive notion of learning more closely, it is assumed that learning happens under an arbitrary distribution, rather than under an arbitrary simple distribution, as assumed by Valiant. A distribution is called simple if it is dominated by a semicomputable distribution. A general theory of learning under simple distributions is developed. In particular, it is shown that one can learn under all simple distributions if one can learn under one fixed simple distribution, called the universal distribution. Interesting learning algorithms and several quite general new learnable classes are presented. It is shown that for essentially all algorithms, if the inputs are distributed according to the universal distribution, then the average-case complexity is of the same order of magnitude as the worst-case complexity. >
STOC Conference 1988 Conference Paper
FOCS Conference 1987 Conference Paper
Time-stamps are numerical labels which enable a system to keep track of temporal precedence relation among its data elements. Traditionally time-stamps are used as unbounded numbers and inevitable overflows cause a loss of this precedence relation. In this paper we develop a complete theory of bounded time-stamps. Time-stamp systems are defined and the complexity of their implementation is fully analyzed. This theory gives a very general tool for converting timestamp based protocols to bounded protocols. The generality of this theory is demonstrated by novel, conceptually simple, protocols for a multiuser atomic registers, as well as by proving for the first time a non-trivial lower bound for such a register.
STOC Conference 1987 Conference Paper
FOCS Conference 1986 Conference Paper
We resolve the following long-standing conjecture of Harrison and Ibarra in 1968 [HI, p. 462]: There are languages accepted by (k+1)-head 1-way deterministic pushdown automata ((k+1)-DPDA) but not by k-head 1-way pushdown automata (k-PDA), for every k. (Partial solutions for this conjecture can be found in [M1, M2, C].) On the assumption that their conjecture holds, [HI] also derived many important consequences. Now all those consequences become theorems. For example, the class of languages accepted by k-PDA's is not closed under ∩ and complementation. Several other interesting consequences also follow: CFL ⊆∪kDPDA(k) and FA(2)⊆∪kDPDA(k), where DPDA (k)={L|L is accepted by a k-DPDA} and FA(2)={L|L is accepted by a 2-head FA). Our new proof itself is also interesting in the sense that the k+l versus k heads problems was solved by diagonalization methods [I2, M2, M3, M4, S] for stronger machines (2-way, etc). and by traditional counting arguments [S2, IK, YR, M1] for weaker machines (k-FA, k-head counter machine, etc).
STOC Conference 1986 Conference Paper
FOCS Conference 1985 Conference Paper
Based on two graph separator theorems, we present two unexpected upper bounds and resolve several open problems for on-line computations. (1) 1 tape nondeterministic machines can simulate 2 pushdown stores in time O(n1. 5√logn) (true for both on-line and off-line machines). Together with the Ω(n1. 5/√logn) lower bound, this solves the open problem 1 in [DGPR] for the 1 tape vs. 2 pushdown case. It also disproves the commonly conjectured Ω(n2) lower bound. (2) The languages defined by Maass and Freivalds, aimed to obtain optimal lower bound for 1 tape nondeterministic machines, can be accepted in O(n2loglogn√logn) and O(n1. 5√logn) time by a 1 tape TM, respectively. (3) 3 pushdown stores are better than 2 pushdown stores. This answers a rather old open problem by Book and Greibach, and Duris and Galil. An Ω(n4/3/loge n) lower bound is also obtained. (4) 1 tape can nondeterministically simulate 1 queue in O(n1. 5/√logn) time. This disproves the conjectured Ω(n2) lower bound. Also 1 queue can simulate 2 pushdowns in time O(n1. 5√logn).