In recent years, a new “fine-grained” theory of computational hardness has been developed,
based on “fine-grained reductions” that focus on exact running times for problems …

Consider the following Online Boolean Matrix-Vector Multiplication problem: We are given
an nxn matrix M and will receive n column-vectors of size n, denoted by v1,..., vn, one by …

We consider several well-studied problems in dynamic algorithms and prove that sufficient
progress on any of them would imply a breakthrough on one of five major open problems in …

We present a new randomized method for computing the min-plus product (aka, tropical
product) of two n× n matrices, yielding a faster algorithm for solving the all-pairs shortest …

Abstract We give Proofs of Work (PoWs) whose hardness is based on a wide array of
computational problems, including Orthogonal Vectors, 3SUM, All-Pairs Shortest Path, and …

The radius and diameter are fundamental graph parameters, with several natural definitions
for directed graphs. Each definition is well-motivated in a variety of applications. All versions …

Algorithmic research strives to develop fast algorithms for fundamental problems. Despite its
many successes, however, many problems still do not have very efficient algorithms. For …

We introduce graph motif parameters, a class of graph parameters that depend only on the
frequencies of constant-size induced subgraphs. Classical works by Lovász show that many …

Fine-grained reductions have established equivalences between many core problems with
Õ (n 3)-time algorithms on n-node weighted graphs, such as Shortest Cycle, All-Pairs …

For a pattern graph H on k nodes, we consider the problems of finding and counting the
number of (not necessarily induced) copies of H in a given large graph G on n nodes, as …