Buchumschlag

Algebraic Global Gadgetry for Surjective Constraint Satisfaction

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
1. Verfasser:	Chen, Hubie
Format:	Preprint
Veröffentlicht:	2020
Schlagworte:	Computational Complexity
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Jaguar: A Primal Algorithm for Conjunctive Query Evaluation in Submodular-Width Time
von: Khamis, Mahmoud Abo, et al.
Veröffentlicht: (2026)

Limitations of Affine Integer Relaxations for Solving Constraint Satisfaction Problems
von: Lichter, Moritz, et al.
Veröffentlicht: (2024)

Singleton algorithms for the Constraint Satisfaction Problem
von: Zhuk, Dmitriy
Veröffentlicht: (2025)

List Locally Surjective Homomorphisms in Hereditary Graph Classes
von: Dvořák, Pavel, et al.
Veröffentlicht: (2022)

The Complexity of Promise Constraint Satisfaction Problem Seen from the Other Side
von: Asimi, Kristina, et al.
Veröffentlicht: (2024)

Discrete Homotopy and Promise Constraint Satisfaction Problem
von: Beikmohammadi, Arash, et al.
Veröffentlicht: (2025)

The Constraint Satisfaction Problem Over Multisorted Cores
von: Delic, Dejan, et al.
Veröffentlicht: (2025)

$Π_{2}^{P}$ vs PSpace Dichotomy for the Quantified Constraint Satisfaction Problem
von: Zhuk, Dmitriy
Veröffentlicht: (2024)

On the Existence of Algebraic Natural Proofs
von: Chatterjee, Prerona, et al.
Veröffentlicht: (2020)

On Classifying Continuous Constraint Satisfaction Problems
von: Miltzow, Tillmann, et al.
Veröffentlicht: (2021)

Algebraic Pseudorandomness in $VNC^0$
von: Andrews, Robert
Veröffentlicht: (2025)

The Algebraic Cost of a Boolean Sum
von: Orzel, Ian, et al.
Veröffentlicht: (2025)

Symmetric Algebraic Circuits and Homomorphism Polynomials
von: Dawar, Anuj, et al.
Veröffentlicht: (2025)

On the Constant-Factor Approximability of Minimum Cost Constraint Satisfaction Problems
von: DeHaan, Ian, et al.
Veröffentlicht: (2025)

Complexity Classification of Complex-Weighted Counting Acyclic Constraint Satisfaction Problems
von: Yamakami, Tomoyuki
Veröffentlicht: (2024)

Finitely (In)tractable Promise Constraint Satisfaction Problems
von: Asimi, Kristina, et al.
Veröffentlicht: (2020)

Complex Boolean Turing Machines: An Algebraic Semantic Framework for Computational Complexity
von: Zheng, Bojin, et al.
Veröffentlicht: (2026)

VP, VNP and Algebraic Branching Programs over Min-Plus Semirings
von: Komarath, Balagopal, et al.
Veröffentlicht: (2026)

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

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

Systems of Discrete Differential Equations, Constructive Algebraicity of the Solutions
von: Notarantonio, Hadrien, et al.
Veröffentlicht: (2023)

Realizing Graphs with Cut Constraints
von: Silva, Lucas de Oliveira, et al.
Veröffentlicht: (2025)

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

Simple Linear Loops: Algebraic Invariants and Applications
von: Manssour, Rida Ait El, et al.
Veröffentlicht: (2024)

Quantum Polymorphisms and the Complexity of Quantum Constraint Satisfaction
von: Ciardo, Lorenzo, et al.
Veröffentlicht: (2025)

Consistent Query Answering over SHACL Constraints
von: Ahmetaj, Shqiponja, et al.
Veröffentlicht: (2024)

Query Lower Bounds for Correlation Clustering under Memory Constraints
von: Garg, Sumegha, et al.
Veröffentlicht: (2026)

On Closure Properties of Read-Once Oblivious Algebraic Branching Programs
von: Armand, Jules, et al.
Veröffentlicht: (2025)

Unifying the Three Algebraic Approaches to the CSP via Minimal Taylor Algebras
von: Barto, Libor, et al.
Veröffentlicht: (2021)

Towards Geometry-Preserving Reductions Between Constraint Satisfaction Problems (and other problems in NP)
von: Istrate, Gabriel
Veröffentlicht: (2024)

An Unconditional Barrier for Proving Multilinear Algebraic Branching Program Lower Bounds
von: Kush, Deepanshu
Veröffentlicht: (2026)

Maximizing Phylogenetic Diversity under Ecological Constraints: A Parameterized Complexity Study
von: Komusiewicz, Christian, et al.
Veröffentlicht: (2024)

The Rise of Plurimorphisms: Algebraic Approach to Approximation
von: Barto, Libor, et al.
Veröffentlicht: (2024)

The Network Satisfaction Problem for Relation Algebras with at most 4 Atoms
von: Bodirsky, Manuel, et al.
Veröffentlicht: (2025)

CSPs with Few Alien Constraints
von: Jonsson, Peter, et al.
Veröffentlicht: (2024)

Near-Optimal Encodings of Cardinality Constraints
von: Krapivin, Andrew, et al.
Veröffentlicht: (2026)

Network Satisfaction Problems Solved by k-Consistency
von: Bodirsky, Manuel, et al.
Veröffentlicht: (2023)

Homogeneous Algebraic Complexity Theory and Algebraic Formulas
von: Dutta, Pranjal, et al.
Veröffentlicht: (2023)

Committee Elections with Candidate Attribute Constraints
von: Zhou, Aizhong, et al.
Veröffentlicht: (2024)

Classifying Entanglement by Algebraic Geometry
von: Gharahi, Masoud
Veröffentlicht: (2024)