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 …

Our work explores the hardness of 3SUM instances without certain additive structures, and
its applications. As our main technical result, we show that solving 3SUM on a size-n integer …

The last two decades have witnessed a dramatic increase in the amount of highly repetitive
datasets consisting of sequential data (strings, texts). Processing these massive amounts of …

We revisit the fundamental Boolean Matrix Multiplication (BMM) problem. With the invention
of algebraic fast matrix multiplication over 50 years ago, it also became known that BMM can …

In the approximate pattern matching problem, given a text T, a pattern P, and a threshold k,
the task is to find (the starting positions of) all substrings of T that are at distance at most k …

The Strong Exponential Time Hypothesis and the OV-conjecture are two popular hardness
assumptions used to prove a plethora of lower bounds, especially in the realm of polynomial …

In the Subset Sum problem we are given a set of n positive integers X and a target t and are
asked whether some subset of X sums to t. Natural parameters for this problem that have …

Real-world data often comes in compressed form. Analyzing compressed data directly
(without first decompressing it) can save space and time by orders of magnitude. In this …

We pose the fine-grained hardness hypothesis that the textbook algorithm for the NFA
Acceptance problem is optimal up to subpolynomial factors, even for dense NFAs and fixed …

Graph Neural Networks (GNNs) are extensively employed in graph machine learning, with
considerable research focusing on their expressiveness. Current studies often assess GNN …