157 citations · 381 across the 18 of their papers we have counts for
Showing cs.DSShow all
2 papers · 1 filter
cs.DS2020
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…
cs.DS2019
$\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…