Joshua Brakensiek ; Venkatesan Guruswami ; Sai Sandeep - Conditional Dichotomy of Boolean Ordered Promise CSPs

theoretics:8967 - TheoretiCS, January 25, 2023, Volume 2 - https://doi.org/10.46298/theoretics.23.2
Conditional Dichotomy of Boolean Ordered Promise CSPsArticle

Authors: Joshua Brakensiek ; Venkatesan Guruswami ; Sai Sandeep

    Promise Constraint Satisfaction Problems (PCSPs) are a generalization of Constraint Satisfaction Problems (CSPs) where each predicate has a strong and a weak form and given a CSP instance, the objective is to distinguish if the strong form can be satisfied vs. even the weak form cannot be satisfied. Since their formal introduction by Austrin, Guruswami, and H\aa stad, there has been a flurry of works on PCSPs [BBKO19,KO19,WZ20]. The key tool in studying PCSPs is the algebraic framework developed in the context of CSPs where the closure properties of the satisfying solutions known as the polymorphisms are analyzed. The polymorphisms of PCSPs are much richer than CSPs. In the Boolean case, we still do not know if dichotomy for PCSPs exists analogous to Schaefer's dichotomy result for CSPs. In this paper, we study a special case of Boolean PCSPs, namely Boolean Ordered PCSPs where the Boolean PCSPs have the predicate $x \leq y$. In the algebraic framework, this is the special case of Boolean PCSPs when the polymorphisms are monotone functions. We prove that Boolean Ordered PCSPs exhibit a computational dichotomy assuming the Rich 2-to-1 Conjecture [BKM21] which is a perfect completeness surrogate of the Unique Games Conjecture. Assuming the Rich 2-to-1 Conjecture, we prove that a Boolean Ordered PCSP can be solved in polynomial time if for every $\epsilon>0$, it has polymorphisms where each coordinate has Shapley value at most $\epsilon$, else it is NP-hard. The algorithmic part of our dichotomy is based on a structural lemma that Boolean monotone functions with each coordinate having low Shapley value have arbitrarily large threshold functions as minors. The hardness part proceeds by showing that the Shapley value is consistent under a uniformly random 2-to-1 minor. Of independent interest, we show that the Shapley value can be inconsistent under an adversarial 2-to-1 minor.


    Volume: Volume 2
    Published on: January 25, 2023
    Accepted on: December 16, 2022
    Submitted on: January 19, 2022
    Keywords: Computer Science - Computational Complexity,Computer Science - Logic in Computer Science
    Funding:
      Source : OpenAIRE Graph
    • CIF: Medium: Collaborative Research: Frontiers in coding for cloud storage systems; Funder: National Science Foundation; Code: 1563742
    • AF: Small: The Polymorphic Gateway between Structure and Algorithms: Beyond CSP Dichotomy; Funder: National Science Foundation; Code: 1908125

    3 Documents citing this article

    Consultation statistics

    This page has been seen 376 times.
    This article's PDF has been downloaded 245 times.