Strongly Refuting Random CSPs below the spectral threshold

Prasad Raghavendra
University of California, Berkeley
February 6, 2017
Random constraint satisfaction problems (CSPs) are known to exhibit threshold phenomena: given a uniformly random instance of a CSP with $n$ variables and $m$ clauses, there is a value of $m = \Omega(n)$ beyond which the CSP will be unsatisfiable with high probability. Strong refutation is the problem of certifying that no variable assignment satisfies more than a constant fraction of clauses; this is the natural algorithmic problem in the unsatisfiable regime (when $m/n=\omega(1)$).

Local systems and the Hofer-Zehnder capacity

Alexandru Oancea
Université Pierre et Marie Curie; Member, School of Mathematics
February 6, 2017
The Hofer-Zehnder capacity of a symplectic manifold is one of the early symplectic invariants: it is a non-negative real number, possibly infinite. Finiteness of this capacity has strong consequences for Hamiltonian dynamics, and it is an old question to decide whether it holds for small compact neighborhoods of closed Lagrangians. I will explain a positive answer to this question for a class of manifolds whose free loop spaces admit nontrivial local systems.

Discrete harmonic analysis and applications to ergodic theory

Mariusz Mirek
University of Bonn; Member, School of Mathematics
February 8, 2017
Given $d, k\in\mathbb N$, let $P_j$ be an integer-valued polynomial of $k$ variables for every $1\le j \le d$. Suppose that $(X, \mathcal{B}, \mu)$ is a $\sigma$-finite measure space with a family of invertible commuting and measure preserving transformations $T_1, T_2,\ldots,T_{d}$ on $X$. For every $N\in\mathbb N$ and $x \in X$ we define the ergodic Radon averaging operators by setting \[ A_N f(x) = \frac{1}{N^{k}}\sum_{m \in [1, N]^k\cap\mathbb Z^k} f\big(T_1^{ P_1(m)}\circ T_2^{ P_2(m)} \circ \ldots \circ T_{d}^{ P_{d}(m)} x\big).

Post Concert Discussion

Gamelan Galak Tika and David Lang
February 10, 2017
Edward T. Cone Concert Series: February 10, 2017

A concert of new and traditional Balinese music will be performed by Boston’s large percussion orchestra, Gamelan Galak Tika. An ensemble comprised of gongs, metallophones and hand drums, cymbals, vocals, bamboo flutes and spiked fiddles, Gamelan Galak Tika is approximately thirty members strong, drawing membership from the Massachusetts Institute of Technology students, staff and community. A concert talk with David Lang and the artists will follow the Friday, February 10 performance.

Nearest neighbor search for general symmetric norms via embeddings into product spaces

Ilya Razenshteyn
Massachusetts Institute of Technology
February 13, 2017
I will show a new efficient approximate nearest neighbor search (ANN) algorithm over an arbitrary high-dimensional *symmetric* norm. Traditionally, the ANN problem in high dimensions has been studied over the $\ell_1$ and $\ell_2$ distances with a few exceptions. Thus, the new result can be seen as a (modest) step towards a "unified theory" of similarity search.

Mirror symmetry via Berkovich geometry I: overview

Tony Yue Yu
Visitor, School of Mathematics
February 13, 2017
Berkovich geometry is an enhancement of classical rigid analytic geometry. Mirror symmetry is a conjectural duality between Calabi-Yau manifolds. I will explain (1) what is mirror symmetry, (2) what are Berkovich spaces, (3) how Berkovich spaces appear naturally in the study of mirror symmetry, and (4) how we obtain a better understanding of several aspects of mirror symmetry via this viewpoint. This member seminar serves also as an overview of my minicourses in the same week.