:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Author:	Chen, Hubie
Format:	Preprint
Published:	2020
Subjects:	Computational Complexity
Online Access:	https://arxiv.org/abs/2005.11307
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

Singleton algorithms for the Constraint Satisfaction Problem
by: Zhuk, Dmitriy
Published: (2025)

List Locally Surjective Homomorphisms in Hereditary Graph Classes
by: Dvořák, Pavel, et al.
Published: (2022)

Limitations of Affine Integer Relaxations for Solving Constraint Satisfaction Problems
by: Lichter, Moritz, et al.
Published: (2024)

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

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

The Constraint Satisfaction Problem Over Multisorted Cores
by: Delic, Dejan, et al.
Published: (2025)

On Classifying Continuous Constraint Satisfaction Problems
by: Miltzow, Tillmann, et al.
Published: (2021)

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

On the Constant-Factor Approximability of Minimum Cost Constraint Satisfaction Problems
by: DeHaan, Ian, et al.
Published: (2025)

Complexity Classification of Complex-Weighted Counting Acyclic Constraint Satisfaction Problems
by: Yamakami, Tomoyuki
Published: (2024)

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

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

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

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)

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

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

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

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

New Sufficient Algebraic Conditions for Local Consistency over Homogeneous Structures of Finite Duality
by: Nagy, Tomáš, 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)

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

Towards Geometry-Preserving Reductions Between Constraint Satisfaction Problems (and other problems in NP)
by: Istrate, Gabriel
Published: (2024)

Realizing Graphs with Cut Constraints
by: Silva, Lucas de Oliveira, et al.
Published: (2025)

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

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

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

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

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

An Unconditional Barrier for Proving Multilinear Algebraic Branching Program Lower Bounds
by: Kush, Deepanshu
Published: (2026)

The Network Satisfaction Problem for Relation Algebras with at most 4 Atoms
by: Bodirsky, Manuel, et al.
Published: (2025)

Query Lower Bounds for Correlation Clustering under Memory Constraints
by: Garg, Sumegha, et al.
Published: (2026)

Network Satisfaction Problems Solved by k-Consistency
by: Bodirsky, Manuel, et al.
Published: (2023)

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

Maximizing Phylogenetic Diversity under Ecological Constraints: A Parameterized Complexity Study
by: Komusiewicz, Christian, et al.
Published: (2024)

Conservative Maltsev Constraint Satisfaction Problems
by: Bodirsky, Manuel, et al.
Published: (2025)

CSPs with Few Alien Constraints
by: Jonsson, Peter, et al.
Published: (2024)

Near-Optimal Encodings of Cardinality Constraints
by: Krapivin, Andrew, et al.
Published: (2026)

A Complexity Dichotomy for Temporal Valued Constraint Satisfaction Problems
by: Bodirsky, Manuel, et al.
Published: (2024)