@COMMENT This file was generated by bib2html.pl <https://sourceforge.net/projects/bib2html/> version 0.94
@COMMENT written by Patrick Riley <http://sourceforge.net/users/patstg/>
@COMMENT This file came from Kuldeep S. Meel's publication pages at
@COMMENT http://www.comp.nus.edu.sg/~meel/publications/
@inproceedings{ABM24,
  author={Amarilli, Antoine and Bremen, Timothy van and Meel, Kuldeep S.},
  title={
    Conjunctive Queries on Probabilistic Graphs: The Limits of Approximability
  },
  abstract={
    Query evaluation over probabilistic databases is a notoriously intractable
    problem -
    not only in combined complexity, but for many natural queries in data
    complexity as well [Antoine Amarilli et al., 2017; Nilesh N. Dalvi and Dan
    Suciu, 2012].
    This motivates the study of probabilistic query evaluation through the lens
    of approximation algorithms, and particularly of
    combined FPRASes, whose runtime is polynomial in both the query and instance
    size. In this
    paper, we focus on tuple-independent probabilistic databases over binary
    signatures, which
    can be equivalently viewed as probabilistic graphs. We study in which cases
    we can devise
    combined FPRASes for probabilistic query evaluation in this setting. We
    settle the complexity
    of this problem for a variety of query and instance classes, by proving both
    approximability and
    (conditional) inapproximability results. This allows us to deduce many
    corollaries of possible independent interest.
    For example, we show how the results of [ACJR21]
    on counting fixed-length strings accepted by an NFA imply the existence of
    an FPRAS for the
    two-terminal network reliability problem on directed acyclic graphs: this
    was an open problem
    until now [Rico Zenklusen and Marco Laumanns, 2011]. We also show that one
    cannot extend
    a recent result [Timothy van Bremen and Kuldeep S. Meel, 2023] that gives a
    combined FPRAS
    for self-join-free conjunctive queries of bounded hypertree width on
    probabilistic databases:
    neither the bounded-hypertree-width condition nor the self-join-freeness
    hypothesis can be
    relaxed. Finally, we complement all our inapproximability results with
    unconditional lower bounds,
    showing that DNNF provenance circuits must have at least moderately
    exponential size in combined complexity.
  },
  month=mar,
  year={2024},
  booktitle=ICDT,
  note={
    Selected as one of the 7 best papers from the conference to be invited for a
    special issue of the journal Logical Methods in Computer Science.
  },
  bib2html_pubtype={Refereed Conference,Award Winner},
  bib2html_rescat={Data Streams},
  bib2html_dl_pdf={https://doi.org/10.4230/LIPIcs.ICDT.2024.15},
}