Image de couverture de livre

The complexity of finding coset-generating polymorphisms and the promise metaproblem

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Bodirsky, Manuel, Weiß, Armin
Format:	Preprint
Publié:	2026
Sujets:	Computational Complexity Rings and Algebras F.2.2
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

A Complexity Dichotomy for Temporal Valued Constraint Satisfaction Problems
par: Bodirsky, Manuel, et autres
Publié: (2024)

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

Symmetric Linear Arc Monadic Datalog and Gadget Reductions
par: Bodirsky, Manuel, et autres
Publié: (2024)

Notes on CSPs and Polymorphisms
par: Brady, Zarathustra
Publié: (2022)

Thin Tree Verification is coNP-Complete
par: Moayyedi, Alice
Publié: (2025)

When Does Sparsity Help for k-Independent Set in Hypergraphs and Other Boolean CSPs?
par: Fritsch, Timo, et autres
Publié: (2026)

NP-Completeness Proofs of Puzzles using the T-Metacell Framework
par: Kiatchaipipat, Nattapol, et autres
Publié: (2025)

Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs
par: Gupta, Chetan, et autres
Publié: (2025)

Fast Simulation of Cellular Automata by Self-Composition
par: Natal, Joseph, et autres
Publié: (2024)

A Polynomial Time Algorithm for 3SAT
par: Quigley, Robert
Publié: (2024)

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

Approximate all-pairs Hamming distances and 0-1 matrix multiplication
par: Kowaluk, Miroslaw, et autres
Publié: (2025)

Direct Sums for Parity Decision Trees
par: Besselman, Tyler, et autres
Publié: (2024)

A CSP approach to Graph Sandwich Problems
par: Bodirsky, Manuel, et autres
Publié: (2025)

Simplified Algorithmic Metatheorems Beyond MSO: Treewidth and Neighborhood Diversity
par: Knop, Dušan, et autres
Publié: (2017)

The framework to unify all complexity dichotomy theorems for Boolean tensor networks
par: Xia, Mingji
Publié: (2026)

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

The Complexity of Resilience Problems via Valued Constraint Satisfaction
par: Bodirsky, Manuel, et autres
Publié: (2023)

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

Efficient Compression in Semigroups
par: Thumm, Alexander, et autres
Publié: (2026)

Ordered semigroups and ideal categories of principal ideal rings
par: Minnumol, P. K., et autres
Publié: (2026)

On the Complexity of Determinations
par: Hellerstein, Joseph M.
Publié: (2026)

A Compendium of Subset Search Problems and Reductions relating to the Parsimonious Property
par: Bartlett, Celina Janet
Publié: (2025)

A Fine-Grained Complexity View on Propositional Abduction -- Algorithms and Lower Bounds
par: Lagerkvist, Victor, et autres
Publié: (2025)

Liquid Amortization: Proving Amortized Complexity with LiquidHaskell (Functional Pearl)
par: van Brügge, Jan
Publié: (2024)

On Minimum Maximal Distance-k Matchings
par: Kartynnik, Yury, et autres
Publié: (2016)

Graph Threading with Turn Costs
par: Demaine, Erik D., et autres
Publié: (2024)

Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices
par: Dvořák, Pavel, et autres
Publié: (2017)

Realizing temporal graphs from fastest travel times
par: Klobas, Nina, et autres
Publié: (2023)

A Piecewise Approach for the Analysis of Exact Algorithms
par: Clinch, Katie, et autres
Publié: (2024)

Proving Unsatisfiability with Hitting Formulas
par: Filmus, Yuval, et autres
Publié: (2023)

Lower Bounds for CSP Hierarchies Through Ideal Reduction
par: Conneryd, Jonas, et autres
Publié: (2025)

On Solving Problems of Substantially Super-linear Complexity in $N^{o(1)}$ Rounds in the MPC Model
par: Lingas, Andrzej
Publié: (2026)

Complexity Classification Transfer for CSPs via Algebraic Products
par: Bodirsky, Manuel, et autres
Publié: (2022)

Conservative Maltsev Constraint Satisfaction Problems
par: Bodirsky, Manuel, et autres
Publié: (2025)

Complexity of Firefighting on Graphs
par: Althoetmar, Julius, et autres
Publié: (2025)

The Quantum Query Complexity of Finding a Tarski Fixed Point on the 2D Grid
par: Phillips, Reed
Publié: (2026)

The Word Problem for Products of Symmetric Groups
par: Simon, Hans U.
Publié: (2025)

Parameterized Complexity of Biclique Contraction and Balanced Biclique Contraction
par: Krithika, R., et autres
Publié: (2023)

Identity Testing for Circuits with Exponentiation Gates
par: Li, Jiatu, et autres
Publié: (2025)