ETH Zurich

Semidefinite programming (SDP) is a powerful tool in the design of approximation algorithms. After providing a gentle introduction to the basics of this method, I will explore a different facet of SDP and show how it can be used to derive short and elegant proofs of both classical and new estimates related to the MaxCut problem and discrepancy theory in graphs and matrices.

Building on this, I will demonstrate how these results lead to an improved upper bound on the celebrated log-rank conjecture in communication complexity.

The study of counting point-hyperplane incidences in the $d$-dimensional space was initiated in the 1990's by Chazelle and became one of the central problems in discrete geometry. It has interesting connections to many other topics, such as additive combinatorics and theoretical computer science. Assuming a standard non-degeneracy condition, i.e., that no $s$ points are contained in the intersection of $s$ hyperplanes, the currently best known upper bound on the number of incidences of $m$ points and $n$ hyperplanes in $\mathbb{R}^d$ is $O((mn)^{1-1/(d+1)}+m+n)$. This bound by Apfelbaum and Sharir is based on geometrical space partitioning techniques, which apply only over the real numbers.

In this talk, we discuss a novel combinatorial approach to study such incidence problems over arbitrary fields. Perhaps surprisingly, this approach matches the best known bounds for point-hyperplane incidences in $\mathbb{R}^d$ for many interesting values of $m, n, d$. Moreover, in finite fields our bounds are sharp as a function of $m$ and $n$ in every dimension. This approach can also be used to study point-variety incidences and unit-distance problem in finite fields, giving tight bounds for both problems under a similar non-degeneracy assumption. Joint work with A. Milojevic and I. Tomon.

In this talk, I will present new results addressing two rather well-known problems on the embeddability of planar graphs on point-sets in the plane. The first problem, often attributed to Mohar, asks for the asymptotics of the minimum size of so-called universal point sets, i.e. point sets that simultaneously allow straight-line embeddings of all planar graphs on $n$ vertices. In the first half of the talk I will present a family of point sets of size $O(n)$ that allow straight-line embeddings of a large family of $n$-vertex planar graphs, including all bipartite planar graphs. In the second half of the talk, I will present a family of $(3+o(1))\log_2(n)$ planar graphs on $n$ vertices that cannot be simultaneously embedded straight-line on a common set of $n$ points in the plane. This significantly strengthens the previously best known exponential bound.

I will discuss a line of work on estimating causal effects from observational data. In the first part of the talk, I will discuss identification and estimation of causal effects when the underlying causal graph is known, using adjustment. In the second part, I will discuss what one can do when the causal graph is unknown. Throughout, examples will be used to illustrate the concepts and no background in causality is assumed.

Generative AI has seen tremendous successes recently, most notably the chatbot ChatGPT and the DALLE2 software creating realistic images and artwork from text descriptions. Underlying these and other generative AI systems are usually neural networks trained to produce text, images, audio, or video from text inputs. The aim of this talk is to develop an understanding of the fundamental capabilities of generative neural networks. Specifically and mathematically speaking, we consider the realization of high-dimensional random vectors from one-dimensional random variables through deep neural networks. The resulting random vectors follow prescribed conditional probability distributions, where the conditioning represents the text input of the generative system and its output can be text, images, audio, or video. It is shown that every d-dimensional probability distribution can be generated through deep ReLU networks out of a 1-dimensional uniform input distribution. What is more, this is possible without incurring a cost—in terms of approximation error as measured in Wasserstein-distance—relative to generating the d-dimensional target distribution from d independent random variables. This is enabled by a space-filling approach which realizes a Wasserstein-optimal transport map and elicits the importance of network depth in driving the Wasserstein distance between the target distribution and its neural network approximation to zero. Finally, we show that the number of bits needed to encode the corresponding generative networks equals the fundamental limit for encoding probability distributions (by any method) as dictated by quantization theory according to Graf and Luschgy. This result also characterizes the minimum amount of information that needs to be extracted from training data so as to be able to generate a desired output at a prescribed accuracy and establishes that generative ReLU networks can attain this minimum.

This is joint work with D. Perekrestenko and L. Eberhard


 

Over the last years, two different approaches to construct symmetry algebras acting on the cohomology of Nakajima quiver varieties have been developed. The first one, due to Maulik and Okounkov, exploits certain Lagrangian correspondences, called stable envelopes, to generate R-matrices for an arbitrary quiver and hence, via the RTT formalism, an algebra called Yangian. The second one realises the cohomology of Nakajima varieties as modules over the cohomological Hall algebra (CoHA) of the preprojective algebra of the quiver Q. It is widely expected that these two approaches are equivalent, and in particular that the Maulik-Okounkov Yangian coincides with the Drinfel’d double of the CoHA.

Motivated by this conjecture, in this talk I will show how to identify the stable envelopes themselves with the multiplication map of a subalgebra of the appropriate CoHA. 

As an application, I will introduce explicit inductive formulas for the stable envelopes and use them to produce integral solutions of the elliptic quantum Knizhnik–Zamolodchikov–Bernard (qKZB) difference equation associated to arbitrary quiver (ongoing project with G. Felder and K. Wang). Time permitting, I will also discuss connections with Cherkis bow varieties in relation to 3d Mirror symmetry (ongoing project with R. Rimanyi).

In this talk we discuss solution of the well-known problem of Erdős and Sauer from 1975 which asks for the maximum number of edges an $n$-vertex graph can have without containing a $k$-regular subgraph, for some fixed integer $k\geq 3$. We prove that any $n$-vertex graph with average degree at least $C_k\log\log n$ contains a $k$-regular subgraph. This matches the lower bound of Pyber, Rödl and Szemerédi and substantially
improves an old result of Pyber, who showed that average degree at least $C_k\log n$ is enough.

Our method can also be used to settle asymptotically a problem raised by Erdős and Simonovits in 1970 on almost regular subgraphs of sparse graphs and to make progress on the well-known question of Thomassen from 1983 on finding subgraphs with large girth and large average degree.

Joint work with Oliver Janzer