October – 2006 ^November

I will present some new results regarding discrete piercing. In the typical discrete piercing problem one is given a set of disks of arbitrary radii, where the piercing points are restricted to a given set of points in the plane and the goal is to minimize the number of chosen piercing points. This problem has applications in clustering and routing aspects of ad-hoc and sensor networks, where the set of chosen piercing points can be used as a representative set of stations. This work is joint with Matya Katz and Paz Carmi. For the discrete piercing of unit disks, only a constant approximation algorithm is known and I will talk about our new algorithm that achieves substantial improvement of the approximation ratio. This problem is equivalent to the problem of covering a set of points by unit disks. I will also present a result for the problem of conflict free coloring of unit disks in the plane, and talk about its applications to frequency assignment in wireless networks. This work is joint with David Peleg (Weizmann Inst.).

The maximal-margin approach of machine learning is the basis of several successful algorithms such as Support Vector Machines which have recently been very popular due to their good generalization ability. In this talk I will describe how this approach may be used for learning directly binary functions from a finite labeled sample $\zeta$ of cardinality $m$. I will introduce a new concept of sample width which is similar to the notion of margin for real-valued functions. Our result shows that learning binary functions by maximizing the width yields tight upper bound on the generalization error. Compared to existing bounds on maximal-margin learners (for instance, via thresholding of real-valued functions) our bound is significantly tighter and excludes the usual $O(\sqrt{\ln(m)})$ factor.

This is joint work with Prof. Martin Anthony from the department of Mathematics, London School of Economics.