skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Minimal Taylor Algebras as a Common Framework for the Three Algebraic Approaches to the CSP
This paper focuses on the algebraic theory underlying the study of the complexity and the algorithms for the Constraint Satisfaction Problem (CSP). We unify, simplify, and extend parts of the three approaches that have been developed to study the CSP over finite templates - absorption theory that was used to characterize CSPs solvable by local consistency methods (JACM'14), and Bulatov's and Zhuk's theories that were used for two independent proofs of the CSP Dichotomy Theorem (FOCS'17, JACM'20). As the first contribution we present an elementary theorem about primitive positive definability and use it to obtain the starting points of Bulatov's and Zhuk's proofs as corollaries. As the second contribution we propose and initiate a systematic study of minimal Taylor algebras. This class of algebras is broad enough so that it suffices to verify the CSP Dichotomy Theorem on this class only, but still is unusually well behaved. In particular, many concepts from the three approaches coincide in the class, which is in striking contrast with the general setting. We believe that the theory initiated in this paper will eventually result in a simple and more natural proof of the Dichotomy Theorem that employs a simpler and more efficient algorithm, and will help in attacking complexity questions in other CSP-related problems.  more » « less
Award ID(s):
1705177
PAR ID:
10311165
Author(s) / Creator(s):
; ; ; ;
Date Published:
Journal Name:
2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; (, Münster journal of mathematics)
    Cuntz, Joachim (Ed.)
    Complexity rank for C*-algebras was introduced by the second author and Yu for applications towards the UCT: very roughly, this rank is at most n if you can repeatedly cut the C∗-algebra in half at most n times, and end up with something finite-dimensional. In this paper, we study complexity rank, and also a weak complexity rank that we introduce; having weak complexity rank at most one can be thought of as “two-colored local finite-dimensionality”. We first show that, for separable, unital, and simple C*-algebras, weak complexity rank one is equivalent to the conjunction of nuclear dimension one and real rank zero. In particular, this shows that the UCT for all nuclear C*-algebras is equivalent to equality of the weak complexity rank and the complexity ranks for Kirchberg algebras with zero K-theory groups. However, we also show using a K-theoretic obstruction (torsion in K1) that weak complexity rank one and complexity rank one are not the same in general. We then use the Kirchberg–Phillips classification theorem to compute the complexity rank of all UCT Kirchberg algebras: it equals one when the K1-group is torsion-free, and equals two otherwise. 
    more » « less
  2. ; (, Memoirs of European Mathematical Society)
    The universal coefficient theorem is a fundamental problem in the classification theory for C*-algebras. In this article we develop a quantitative K-homology theory to prove the universal coefficient theorem for C*-algebras with finite complexity. 
    more » « less
  3. ; ; (, Journal of Graph Theory)
    ABSTRACT We study extensions of Turán Theorem in edge‐weighted settings. A particular case of interest is when constraints on the weight of an edge come from the order of the largest clique containing it. These problems are motivated by Ramsey‐Turán type problems. Some of our proofs are based on the method of graph Lagrangians, while the other proofs use flag algebras. Using these results, we prove several new upper bounds on the Ramsey‐Turán density of cliques. Other applications of our results are in a recent paper of Balogh, Chen, McCourt, and Murley. 
    more » « less
  4. ; ; (, Quantum)
    The permanent is pivotal to both complexity theory and combinatorics. In quantum computing, the permanent appears in the expression of output amplitudes of linear optical computations, such as in the Boson Sampling model. Taking advantage of this connection, we give quantum-inspired proofs of many existing as well as new remarkable permanent identities. Most notably, we give a quantum-inspired proof of the MacMahon master theorem as well as proofs for new generalizations of this theorem. Previous proofs of this theorem used completely different ideas. Beyond their purely combinatorial applications, our results demonstrate the classical hardness of exact and approximate sampling of linear optical quantum computations with input cat states. 
    more » « less
  5. ; (, Computational complexity)
    The complexity of graph homomorphism problems has been the subject of intense study for some years. In this paper, we prove a decidable complexity dichotomy theorem for the partition function of directed graph homomorphisms. Our theorem applies to all non-negative weighted forms of the problem: given any fixed matrix A with non-negative algebraic entries, the partition function ZA(G) of directed graph homomorphisms from any directed graph G is either tractable in polynomial time or #P-hard, depending on the matrix A. The proof of the dichotomy theorem is combinatorial, but involves the definition of an infinite family of graph homomorphism problems. The proof of its decidability on the other hand is algebraic and based on properties of polynomials. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email