^February March – 2005 ^April

Understanding the origin and evolution of extant and extinct species is a fundamental scientific quest. Today, phylogenetic trees are widely used as the accepted evolutionary model, and are mostly based upon molecular sequences (amino acid or DNA) data. The space of candidate trees grows exponentially with the number of species, implying that even on modern computers, an exhaustive search over all trees is infeasible (except for few species, no more than approximately 20).

Two reconstruction criteria most frequently used are maximum parsimony (MP), and maximum likelihood (ML). But are they solvable in a computationally efficient manner? Maximum parsimony (MP) was proved intractable almost 20 years ago (1986). The analogue question for maximum likelihood (ML) remained unsolved.

This created a strange situation, because most practitioners believe that ML is computationally harder than MP. Namely computer programs running on the same sets of sequences tend to take much longer to solve ML than MP. Yet ML remained ``unclassified'', leaving the existence of an efficient ML algorithm a possibility.

We resolve this question, and show that ML on phylogenetic trees is indeed computationally intractable (NP hard). Therefore, the reason why no ``magic bullet'', or efficient ML algorithm using clever algorithmic techniques was found, is because no such ``magic bullet'' exists.

This is joint work with Tamir Tuller.

Convolving an image with a sequence of filter kernels is an important part of many image processing and computer vision applications. It often serves in the feature extraction process for classification tasks, pattern detection and recognition systems. This fundamental task is usually of high complexity for real-time systems, especially when an extensive set of large filter kernels are involved.

In this talk I'll introduce a family of filter kernels - the Gray-Code Kernels (GCK) and demonstrate their use in image analysis. Filtering an image with a sequence of Gray-Code Kernels is highly efficient and requires only 2 operations per pixel for each filter kernel, independent of the size or dimension of the kernel.

A joint work with Gil Ben-Artzi (BIU) and Hagit Hel-Or (Haifa U)

In recent years the notion of learning real-valued functions by maximizing the sample-margin has been shown to improve the learning error rates. This has been the primary cause behind the success of the latest generation of machine learning algorithms such as Support Vector Machines. As in other forms of statistical model selection the generalization accuracy is improved as a result of having a reduced effective hypothesis-class complexity (epsilon-entropy).

When learning binary-valued hypotheses the complexity that governs the error convergence rate is the Vapnik and Chervonenkis growth function. In this talk I describe my recent results on the reduced effective complexity of classes of binary-valued functions which have a large sample margin. It turns out that such classes exhibit a strong combinatorial threshold growth with respect to the margin value.

My result can be viewed as an extension of the well known Sauer's Lemma.

Bio:

B.S. and M.S., Electrical Engineering, Brooklyn Polytechnic Institute of New York

Ph.D. Moore School of Electrical Engineering, University of Pennsylvania

Post-Doctoral, Electrical Engineering, Technion

Lecturer at Computer Science Department, University College London

Currently Lecturer at Industrial Engineering, Ben Gurion University, Israel

Weighted threshold functions with positive weights are a natural generalization of unweighted threshold functions. These functions are clearly monotone.

However, the naive way of computing it is adding the weights of the satisfied variables and checking if the sum is greater than the threshold; this algorithm is inherently non-monotone since addition is a non-monotone function. In this work we by-pass this addition step and construct a polynomial size logarithmic depth monotone circuit for every weighted threshold function, Our monotone circuits are applicable for the cryptographic tool of secret sharing schemes.

Using general results for compiling monotone circuits (Yao, 1989) and monotone formulae (Benaloh and Leichter, 1990) into secret sharing schemes, we get secret sharing schemes for every weighted threshold access structure.

Variations in lighting can have a significant impact on the appearance of an object. In this talk I will provide a novel characterization of this variability for the case of Lambertian objects. In particular, I will use harmonic analysis to show that the set of all reflectance functions (the mapping from surface normals to intensities) produced by Lambertian objects under distant lighting lies close to a 9D linear subspace.

This implies, in general, that the set of images of a convex Lambertian object obtained under a wide variety of lighting conditions can be approximated accurately by a low-dimensional linear subspace, explaining prior empirical results. In addition, a simple analytic characterization of this linear space is derived. These results are obtained by representing lighting using spherical harmonics and describing the effects of Lambertian materials as the analog of a convolution.

We use these results to develop novel algorithms for object recognition and shape reconstruction that work under complex lighting that include unknown combination of point and extended light sources.