Workshop Details

The field of fine-grained complexity has leveraged the Strong Exponential Time Hypothesis (SETH) to establish remarkably tight conditional lower bounds for dozens of problems across a wide range of domains and complexity classes, including Edit Distance, Graph Diameter, Hitting Set, Independent Set, and Orthogonal Vectors. However, a recurring question in the literature is whether similar SETH-hardness results can be obtained for other fundamental problems, such as Hamiltonian Path, Independent Set, Chromatic Number, MAX-k-SAT, and Set Cover.

We introduce a framework showing that any fine-grained reduction from SETH implying exponential hardness for any of these problems would imply new circuit lower bounds.

The Online-Matrix-Vector (OMv) conjecture states that the product of a vector with an nxn matrix needs Omega(n^2) time in the worst-case. It is a central fine-grained complexity assumption ruling out dynamic algorithms for a wide range of graph problems.

In this talk, we will see beyond worst-case models and algorithms, allowing us to circumvent this OMv barrier. As long as the graph, matrix, or updates have some generic notion of structure, then both the OMv problem and various dynamic graph problems can be solved/maintained in subquadratic time.

Quantities such as escape probabilities in Markov chains can be recovered by solving linear systems in diagonally dominant matrices arising from graph Laplacians. However, these probabilities may vary exponentially across different nodes of the graph. As a result, under standard norm-based error guarantees, accurately recovering small entries requires exponentially small error parameters, leading to prohibitively large running times. For example, a direct application of existing Laplacian solvers or fast matrix multiplication algorithms requires $\Omega(mn^2)$ and $\Omega(n^{\omega+1})$ bit operations, respectively, where $m$ denotes the number of nonzero entries, $n$ is the matrix dimension, and $\omega$ is the matrix multiplication exponent. 

In this talk, we discuss faster algorithms for solving such linear systems with entrywise approximation guarantees. In particular, we present an almost-linear-time algorithm for solving symmetric diagonally dominant M-matrix (SDDM) linear systems with entrywise approximation guarantees.

Strassen's theory of bilinear complexity characterizes the arithmetic complexity of primitives such as matrix multiplication via tensor rank of tensors. However, the connection to tensor rank breaks break down in higher degrees of multilinearity.

In this talk, I will highlight an unexplored connection between a generalized notion of tensor rank (namely, partition rank) and multiplicative complexity. This enables novel potential applications of the rank-based approaches to problems in fine-grained algorithms and complexity, such as the hyperclique conjecture of Lincoln-Williams-Vassilevska Williams (SODA 2018).

Based on joint work with Petteri Kaski and Jiaheng Wang.

For a handful of classic intractable problems—including graph coloring, set cover, and computing the permanent—the fastest known algorithms run in time roughly 2^n. Even mild exponential improvements over this baseline, say to 1.999^n, have eluded researchers for decades.

In this talk, I will describe an algebraic approach to such a speedup. Our starting point will be a recent line of work showing that Strassen’s asymptotic rank conjecture, a conjecture originally made in the context of fast matrix multiplication, would imply faster algorithms for all of these problems. I will sketch a proof of this connection, with emphasis on a “balanced 3-way partitioning” problem as the fundamental bottleneck this conjecture would address. In particular, we will see that even small improvements on known rank upper bounds for certain tensors—from 2^n to 2^n/poly(n)—would already have striking algorithmic consequences.

Finally, I will discuss unconditional progress from this approach. In particular, I will sketch a simple tensor-inspired algorithm for k-set cover that improves on prior work.

What are combinatorial algorithms for Boolean Matrix Multiplication, and more importantly (as we will argue), why do we want to find them? The talk will discuss these questions from the perspective of Fine-Grained Complexity.

Computing the connectivity (also known as unweighted maximum flow) between nodes in a network is a foundational problem in combinatorial optimization. In general dense graphs, the current fastest algorithm for computing the connectivities between all pairs of vertices remains the naïve approach, where one simply runs an almost-linear time maximum flow algorithm separately for each pair for each pair of vertices. In this talk, we discuss faster algorithms computing all-pairs connectivities in sparse graphs and for bounded connectivity values. These approaches bypass the machinery of fast max-flow entirely, and instead are based off classic techniques for enumerating lattice paths using determinants. 

The All-Pairs Shortest Paths (APSP) problem is a foundational problem in theoretical computer science. Approximating APSP in undirected unweighted graphs has been studied for many years, beginning with the work of Dor, Halperin and Zwick [SICOMP’01]. The combinatorial, additive-approximation algorithms shown in this paper remained the state of the art for 2 decades and it was unclear if algebraic tools from the world of matrix multiplication had the potential to speed up this problem.



In recent years, however, we have been able to harness these algebraic tools and give increasingly faster algorithms for computing additive approximation to APSP. In this talk I will present two techniques for ordering or partitioning the graph that allow for the use of algebraic tools and produce faster algorithms for approximating APSP. The talk will focus on the graph manipulations that allow for the subsequent use of general, non-proprietary algebraic techniques and not on the algebraic methods themselves.

Given a graph, computing distances and reachability information from a small set of vertices to the whole graph is an important primitive both in theory and in practice. I will discuss algorithms and fine-grained lower bounds for this problem in various important settings: distances in undirected unweighted graphs, and distances and reachability in directed unweighted graphs. The algorithms utilize fast matrix multiplication, and the fine-grained lower bounds are based on matrix-multiplication type problems. I will also discuss several applications of the algorithms such as hopset and shortcut set construction. 

Based on joint work with Barna Saha and Christopher Ye.