Cover Image

New Sufficient Algebraic Conditions for Local Consistency over Homogeneous Structures of Finite Duality

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Nagy, Tomáš, Pinsker, Michael, Wrona, Michał
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

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

Constraint Satisfaction Problems over Finitely Bounded Homogeneous Structures: a Dichotomy between FO and L-hard
by: Dorochko, Leonid, et al.
Published: (2026)

Collapsing the bounded width hierarchy for infinite-domain CSPs: when symmetries are enough
by: Mottet, Antoine, et al.
Published: (2021)

An algebraic proof of the dichotomy for graph orientation problems with forbidden tournaments
by: Feller, Roman, et al.
Published: (2024)

The complete classification for quantified equality constraints
by: Zhuk, Dmitriy, et al.
Published: (2021)

Complexity Classes Arising from Circuits over Finite Algebraic Structures
by: Kawałek, Piotr, et al.
Published: (2026)

Strict width for Constraint Satisfaction Problems over homogeneous strucures of finite duality
by: Nagy, Tomáš, et al.
Published: (2024)

Homogeneous Algebraic Complexity Theory and Algebraic Formulas
by: Dutta, Pranjal, et al.
Published: (2023)

VP, VNP and Algebraic Branching Programs over Min-Plus Semirings
by: Komarath, Balagopal, et al.
Published: (2026)

Consistent Query Answering over SHACL Constraints
by: Ahmetaj, Shqiponja, et al.
Published: (2024)

Equations over Finite Monoids with Infinite Promises
by: Larrauri, Alberto, et al.
Published: (2025)

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

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

On Sufficient Conditions for the class $S^*_\cosh\sqrt{z}$
by: Kumar, S. Sivaprasad, et al.
Published: (2023)

Algebraic Pseudorandomness in $VNC^0$
by: Andrews, Robert
Published: (2025)

On the Existence of Algebraic Natural Proofs
by: Chatterjee, Prerona, et al.
Published: (2020)

Local Correction of Linear Functions over the Boolean Cube
by: Amireddy, Prashanth, et al.
Published: (2024)

The Algebraic Cost of a Boolean Sum
by: Orzel, Ian, et al.
Published: (2025)

Symmetric Algebraic Circuits and Homomorphism Polynomials
by: Dawar, Anuj, et al.
Published: (2025)

Algebraic Global Gadgetry for Surjective Constraint Satisfaction
by: Chen, Hubie
Published: (2020)

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

On the Complexity of Pure-State Consistency of Local Density Matrices
by: Kamminga, Jonas, et al.
Published: (2024)

New results in canonical polyadic decomposition over finite fields
by: Yang, Jason
Published: (2025)

Query complexity of Boolean functions on the middle slice of the cube
by: Gerbner, Dániel, et al.
Published: (2023)

Complex Boolean Turing Machines: An Algebraic Semantic Framework for Computational Complexity
by: Zheng, Bojin, et al.
Published: (2026)

Necessary and Sufficient Oracles: Toward a Computational Taxonomy For Reinforcement Learning
by: Rohatgi, Dhruv, et al.
Published: (2025)

Poincaré Duality and Multiplicative Structures on Quantum Codes
by: Li, Yiming, et al.
Published: (2025)

Dual-Tape Perspective and Generator Independence: The Algebraic Foundation of Real Boolean Turing Machines
by: Zheng, Jingwen, et al.
Published: (2026)

Systems of Discrete Differential Equations, Constructive Algebraicity of the Solutions
by: Notarantonio, Hadrien, et al.
Published: (2023)

Precoloring extension with demands on paths
by: Das, Arun Kumar, et al.
Published: (2025)

Local Enumeration and Majority Lower Bounds
by: Gurumukhani, Mohit, et al.
Published: (2024)

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

AC^0[p]-Frege Cannot Efficiently Prove that Constant-Depth Algebraic Circuit Lower Bounds are Hard
by: Lu, Jiaqi, et al.
Published: (2025)

Simple Linear Loops: Algebraic Invariants and Applications
by: Manssour, Rida Ait El, et al.
Published: (2024)

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

Information-Based Complexity vs Computational Complexity in Phaseless Polynomial Interpolation
by: Przybyłek, Michał R., et al.
Published: (2026)

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

Deterministic Hardness of Approximation For SVP in all Finite $\ell_p$ Norms
by: Hair, Isaac M, et al.
Published: (2026)

On the Complexity of Target Set Selection in Simple Geometric Networks
by: Dvořák, Michal, et al.
Published: (2023)

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