Theoretical quantum advantage is well-established in centralized computing, where computation is performed on a single computer. However, its potential in distributed computing is less understood. In this talk, we consider the LOCAL model of computation (Linial 1987), a model of synchronous distributed computation where the complexity measure is the number of communication rounds needed to solve a problem, with no constraints on communication bandwidth or local computation capabilities. The classical LOCAL model is well-studied, especially regarding Locally Checkable Labeling (LCL) problems (Naor and Stockmeyer 1993), which include problems like graph coloring, finding maximal independent sets, etc. However, determining whether quantum computers and quantum communication can speed up computation in this setting remains an open question. Currently, no tools specific to quantum-LOCAL exist to address this question. Nonetheless, arguments based on independence and causality have been useful in “sandwiching” quantum-LOCAL between classical LOCAL and super-quantum models. This talk will discuss recent findings in this area, highlighting settings where quantum advantage is impossible and where current arguments fail to rule out quantum advantage.

This talk is about distributed computation with signals—when devices communicate by sending contentless “pulses” instead of content-based messages. In asynchronous environments, the arrival time of such pulses is arbitrary, and devices can infer information only from the origin of each pulse and their order of arrival. I will review recent Content-Oblivious Algorithms—algorithms for solving various tasks based on point-to-point signaling without the ability to convey information in the content of the transmitted messages.

Graph sparsification is a technique that approximates a given graph by another graph, called a sparsifier, which has fewer vertices and/or edges. The goal of a sparsifier is to provably preserve specific graph properties of interest, such as connectivity, shortest paths, and flow/cut structure, among others.

In this talk, I will focus on spectral vertex sparsifiers, which reduce the number of vertices while preserving the graph spectrum. I will explain how to efficiently compute these sparsifiers in dynamically changing graphs and in the distributed CONGEST model. I will also discuss the implications of these results for exact computations of maximum and minimum-cost flows in both the sequential and distributed setting.

I will provide a gentle introduction to measurable combinatorics, a field that lies at the intersection of areas that study discrete structures (finite combinatorics, random graphs, distributed computing), analytic objects (descriptive set theory, measured group theory, analysis) and interactions between them (graph limits, stochastic processes). After presenting a couple of fundamental and motivating results, such as the constructible solutions to Tarski's circle-squaring problem, I will focus on the recently discovered connections between the theory of distributed computing and descriptive set theory, which are formalized through the study of complexity classes of locally checkable labeling (LCL) problems.

Given access to a large graph, can we quickly test whether it can be partitioned into a few good clusters? And if so, quickly tell, given a vertex, which cluster it belongs to?

This problem for $k = 2$ clusters is the expansion testing problem, introduced in the classical work of Goldreich and Ron and studied extensively over the following two decades. The main idea of these works is to associate with every vertex the distribution of a short random walk started at it, and then use distance-based Euclidean clustering on the resulting point set—with a careful implementation this leads to an algorithm with runtime $\approx n^{1/2}$ for $k = 2$.

It turns out, however, that ‘distance-based’ clustering methods fundamentally do not extend to any number of clusters higher than 2 without a major loss in efficiency. I will talk about our recent line of work that uses angles as opposed to distances in the corresponding Euclidean space one can optimally test cluster structure for all $k \ge 2$. A key component of our approach is the concept of a spectral clustering oracle, which is a small space data structure that allows dot product access to the spectral embedding of the input graph. This results in close to information theoretically optimal algorithms for testing and querying the cluster structure of the graph.

Traditionally, in distributed graph algorithms, the locality of a problem is measured by the number of communication rounds required to solve the problem in the LOCAL model. However, Feuilloley [DMTCS 2021] suggested that for decision problems, the local certification framework could provide a different way of measuring locality: let an external prover assign a certificate to each node, and measure how large the certificates must be for the nodes to locally verify a given graph property (the smaller the certificates, the more local the property).

In this talk, we will explore a third potential measure of locality: quantifier alternation, the key concept underlying the polynomial hierarchy. The proposed thesis is that the locality of a graph property can be measured by the number of alternations in a game between two players who argue whether the network has the property, alternately assigning proofs and counterproofs to the nodes (the fewer alternations needed, the more local the property).