School of Mathematics

A PRG for Gaussian Polynomial Threshold Functions

Daniel Kane
Harvard University
March 15, 2011

We define a polynomial threshold function to be a function of the form f(x) = sgn(p(x)) for p a polynomial. We discuss some recent techniques for dealing with polynomial threshold functions, particular when evaluated on random Gaussians. We show how to use these ideas to produce a pseudo random generator for degree-d polynomial threshold functions of Gaussians with seed length poly(2^d,log(n),epsilon^{-1}) .

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).

Self-Avoiding Walk and Branched Polymers

John Imbrie
University of Virginia; Member, School of Mathematics
March 7, 2011

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.

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.