Khot's Unique Games Conjecture (UGC) is one of the most central open problems in computational complexity theory. UGC asserts that for a certain constraint satisfaction problem, it is NP-hard to decide whether there is a labeling that satisfies almost all the constraints or, for every labeling, the fraction of the constraints satisfied is very small. Since its origin, the UGC has been applied with remarkable success to prove tight hardness of approximation results for several important NP-hard problems such as Vertex Cover, MAXCUT.

In this talk, we will present a purely spectral algorithm for Unique Games (UG). Our algorithm, given a 1-\epsilon satisfiable instance of UG, recovers a good labelling (that satisfies more than 99% of the constraints). The running time of the algorithm depends exponentially on the dimension of a certain eigenspace of the underlying constraint graph. As a significant application, our algorithm is able to distinguish (in quasi-polynomial time) highly satisfiable instances of UG on underlying graphs that have been proved to be hard for a natural semidefinite programming relaxation for Unique Games (integrality gap instances), giving evidence that spectral techniques might be a more powerful tool for approximation algorithms than SDPs.

We fix F a local non archmedean field of characteristic zero, G the points over F of an algebraic reductive group defined over F and s a rational involution of G defined over F. We note H the group of fixed points of G under the action of s and X(G,s) the connected component on the neutral element of the set of complex characters of G antiinvariant under the action of s. Let P be a s-parabolic subgroup of G, id est the intersection M of P with s(P) is a s-stable Levi subgroup, we construct from a irreducible, smooth representation r of M, a rational family of distributions above the algebraic variety X(G,s), which are H-invariant linear forms on tne smooth induced representation ind(P,G; r ). Our main trick is the use of homology of groups.

The scattering of electromagnetic waves by homogeneous dielectric media is characterized by a strongly singular integral equation, corresponding to the identity operator perturbed by a non-compact Green operator. Using the Kondrachov-Rellich compact imbedding and the Calderon-Zygmund theory, we prove that the Green operator is polynomially compact if the dielectric boundary is a compact smooth manifold. We then show that the electromagnetic scattering problem admits a robust solution for all non-accretive media ($\mathrm{Im}\chi\leq0$) satisfying certain geometric and topological constraints, except for the critical point $\chi=-2$, where unbounded electromagnetic enhancement may occur. Combining the polynomial compactness of the Green operator with the Arendt-Batty-Lyubich-Vu theorem in semigroup theory, we devise a non-perturbative approach to the solution of electromagnetic scattering problem, as an improvement of the Born approximation.

This work was part of the speaker's PhD thesis project completed at Harvard University.

o an abelian variety over a number field one can associate an abelian variety to each prime ideal p of good reduction by reducing the variety modulo p. The geometry of these reductions need not resemble the geometry of the original abelian variety; for example, there are absolutely simple abelian varieties of dimension 2 whose reductions modulo p always split as a product of elliptic curves. In this talk, we shall describe progress on a conjecture of Murty and Patankar which predicts exactly which absolutely simple abelian varieties have reductions modulo p that are also absolutely simple.