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 …

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 …

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 …

In this paper we carefully combine Fredman's trick [SICOMP'76] and Matoušek's approach
for dominance product [IPL'91] to obtain powerful results in fine-grained complexity. Under …

Suppose the fastest algorithm that we can design for some problem runs in time O (n^ 2).
However, we want to solve the problem on big data inputs, for which quadratic time is …

We study the approximability of two related problems on graphs with n nodes and m edges:
n-Pairs Shortest Paths (n-PSP), where the goal is to find a shortest path between O (n) …

Minimum Weight Cycle (MWC) is the problem of finding a simple cycle of minimum weight in
a graph $ G=(V, E) $. This is a fundamental graph problem with classical sequential …

We define a natural class of range query problems, and prove that all problems within this
class have the same time complexity (up to polylogarithmic factors). The equivalence is very …

We present several results on the round complexity of Replacement Paths and Second
Simple Shortest Path which are basic graph problems that can address fault tolerance in …

In recent years, the expander decomposition method was used to develop many graph
algorithms, resulting in major improvements to longstanding complexity barriers. This …