Seminars Sorted by Series

High dimensional expanders are an exciting generalization of expander graphs to hypergraphs and other set systems.  Loosely speaking, high dimensional expanders are sparse approximation to the complete hypergraph.  In this talk, we’ll give a gentle...

Explicit constructions of "random-like" objects play an important role in complexity theory and pseudorandomness. For many important objects such as prime numbers and rigid matrices, it remains elusive to find fast deterministic algorithms for...

Consider a function on $R^n$ that can be written as a sum of functions $f = f_1$ + $f_2$ + ... + $f_m$, for $m >> n$.

The question of approximating f by a reweighted sum using only a small number of summands has many applications in CS theory...

A weighted pseudorandom generator (WPRG) is a generalization of a pseudorandom generator (PRG) in which, roughly speaking, probabilities are replaced with weights that are permitted to be positive or negative. In this talk, we present new explicit...

Coboundary expansion and cosystolic expansion are generalizations of edge expansion to hypergraphs. In this talk, we will first explain how the generalizations work. Next we will motivate the study of such hypergraphs by looking at their...

The online discrepancy minimization problem asks, given unit vectors v_1, ..., v_t arriving one at a time, for online signs x_1 ..., x_t4 in {-1, 1} so that the signed sum x_1 v_1 + ... + x_t v_t has small coordinates in absolute value. 

In the first...

Consider a scenario where we are learning a predictor, whose predictions will be evaluated by their expected loss. What if we do not know the precise loss at the time of learning, beyond some generic properties (like convexity)? What if the same...

I will prove that the block length of every linear 3-query Locally Correctable Code (LCC) with a constant distance over any small field grows exponentially with k, the dimension of the code. This result gives the first separation between LCCs and...

Consider the process where a signal propagates downward an infinite rooted tree. On every edge some independent noise is applied to the signal. The reconstruction problem asks whether it is possible to reconstruct the original signal given...

I will discuss recent progress on approximating the metric traveling salesperson problem, focusing on a line of work beginning in 2011 that studies the behavior of the max entropy algorithm. This algorithm is a randomized variant of the beautiful...

Given two univariate polynomials, how does one compute their greatest common divisor (GCD)? This problem can be solved in polynomial time using the Euclidean algorithm, and even in quasi-linear time using a fast variant of the Euclidean algorithm...

Edit distance is a similarity measure for strings that counts how many characters have to be deleted, inserted or substituted in one string to get another one. It has many applications from comparing DNA sequences to text processing. We are still in...

A finite set $F$ in $\mathbb{Z}^d$ is a translational tile of  $\mathbb{Z}^d$ if one can cover  $\mathbb{Z}^d$ by translated copies of $F$ without any overlaps, i.e., there exists a translational tiling of $\mathbb{Z}^d$ by $F$.  Suppose that $F$ is...

Endow the edges of the $Z^D$ lattice with positive weights, sampled independently from a suitable distribution (e.g., uniformly distributed on [a,b] for some b>a>0). We wish to study the geometric properties of the resulting network, focusing on the...

Agreement testing (aka direct product testing), checks if consistent local information reveals global structure. Beyond its theoretical connections to probabilistic checkable proofs (PCPs), constructing agreement testers is a fundamental...

