We show a (3/2-\epsilon)-approximation algorithm for the graphical traveling salesman problem where the goal is to find a shortest tour in an unweighted graph G. This is a special case of the metric traveling salesman problem when the underlying metric is defined by shortest path distances in G. The result improves on the 3/2-approximation algorithm due to Christofides for the case of graphical TSP.
School of Mathematics
I will introduce two basic problems in random geometry. A self-avoiding walk is a sequence of steps in a d-dimensional lattice with no self-intersections. If branching is allowed, it is called a branched polymer. Using supersymmetry, one can map these problems to more tractable ones in statistical mechanics. In many cases this allows for the determination of exponents governing the relationship between the diameter and the number of steps.
Let G be a connected reductive group over Q such that G(R) has discrete series representations. I will report on some statistical results on the Satake parameters (w.r.t. Sato-Tate distributions) and low-lying zeros of L-functions for families of automorphic representations of G(A). This is a joint work with Nicolas Templier.
I will survey the development of modern infinite cardinal arithmetic, focusing mainly on S. Shelah's algebraic pcf theory, which was developed in the 1990s to provide upper bounds in infinite cardinal arithmetic and turned out to have applications in other fields.
This modern phase of the theory is marked by absolute theorems and rigid asymptotic structure, in contrast to the era following P. Cohen's discovery of forcing in 1963, during which infinite cardinal arithmetic was almost entirely composed of independence results.
GALOIS REPRESENTATIONS AND AUTOMORPHIC FORMS SEMINAR
We study the local testabilty of sparse linear codes. This problem is intimately connected to the problem of tolerant linearity testing of Boolean functions under nonuniform distributions. We give linearity tests for several natural and interesting classes of distributions, and use this to show local testability for the corresponding codes.