On the Fourier Spectrum of Symmetric Boolean Functions

Amir Shpilka
Technion; on leave at Microsoft Research New England
March 14, 2011

It is well-known that any Boolean function f:{-1,+1}^n \to {-1,+1} can be written uniquely as a polynomial f(x) = \sum_{S subset [n]} f_s \prod_{i in S} x_i. The collection of coefficients (f_S's) this expression are referred to (with good reason) as the Fourier spectrum of f. The Fourier spectrum has played a central role in modern computer science by converting combinatorial and algorithmic questions about f into algebraic or analytic questions about the spectrum.

Analytic Geometry Over F_1

Vladimir Berkovich
Weizmann Institute of Science
March 10, 2011

I'll talk on work in progress on algebraic and analytic geometry over the field of one element F_1. This work originates in non-Archimedean analytic geometry as a result of a search for appropriate framework for so called skeletons of analytic spaces and formal schemes, and is related to logarithmic and tropical geometry. I'll explain what analytic spaces over F_1 are, and will describe non-Archimedean and complex analytic spaces which are obtained from them.

Galois Representations Associated to Holomorphic Limits of Discrete Series

Wushi Goldring
Harvard University
March 9, 2011

We attach Galois representations to automorphic representations on unitary groups whose weight (=component at infinity) is a holomorphic limit of discrete series. The main innovation is a new construction of congruences, using the Hasse Invariant, which avoids q-expansions and so is applicable in much greater generality than previous methods. Our result is a natural generalization of the classical Deligne-Serre Theorem on weight one modular forms and work of Taylor on GSp(4).

A Randomized Rounding Approach for Symmetric TSP

Mohit Singh
McGill University
March 7, 2011

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.