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 …

We present the first protocols for private information retrieval that allow fast (sublinear-time)
database lookups without increasing the server-side storage requirements. To achieve …

The 3SUM conjecture has proven to be a valuable tool for proving conditional lower bounds
on dynamic data structures and graph problems. This line of work was initiated by Pâtraşcu …

In this paper we study the (Bichromatic) Maximum Inner Product Problem (Max-IP), in which
we are given sets $ A $ and $ B $ of vectors, and the goal is to find $ a\in A $ and $ b\in B …

Given two strings S and T, each of length at most n, the longest common substring (LCS)
problem is to find a longest substring common to S and T. This is a classical problem in …

In this paper we study the fine-grained complexity of finding exact and approximate solutions
to problems in P. Our main contribution is showing reductions from an exact to an …

This paper shows several connections between data structure problems and cryptography
against preprocessing attacks. Our results span data structure upper bounds, cryptographic …

Relational queries, and in particular join queries, often generate large output results when
executed over a huge dataset. In such cases, it is often infeasible to store the whole …

Suffix trees are an important data structure at the core of optimal solutions to many
fundamental string problems, such as exact pattern matching, longest common substring …

The classic string indexing problem is to preprocess a string S into a compact data structure
that supports efficient pattern matching queries. Typical queries include existential queries …