Results 381 - 390 of 24716
Louis Golowich (UC Berkeley) shows how to perform classical and quantum computation in the presence of an almost-linear number of adversarial errors in every time step, and the utility of such schemes toward PCP constructions, both classical and quantum.
Shankar Balasubramanian (Caltech) presents research constructing a 3D Pauli stabilizer Hamiltonian whose ground-state space can encode a qubit for exponential time when coupled to a bath at nonzero temperature.
Hsin-Yuan (Robert) Huang asks whether there is a path forward for working with LLMs in a way that does not undermine the sacred human act of doing research.
Fan Chen (MIT) presents an algorithmic framework for high-accuracy sampling using unbiased stochastic queries.
Greetings from Berkeley! This has been a dizzying summer, one in which we witnessed an inflection point in AI’s capability to autonomously solve major open problems in math and theoretical CS. Like many of you, I feel a mix of amazement at this rapid acceleration and uncertainty about what it means for the future of TCS research as a profession. Scientifically, though, there is much to celebrate: the field has advanced by leaps and bounds this summer, whether done the old-school way, AI-assisted, or AI-driven.
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.