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 …

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 present a new technique for efficiently removing almost all short cycles in a graph
without unintentionally removing its triangles. Consequently, triangle finding problems do …

Due to the lack of unconditional polynomial lower bounds, it is now in fashion to prove
conditional lower bounds in order to advance our understanding of the class P. The vast …

A recent, active line of work achieves tight lower bounds for fundamental problems under the
Strong Exponential Time Hypothesis (SETH). A celebrated result of Backurs and Indyk …

We investigate the complexity of several fundamental polynomial-time solvable problems on
graphs and on matrices, when the given instance has low treewidth; in the case of matrices …

A minimum path cover (MPC) of a directed acyclic graph (DAG) G=(V, E) is a minimum-size
set of paths that together cover all the vertices of the DAG. Computing an MPC is a basic …

We revisit the classic combinatorial pattern matching problem of finding a longest common
subsequence (LCS). For strings x and y of length n, a textbook algorithm solves LCS in time …

We introduce the Nondeterministic Strong Exponential Time Hypothesis (NSETH) as a
natural extension of the Strong Exponential Time Hypothesis (SETH). We show that both …

We present KADABRA, a new algorithm to approximate betweenness centrality in directed
and undirected graphs, which significantly outperforms all previous approaches on real …