Special day on sparsification Speakers: Ilan Newman and Yuri Rabinovich.
Part I: 10:30 - 12:30 Part II: 14:00 - 15:50
Abstract for the day: Time permitting, we plan to discuss the following topics (in this order):
1. * Additive Sparsification and VC dimension * Multiplicative Sparsification * Examples: cut weights, cut-dimension of L_1 metrics, general metrics, and their high-dimensional analogues
In the past decades There has been considerable interest in the probability that two random elements of (finite or certain infinite)
groups commute.
I will describe new works (by myself and by others) on probabilistically nilpotent groups, namely groups in which the probability that [x_1,...,x_k]=1 is positive/bounded away from zero.
It turns out that, under some natural conditions,
these are exactly the groups which have a finite/bounded index
subgroup which is nilpotent of class < k.
The proofs have some combinatorial flavor.
Let X be the spherical building associated to the group G=GL(n,F) ,
where F is a finite field. We will survey some results on the homology of X with constant and twisted coefficients, and on the corresponding expansion properties.
In this talk we recall Conlon's random construction of sparse 2-dim simplicial complexes arising from Cayley graphs of F_2^t . We check what expansion properties this construction has (and doesn't have): Mixing of random walks, Spectral gap of the 1-skeleton, Spectral gap of the links, Co-systolic expansion and the geometric overlap property.
Computing R=P.Q ,the product of two mXm Boolean matrices [BMM] is an ingredient
of many combinatorial algorithms.
Many efforts were made to speed it beyond the standard m^3 steps, without using
the algebraic multiplication.
To divide the computation task, encoding of the rows and column indices were
used (1.1) j by (j1,j2) k by (k1,k2)
e.g. using integer p j2=j mod p ,j1=ceiling of j/p.
Clearly, the product of the ranges of the digits= m1.m2 - is approximately m.
In this talk we shall review a paper by Gromov and Guth, in which they introduced several ways to measure the geometric complexity of an embedding of simplicial complexes to Euclidean spaces.
One such measurement is strongly related to the notion of high dimensional expanders introduced by Gromov, and in fact, it is based on a paper of Kolmogorov and Barzadin from 1967, in which the notion of an expander graph appeared implicitly.
We shall show one application of bounded degree high dimensional expanders, and present many more open questions arising from the above mentioned paper.
Locally testable codes are error-correcting codes that admit
super-efficient checking procedures. In the first part of the talk, we will
see why expander based codes are NOT locally testable. This is in contrast
to typical "good" error correcting properties which follow from expansion.
We will then see that despite this disconnect between expansion and
testability, all known construction of locally testable codes follow from
the high-dimensional expansion property of a related complex leaving open
Both talks will be given by Oren Becker. 9:00 - 10:50 Title: Proving stability via hyperfiniteness, graph limits and invariant random subgroups
Abstract: We will discuss stability in permutations, mostly in the context of amenable groups. We will characterize stable groups among amenable groups in terms of their invariant random subgroups. Then, we will introduce graph limits and hyperfinite graphings (and some theorems about them), and show how the aforementioned characterization of stability follows.
We will give a short review of various topics discussed in the first semester and last Monday and then we'll pick the fruits: namely, we will show how to get groups which are no approximated.
A random linear (binary) code is a dimension lamba*n (0
Much of the interesting information about a code C is captured by its weight vector. Namely, this is the vector (w_0,w_1,...,w_n) where w_i counts the elements of C with Hamming weight i. In this work we study the weight vector of a random linear code. Our main result is computing the moments of the random variable w_(gamma*n), where 0 < gamma < 1 is a fixed constant and n goes to infinity.
This is a joint work with Nati Linial.
A k-dimensional permutation is a (k+1)-dimensional array of zeros
and ones, with exactly a single one in every axis parallel line. We consider the
“number on the forehead" communication complexity of a k-dimensional permutation
and ask how small and how large it can be. We give some initial answers to these questions.
We prove a very weak lower bound that holds for every permutation, and mention a surprising
upper bound. We motivate these questions by describing several closely related problems:
