The High Dimensional Combinatorics seminars take pace on Mondays at the IIAS, Feldman Building, Givat Ram.
2018 Jan 15

Michael Farber: "Robot motion planning and equivariant Bredon cohomology"

9:00am to 11:00am


IIAS, Feldman Building, Givat Ram

Abstract: The motion planning problem of robotics leads to an interesting invariant of topological spaces, TC(X), depending on the homotopy type of X = the configuration space of the system. TC(X) is an integer reflecting the complexity of motion planning algorithms for all systems (robots) having X as their configuration space. Methods of algebraic topology allow to compute or to estimate TC(X) in many examples of practical interest. In the case when the space X is aspherical the number TC(X) depends only on the fundamental group of X.

2018 Mar 05

HD-Combinatorics Special Day: Samplers in Computer Science (organized by Amnon Ta-Shma)

(All day)


Room 130, IIAS, Feldman Building, Givat Ram

All talks will be given by Amnon Ta-Shma.
10:00-11:00 - The sampling problem and some equivalent formulations

11:30-12:30 - A basic "combinatorial" construction

14:00-14:45 - Algebraic constructions of randomness condensers

15:15-16:00 - Structured sampling


1. 10:00-11:00 - The sampling problem and some equivalent formulations. 
We will first define Samplers, and the parameters that
one usually tries to optimize: accuracy, confidence, query complexity
2018 Jan 29

HD-Combinatorics Special day: Pseudo-randomness (organised by Uli Wagner)

10:00am to 5:00pm


IIAS, Feldman Building, Givat Ram
10:00-11:00     Anna Gundert Uli Wagner - Quasirandomness and expansion for graphs

11:30-12:30     Anna Gundert Uli Wagner - Quasirandomness for hypergraphs

13:45- 14:45    Uli Wagner - Szemeredi's regularity lemma for dense graphs

15:00-16:00     Tamar Ziegler - Gowers uniformity norms

16:30-17:30     Anna Gundert Uli Wagner - Hypergraph regularity 
2018 Jan 08

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

2:00pm to 4:00pm


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.