How do we prove a mathematical theorem that is too large for any human to verify? We will dive into the engineering behind modern distributed SAT solvers. We will focus on the practical side: how SAT competition winners tackle “unsolvable” problems, how they generate massive proofs across clusters, and why doing this in a distributed system is harder than it looks.

No specialized SAT knowledge required - just a basic Computer Science background.

Triangle-free graphs play a central role in graph theory, and triangle detection as well as triangle listing play central roles in the field of graph algorithms. For example, in 2010 Vassilevska Williams and Williams showed that a subcubic-time algorithm for triangle finding can be used to construct a subcubic-time algorithm for Boolean matrix multiplication.

In distributed computing, algorithms with sublinear round complexity for triangle finding and listing have recently been developed with the powerful Congested Clique model. In this seminar, we discuss randomized algorithms for triangle finding and listing with round complexities $O(n^{2/3}(\log n)^{2/3})$ and $O(n^{3/4}\log n)$, where $n$ denotes the number of nodes of the network, as well as the lower bound $\Omega(n^{1/3}/\log n)$ on the round complexity of triangle listing.

We continue the topic from the previous week and show upper and lower bounds for finding a $4$-cycle in the $\mathrm{CLIQUE}\text{-}\mathrm{BCAST}$ model.

Based on the paper by Drucker, Kuhn, and Oshman, we will study the Congested Clique model. It is a model where players communicate with each other over a complete network in order to compute some function of their inputs. The number of bits that can be sent on any edge in a round is bounded by some parameter. We will consider two versions of the model: in the first, the players communicate by unicast, allowing them to send a different message on each of their links in one round; in the second, the players communicate by broadcast, sending one message to all their neighbors.

We will show that the unicast Congested Clique can simulate powerful classes of bounded-depth circuits, implying that even slightly super-constant lower bounds for the Congested Clique would give new lower bounds in circuit complexity.

We will also show that in the broadcast setting, the subgraph detection problem requires polynomially many rounds for several classes of subgraphs. We also give upper bounds for the subgraph detection problem, and relate the hardness of triangle detection in the broadcast Congested Clique to the communication complexity of set disjointness in the 3-party number-on-forehead model.

We will start the study of distributed algorithms by examining selected chapters from “Distributed Algorithms (2020)” by Juho Hirvonen and Jukka Suomela. In particular, we will introduce several computational models used in distributed systems, such as the Port Numbering ($\mathrm{PN}$), $\mathrm{LOCAL}$, and $\mathrm{CONGEST}$ models.

We will show how these models are applied to classical distributed problems such as graph coloring and the all-pairs shortest path problem ($\mathrm{APSP}$). In addition, we present key techniques used to establish impossibility results, including covering maps and the analysis of local neighborhoods.

We examine the paper “The Orthogonal Vectors Conjecture and Non-Uniform Circuit Lower Bounds” by Ryan Williams. Ryan showed a connection between lower bounds for algorithms solving the Orthogonal Vectors problem and lower bounds for small-depth circuits.

In short, improving algorithms for $\mathrm{OV}$ automatically yields new, significant lower bounds for classes such as $\mathrm{AC}^0[\oplus]$ and exact-threshold circuits. Conversely, if there is a small circuit, then one can construct a fast algorithm for $\mathrm{OV}$, thereby refuting $\mathrm{SETH}$. This gives a win-win situation where at least one of the two lower bounds has to hold.

The key technical tool is a decomposition of the Disjointness matrix using equality ranks and its connections with $\mathrm{ETHR} \circ \mathrm{ETHR}$ and $\mathrm{SUM} \circ \mathrm{ETHR}$ circuits.

We will look at the recent surge of work on range avoidance. We will start from the search perspective classes: not just “does a solution exist?” but “find one.” I will review the classes $\mathrm{FP}$, $\mathrm{FNP}$, $\mathrm{TFNP}$, and the $\mathrm{PPP}$ subclass that emerges from the pigeonhole principle.

