We consider Lagrangians of classical mechanics which are weakly invariant with respect to a given symmetry group, i.e. whose left hand side of the equations of motion are invariant with respect to a given group. Obstructions to corresponding Lagrangian to be invariant with respect to this symmetry group arise because of cohomology of Lie algebra of symmetries and the configuration space which may have non-trivial interplay. We shall discuss physical consequence of this phenomenon which are usually revealed on quantum mechanical level.

Examples include non-relativistic particle in a constant magnetic field and an example of free particle on the punctured sphere which leads to Dirac monopole. A beautiful example is a case of non-relativistic free particle considered as a limit of relativistic one, when Bargmann cocycle ceases to be a boundary.}

For a squarefree integer $d$ we ask, if the negative Pell equation $x2-dy2 = -1$ is solvable over the integers. By easy considerations we see that in this case $d>0$ and that all odd prime divisors of $d$ are congruent to 1 modulo 4. Now we call a $d$ special, if it satisfies those two conditions. We are able to prove that for a positive density of special $d$ we can solve the negative Pell equation. Furthermore there is a positive density of special $d$, where the negative Pell equation cannot be solved. This result gives a big support to a conjecture of Stevenhagen who predicts those densities.

The problem is related to the behaviour of the ordinary and narrow class group of the corresponding quadratic number field. The asymptotic behaviour of those class groups is predicted by the Cohen-Lenstra heuristics. We are able to prove those conjectures for the $4$--rank.

Sometime in the nineties, M. R. Herman gave a series of lectures at Columbia on KAM theory. Yasha asked me to speak on one of the results that Herman discussed in his lectures. Here is the result:

Let f be an area preserving infinitely differentiable diffeomorphism of a closed annulus. Suppose that the restriction of f to one of the boundary components is a rotation whose rotation number satisfies a Diophantine condition. Then there exist an infinite number of rotational invariant curves in an arbitrarily small neighborhood of the given boundary component.

This result differs from earlier results in that no twist hypothesis is assumed, although then it is necessary to add the hypothesis given above about the restriction of f to the boundary component. The proof is a simple application of the formidable machinary of KAM theory. In this talk, I will state the relevant general result from KAM theory and deduce Herman's theorem from them.

In 2006 Brendan McKay asked the following on sci.math.research: We have n points in a disk centered at the centroid of the points. We successively replace the two furthest points from each other by two copies of their average. (After each move we still have n points with the same centroid. How many moves are necessary to guarantee that all points lie in the concentric disk of half the radius?

This really is the wrong question: it turns out that the situation is easier to study of we use a general Euclidean space and look at the rate of decay of the diameter in terms of number of moves. We get sharp asymptotic upper and lower bounds on the maximum diameter after certain numbers of moves. This involves interesting geometrical configurations and simple linear-programming arguments.

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.