The "PCP theorem" says that problems in NP are hard in a robust or stable way.
I will give a brief intro to PCPs (and explain the acronym) and then try to outline a proof of the PCP theorem based on "agreement expansion" which is a form of high dimensional expansion.
My aim is to show how high dimensional expansion is inherently present in PCP type questions.
I will introduce the notion of (PCP)-agreement expansion which is an important building block in PCPs constructions.
I will then show that a high dimensional expanders imply PCP-agreement expanders.
based on Joint work with Irit Dinur
Speaker : Tatiana Nagnibeda (University of Geneva)
Abstract: The definition of a Ramanujan graph extends naturally to infinite graphs: an infinite graph is Ramanujan if its spectral radius is not larger than (and hence equal to) the spectral radius of its universal covering tree. As with infinite families of finite graphs, it is interesting and non-trivial to understand, how much Ramanujan graphs resemble trees. I will discuss some results in this direction obtained in a joint work with Vadim Kaimanovich, by investigating ergodic properties of boundary actions of free groups.
Speaker: Steven Damelin (The American Mathematical Society)
A classical problem in geometry goes as follows. Suppose we are given two sets of $D$ dimensional data, that is, sets of points in $R^D$. The data sets are indexed
by the same set, and we know that pairwise distances between corresponding points are equal in the two data sets. In other words, the sets are isometric. Can this correspondence be extended
to an isometry of the ambient Euclidean space?
In this form the question is not terribly interesting; the answer has long known
In the recent theory of high dimensional expanders, the following open problem was raised by Gromov: Are there bounded degree high dimensional expanders?
For the definition of high dimensional expanders, we shall follow the pioneers of this field, and consider the notions of coboundary expanders (Linial-Meshulam) and topological expanders (Gromov).
In a recent work, building on an earlier work of Kaufman-Kazhdan-Lubotzky in dimension 2, we were able to prove the existence of bounded degree expanders according to Gromov, in every dimension.
There are several prominent computational problems for which
simple iterative methods are widely preferred in practice despite
an absence of runtime or performance analysis (or "worse", actual
evidence that more sophisticated methods have superior
performance according to the usual criteria). These situations
raise interesting challenges for the analysis of algorithms.
We are concerned in this work with one such simple method: a
classical iterative algorithm for balancing matrices via scaling
transformations. This algorithm, which goes back to Osborne and
Israel Institute for Advanced Studies (Feldman building, Givat Ram), Eilat Hall
This is a survey talk about one of the main parts of what we call high-dimensional combinatorics. We start by equating a permutation with a permutation matrix. Namely, an nxn array of zeros and ones where every line (=row or column) contains exactly one 1. In general, a d-dimensional permutation is an array [n]x[n]x....x[n] (d+1 factors) of zeros and ones in which every line (now there are d+1 types of lines) contains exactly one 1. Many questions suggest themselves, some of which we have already solved, but many others are still wide opne. Here are a few examples:
Markoff triples are integer solutions to Markoff equation $x^2+y^2+z^2=3xyz$ which arose in Markoff's spectacular and fundamental work (1879) on diophantine approximation and has been henceforth ubiquitous in a tremendous variety of different fields in mathematics and beyond.
Abstract: I will give an introduction to the cohomology of universal covers of finite complexes. These groups are (for infinite covers) either trivial or infinite dimensional, but they have renormalized real valued Betti numbers. Their study is philosophically related to the topic of our year, and they have wonderful applications in geometry, group theory, topology etc and I hope to explain some of this.
Abstract: While algebraic topology is now well established as an applicable branch of mathematics, its emergence in neuroscience is surprisingly recent. In this talk I will present a summary of an ongoing joint project with mathematician and neuroscientists. I will start with some basic facts on neuroscience and the digital reconstruction of a rat’s neocortex by the Blue Brain Project in EPFL.