Cover Image

Counting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Focke, Jacob, Goldberg, Leslie Ann, Roth, Marc, Živný, Stanislav
Format:	Preprint
Published:	2023
Subjects:	Discrete Mathematics Databases
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

The Weisfeiler-Leman Dimension of Conjunctive Queries
by: Göbel, Andreas, et al.
Published: (2023)

Counting Subgraphs in Somewhere Dense Graphs
by: Bressan, Marco, et al.
Published: (2022)

The Selection Problem in Multi-Query Optimization: a Comprehensive Survey
by: Zinchenko, Sergey, et al.
Published: (2024)

Additive Sparsification of CSPs
by: Pelleg, Eden, et al.
Published: (2021)

Hierarchies of Minion Tests for PCSPs through Tensors
by: Ciardo, Lorenzo, et al.
Published: (2022)

Optimal Inapproximability of Promise Equations over Finite Groups
by: Butti, Silvia, et al.
Published: (2024)

An approximation algorithm for Maximum DiCut vs. Cut
by: Nakajima, Tamio-Vesa, et al.
Published: (2024)

Complexity of approximate conflict-free, linearly-ordered, and nonmonochromatic hypergraph colourings
by: Nakajima, Tamio-Vesa, et al.
Published: (2025)

A Strongly Polynomial-Time Algorithm for Weighted General Factors with Three Feasible Degrees
by: Shao, Shuai, et al.
Published: (2023)

Approximate Graph Colouring and the Crystal with a Hollow Shadow
by: Ciardo, Lorenzo, et al.
Published: (2022)

The periodic structure of local consistency
by: Ciardo, Lorenzo, et al.
Published: (2024)

Numbering Combinations for Compact Representation of Many-to-Many Relationship Sets
by: Tomovic, Savo
Published: (2025)

Improving Data Cleaning Using Discrete Optimization
by: Smith, Kenneth, et al.
Published: (2024)

Sampling from the random cluster model on random regular graphs at all temperatures via Glauber dynamics
by: Galanis, Andreas, et al.
Published: (2023)

Logarithmic Mixing of Random Walks on Dynamical Random Cluster Models
by: Galanis, Andreas, et al.
Published: (2026)

Maximum $k$- vs. $\ell$-colourings of graphs
by: Nakajima, Tamio-Vesa, et al.
Published: (2023)

On the complexity of symmetric vs. functional PCSPs
by: Nakajima, Tamio-Vesa, et al.
Published: (2022)

A Dichotomy for Maximum PCSPs on Graphs
by: Nakajima, Tamio-Vesa, et al.
Published: (2024)

Relational Algebras for Subset Selection and Optimisation
by: Pratten, David Robert, et al.
Published: (2025)

Semidefinite programming and linear equations vs. homomorphism problems
by: Ciardo, Lorenzo, et al.
Published: (2023)

Knowledge management in House of Graphs
by: Devillez, Gauvain, et al.
Published: (2026)

Aspects of Artificial Intelligence: Transforming Machine Learning Systems Naturally
by: Guo, Xiuzhan
Published: (2025)

Inapproximability of the independent set polynomial in the complex plane
by: Bezakova, Ivona, et al.
Published: (2017)

A logarithmic approximation of linearly ordered colourings
by: Håstad, Johan, et al.
Published: (2024)

Decidability of Querying First-Order Theories via Countermodels of Finite Width
by: Feller, Thomas, et al.
Published: (2023)

Instability of backoff protocols with arbitrary arrival rates
by: Goldberg, Leslie Ann, et al.
Published: (2022)

Geometric planted matchings beyond the Gaussian model
by: Schwengber, Lucas da Rocha, et al.
Published: (2024)

Cuts and Gauges for Submodular Width
by: Lanzinger, Matthias
Published: (2026)

The Rise of Plurimorphisms: Algebraic Approach to Approximation
by: Barto, Libor, et al.
Published: (2024)

Strong Sparsification for 1-in-3-SAT via Polynomial Freiman-Ruzsa
by: Bedert, Benjamin, et al.
Published: (2025)

The Instability of all Backoff Protocols
by: Goldberg, Leslie Ann, et al.
Published: (2026)

1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise
by: Ciardo, Lorenzo, et al.
Published: (2023)

Counting Solutions to Conjunctive Queries: Structural and Hybrid Tractability
by: Chen, Hubie, et al.
Published: (2023)

Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: a Labelling Approach
by: Liao, Meihao, et al.
Published: (2025)

A Parametrized Complexity View on Robust Scheduling with Budgeted Uncertainty
by: Goldberg, Noam, et al.
Published: (2026)

Isolated Suborders and their Application to Counting Closure Operators
by: Glück, Roland
Published: (2023)

Tractability Frontiers of the Shapley Value for Aggregate Conjunctive Queries
by: Standke, Christoph, et al.
Published: (2025)

Near-optimal edge partitioning via intersecting families
by: Yakunin, Alexander, et al.
Published: (2025)

Counting Tree-Like Multigraphs with a Given Number of Vertices and Multiple Edges
by: Ilyas, Muhammad, et al.
Published: (2025)