Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations
Summary: Dichotomy (FPTRAS) for counting answers to conjunctive queries with disequalities/negations: under rETH, bounded-arity queries admit an FPTRAS iff treewidth is bounded; unbounded-arity (no negations) admit an FPTRAS iff adaptive width is bounded. No FPRAS exists unless NP=RP even for width 1, but if neither disequalities nor negations appear there is an FPRAS for queries of bounded fractional hypertreewidth, strictly generalizing STOC'21. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Jacob Focke
- 2. Leslie Ann Goldberg
- 3. Marc Roth
- 4. Stanislav Živný
Incoming Citations (Sorted by Pagerank)
Showing 2 of 2 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 5,104 | Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins | 2023 | PODS | 5.6946113e-05 |
| 10,919 | Counting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity | 2024 | PODS | 4.1945683e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 2 of 2 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 431 | On the Complexity of Database Queries (Extended Abstract) | 1997 | PODS | 0.00023370207 |
| 3,003 | Counting Answers to Existential Positive Queries: A Complexity Classification | 2016 | PODS | 7.7388586e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 4,194 | On the Complexity of Approximate Query Optimization | 2002 | PODS | 6.3697822e-05 |
| 10,919 | Counting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity | 2024 | PODS | 4.1945683e-05 |
| 11,324 | The Complexity of Conjunctive Queries with Degree 2 | 2022 | PODS | 4.1945683e-05 |
| 772 | Answering Conjunctive Queries under Updates | 2017 | PODS | 0.00016876498 |
| 571 | The Complexity of Query Reliability | 1998 | PODS | 0.00019910719 |
| 9,748 | Combined Approximations for Uniform Operational Consistent Query Answering | 2024 | PODS | 4.2897489e-05 |
| 4,048 | On the Complexity of the Containment Problem for Conjunctive Queries with Built-in Predicates | 1998 | PODS | 6.4968603e-05 |
| 8,132 | Counting Database Repairs Entailing a Query: The Case of Functional Dependencies | 2022 | PODS | 4.5784634e-05 |
| 7,163 | Probabilistic Query Evaluation: The Combined FPRAS Landscape | 2023 | PODS | 4.8132033e-05 |
| 8,851 | Efficient Approximations of Conjunctive Queries | 2012 | PODS | 4.4363908e-05 |