Cover Image

The Complexity of Finding Missing Answer Repairs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Comer, Jesse, Tannen, Val
Format:	Preprint
Published:	2026
Subjects:	Databases Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Diversity of Answers to Conjunctive Queries
by: Merkl, Timo Camillo, et al.
Published: (2023)

A Unifying Algorithm for Hierarchical Queries
by: Khamis, Mahmoud Abo, et al.
Published: (2025)

Provenance Analysis and Semiring Semantics for First-Order Logic
by: Grädel, Erich, et al.
Published: (2024)

Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations
by: Focke, Jacob, et al.
Published: (2021)

Parameterised Complexity of Consistent Query Answering via Graph Representations
by: Hankala, Teemu, et al.
Published: (2024)

Expected Shapley-Like Scores of Boolean Functions: Complexity and Applications to Probabilistic Databases
by: Karmakar, Pratik, et al.
Published: (2024)

Jaguar: A Primal Algorithm for Conjunctive Query Evaluation in Submodular-Width Time
by: Khamis, Mahmoud Abo, et al.
Published: (2026)

Towards Parameterized Hardness on Maintaining Conjunctive Queries
by: Wang, Qichen
Published: (2026)

Lower Bounds for Conjunctive Query Evaluation
by: Mengel, Stefan
Published: (2025)

PFCS: Prime Factorization Cache System for Deterministic Data Relationship Discovery
by: Le, Duy
Published: (2025)

Circuits and Formulas for Datalog over Semirings
by: Fan, Austen Z., et al.
Published: (2025)

Tight Fine-Grained Bounds for Direct Access on Join Queries
by: Bringmann, Karl, et al.
Published: (2022)

Fast Matrix Multiplication meets the Submodular Width
by: Abo-Khamis, Mahmoud, et al.
Published: (2024)

Finding a Fair Scoring Function for Top-$k$ Selection: From Hardness to Practice
by: Cai, Guangya
Published: (2025)

Evaluating Datalog over Semirings: A Grounding-based Approach
by: Zhao, Hangdong, et al.
Published: (2024)

Fine-Grained Complexity of Regular Path Queries
by: Casel, Katrin, et al.
Published: (2021)

The Complexity of Order-Finding for ROABPs
by: Bhargava, Vishwas, et al.
Published: (2024)

Learning Tree Pattern Transformations
by: Neider, Daniel, et al.
Published: (2024)

Matching walks that are minimal with respect to edge inclusion
by: Marsault, Victor
Published: (2024)

From Time to Space: The Impact of Linearity in Higher-Order Datalog
by: Charalambidis, Angelos, et al.
Published: (2026)

The Power of Negation in Higher-Order Datalog
by: Charalambidis, Angelos, et al.
Published: (2025)

Multiparty Communication Complexity of Collision Finding
by: Beame, Paul, et al.
Published: (2024)

A Parameterized-Complexity Framework for Finding Local Optima
by: Ganian, Robert, et al.
Published: (2026)

Optimal Proof Systems for Complex Sets are Hard to Find
by: Egidy, Fabian, et al.
Published: (2024)

Capturing P: On the Expressive Power and Efficient Evaluation of Boolean Retrieval
by: Aavani, Amir
Published: (2026)

Enumeration and updates for conjunctive linear algebra queries through expressibility
by: Muñoz, Thomas, et al.
Published: (2023)

Enhancing Grover's Search Algorithm: A Modified Approach to Increase the Probability of Good States
by: Abdulrahman, Ismael
Published: (2024)

New Algebrization Barriers to Circuit Lower Bounds via Communication Complexity of Missing-String
by: Chen, Lijie, et al.
Published: (2025)

To Store or Not to Store: a graph theoretical approach for Dataset Versioning
by: Guo, Anxin, et al.
Published: (2024)

The Complexity of Finding and Counting Subtournaments
by: Döring, Simon, et al.
Published: (2025)

Generalizing Fair Top-$k$ Selection: An Integrative Approach
by: Cai, Guangya
Published: (2026)

The Complexity of Resilience for Digraph Queries
by: Bodirsky, Manuel, et al.
Published: (2026)

Space Complexity Dichotomies for Subgraph Finding Problems in the Streaming Model
by: Shih, Yu-Sheng, et al.
Published: (2026)

The Structural Complexity Landscape of Finding Balance-Fair Shortest Paths
by: Bentert, Matthias, et al.
Published: (2024)

The Complexity of Finding Local Optima in Contrastive Learning
by: Yan, Jingming, et al.
Published: (2025)

Complexity of Local Search for Euclidean Clustering Problems
by: Manthey, Bodo, et al.
Published: (2023)

Complexity of Finding and Enumerating Interconnection Trees
by: Demange, Noé, et al.
Published: (2026)

The Adaptive Complexity of Finding a Stationary Point
by: Zhou, Huanjian, et al.
Published: (2025)

On the Hardness of Order Finding and Equivalence Testing for ROABPs
by: Ramya, C., et al.
Published: (2025)

The Randomized Query Complexity of Finding a Tarski Fixed Point on the Boolean Hypercube
by: Brânzei, Simina, et al.
Published: (2024)