Results 331 - 340 of 24664

Markov chains are important stochastic processes used ubiquitously to algorithmically solve high-dimensional sampling problems. In this minicourse, we present a powerful framework called spectral independence for upper bounding the rate of convergence to stationarity for discrete Markov chains. This framework has intimate connections with the theory of high-dimensional expanders (HDX), and since been generalized significantly via the theory of localization schemes, which also encompasses Eldan's stochastic localization. This minicourse is structured as follows:

Lecture 1: We begin by stating basic examples and applications of the theory. We then define spectral independence and prove that it implies rapid mixing.
Lecture 2: We describe several classes techniques for establishing spectral independence, using the monomer-dimer model on matchings as a running example. Time permitting, we will sketch the theory of localization schemes.

High-dimensional expansion (HDX) is a generalization of expansion in graphs to higher dimensions (i.e., hypergraphs). In recent years, HDXs have already seen a lot of amazing applications in areas such as error-correcting codes, bounding the mixing time of Markov chains and probabilistically checkable proofs (PCPs), and in explicit constructions of vertex expanders.

This mini-course aims to cover the basics of HDX and will follow this outline:
Lecture 1: We will start by defining the spectral notion of HDX, prove the trickling down theorem and define random walks on HDX.
Lectures 2 & 3: Show the Kaufman-Oppenheim construction of HDX. Time-permitting we will also cover an application to agreement testing, which is an important component of PCP constructions.

We will discuss the structure versus randomness paradigm: the idea that an arbitrary mathematical object (like a graph, function, or set) can often be decomposed into a usefully structured part and a certifiably pseudorandom part. In contrast to problems centered on the explicit construction of pseudorandom objects, here the objects are given to us, and the task is to find the pseudorandomness inside them. The first part of the lectures will be about how this is done, starting with Roth's theorem on three-term arithmetic progressions and then looking at density increment and regular decomposition arguments more generally. In the second part, we will discuss the problem of comparing two given notions of pseudorandomness and understanding how they relate, for instance by way of inverse theorems. This turns out to occupy much of the subject, in part because the notions we are forced to work with when finding pseudorandomness in arbitrary objects are relatively weak ones.

Markov chains are important stochastic processes used ubiquitously to algorithmically solve high-dimensional sampling problems. In this minicourse, we present a powerful framework called spectral independence for upper bounding the rate of convergence to stationarity for discrete Markov chains. This framework has intimate connections with the theory of high-dimensional expanders (HDX), and since been generalized significantly via the theory of localization schemes, which also encompasses Eldan's stochastic localization. This minicourse is structured as follows:

Lecture 1: We begin by stating basic examples and applications of the theory. We then define spectral independence and prove that it implies rapid mixing.
Lecture 2: We describe several classes techniques for establishing spectral independence, using the monomer-dimer model on matchings as a running example. Time permitting, we will sketch the theory of localization schemes.

We will explore the pseudorandomness toolkit: the basic objects and techniques used to construct pseudorandom generators and prove various other derandomization results. Topics will include bounded independence, small-bias spaces, randomness extractors, expander graphs, and random restrictions. We will present some of the key constructions and their applications, and see how these ingredients fit together in the main challenges in pseudorandomness. Time permitting, we will also give some ideas being more advanced results, and discuss some open problems.