2 citations · 2 across the 4 of their papers we have counts for
3 papers · 1 filter
Lower Bounds for the Algorithmic Complexity of Learned Indexes
Luis Alberto Croquevielle, Roman Sokolovskii, Thomas Heinis
Learned index structures aim to accelerate queries by training machine learning models to approximate the rank function associated with a database attribute. While effective in pra…
When is Approximate Counting for Conjunctive Queries Tractable?
Marcelo Arenas, Luis Alberto Croquevielle, Rajesh Jayaram +1
Conjunctive queries are one of the most common class of queries used in database systems, and the best studied in the literature. A seminal result of Grohe, Schwentick, and Segoufi…
$\text{#NFA}$ admits an FPRAS: Efficient Enumeration, Counting, and Uniform Generation for Logspace Classes
Marcelo Arenas, Luis Alberto Croquevielle, Rajesh Jayaram +1
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…