157 citations · 381 across the 18 of their papers we have counts for
Showing 2019Show all
2 papers · 1 filter
cs.DB2019★ 1 cited
Counting Problems over Incomplete Databases
Marcelo Arenas, Pablo Barceló, Mikaël Monet
We study the complexity of various fundamental counting problems that arise in the context of incomplete databases, i.e., relational databases that can contain unknown values in th…
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…