Colorings of graphs form a prominent topic in graph theory. Several relaxations of usual colorings have been introduced and intensively studied. In this talk, we focus on circular colorings. A proper circular k-coloring, for a real k>=1, is a coloring by real numbers from the interval [0,k) such that the difference modulo k of the colors c_1 and c_2 assigned to adjacent vertices is at least one, i.e., 1 <= |c_1-c_2| <= k-1 . It is easy to observe that the chromatic number of a graph is always the ceiling of its circular chromatic number.

A classical theorem of Vizing states that the edges of every graph G with maximum degree D can be colored by at most D+1 colors so that no two incident edges have the same color, i.e., the chromatic index of G is at most D+1. We show that for every e>0 there exists g such that the circular chromatic index of a graph G with maximum degree D whose girth is at least g does not exceed D+e. Note that the index must be at least D because the line graph of such graph G contains a clique of order D.

Our research is motivated by a conjecture of Jaeger and Swart 1979 (that turned out to be false) that high girth cubic graphs have chromatic index three. Our results imply that the conjecture is true when relaxed to circular colorings: the circular chromatic index of high girth cubic graphs is close to three.

One of the ingredients of our proof are results on systems of independent representatives and hypergraph matchability of by Aharoni, Haxell, Meshulam and others, which we also briefly survey during the talk. Based on joint work with Tomas Kaiser, Riste Skrekovski and Xuding Zhu.

Beginning with the seminal work of Goemans and Williamson on Max-Cut, semidefinite programming (SDP) has firmly established itself as an important ingredient in the toolkit for designing approximation algorithms for NP-hard problems. Algorithms designed using this approach produce configurations of vectors in high dimensions which are then converted into actual solutions.

In recent years, we have made several strides in understanding the power as well as the limitations of of such SDP approaches. New insights into the geometry of these vector configurations have led to breakthroughs for several basic optimization problems. At the same time, a sequence of recent results seems to suggest the tantalizing possibility that, for several optimization problems including Max-Cut, SDP approaches may indeed be the best possible. In this talk, I will present a glimpse of some of this recent excitement around SDP-based methods and explain some of the new insights we have developed about the strengths and weaknesses of this sophisticated tool.

The statistical properties of the Lorentz gas with periodically positioned obstacles are well understood. The random case, obtained after each of the obstacles undergoes a small i.i.d. displacement, stands as a challenge. The latter can be studied in terms of a random sequence of hyperbolic symplectic (billiard) maps, which however is not i.i.d. due to recollisions. In fact, even the i.i.d. sequence (no recollisions) is poorly understood.

Motivated by the above, we study an i.i.d. sequence of toral automorphisms in two dimensions. We will argue that the time-N average of any observable has Gaussian fluctuations of order \sqrt{N} for almost every sequence of maps, and that the variance is independent of the sequence. Joint work with Arvind Ayyer (Rutgers) and Carlangelo Liverani (Rome 1).

In 2001, artist David Hockney and scientist Charles Falco stunned the art world with a controversial theory that, if correct, would profoundly alter our view of the development of image making. They claimed that as early as 1420, Renaissance artists employed optical devices such as concave mirrors to project images onto their canvases, which they then traced or painted over. In this way, the theory attempts to explain the newfound heightened naturalism or "opticality" of painters such as Jan van Eyck, Robert Campin, Hans Holbein the Younger, and many others.

This talk will describe the application of rigorous computer image analysis to masterpieces adduced as evidence for this theory. It covers basic geometrical optics of image projection, the analysis of perspective, curved surface reflections, shadows, lighting and color. While there remain some loose ends, such analysis of the paintings, infra-red reflectograms, modern reenactments, internal consistency of the theory, and alternate explanations allows us to judge with high confidence the plausibility of this bold theory. You may never see Renaissance paintings the same way again (http://www.diatrope.com/stork/FAQs.html).

A branched polymer is a finite, connected set of non-overlapping unit balls in space. The powerful "dimension reduction" theorem of Brydges and Imbrie permits computation of the volume of the space of branched polymers of size N in dimensions 2 or 3. We will show how these and some related computations can be done using elementary calculus and combinatorics. New results include methods for random generation, asymptotic diameter in 3-space, and a combinatorial proof of the notorious "random flight" problem of Rayleigh and Spitzer. Joint work with Rick Kenyon (Brown).

In this talk we'll explore the emerging potential of computer vision to transform the way we think about the interconnectedness of digital imagery and the Web, and how these relate to our physical environment. We'll begin with an introduction to the foundations of "3D computer vision", a bag of tricks which has been developing steadily for three decades, combining classical photogrammetry with machine vision. We'll then dive specifically into Photosynth, based on a combination of the Photo Tourism project (a collaboration between Microsoft Research and the University of Washington) and Seadragon, a multiresolution networked platform allowing one to play with arbitrarily many arbitrary large visual objects using only constant-time and constant-bandwidth operations. The aim of Photosynth is to allow meaningful 3D navigation within real-world environments reconstructed entirely from the photos. Interesting social dimensions are added to this application when one considers that the source photos can be mined from the existing Web, aggregated from user communities, and actively contributed to and interconnected. We'll end with some preliminary findings about the latent graph structure of Internet photography, and a glimpse of where we're heading next.

It is hard to think of a process that is more boring than boarding an airplane. In the hope of relieving, or at least shortening, some of the pain, airlines have devised various boarding strategies such as back-to-front, window to aisle, boarding by zones or even unassigned seating. In the talk we will try to overturn the negative image that airplane boarding has and will try to portray it as a very exciting process which is modeled via space-time (a.k.a Lorentzian) geometry with a touch of random matrix theory. Using the model we will try to figure out what are the better strategies. If time permits, we will use insights from the airplane borading process to suggest an interpretation for Einstein's law of motion in which god plays the ultimate dice game. The talk is entirely self contained. Partly based on joint works with D. Berend, L. Sapir, S. Skiena, M. Elkin and V. Khachaturov.