Can we remove randomness from randomized algorithms? In this tutorial, we explore questions like this, and study basic techniques such as k-wise independence, epsilon-biased spaces, error-correcting codes, and probabilistic existence arguments.

The first session of this mini course will take place on Tuesday, January 17 from 9:30 am – 10:30 pm; the third session of this mini course will take place on Wednesday January 18 from 9:30 am – 10:30 am; the fourth session of this mini course will take place on Wednesday January 18 from 11:00 am – 12:00 pm.  

In this tutorial we introduce and study basic properties and constructions of expander graphs and randomness extractors, as well as their connections.  Topics include expanders and the second eigenvalue, random walks on expanders, seeded extractors and their different guises, and seedless extractors.

The second session of this mini course will take place on Thursday, January 19 from 2:30 pm – 10:30 am; the third session of this mini course will take place on Thursday, January 19 from 3:00 pm – 4:00 pm; the fourth session of this mini course will take place on Friday, January 20 from 9:30 am – 10:30 am.

Can we remove randomness from randomized algorithms? In this tutorial, we explore questions like this, and study basic techniques such as k-wise independence, epsilon-biased spaces, error-correcting codes, and probabilistic existence arguments.

The first session of this mini course will take place on Tuesday, January 17 from 9:30 am – 10:30 pm; the second session of this mini course will take place on Tuesday January 17 from 11:00 am – 12:00 pm; the third session of this mini course will take place on Wednesday, January 18 from 9:30 am – 10:30 am. 

This tutorial focuses on the use of discrete Fourier analysis and its higher-order generalisations as a tool for decomposing any bounded function into a structured and a pseudorandom part. Several number-theoretic applications of such decompositions will be presented, together with an account of recent developments which do not fit neatly into the traditional structure-pseudorandomness dichotomy.

The first session of this mini course will take place on Tuesday, January 17 from 4:30 pm – 5:30 pm; the third session of this mini course will take place on Thursday, January 19 from 3:00 pm – 4:00 pm; the fourth session of this mini course will take place on Friday, January 20 from 4:30 pm– 5:30 pm.

This tutorial will focus on notions of pseudorandomness in graphs, with a particular emphasis on Szemerédi's regularity method. This says that every graph can be partitioned into a bounded number of nearly equal-sized parts such that the bipartite graph between almost all pairs of parts is pseudorandom. We also discuss a technique known as dependent random choice, which goes beyond the regularity method in some applications, and develop the sparse regularity method, whose applications include sparse extensions of classical results in combinatorics, and the Green-Tao theorem on long arithmetic progressions in the primes.

The first session of this mini course will take place on Wednesday, January 18 from 1:30 pm – 2:30 pm; the second session of this mini course will take place on Wednesday, January 18 from 1:30 pm – 2:30 pm; the fourth session of this mini course will take place on Friday, January 20 from 3:00 pm – 4:00 pm.

In this tutorial we introduce and study basic properties and constructions of expander graphs and randomness extractors, as well as their connections.  Topics include expanders and the second eigenvalue, random walks on expanders, seeded extractors and their different guises, and seedless extractors.

The first session of this mini course will take place on Tuesday, January 17 from 3:00 pm – 4:00 pm; the second session of this mini course will take place on Wednesday, January 18 from 1:30 pm – 2:30 pm; the fourth session of this mini course will take place on Friday, January 20 from 9:30 am – 10:30 am. 

In this tutorial we build on the fundamentals and construct pseudorandom generators fooling interesting classes of tests.  Topics include pseudorandom generators for polynomials, pseudorandom generators from lower bounds, and pseudorandom generators for space-bounded computation.

The first session of this mini course will take place on Wednesday, January 18 from 4:30 pm – 5:30 pm; the second session of this mini course will take place on Thursday January 19 from 3:00 pm – 4:00 pm; the fourth session of this mini course will take place on Friday, January 20 from 1:30 pm – 2:30 pm.

This tutorial will focus on notions of pseudorandomness in graphs, with a particular emphasis on Szemerédi's regularity method. This says that every graph can be partitioned into a bounded number of nearly equal-sized parts such that the bipartite graph between almost all pairs of parts is pseudorandom. We also discuss a technique known as dependent random choice, which goes beyond the regularity method in some applications, and develop the sparse regularity method, whose applications include sparse extensions of classical results in combinatorics, and the Green-Tao theorem on long arithmetic progressions in the primes.

The first session of this mini course will take place on Wednesday, January 18 from 1:30 pm – 2:30 pm; the second session of this mini course will take place on Wednesday, January 18 from 1:30 pm – 2:30 pm; the third session of this mini course will take place on Thursday, January 19 from 11:00 am – 12:00 pm.