HD-Combinatorics

  • 2018 Jun 25

    HD-Combinatorics Special Day: "Quantum ergodicity and spectral theory with a discrete flavour" (organized by Elon Lindenstrauss and Shimon Brooks)

    (All day)

    Location: 

    Feldman Building, Givat Ram
    Title for the day: "Quantum ergodicity and spectral theory with a discrete flavour"

    9:00-10:50: Shimon Brooks (Bar Ilan), "Delocalization of Graph Eigenfunctions"
    14:00-15:50: Elon Lindenstrauss (HUJI), "Quantum ergodicity on graphs and beyond"

    See also the Basic Notions by Elon Lindenstrauss @ Ross 70 (16:30).

    Abstract for morning session:
  • 2018 Jun 18

    HD-Combinatorics: Special day on sparsification (by Ilan Newman and Yuri Rabinovich)

    (All day)

    Location: 

    Eilat Hall, Feldman Building, Givat Ram

    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

    2.
  • 2018 Jun 11

    HD-Combinatorics: Michael Chapman, "Conlon's construction of hypergraph expanders"

    2:00pm to 3:50pm

    Location: 

    Feldman Building, Givat Ram
    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.
  • 2018 Jun 11

    HD-Combinatorics: Aner Shalev, "Probabilistically nilpotent groups"

    10:00am to 10:50am

    Location: 

    Feldman Building, Givat Ram
    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.
  • 2018 Jun 04

    HD-Combinatorics: Shai Evra, "Gromov-Guth embedding complexity"

    2:00pm to 3:50pm

    Location: 

    Feldman Building, Givat Ram
    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.
  • 2018 Jun 04

    HD-Combinatorics: Prahladh Harsha, "Local Testability and Expansion"

    10:00am to 10:50am

    Location: 

    Feldman Building, Givat Ram
    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 an intriguing connection between local-testability and high-dimension
  • 2018 Jun 04

    HD-Combinatorics: Eli Shamir, "Almost optimal Boolean matrix multiplication[BMM] - By Multi-encoding of rows and columns"

    9:00am to 9:50am

    Location: 

    Feldman Building, Givat Ram
    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. L.Lee’s article reduced BMM to parsing substrings of a fixed string u with
  • 2018 May 21

    HD-Combinatorics Special Day on "Stability in permutations" (organized by Oren Becker)

    (All day)

    Location: 

    Room 130, IIAS, Feldman Building, Givat Ram

    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.

    14:00 - 16:00

Pages