The core of the talk is the $\mathrm{AVOID}$ problem: given a circuit from $n$ bits to $m$ bits with $m > n$, the task is to find a string outside its range. I will explain why $\mathrm{AVOID}$ already sits at the second level of the hierarchy, and how it captures the familiar union-bound reasoning. Many explicit-construction tasks can be reduced cleanly to $\mathrm{AVOID}$, for example, finding a Boolean function with high circuit complexity. We will see that, for the class corresponding to $\mathrm{AVOID}$, this hard-function search is complete, which puts Shannon’s method in a “universal union-bound” light.

Some background in complexity is helpful, but I will recap the necessary classes and models at the start.

The paper uses Strassen’s asymptotic spectrum theory to construct a small depth-2 linear circuit for the Disjointness matrix and then uses it to solve the Orthogonal Vectors problem by a deterministic algorithm in time $\widetilde{O}(n \cdot 1.155^d)$. It is a rather complicated paper, so we will definitely not cover all of it, but we will try to extract the most important results.

A few years ago, people applied the Disjointness matrix to the Orthogonal Vectors problem and, for example, achieved better space complexity for the Subset Sum problem via that. Then a few related papers appeared from prominent researchers in the field. This paper is the most recent and advanced one.

We continue the discussion of Merlin-Arthur algorithms. In the previous meeting, we saw how multipoint circuit evaluation can be used to speed up many tasks in $\mathrm{MA}$. In this seminar, we discuss a newer paper where several techniques, not only Multipoint Circuit Evaluation, are used to speed up known problems in $\mathrm{MA}$.

The applications include a near-linear-time algorithm for $3$SUM, an algorithm for Subset Sum running in time $2^{n/3}$, counting weighted $k$-cliques in time $n^{k/2}$, linear-time counting of zero-weight triangles in dense graphs, all-pairs shortest paths in time $n^2$, and a two-round algorithm for QBF in time $2^{4n/5}$.

For some of these problems, faster algorithms are known in co-nondeterministic settings, but they remain far from the optimal running times. Randomness allows significantly stronger results.

Suppose we have a circuit of size $s$ computing a polynomial of degree $d$, and we want to evaluate it at $K$ points. If someone gives us the values quickly, how can we verify that they are correct? Checking all points directly would take roughly $K \cdot s$ time.

Ryan Williams proposed an algorithm that, in a Merlin-Arthur protocol, verifies the correctness of these evaluations in time $K \cdot d + s$. For low-degree functions, this can be much faster. Using this approach, he improved running times for a number of problems and refuted the MASETH hypothesis, which claimed that $\mathrm{MA}$ protocols cannot solve $k$-SAT substantially faster than $2^n$, by giving an algorithm with running time $2^{n/2}$.

We discuss how Merlin-Arthur protocols can be used for problems such as QBF, Orthogonal Vectors, counting $k$-cliques in graphs, and other well-known tasks.

Bitwise addition is one of the simplest computational tasks from a human point of view, and it is natural to want circuits for it that are as small as possible. One might expect this problem to have been completely understood long ago. However, recent work shows that circuits believed to be optimal since 1965 can be improved: many arithmetic operations had been computed by circuits that were not size-optimal.

The talk discusses a joint result with Alexander Kulikov and Georgie Levtsov on more compact circuits for weighted bit summation. We cover applications of the new bounds, discuss circuit depth, and mention open questions. If time permits, we also discuss a related paper proving a stronger bound for a specific input distribution, namely multiplication of two $n$-bit numbers.

For many computational problems that we care about, such as $3$-SAT, we do not expect very fast exact algorithms. A natural way to make progress is to relax the problem and ask for an approximate answer: for example, can we satisfy a $0.99$ fraction of clauses in a $3$-CNF formula, or find a Hamiltonian path whose value is within a factor of $2$ from optimum?

In this seminar, we discuss several classical results on approximation algorithms, but spend most of the time on why these algorithms cannot be improved. We survey techniques around hardness of approximation and focus on the Unique Games Conjecture.

We show the beautiful approximation ratio for Max-Cut, \(\min_{0 \le x \le \pi} \frac{2}{\pi}\cdot\frac{x}{1-\cos x} \approx 0.878,\) and explain why, assuming the Unique Games Conjecture, this ratio is optimal. Along the way, we touch on semidefinite programming, encodings, and analysis of Boolean functions.

We discuss the paper “New Algorithms for Pigeonhole Equal Subset Sum.” The classical Subset Sum problem asks for a zero-sum subset among $n$ elements. The best known simple algorithm for it dates back roughly 50 years and runs in time $2^{0.5n}$, and it remains hard to prove that significantly faster algorithms are impossible.

Pigeonhole Equal Subset Sum is a closely related problem, but it can be solved in time $2^{0.33n}$. The talk explains this contrast and the main algorithmic ideas behind the improvement.

We discuss the paper “Tree Evaluation is in Space $O(\log n \cdot \log \log n)$” by Cook and Mertz. The motivating question is whether one can use extra storage space without destroying its original contents: temporarily alter the memory during a computation, but guarantee that after the computation finishes, the memory is restored exactly as before.

The answer is yes: one can use such reversible or catalytic space in a clever way to perform computations using less ordinary memory. I will explain how this applies to Tree Evaluation, a problem that at some point was studied as a possible route toward separating $\mathrm{L}$ and $\mathrm{P}$.

We will also discuss a very recent application by Williams, who used techniques from this work to improve a 50-year-old result on simulating an arbitrary Turing machine running in time $t(n)$ using roughly $\sqrt{t(n)\log t(n)}$ space.

We start with a broad discussion of lower bounds in computational complexity and how they relate to attempts to prove that not all programs can be parallelized perfectly.

After that, I present our result “Toward Better Depth Lower Bounds: Strong Composition of XOR and a Random Function.” The talk focuses on formula and depth lower bounds, and on why strong composition phenomena are useful for proving lower bounds for explicit or randomized constructions.

We continue the discussion of easy witnesses and cover several additional results and ideas around the topic.

This introductory talk explains what distributed algorithms are and why they matter for modern systems such as blockchains and large-scale infrastructure. We discuss challenges such as double payment, asynchronous networks, crashes, and Byzantine faults.

The main focus is the consensus problem: first through an informal motivation, then through a more formal statement and discussion of impossibility results. We also cover the synchronous setting, crash faults, message complexity, the Dolev-Reischuk lower bound, and Paramonov’s lower bound. If time permits, we also discuss distributed machine learning, smart contracts, and practical challenges.

The Subset Sum problem asks, given $n$ numbers, whether some subset has sum zero. It is a well-known NP-hard problem with applications in cryptography. In 1979, Schroeppel and Shamir gave an algorithm running in time $2^{n/2}$ and space $2^{n/4}$. The running time is still the best known, while the space bound was recently improved to $2^{0.249999n}$.

In September, together with Tatyana Belova, Alexander Kulikov, and Ivan Mihajlin, we improved the space bound to $2^{0.246n}$ and simplified the algorithm. In this talk, I explain the algorithm and the idea behind the improved space analysis.

We discuss tight bounds for graph homomorphism and subgraph isomorphism. The result is closer to fine-grained complexity than to algorithms: in particular, it contains a reduction from $3$-Coloring to Subgraph Isomorphism.

One motivation is that the result implies lower bounds related to the computation of the Hadwiger number and related contraction problems. We also discuss possible extensions toward understanding the complexity of computing the Hadwiger number even when it is small.

We discuss a recent improvement to the space complexity of the classical Schroeppel-Shamir algorithm for the Subset Sum problem. The Schroeppel-Shamir algorithm solves Subset Sum in time $O^(2^{n/2})$ and space $O^(2^{n/4})$, and had not been improved in either time or space since 1979.

The algorithm itself is relatively simple: the running time comes from a reduction to $2$-SUM, and the space bound comes from enumerating all pairwise sums of two arrays in nondecreasing order using linear space. The talk explains how this space bound was finally improved using a connection to Orthogonal Vectors.