Back to papers
The Impact of Negation on the Complexity of the Shapley Value in Conjunctive Queries
Summary: Extends the Shapley-value dichotomy to conjunctive queries with negated atoms, characterizing exact complexity. Shows negation fundamentally changes approximability—reduces approximation to the tuple-relevance decision, yielding new hardness and only limited randomized-approximation cases.
(summarized by gpt-5-mini on Feb 09 2026)
- Paper ID
- 1795
- Venue
- PODS
- Year
- 2020
- Pagerank
- 7.6842412e-05
- Overall Rank
- 3,027 | 78.95%
- DOI
-
10.1145/3375395.3387664
Incoming Non-self Citations Over Time
Incoming Citations (Sorted by Pagerank)
Showing 13 of 13 citing papers.
| Rank |
Citing Paper |
Year |
Venue |
Pagerank |
| 2,868 |
Computing the Shapley Value of Facts in Query Answering |
2022 |
SIGMOD |
7.9816425e-05 |
| 4,591 |
From Shapley Value to Model Counting and Back |
2024 |
PODS |
6.0619399e-05 |
| 5,916 |
Banzhaf Values for Facts in Query Answering |
2024 |
SIGMOD |
5.273953e-05 |
| 5,959 |
Expected Shapley-Like Scores of Boolean Functions: Complexity and Applications to Probabilistic Databases |
2024 |
PODS |
5.2562342e-05 |
| 6,055 |
When is Shapley Value Computation a Matter of Counting? |
2024 |
PODS |
5.2324399e-05 |
| 6,429 |
ShapGraph: An Holistic View of Explanations through Provenance Graphs and Shapley Values |
2022 |
SIGMOD |
5.0666822e-05 |
| 7,172 |
Summarized Causal Explanations For Aggregate Views |
2024 |
SIGMOD |
4.8114797e-05 |
| 7,932 |
P-Shapley: Shapley Values on Probabilistic Classifiers |
2024 |
VLDB |
4.613363e-05 |
| 8,665 |
Advancing Fact Attribution for Query Answering: Aggregate Queries and Novel Algorithms |
2025 |
VLDB |
4.471975e-05 |
| 9,640 |
Shapley Revisited: Tractable Responsibility Measures for Query Answers |
2025 |
PODS |
4.3109001e-05 |
| 9,766 |
DPXPlain: Privately Explaining Aggregate Query Answers |
2023 |
VLDB |
4.2856106e-05 |
| 10,010 |
Tractability Frontiers of the Shapley Value for Aggregate Conjunctive Queries |
2026 |
PODS |
4.1945683e-05 |
| 10,392 |
Shapley Value Estimation Based on Differential Matrix |
2025 |
SIGMOD |
4.1945683e-05 |
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.
Semantically Similar Papers
| Overall Rank |
Paper |
Year |
Venue |
Pagerank |
| 8,721 |
Aggregated Deletion Propagation for Counting Conjunctive Query Answers |
2021 |
VLDB |
4.4608778e-05 |
| 6,262 |
Fast Shapley Value Computation in Data Assemblage Tasks as Cooperative Simple Games |
2024 |
SIGMOD |
5.1349507e-05 |
| 8,851 |
Efficient Approximations of Conjunctive Queries |
2012 |
PODS |
4.4363908e-05 |
| 10,898 |
Conjunctive Queries with Negation and Aggregation: A Linear Time Characterization |
2024 |
PODS |
4.1945683e-05 |
| 2,868 |
Computing the Shapley Value of Facts in Query Answering |
2022 |
SIGMOD |
7.9816425e-05 |
| 5,959 |
Expected Shapley-Like Scores of Boolean Functions: Complexity and Applications to Probabilistic Databases |
2024 |
PODS |
5.2562342e-05 |
| 4,591 |
From Shapley Value to Model Counting and Back |
2024 |
PODS |
6.0619399e-05 |
| 6,055 |
When is Shapley Value Computation a Matter of Counting? |
2024 |
PODS |
5.2324399e-05 |
| 9,640 |
Shapley Revisited: Tractable Responsibility Measures for Query Answers |
2025 |
PODS |
4.3109001e-05 |
| 10,010 |
Tractability Frontiers of the Shapley Value for Aggregate Conjunctive Queries |
2026 |
PODS |
4.1945683e-05 |