2017
Nov
23

# Eventss

2017
Dec
11

2017
Nov
06

# High Dimensional Expanders and Group Stability, Alex Lubotkzy

9:00am to 11:00am

## Location:

Room 130

In the first talk we gave a brief outline of the contents of the course. In the rest of the semester we will get deeper into some topics. In the coming lecture ( and the next one) we will discuss Kazhdan property T and its connections with expanders and with first cohomology groups. No prior knowledge will be assumed.

2017
Nov
06

2018
Jan
08

# HD-Combinatorics: Amnon Ta-Shma, "Bias samplers and reducing overlap in random walks over graphs"

2:00pm to 4:00pm

Abstract:

The expander Chernoff bound states that random walks over expanders are good samplers, at least for a certain range of parameters. In this talk we will be interested in “Parity Samplers” that have the property that for any test set, about half of the sample sets see the test set an *even* number of times, and we will check whether random walks over expanders are good parity samplers. We will see that:

1. Random walks over expanders fare quite well with the challenge, but,

2. A sparse Random complex does much better.

The expander Chernoff bound states that random walks over expanders are good samplers, at least for a certain range of parameters. In this talk we will be interested in “Parity Samplers” that have the property that for any test set, about half of the sample sets see the test set an *even* number of times, and we will check whether random walks over expanders are good parity samplers. We will see that:

1. Random walks over expanders fare quite well with the challenge, but,

2. A sparse Random complex does much better.

2017
Oct
23

2017
Nov
27

# HD-Combinatorics: Irit Dinur, "PCPs and high dimensional expansion"

2:00pm to 4:00pm

## Location:

Room 130, Feldman Building (IIAS), Givat Ram

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

2017
Dec
04

# HD-Combinatorics: Tali Kaufman, "High dimensional expanders imply PCP-agreement expansion"

2:00pm to 4:00pm

## Location:

Room 130, Feldman Building (IIAS), Givat Ram

Abstract:

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

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

2017
Sep
05

# IIAS Seminar: Tatiana Nagnibeda - Infinite Ramanujan graphs and completely dissipative actions

4:00pm to 5:00pm

## Location:

Math room 209

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.

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.

2017
Dec
18

# HD-Combinatorics: Steven Damelin, "Approximate and exact alignment of data, extensions and interpolation in R^D--parts"

2:00pm to 4:00pm

## Location:

Sprinzak Building, Room 28

Speaker: Steven Damelin (The American Mathematical Society)

Abstract:

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

Abstract:

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

2017
Nov
20

2017
Nov
27

2017
Dec
25

# HD-Combinatorics: Shai Evra, "Bounded degree high dimensional expanders"

2:00pm to 4:00pm

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.

2017
Nov
20

# Leonard Schulman, "Analysis of a Classical Matrix Preconditioning Algorithm"

2:00pm to 3:00pm

## Location:

Room 130, Feldman Building, Givat Ram

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

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

2017
Oct
23

# HD-Combinatorics: Nati Linial, "High-dimensional permutations"

2:00pm to 4:00pm

## Location:

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: