Algorithms and Complexity Seminar

We know that constant-depth circuits for Parity require exponential size. The usual proof simplifies a circuit from the inputs towards the output using random restrictions. Can we instead prove the lower bound by following the circuit from its output towards the inputs?

We will discuss Oliver Korten’s top-down proof for every constant depth. Through the Karchmer-Wigderson correspondence, the problem becomes a lower bound for a communication game. We will start with the combinatorial adversary argument and then discuss how it is strengthened to obtain the bound $\exp(\varepsilon_d n^{1/(d-1)})$, matching the classical lower bound up to the depth-dependent constant.

Paper: Top-Down Lower Bounds for All Depths.

Håstad’s classical lower bound says that depth-$d$ circuits computing Parity require $2^{\Omega(n^{1/(d-1)})}$ gates. For decades, no explicit function was known to require asymptotically larger circuits at any constant depth. Recently, OpenAI announced a function in P that breaks this barrier at depth three.

In this talk, I will present a simpler function that breaks the parity barrier at every fixed depth $d\ge 3$. For $n$-bit vectors $x,y$ and a $(2n-1)$-bit vector $a$, the function $\sum_{i,j}a_{i+j}x_i y_j\bmod 2$ requires $2^{\Omega((n\log n/\log\log n)^{1/(d-1)})}$ gates in depth-$d$ circuits with unbounded-fan-in AND and OR gates. The proof combines a short new proof of OpenAI’s restriction lemma with Håstad’s switching lemma and the sparsification lemma of Calabro, Impagliazzo, and Paturi.

Paper: Breaking the Parity Barrier for Constant-Depth Circuits.

Strassen’s asymptotic rank conjecture concerns tensors and would, in particular, imply matrix multiplication in almost quadratic time. The Set Cover conjecture says that we cannot solve Set Cover substantially faster than exhaustive search. Surprisingly, these two conjectures cannot both be true!

In this talk, we will discuss a short proof of this connection. We will introduce tensor rank and asymptotic rank, and see how the asymptotic rank conjecture gives a faster algorithm for Set Cover.

Paper: A Stronger Connection between the Asymptotic Rank Conjecture and the Set Cover Conjecture.

Proving $\mathrm{AC}^0$ circuit lower bounds is an old open problem in complexity theory. 40 years ago, Håstad proved a classical $2^{\Omega(n^{1/(h-1)})}$ lower bound for depth-$h$ circuits computing Parity, which remains the best-known $\mathrm{AC}^0$ circuit lower bound for any explicit function. However, the lower bound for Parity cannot be improved, since we know the matching upper bound. On the other hand, another candidate for proving constant-depth lower bounds is the Majority function, for which the same lower bound holds, but no matching upper bound was known. For a long time, it was believed that the lower bound for Majority can be improved.

In this talk, we will consider a simple construction of depth-$h$ circuits for Majority matching the lower bound.

In this survey talk, we discuss distributed algorithms for detecting and listing subgraphs such as triangles, cycles, and cliques. We review known upper and lower bounds in the CONGEST and CONGESTED CLIQUE models, the main techniques behind the best algorithms, and some of the key open problems in the area.

We present quantum algorithms for Subset Sum and $k$-SUM. We first review several quantum primitives, including quantum search, quantum walks, and claw finding, and then explain how they are combined to obtain a faster worst-case algorithm for $k$-SUM.

As an application, this improves the quantum running time for Subset Sum from roughly $1.26^n$ to $1.21^n$. Since the best known classical running time is about $2^{n/2}$ and the standard quantum primitives provide at most a square-root speedup, the natural benchmark is about $2^{n/4} \approx 1.19^n$.

We continue our discussion of lower bounds in distributed communication, working towards proving a lower bound in the CONGEST model. We consider the shared blackboard model: there is one player for every vertex of a graph; each player knows all edges incident to their vertex; and in every round, all players broadcast short messages visible to everyone.

The main result is a lower bound for the maximal independent set problem: protocols with polylogarithmic per-player communication require $\Omega(\log \log n)$ rounds. The same lower bound applies to maximal matching and to constant-factor approximations of maximum matching.

We study the complexity of the graph homomorphism problem when the target graph is parameterized by degeneracy. Under ETH, there is no $2^{o(\operatorname{degen}(H)n)}$ algorithm for any value of $\operatorname{degen}(H)$ as a function of $n$.

We also show that bounded degeneracy alone does not make the target size benign: even target graphs of degeneracy at most $2$ and quasipolynomial size force $n^{\Omega(n)}$-scale hardness. Finally, we discuss a no-compression barrier explaining why known fine-grained lower bounds for sparse $2$-CSP are not tight under ETH.

The complexity of multi-message broadcast in the CONGEST model has traditionally been tied to the network diameter. A natural question is whether, for well-connected networks such as expander graphs, this dependence can instead be characterized by a more refined structural parameter like mixing time.

In this talk, we will discuss a recent algorithm by Anton Paramonov and Roger Wattenhofer achieving $O(t_{\mathrm{mix}} + k)$ rounds for multi-message broadcast on expander graphs. The key technical tool is a novel use of branching random walks to construct a packing of broadcast trees. We will also discuss the paper’s NP-hardness result for constructing optimal broadcast structures.

At the upcoming seminar, we will further discuss the paper “Fast Distributed Algorithms for Girth, Cycles and Small Subgraphs” (Censor-Hillel et al., 2021), which presents fast distributed algorithms for detecting even cycles and computing the exact girth in the CONGEST model. We will focus on new algorithms for cycle detection.

We will construct an $n^{1-1/k}$-round algorithm for detecting $2k$-cycles for small values of $k$, as well as a parameterized algorithm for exact girth computation, which shows that computing any constant girth can be done in a truly sublinear number of rounds.

The paper studies the problem of finding a near-maximal matching in a bipartite graph when each player knows only their own incident edges and can communicate only a limited number of bits each round. The main result is a multi-round lower bound: with small per-player communication, any protocol needs at least $\Omega(\log \log n)$ rounds to achieve a constant-factor approximation (e.g. a matching of size which is a constant fraction of a maximal one).

This result was an inspiration for the $\Omega(\log \log n)$ lower bound on triangle finding in CONGEST.

At the upcoming seminar, we will discuss the paper “Fast Distributed Algorithms for Girth, Cycles and Small Subgraphs” (Censor-Hillel et al., 2021), which studies fast distributed algorithms for cycle detection, girth computation, and small subgraph listing in the CONGEST and Congested Clique models.

We will examine a constant-round algorithm for additive +1 approximation of the girth in the Congested Clique model, based on learning local neighborhoods and progressively expanding them until the shortest cycle is localized. We will then study the partition tree technique, a new deterministic approach to subgraph listing that yields, among other results, $O(1)$-round algorithms for detecting fixed even cycles ($C_{2k}$) and an $\widetilde O(n^{1/10})$-round algorithm for exact girth computation in triangle-free graphs.

Finally, we will discuss a barrier for proving lower bounds for $C_6$-freeness in the CONGEST model and see why obtaining a lower bound of the form $\Omega(n^{1/2+\varepsilon})$ appears to be connected to notoriously difficult open problems in circuit complexity.

We will discuss the problem of detecting, counting, and enumerating triangles in the CONGEST model. The main result is a near-optimal $n^{1/3}$-round algorithm, matching the known lower bound up to polylogarithmic factors. The main technical tool is expander decomposition.

The talk is based on a paper by Chang, Pettie, Saranurak, and Zhang.

Proving lower bounds on the circuit complexity of explicitly defined Boolean functions remains a difficult open problem. At present, we cannot rule out even the possibility that all problems in NP are solvable by linear-size circuits.

In this talk, we focus on a special case: linear functions and linear circuits computing such functions. Until recently, the best lower bound for these functions was 3n, proved by Chashkin in 1994. Recently, Sergeev improved this bound to 5n by introducing the notion of extended complexity. In the talk, we will present a proof of this lower bound.

Last week, we saw how to transform a network-coding protocol into a routing protocol with not too much overhead. In this talk, I will first briefly recall the main idea of that conversion and then explain why the obtained gap cannot be substantially improved.

The goal is to prove a matching limitation for routing. We will discuss a family of graphs where solving the same multiple-unicast problem without network coding is logarithmically harder. This shows that, although coding can be simulated by routing up to a controlled loss, this loss is not just an artifact of the proof.

We will discuss the paper “Network Coding Gaps for Completion Times of Multiple Unicasts.” Suppose we have a distributed network and many pairs of nodes want to exchange messages. The most direct approach is routing: messages are forwarded through the network along chosen paths.

Network coding allows a more flexible strategy. Instead of only forwarding packets, intermediate nodes may send functions of the packets they have received, so that each destination can eventually decode the message intended for it. The network coding gap measures how much faster this coded communication can be compared with ordinary routing.

In this talk, we will show that coding cannot help arbitrarily much in this setting. More precisely, given a network-coding protocol, one can construct a routing protocol with only a limited overhead. The talk will focus on the intuition behind this conversion and on why completion time is robust under replacing coding by routing.

The diameter $D$ of a graph is one of the most fundamental parameters in graph theory. In distributed computing, the diameter is of utmost importance, as it captures the minimal number of rounds needed for a message to traverse all the nodes in the network.

In the CONGEST model, computing the exact diameter requires almost $n$ rounds. On the other hand, usually one needs only an approximate diameter. For example, just by running BFS from an arbitrary vertex and outputting the longest distance, the problem can be solved in $O(D)$ rounds and gives an approximation ratio of $2$.

In this talk, we will prove several lower bounds on the number of rounds in the CONGEST model needed to approximate the diameter using connections with extremal combinatorics. We will show that $(\frac {6} {11} + \varepsilon)$ approximation requires about $n^{0.16}$ rounds, $(\frac 4 7 + \varepsilon)$ requires about $n^{0.25}$ rounds, and a $(\frac 3 5 + \varepsilon)$ approximation requires about $n^{0.33}$ rounds.

In the second part, we will continue the discussion of subgraph detection in distributed settings, focusing on the case of even cycles.

We will present improved algorithms for $C_{2k}$-freeness, based on a connection to extremal combinatorics and Zarankiewicz numbers, leading to faster runtimes for detecting such cycles.

Then, we will discuss the “hardness of hardness” phenomenon: why proving strong lower bounds for $C_{2k}$-freeness is inherently difficult, and how such bounds would imply breakthroughs in circuit complexity.

In this talk, we will consider the problems of $H$-freeness and $H$-listing: given a graph $G$, the goal is to determine whether it contains a fixed subgraph $H$, and to enumerate all its copies, for some $H$, in the CONGEST model.

We will show that $K_4$ and $K_5$ can be listed in sublinear time, in particular roughly $n^{5/6}$ and $n^{21/22}$ rounds, respectively, using an edge decomposition into well-connected clusters and a sparse part, together with a simulation of the Congested Clique within clusters.

Next, we will consider even cycles $C_{2k}$: by exploiting a connection to Zarankiewicz numbers, one obtains improved running times of the form $O(n^{1-\Theta(1/k^2)})$.

Finally, we will discuss why listing all copies of $C_4$ requires $\Theta(n)$ rounds, highlighting a fundamental difference between cycles and cliques.

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.