School of Mathematics

Hamiltonian Evolution Equations -- Where They Come From, What They Are Good For

Juerg Frohlich
ETH Zurich; Member, School of Mathematics
January 22, 2013

Several examples of Hamiltonian evolution equations for systems with infinitely many degrees of freedom are presented. It is sketched how these equations can be derived from some underlying quantum dynamics ("mean-field limit") and what kind of physics they describe.

Sparsity Lower Bounds for Dimensionality Reducing Maps

Jelani Nelson
Member, School of Mathematics
January 22, 2013

We give near-tight lower bounds for the sparsity required in several dimensionality reducing linear maps. In particular, we show:
(1) The sparsity achieved by [Kane-Nelson, SODA 2012] in the sparse Johnson-Lindenstrauss lemma is optimal up to a log(1/eps) factor.
(2) RIP_2 matrices preserving k-space vectors in R^n with the optimal number of rows must be dense as long as k < n / polylog(n).

On Bilinear Complexity

Pavel Hrubes
University of Washington
January 14, 2013

For a set of polynomials F, we define their bilinear complexity as the smallest k so that F lies in an ideal generated by k bilinear polynomials. The main open problem is to estimate the bilinear complexity of the single polynomial $\sum_{i,j}x_i^2 y_j^2$. This question is related to the classical sum-of-squares problem as well as to problems in arithmetic circuit complexity. We will focus on related sets of polynomials and prove some lower and upper bounds on their bilinear complexity.

The SOS (aka Lassere/Positivestellensatz/Sum-of-Squares) System Series

Raghu Meka (1) and Avi Wigderson (2)
DIMACS (1) and Professor, School of Mathematics, IAS (2)
December 18, 2012

We will give an overview of this system, which has been at the center of recent algorithmic and proof complexity developments. We will give the definitions of the system (as a proof system for polynomial inequalities, and as an SDP-based algorithm), and basic upper and lower bounds for it. In particular we'll explain the recent SOS-proof of the hypercontractive inequality for the noisy hypercube of Barak et al., as well as the degree lower bounds for proving Tseitin and Knapsack tautologies of Grigoriev.

Local Global Principles for Galois Cohomology

Julia Hartmann
RWTH Aachen University; Member, School of Mathematics, IAS
December 13, 2012

We consider Galois cohomology groups over function fields F of curves that are defined over a complete discretely valued field.
Motivated by work of Kato and others for n=3, we show that local-global principles hold for
$H^n(F, Z/mZ(n-1))$ for all n>1.
In the case n=1, a local-global principle need not hold. Instead, we will see that the obstruction to a local-global principle for $H^1(F,G)$, a Tate-Shafarevich set, can be described explicitly for many (not necessarily abelian) linear algebraic groups G.