^April May – 2013 ^June

A {it Euclidean (1+eps)-spanner} for a point set S in the plane is a sparse subgraph H of the complete Euclidean graph corresponding to S, which preserves all pairwise distances to within a factor of 1+eps. Euclidean spanners constitute a fundamental graph structure as they can be used to approximately solve many geometric proximity problems. In many applications of Euclidean (1+eps)-spanners, in addition to being sparse, the spanners should achieve small {it weight}, {it maximum degree} and {it hop-diameter}. Understanding the inherent tradeoffs between these parameters is the foremost open question in this area. In this talk I will survey the previous state-of-the-art results, and then present our new constructions of optimal Euclidean spanners. If time permits, I will discuss extensions to {it doubling metrics} and to {it fault-tolerant spanners}, and present some open problems in this area.

The talk will be self-contained. It is based on my FOCS'08 paper (with Dinitz and Elkin), my SODA'11 paper, my STOC'13 paper (with Elkin), and my recent manuscript http://arxiv.org/abs/1304.8135

One of the most significant recent developments in machine learning has been the resurgence of ``deep learning'', usually in the form of artificial neural networks. These systems are based on a multi-layered architecture, where the input goes through several transformations, with higher-level concepts derived from lower-level ones. Thus, these systems are considered to be particularly suitable for hard AI tasks, such as computer vision and language processing. Nevertheless, despite decades of research,a major caveat of deep learning is - and always has been - its strong reliance on heuristic methods. I will describe a new, provably efficient, algorithm for learning deep neural networks.

Joint work with Roi Livni and Ohad Shamir.

When we refer to efficient algorithms, we usually mean polynomial-time algorithms. In particular this is true for graph algorithms, which are considered efficient if they run in time polynomial in the number of vertices and edges of the graph. However, in some cases we may seek even more efficient algorithms whose running time is sublinear in the size of the input graph. Such algorithms do not even read the whole input graph, but rather sample random parts of the graph and compute approximations of various parameters of interest. In this talk I will survey various such algorithms, where the parameters I will discuss are: (1) The average degree the number of small stars (2) The weight of a minimum spanning tree (3) The size of a minimum vertex cover and a maximum matching (4) The number of edges that should be added/removed in order to obtain various properties

Clustering is one of the most widely used techniques for exploratory data analysis. Across many disciplines, people try to get intuition about their data by identifying meaningful groups among the data points. In the past five decades, many clustering algorithms have been developed and applied to a wide range of practical problems. However, in spite of the abundance of clustering research published every year, we are far from having satisfactory understanding of some of the most basic general issues in clustering. In this talk I survey some recent work on developing a general theory of clustering, aiming, among other things, to provide the clustering user with some systematic guidance concerning the matching between clustering algorithms (and their parameter settings) and specific clustering tasks. This talk is based on joint work with my past students, David, Pal, Rita Ackerman and David Loker.