Cover Image

The Rise of Plurimorphisms: Algebraic Approach to Approximation

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Barto, Libor, Butti, Silvia, Kazda, Alexandr, Viola, Caterina, Živný, Stanislav
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity Discrete Mathematics Logic in Computer Science
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)

Lower Bounds in Algebraic Complexity via Symmetry and Homomorphism Polynomials
by: Dwivedi, Prateek, et al.
Published: (2026)

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

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

Small unsatisfiable $k$-CNFs with bounded literal occurrence
by: Zhang, Tianwei, et al.
Published: (2024)

Rice-like complexity lower bounds for Boolean and uniform automata networks
by: Goubault-Larrecq, Aliénor, et al.
Published: (2024)

Complexity lower bounds for succinct binary structures of bounded clique-width with restrictions
by: Geniet, Colin, et al.
Published: (2026)

The Unit Gap: How Sharing Works in Boolean Circuits
by: Krinkin, Kirill
Published: (2026)

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

Unifying the Three Algebraic Approaches to the CSP via Minimal Taylor Algebras
by: Barto, Libor, et al.
Published: (2021)

An Algorithmic Meta Theorem for Homomorphism Indistinguishability
by: Seppelt, Tim
Published: (2024)

Restricted CSPs and F-free Digraph Algorithmics
by: Guzmán-Pro, Santiago, et al.
Published: (2025)

Logical Equivalences, Homomorphism Indistinguishability, and Forbidden Minors
by: Seppelt, Tim
Published: (2023)

The Richness of CSP Non-redundancy
by: Brakensiek, Joshua, et al.
Published: (2025)

A Classification of Long-Refinement Graphs for Colour Refinement
by: Kiefer, Sandra, et al.
Published: (2025)

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

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

Computability of extender sets in multidimensional subshifts: asymptotic growths, dynamical constraints
by: Callard, Antonin, et al.
Published: (2024)

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

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)

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

Homomorphism Indistinguishability, Multiplicity Automata Equivalence, and Polynomial Identity Testing
by: Černý, Marek, et al.
Published: (2025)

On Numbers of Simplicial Walks and Equivalent Canonizations for Graph Recognition
by: Černý, Marek
Published: (2026)

Smaller Circuits for Bit Addition
by: Goncharov, Mikhail, et al.
Published: (2025)

Lasserre Hierarchy for Graph Isomorphism and Homomorphism Indistinguishability
by: Roberson, David E., et al.
Published: (2023)

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

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

Graph Homomorphisms and Universal Algebra
by: Bodirsky, Manuel
Published: (2026)

CMSO-transducing tree-like graph decompositions
by: Campbell, Rutger, et al.
Published: (2024)

Weighted basic parallel processes and combinatorial enumeration
by: Clemente, Lorenzo
Published: (2024)

Toward a Uniform Algorithm and Uniform Reduction for Constraint Problems
by: Barto, Libor, et al.
Published: (2026)

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

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

The Sherali-Adams and Weisfeiler-Leman hierarchies in (Promise Valued) Constraint Satisfaction Problems
by: Barto, Libor, et al.
Published: (2024)

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

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

Symmetric Arithmetic Circuits
by: Dawar, Anuj, et al.
Published: (2020)

Lower Bounds for Symmetric Circuits for the Determinant
by: Dawar, Anuj, et al.
Published: (2021)

Logic-based analogical proportions
by: Antić, Christian
Published: (2024)