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.

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

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.

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

Noncommutative algebraic varieties, their properties and geometric realizations

Dmitry Orlov
Steklov Mathematical Institute, Russian Academy of Sciences; Member, School of Mathematics
February 3, 2017
We are will discuss a notion of noncommutative and derived algebraic variety. This approach comes from a generalization of derived categories of (quasi)coherent sheaves on usual algebraic varieties and their enhancements. We are going to talk about different properties of noncommutative varieties such as regularity, smoothness and properness. A new operation of gluing of noncommutative varieties will be introduced.

Relative quantum product and open WDVV equations

Sara Tukachinsky
University of Montreal
February 2, 2017
The standard WDVV equations are PDEs in the potential function that generates Gromov-Witten invariants. These equations imply relations on the invariants, and sometimes allow computations thereof, as demonstrated by Kontsevich-Manin (1994). We prove analogous equations for open Gromov-Witten invariants that we defined in a previous work. For ($\mathbb CP^n$ ,$\mathbb RP^n$), the resulting relations allow the computation of all invariants. The formulation of the open WDVV requires a lift of the big quantum product to relative cohomology.