Image de couverture de livre

Symmetric Linear Arc Monadic Datalog and Gadget Reductions

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Bodirsky, Manuel, Starke, Florian
Format:	Preprint
Publié:	2024
Sujets:	Rings and Algebras Computational Complexity Logic in Computer Science
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Network Satisfaction Problems Solved by k-Consistency
par: Bodirsky, Manuel, et autres
Publié: (2023)

Datalog-Expressibility for Monadic and Guarded Second-Order Logic
par: Bodirsky, Manuel, et autres
Publié: (2020)

Graph Homomorphisms and Universal Algebra
par: Bodirsky, Manuel
Publié: (2026)

The Network Satisfaction Problem for Relation Algebras with at most 4 Atoms
par: Bodirsky, Manuel, et autres
Publié: (2025)

A simplified proof of the CSP Dichotomy Conjecture and XY-symmetric operations
par: Zhuk, Dmitriy
Publié: (2024)

On Deciding the Data Complexity of Answering Linear Monadic Datalog Queries with LTL Operators(Extended Version)
par: Artale, Alessandro, et autres
Publié: (2025)

An algebraic proof of the dichotomy for graph orientation problems with forbidden tournaments
par: Feller, Roman, et autres
Publié: (2024)

The complexity of finding coset-generating polymorphisms and the promise metaproblem
par: Bodirsky, Manuel, et autres
Publié: (2026)

Structures preserved by primitive actions of $S_ω$
par: Bodirsky, Manuel, et autres
Publié: (2025)

From Time to Space: The Impact of Linearity in Higher-Order Datalog
par: Charalambidis, Angelos, et autres
Publié: (2026)

SAT, Gadgets, Max2XOR, and Quantum Annealers
par: Ansótegui, Carlos, et autres
Publié: (2024)

The Power of Negation in Higher-Order Datalog
par: Charalambidis, Angelos, et autres
Publié: (2025)

Local structure of idempotent algebras I
par: Bulatov, Andrei A.
Publié: (2020)

When Darwin met Ianus: dichotomies of expressivity
par: Brunar, Johanna, et autres
Publié: (2025)

Proof Complexity of Linear Logics
par: Tabatabai, Amirhossein Akbar, et autres
Publié: (2026)

Symmetric Proofs in the Ideal Proof System
par: Dawar, Anuj, et autres
Publié: (2025)

Optimal Lower Bounds for Symmetric Modular Circuits
par: Pago, Benedikt
Publié: (2026)

Spectrahedral Shadows and Completely Positive Maps on Real Closed Fields
par: Bodirsky, Manuel, et autres
Publié: (2022)

Formalizing Mason-Stothers Theorem and its Corollaries in Lean 4
par: Baek, Jineon, et autres
Publié: (2024)

The Equational Theories Project: Advancing Collaborative Mathematical Research at Scale
par: Bolan, Matthew, et autres
Publié: (2025)

Formalizing Gröbner Basis Theory in Lean
par: Guo, Junyu, et autres
Publié: (2026)

Specification and Automatic Verification of Computational Reductions
par: Grange, Julien, et autres
Publié: (2024)

Modular Counting CSP: Reductions and Algorithms
par: Kazeminia, Amirhossein, et autres
Publié: (2025)

Termination of Real Linear Loops
par: Neumann, Eike, et autres
Publié: (2026)

On the Descriptive Complexity of Vertex Deletion Problems
par: Bannach, Max, et autres
Publié: (2024)

Undecidability and incompleteness in quantum information theory and operator algebras
par: Goldbring, Isaac
Publié: (2024)

The Descriptive Complexity of Relation Modification Problems
par: Chudigiewitsch, Florian, et autres
Publié: (2026)

The Ideal Membership Problem and Abelian Groups
par: Bulatov, Andrei A., et autres
Publié: (2022)

Polynomial-time Tractable Problems over the $p$-adic Numbers
par: Fehm, Arno, et autres
Publié: (2025)

Functional variant of Polynomial Analogue of Gandy's Fixed Point Theorem
par: Nechesov, Andrey
Publié: (2024)

Feasibly Constructive Proof of Schwartz-Zippel Lemma and the Complexity of Finding Hitting Sets
par: Atserias, Albert, et autres
Publié: (2024)

$Π_{2}^{P}$ vs PSpace Dichotomy for the Quantified Constraint Satisfaction Problem
par: Zhuk, Dmitriy
Publié: (2024)

An order out of nowhere: a new algorithm for infinite-domain CSPs
par: Mottet, Antoine, et autres
Publié: (2023)

The Proof Analysis Problem
par: Arteche, Noel, et autres
Publié: (2025)

Proof complexity of positive branching programs
par: Das, Anupam, et autres
Publié: (2021)

Parallelism and Adaptivity in Student-Teacher Witnessing
par: Ježil, Ondřej, et autres
Publié: (2026)

Effective Versions of Strong Measure Zero
par: Rayman, Matthew
Publié: (2025)

The complete classification for quantified equality constraints
par: Zhuk, Dmitriy, et autres
Publié: (2021)

Meta-Mathematics of Computational Complexity Theory
par: Oliveira, Igor C.
Publié: (2025)

On the consistency of stronger lower bounds for NEXP
par: Thapen, Neil
Publié: (2025)