Copertina

Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Focke, Jacob, Goldberg, Leslie Ann, Roth, Marc, Živný, Stanislav
Natura:	Preprint
Pubblicazione:	2021
Soggetti:	Discrete Mathematics Computational Complexity Databases
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Counting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity
di: Focke, Jacob, et al.
Pubblicazione: (2023)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

A Courcelle-Type Metatheorem for Rank-Bounded Unconstrained Binary Optimization
di: Harary, Marc
Pubblicazione: (2025)

Approximate cycle double cover
di: Ghanbari, Babak, et al.
Pubblicazione: (2025)

Maximal Line Digraphs
di: Japhet, Quentin, et al.
Pubblicazione: (2024)

Counting Locally Optimal Tours in the TSP
di: Manthey, Bodo, et al.
Pubblicazione: (2024)

Hyperplanes Avoiding Problem and Integer Points Counting in Polyhedra
di: Dakhno, Grigorii, et al.
Pubblicazione: (2024)

Infinitely growing configurations in Emil Post's tag system problem
di: Kurilenko, Nikita V.
Pubblicazione: (2021)

On the equivalence of two post-quantum cryptographic families
di: Meneghetti, Alessio, et al.
Pubblicazione: (2021)

On Closure Properties of Read-Once Oblivious Algebraic Branching Programs
di: Armand, Jules, et al.
Pubblicazione: (2025)

On the enumeration of Tarski fixed points
di: Müller, Julian
Pubblicazione: (2023)

Edge-Disjoint Paths in Eulerian Digraphs
di: Cavallaro, Dario, et al.
Pubblicazione: (2024)

Monotone Bounded-Depth Complexity of Homomorphism Polynomials
di: Bhargav, C. S., et al.
Pubblicazione: (2025)

Relations between monotone complexity measures based on decision tree complexity
di: Byramji, Farzan, et al.
Pubblicazione: (2024)

Gap Preserving Reductions Between Reconfiguration Problems
di: Ohsaka, Naoto
Pubblicazione: (2022)

Computational complexity of the Weisfeiler-Leman dimension
di: Lichter, Moritz, et al.
Pubblicazione: (2024)

Gap Amplification for Reconfiguration Problems
di: Ohsaka, Naoto
Pubblicazione: (2023)

Is Graph Local Complementation Inherently Sequential?
di: Concha-Vega, Pablo
Pubblicazione: (2025)

An Algorithm for Monitoring Edge-geodetic Sets in Chordal Graphs
di: Marcille, Clara, et al.
Pubblicazione: (2026)

Enumerating Minimal Defensive Alliances
di: Feng, Zhidan, et al.
Pubblicazione: (2023)

Three Hardness Results for Graph Similarity Problems
di: Sun, He, et al.
Pubblicazione: (2023)

How to Reconfigure Your Alliances
di: Fernau, Henning, et al.
Pubblicazione: (2025)

List Decoding Quotient Reed-Muller Codes
di: Gotlib, Omri, et al.
Pubblicazione: (2025)

Property Testing in Bounded Degree Hypergraphs
di: Aaronson, Hugo, et al.
Pubblicazione: (2025)