The method of hypergraph containers is a widely-applicable technique in probabilistic combinatorics. The method enables one to gain control over the independent sets of many `interesting' hypergraphs by exploiting the fact that these sets exhibit a...

In a $3$-$\mathsf{XOR}$ game $\mathcal{G}$, the verifier samples a challenge $(x,y,z)\sim \mu$ where $\mu$ is a probability distribution over $\Sigma\times\Gamma\times\Phi$,  and a map $t\colon \Sigma\times\Gamma\times\Phi\to\mathcal{A}$ for a...

Cayley graphs provide interesting bridges between graph theory, additive combinatorics and group theory. Fixing an ambient finite group, random Cayley graphs are constructed by choosing a generating set at random. These graphs reflect interesting...

A cornerstone result in geometry is the Szemerédi–Trotter theorem, which gives a sharp bound on the maximum number of incidences between $m$ points and $n$ lines in the real plane. A natural generalization of this is to consider point-hyperplane...

A graph $G$ is said to be Ramsey for a tuple of graphs ($H_1,...,H_r$) if every $r$-coloring of the edges of $G$ contains a monochromatic copy of $H_i$ in color $i$, for some $i$. A fundamental question at the intersection of Ramsey theory and the...

This is the introductory talk for a semester-long learning seminar on the notion of solid modules and the resulting 6-functor formalism for coherent cohomology.

Steven will cover the material from the first two lectures by Peter Scholze (available electronically at http://people.mpim-bonn.mpg.de/scholze/Condensed.pdf). In particular, he will introduce the notion of condensed set and condensed abelian group...

Quasi-coherent sheaves cannot support a six-functor formalism in the same way that e.g. \ell-adic sheaves do. Clausen and Scholze have shown that this can be fixed by extending the category of quasi-coherent sheaves to `solid sheaves’. In this talk...

This talk is an introduction to analytic rings. Some examples and non-examples will be covered. Some nice properties of the module categories will be proved.

We will discuss the notion of solid abelian groups.

We will globalize the notion of solid modules to an arbitrary scheme/discrete adic space.

We will discuss the 6-functor formalism for solid quasi-coherent sheaves.

The topic of the learning seminar this semester is "Analytic K-theory''. More precisely, the goal is to use condensed mathematics to obtain a notion of quasi-coherent sheaves/complexes in rigid analytic geometry, develop Efimov's approach to K...

Define the Grothendieck group of a commutative ring. Then define K1 and K2 and 
state Matsumoto’s theorem. Explain the definitions of higher K-theory in terms of the 
+-construction and in terms of the∞-group completion of groupoid of finite...

Introduce the notion of stable compactly generated $\infty$-category and discuss its properties and some examples. In particular, prove that the $\infty$-category of small idempotent complete stable $\infty$-categories is equivalent to the $\infty$...

Introduce the notion of Verdier sequences of presentable stable $\infty$-categories and then discuss the behavior of dualizable $\infty$-categories in Verdier sequence; in particular, discuss Thomason's trick. Introduce the notion of localizing...

Recall the notion of condensed analytic ring, then introduce its animated variant and discuss its properties. Explain the construction of induced analytic structures on animated condensed rings. Introduce the notion of steady maps of analytic rings...

Introduce the notion of nuclear object in a symmetric monoidal stable ($\infty$-)category and discuss its properties. In particular, prove that if the monoidal unit is compact, then an object is dualizable if and only if it is compact and nuclear...

For a general complete Huber pair $(A,A^+)$, define the analytic ring $(A,A^+)_\blacksquare$. Prove that the associations $\mathrm{Spa}\, (A,A^+)\mapsto \mathcal{D}((A,A^+)_\blacksquare)$, $\mathrm{Spa}\, (A,A^+)\mapsto \mathcal{D}^\omega((A,A^+)_...

Define the category of solid quasi-coherent sheaves $\mathcal{D}_\blacksquare(X)$ on a rigid-analytic varity $X$. Show that this assignment comes with a natural $6$-functor formalism. Finally, prove the Grothendieck--Serre duality in the rigid...

Prove that for a qcqs analytic adic space $X$, the category of nuclear sheaves on $X$ is dualizable in two steps. First, establish the result locally over affinoid Tate adic spaces using the notion of weak proregularity and then prove a general...

Review the notion of cd-structure for a Grothendieck topology and explain how it helps check the sheaf conditions. Introduce and discuss the Nisnevich topology for schemes and analytic adic spaces; in particular, discuss their equivalent...

Introduce the notion of hypersheaf and discuss its basic properties and equivalent characterizations. In particular, discuss the notions of homotopy and cohomological dimensions and their relation to hyperdescent. Sketch the proof of the fact for...