# School of Mathematics

## New Tools for Graph Coloring

How to color $3$ colorable graphs with few colors is a problem of longstanding interest. The best polynomial-time algorithm uses $n^{0.2130}$ colors.

We explore the possibility that more levels of Lasserre Hierarchy can give improvements over previous algorithms. While the case of general graphs is still open, we can give analyse the Lasserre relaxation for two interesting families of graphs.

## Quantum Fingerprints that Keep Secrets

In a joint work with Tsuyoshi Ito we have constructed a fingerprinting scheme (i.e., hashing) that leaks significantly less than log(1/epsilon) bits about the preimage, where epsilon is the error ("collision") probability. It is easy to see that classically this is not achievable; our construction is quantum, and it gives a new example of (unconditional) qualitative advantage of quantum computers.

## The Bernstein Center of the Category of Smooth W(k)[GL_n(F)]-Modules

## Atiyah's Connectivity, Morse Theory and Solution Sets

## Graph Sparsification by Edge-Connectivity and Random Spanning Trees

A "sparsifier" of a graph is a weighted subgraph for which every cut has approximately the same value as the original graph, up to a factor of (1 +/- eps). Sparsifiers were first studied by Benczur and Karger (1996). They have wide-ranging applications, including fast network flow algorithms, fast linear system solvers, etc. Batson, Spielman and Srivastava (2009) showed that sparsifiers with O(n/eps^2) edges exist, and they can be computed in time poly(n,eps).

## QUESTION SESSION ON GRASSMANNIANS, POLYTOPES AND QUANTUM FIELD THEORY

## Overconvergent Igusa Tower and Overconvergent Modular Forms

**GALOIS REPRESENTATIONS AND AUTOMORPHIC FORMS SEMINAR**

Note: *(joint work with O. Brinon and A. Mokrane)*

## Automorphic Cohomology II (Carayol's work and an Application)

## Infinite Generaton of Non-Cocompact Lattices on Right-Angled Buildings

SPECIAL LECTURE