Cover Image

Equations over Finite Monoids with Infinite Promises

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Larrauri, Alberto, Mottet, Antoine, Živný, Stanislav
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

Solving promise equations over monoids and groups
by: Larrauri, Alberto, et al.
Published: (2024)

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

New Algorithms and Hardness Results for Robust Satisfiability of (Promise) CSPs
by: Brakensiek, Joshua, et al.
Published: (2026)

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)

Satisfiability of commutative vs. non-commutative CSPs
by: Bulatov, Andrei A., et al.
Published: (2024)

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

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)

An order out of nowhere: a new algorithm for infinite-domain CSPs
by: Mottet, Antoine, et al.
Published: (2023)

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

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

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

Optimal Inapproximability of Generalized Linear Equations over a Finite Group
by: Bhangale, Amey, et al.
Published: (2026)

Quantum Polymorphisms and the Complexity of Quantum Constraint Satisfaction
by: Ciardo, Lorenzo, et al.
Published: (2025)

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

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

Ineffectiveness for Search and Undecidability of PCSP Meta-Problems
by: Larrauri, Alberto
Published: (2025)

On the Usefulness of Promises
by: Austrin, Per, et al.
Published: (2025)

Low-Rank Tensor Decomposition over Finite Fields
by: Yang, Jason
Published: (2024)

New Sufficient Algebraic Conditions for Local Consistency over Homogeneous Structures of Finite Duality
by: Nagy, Tomáš, et al.
Published: (2025)

Inconsistency Probability of Sparse Equations over F2
by: Horak, P., et al.
Published: (2026)

Strong Inapproximability for a Promise Rank Problem
by: Guruswami, Venkatesan, et al.
Published: (2026)

Solving Polynomial Equations Over Finite Fields
by: Dell, Holger, et al.
Published: (2024)

Finitely (In)tractable Promise Constraint Satisfaction Problems
by: Asimi, Kristina, et al.
Published: (2020)

The Complexity of Promise Constraint Satisfaction Problem Seen from the Other Side
by: Asimi, Kristina, et al.
Published: (2024)

Complexity of Planar Graph Orientation Consistency, Promise-Inference, and Uniqueness, with Applications to Minesweeper Variants
by: MIT Hardness Group, et al.
Published: (2024)

Complexity Theory for Quantum Promise Problems
by: Chia, Nai-Hui, et al.
Published: (2024)

Edge-coloring problems with forbidden patterns and planted colors
by: Barsukov, Alexey, et al.
Published: (2025)

Discrete Homotopy and Promise Constraint Satisfaction Problem
by: Beikmohammadi, Arash, et al.
Published: (2025)

Proportionally dense subgraphs of maximum size in degree-constrained graphs
by: Baghirova, Narmina, et al.
Published: (2024)

Attacking the Polynomials in the Maze of Finite Fields problem
by: Barbero, Àngela, et al.
Published: (2026)

Automated Lower Bounds for Small Matrix Multiplication Complexity over Finite Fields
by: Wang, Chengu
Published: (2026)

Complexity Classification Transfer for CSPs via Algebraic Products
by: Bodirsky, Manuel, et al.
Published: (2022)

Parks: A Doubly Infinite Family of NP-Complete Puzzles and Generalizations of A002464
by: Minevich, Igor, et al.
Published: (2024)

Lower Bounds against the Ideal Proof System in Finite Fields
by: Elbaz, Tal, et al.
Published: (2025)

Complexity Theory meets Ordinary Differential Equations
by: Fono, Adalbert, et al.
Published: (2026)