Georgia Institute of Technology College of Sciences

The closest vector problem (CVP) on lattices (i.e. given an n dimensional lattice L with basis B and target point t, find a closest lattice point in L to t) is fundamental NP-hard problem with applications in coding, cryptography & optimization. In this talk, we will consider the preprocessing version of CVP (CVPP), an important variant of CVP, where we allow arbitrary time to preprocess the lattice before answering CVP queries. In breakthrough work, Micciancio & Voulgaris (STOC 2010) gave the first single exponential time algorithm for CVP under the l_2 norm based on Voronoi cell computations. More precisely, after a preprocessing step on L requiring tilde{O}(2^{2n}) time, during which they compute the Voronoi cell of L (the set of points closer to the origin than to any other point in L), they show that additional CVP queries on L (i.e. CVPP) can be solved in tilde{O}(2^{2n}) time. For our main result, we show that given the Voronoi cell V of L as preprocessing, CVP on any target t can be solved in expected tilde{O}(2^n) time. As our main technical contribution, we give a new randomized procedure that starting from any close enough lattice point to the target t, follows a path in the Voronoi graph of L (i.e. x,y in L are adjacent if x+V and y+V share a facet) to the closest lattice vector to t of expected polynomial size. In contrast, the path used by MV algorithm is only known to have length bounded by tilde{O}(2^n). Furthermore, for points x,y in L, we show that the distance between x and y in the Voronoi graph is within a factor n of ||x-y||_V (norm induced by the Voronoi cell), which is best possible. For our analysis, we rely on tools from high dimensional convex geometry. No background in convex geometry or lattices will be assumed. Time permitting, I will describe related results & open questions about paths on more general lattice Cayley graphs. Joint work with Nicolas Bonifas (Ecole Polytechnique).

Suppose that F is a field with p elements, and let G be the finite-index congruence subgroup of SL(n, F[t]) obtained as the kernel of the homomorphism that reduces entries in SL(n, F[t]) modulo the ideal (t). Then H^(n-1)(G;F) is infinitely generated. I'll explain the ideas behind the proof of the above result, which is a special case of a result that applies to any noncocompact arithmetic group defined over function fields.

Given a closed surface S_g of genus g, a mapping class f is said to be pseudo-Anosov if it preserves a pair of transverse measured foliations such that one is expanding and the other one is contracting by a number $\lambda$. The number $\lambda$ is called a stretch factor (or dilatation) of f. Thurston showed that a stretch factor is an algebraic integer with degree bounded above by 6g-6. However, little is known about which degrees occur. Using train tracks on surfaces, we explicitly construct pseudo-Anosov maps on S_g with orientable foliations whose stretch factor $\lambda$ has algebraic degree 2g. Moreover, the stretch factor $\lambda$ is a special algebraic number, called Salem number. Using this result, we show that there is a pseudo-Anosov map whose stretch factor has algebraic degree d, for each positive even integer d such that d is less than or equal to g. Our examples also give a new approach to a conjecture of Penner.

We present the proof of the Shannon-McMillan-Breiman Theorem. This is part of a reading seminar geared towards understanding of Smooth Ergodic Theory. (The study of dynamical systems using at the same time tools from measure theory and from differential geometry)It should be accesible to graduate students and the presentation is informal. The first goal will be a proof of the Oseledets multiplicative ergodic theorem for random matrices. Then, we will try to cover the Pesin entropy formula, invariant manifolds, etc.