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 …

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 …

We study the enumeration complexity of Unions of Conjunctive Queries (UCQs). We aim to
identify the UCQs that are tractable in the sense that the answer tuples can be enumerated …

We consider the information extraction framework known as document spanners and study
the problem of efficiently computing the results of the extraction from an input document …

The regular spanners (characterised by vset-automata) are closed under the algebraic
operations of union, join and projection, and have desirable algorithmic properties. The core …

In this work, we study two simple yet general complexity classes, based on logspace Turing
machines, that provide a unifying framework for efficient query evaluation in areas such as …

In this note we present an algorithm that lists all $4 $-cycles in a graph in time $\tilde
{O}(\min (n^ 2, m^{4/3})+ t) $ where $ t $ is their number. Notably, this separates $4 $-cycle …

In this work, we study two simple yet general complexity classes, based on logspace Turing
machines, which provide a unifying framework for efficient query evaluation in areas like …

Regular expressions and automata models with capture variables are core tools in rule-
based information extraction. These formalisms, also called regular document spanners, use …

We give an algorithm to enumerate the results on trees of monadic second-order (MSO)
queries represented by nondeterministic tree automata. After linear time preprocessing (in …