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.676832e-05
- Overall Rank
- 3,030 | 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,876 |
Computing the Shapley Value of Facts in Query Answering |
2022 |
SIGMOD |
7.9739469e-05 |
| 4,591 |
From Shapley Value to Model Counting and Back |
2024 |
PODS |
6.056109e-05 |
| 5,918 |
Banzhaf Values for Facts in Query Answering |
2024 |
SIGMOD |
5.2688869e-05 |
| 5,960 |
Expected Shapley-Like Scores of Boolean Functions: Complexity and Applications to Probabilistic Databases |
2024 |
PODS |
5.251188e-05 |
| 6,058 |
When is Shapley Value Computation a Matter of Counting? |
2024 |
PODS |
5.2274142e-05 |
| 6,424 |
ShapGraph: An Holistic View of Explanations through Provenance Graphs and Shapley Values |
2022 |
SIGMOD |
5.0618143e-05 |
| 7,172 |
Summarized Causal Explanations For Aggregate Views |
2024 |
SIGMOD |
4.8068645e-05 |
| 7,935 |
P-Shapley: Shapley Values on Probabilistic Classifiers |
2024 |
VLDB |
4.6089395e-05 |
| 8,663 |
Advancing Fact Attribution for Query Answering: Aggregate Queries and Novel Algorithms |
2025 |
VLDB |
4.4676883e-05 |
| 9,639 |
Shapley Revisited: Tractable Responsibility Measures for Query Answers |
2025 |
PODS |
4.3067693e-05 |
| 9,768 |
DPXPlain: Privately Explaining Aggregate Query Answers |
2023 |
VLDB |
4.2815042e-05 |
| 10,010 |
Tractability Frontiers of the Shapley Value for Aggregate Conjunctive Queries |
2026 |
PODS |
4.1905499e-05 |
| 10,403 |
Shapley Value Estimation Based on Differential Matrix |
2025 |
SIGMOD |
4.1905499e-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,718 |
Aggregated Deletion Propagation for Counting Conjunctive Query Answers |
2021 |
VLDB |
4.4566012e-05 |
| 6,262 |
Fast Shapley Value Computation in Data Assemblage Tasks as Cooperative Simple Games |
2024 |
SIGMOD |
5.1300221e-05 |
| 8,850 |
Efficient Approximations of Conjunctive Queries |
2012 |
PODS |
4.4324268e-05 |
| 10,902 |
Conjunctive Queries with Negation and Aggregation: A Linear Time Characterization |
2024 |
PODS |
4.1905499e-05 |
| 2,876 |
Computing the Shapley Value of Facts in Query Answering |
2022 |
SIGMOD |
7.9739469e-05 |
| 5,960 |
Expected Shapley-Like Scores of Boolean Functions: Complexity and Applications to Probabilistic Databases |
2024 |
PODS |
5.251188e-05 |
| 4,591 |
From Shapley Value to Model Counting and Back |
2024 |
PODS |
6.056109e-05 |
| 6,058 |
When is Shapley Value Computation a Matter of Counting? |
2024 |
PODS |
5.2274142e-05 |
| 9,639 |
Shapley Revisited: Tractable Responsibility Measures for Query Answers |
2025 |
PODS |
4.3067693e-05 |
| 10,010 |
Tractability Frontiers of the Shapley Value for Aggregate Conjunctive Queries |
2026 |
PODS |
4.1905499e-05 |