^February March – 2010 ^April

The reconstruction of phylogenetic trees (evolutionary trees) is central to many problems in Biology. Accurate reconstruction methods are currently limited to a maximum of few dozens of species. Therefore, in order to construct a tree over larger sets of species, a method capable of inferring accurately trees over small, overlapping sets, and subsequently merging these sets into a tree over the complete set, is required. A "quartet tree" (a non-rooted phylogenetic tree over four species) is the smallest informative piece of information, and the extensively-studied "quartet approach" is based on combining quartet trees into a big tree. However, even this case is NP-hard, and remains so even when the set of quartet trees is compatible (agree on a certain tree). The general problem of approximating quartets is known as the "maximum quartet consistency" (MQC), even for compatible inputs, is open for nearly twenty years. Despite its importance, the only rigorous results for approximating quartets are the naive $1/3$ approximation that applies to the general case and a PTAS when the input is the complete set of all ${n choose 4}$ possible quartets. Even when it is possible to determine the correct quartet induced by every four species, the time needed to generate the complete set of all quartets may be impractical. A faster approach is to sample at random just $m << {n choose 4}$ quartets, and provide this sample as an input. We present the first approximation algorithm whose guaranteed approximation is strictly better than $1/3$ when the input is any random sample of $m$ compatible quartets. The approximation ratio we obtain is close to $1/2$, and experimental results suggest that the ratio is much larger. An important ingredient in our algorithm involves solving a weighted MaxCut in a certain graph induced by the set of input quartets. We also show an extension of the PTAS algorithm to handle dense, rather than complete, inputs. Joint work with Raphy Yuster.

Segmentation of organs and vascular structures from clinical Computed Tomography (CT) images is a crucial task in many clinical applications including diagnosis, patient specific training simulations, and intra-operative navigation. The segmentation is a challenging task due to the unclear distinction between the required structure and its surrounding tissue, artifacts in the CT images, and the presence of pathologies. We present a shape constrained graph min-cut approach for the segmentation. Discrete energy functions are defined with respect to fixed or latent shape models and optimized using the graph min-cut algorithm to obtain an accurate segmentation. Extensive evaluation of our approach for different tasks, including carotid artery bifurcation segmentation, patient specific modeling of the entire carotid arteries system for simulation, abdominal aortic aneurysms segmentation, and kidney and liver segmentation shows that our method is accurate, robust, and practical for clinical use.

Since their introduction in 1987 by Haussler and Welzl, Epsilon-nets have become one of the central concepts in computational and combinatorial geometry, and have been used in a variety of applications, such as range searching, geometric partitions, and bounds on curve-point incidences. In particular, they are strongly related to geometric set-cover and hitting-set problems. A range space (or a hypergraph) (X,R) is a pair consisting of an underlying universe X of objects, and a certain collection R of subsets of X (also called ranges). Given a range space (X,R), and a parameter 0 < Epsilon < 1, an Epsilon-net for (X,R) is a subset N of X with the property that any range that captures at least Epsilon-fraction of X contains an element of N. In other words, N is a hitting set for all the ``heavy'' ranges. Of particular interest are geometric range spaces, since then they admit small-size Epsilon-nets. Specifically, the Epsilon-Net Theorem of Haussler and Welzl asserts that in this case there exists an Epsilon-net of size O(1/Epsilon log{1/Epsilon}). One of the major questions in the theory of Epsilon-nets, open since their introduction more than 20 years ago, is whether the factor log{1/Epsilon} in the upper bound on their size is really necessary, especially in typical low-dimensional geometric situations. A central motivation then arises from the technique of Bronnimann and Goodrich to obtain, in polynomial time, improved approximation factors for the geometric hitting-set and set-cover problems: The existence of an Epsilon-net of size O((1/Epsilon)f(1/Epsilon)), for some slowly-growing function f(.), implies an approximation factor of O(f(OPT)), where OPT is the size of the smallest such set. In this talk I will survey some of the fundamental results concerning small-size Epsilon-nets. I will then discuss range spaces of points and axis-parallel boxes in two and three dimensions, and show that they admit an Epsilon-net of size O(1/Epsilon loglog{1/Epsilon}). Joint Work with Boris Aronov (Polytechnic Institute of NYU),and Micha Sharir (Tel Aviv University).

Decoding of binary LDPC codes using linear-programming (LP) decoder was proposed by J. Feldman et al. The connections between LP decoding and classical message-passing decoding were established in that paper. In our work, we extend the above approach to nonbinary coded modulations, in particular to codes over rings mapped to nonbinary modulation signals. In both cases, the principal advantage of the linear-programming framework is its mathematical tractability. We define two alternative polytope representations, which offer a smaller number of variables and constraints for many classes of nonbinary codes. These polytope representations, when used with the respective nonbinary LP problems, lead to polynomial-time decoders for a wide variety of classical nonbinary codes. Finally, we present an LP decoder for nonbinary expander codes. We show that that this decoder corrects any pattern of errors of a relative weight up to approximately $1/4 delta_A delta_B$ (where $delta_A$ and $delta_B$ are the relative minimum distances of the constituent codes). Parts of this work are joint work with Mark F. Flanagan, Eimear Byrne and Marcus Greferath.