The following problem is very close to one arising in factorization algorithms.

Generate random numbers in the interval [1,N] until some subset has a product which is a square. How long does this take (and how can you tell when you're done)?

Crude analogies suggest that this stopping time has a very sharp threshold. We prove upper and lower bounds that are within a factor of 4/pi and conjecture that our upper bound is asymptotically sharp. Joint work with Andrew Granville, Ernie Croot and Prasad Tetali.

We discuss a handful of structure theorems for shrinking solitons with bounded curvature. In particular we prove a priori injectivity radi.

We discuss a handful of structure theorems for shrinking solitons, in particular let (M,g,X) be a complete shrinking soliton with bounded curvature, then there exists k>0 and a smooth function f such that (M,g,X) is k-noncollapsed and (M,g,f) is a gradient shrinking soliton, generalizing results from the compact case. If M is a noncompact four dimensional shrinking soliton with nonnegative curvature then up to finite quotient it is isometric to R^4,RxS^3 or S^2xR^2. Finally we show that the singularity dilation of a Type I singularity on a Ricci Flow is a shrinking soliton.

This seminar will explore dynamical systems arising from the deformation theory of representations of fundamental groups of surfaces in Lie groups. These dynamical systems arise from the actions of mapping class groups and automorphism groups of free groups on moduli spaces of flat connections over surfaces. These moduli spaces admit invariant symplectic and Poisson structures. Their Hamiltonian flows closely relate to the mapping class group action.

After a brief overview, I will introduce representation varieties and the character ring, discussing the Poisson structure and automorphisms. In particular I will present a new proof of the ergodicity of the mapping class group action on the SU(2)-character variety. Closely related is the action of the modular group on the real Markoff cubic surface x2 + y2 + z2 - x y z = 2 + t and its relationship to Fricke coordinates on Teichmueller space.

Recently Serge Cantat analyzed the action on the complex Markoff surface, and in particular proved our conjecture on the existence of orbits accumulating both at SU(2)-characters and discrete characters. He will be visiting Princeton at the end of May and will speak Tuesday, April 1.

Other topics which may be discussed in the seminar include: (1) Teichmueller geodesic flow and Masur's ergodicity theorems for the mapping class groups on spaces of measured foliations (2) Closely related is the dependence of the (hyper-Kaehler) geometry of the complex moduli space on the Riemann surface's complex structure. In this case, the moduli spaces appear as moduli of holomorphic vector bundles (when the group is compact) and Higgs bundles in general. (3) Much of the SU(2)-theory has been extended to general compact Lie groups K. Pickrell-Xia proved ergodicity for mapping class groups of closed surfaces on K-characters, and Gelander recently established ergodicity for Out(F_n)-action on K-character varieties of a free groups F_n. Fisher has applied these latter ideas to the spectral gap conjecture. (4) Closely related work by Iwasaki et al on moduli solutions of Painleve equation, and automorphisms of affine cubic surfaces (5) Applications to the monodromy question: which surface group representations occur as monodromy representations for projective structures (real, complex, etc.) on closed surfaces? Answering a question posed by Gunning, Gallo-Kapovich-Marden pushed through a program due to Thurston to construct CP1-structures on surfaces with given monodromy. A key point in this proof is the action of the mapping class group on the representation variety. Similar questions exist for other geometric structures related to surfaces. (6) Properness criteria, energy functional on Teichmueller space for harmonic maps and special surface group representations (Wienhard, Labourie, Wentworth)

For a general (but already outdated!) survey of this subject, see: "Mapping Class Group Dynamics on Surface Group Representations," in ``Problems on Mapping Class Groups and Related Topics'', B. Farb, ed., Proceedings of Symposia in Pure Math. Proc. Symp. in Pure Math. 74, American Mathematical Society (2006), 189 -- 214. math.GT/0509114

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.

The world's sustainable water supply is heavily used (it is estimated that annually 65% of the available water resources are extracted), and with very poor efficiency (typically less than half the water taken from the environment serves the objective for which it was intended). The UNESCO World Water reports 2003/2005 identify management as one of the main issues to be addressed in order to avoid a water catastrophe. Australia is in a particularly critical situation, where management has to deal with significant climate change effects.

In this lecture we outline a sensor networks and systems engineering approach to underpin the management of an entire water catchment basin. The technology exists to construct a sensor network to monitor at a global scale the water resource and manage in closed loop the resource through the distribution infrastructure using the data derived from the sensor network. The control objective is to deliver water on demand with maximal overall efficiency. Such technology would provide the necessary data to implement a sustainable water policy in an adaptive way, where economic, environmental and social issues are properly taken into account.

We review the results from a number of substantial pilot projects in Victoria and New South Whales Australia in which, where Rubicon Systems Australia Pty. Ltd., who commercialise the technology, have realized significant gains in water efficiency in irrigation distribution. We show how this experience may lead to substantial gains in water management overall, and leads to better on farm practices, building further water savings. At present the state government of Victoria is backing this technoly with a 1 billion dollar investment to create significant water savings across the state. We discuss aspects of modeling of water dynamics followed by the control aspects enabled in the present and envisaged hardware upgrades.

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.

Science is arguably the pinnacle of human intellectual achievement, yet the scientific discovery process itself remains an art. Human intuition and experience is still the driving force of the high-level discovery process: we determine which hypotheses and theories to entertain, which experiments to conduct, how data should be interpreted, when hypotheses should be abandoned, and so on. Meanwhile machines are limited to low-level tasks such as gathering and processing data. A grand challenge for scientific discovery in the 21st century is to devise machines that directly participate in the high-level discovery process. Towards this grand challenge, we must formally characterize the limits of machine learning. Statistical learning theory is usually based on supervised training, wherein a learning algorithm is presented with a finite set of i.i.d. labeled training examples. However, modern experimental methods often generate incredibly large numbers of unlabeled data for very little expense, while the task of labeling data is often painstaking and costly. Machine learning methods must leverage the abundance of unlabeled data in scientific problem domains. Active learning (AL) and semi-supervised learing (SSL) are two well known approaches to exploit unlabeled data. In both paradigms one has access to a large pool of unlabeled examples, and only a few labeled examples are provided or selected. AL is a sequential feedback process. Unlabeled examples that are predicted to have very informative labels, based on previously gathered labeled and unlabeled data, are selected for labeling. In SSL, labeled examples are randomly provided, without regard to potential informativeness. Today, little is known about theoretical limits of AL and SSL performance. Sparsity and complexity of the underlying data-generating distributions appear to play a central role in the performance of AL and SSL, and this talk will discuss some of the known theoretical results.

This work is joint with Rui Castro, Aarti Singh and Jerry Zhu.