More Like this

1. On Sketching Approximations for Symmetric Boolean CSPs

   Boyland, Joanna ; Hwang, Michael ; Prasad, Tarun ; Singer, Noah ; Velusamy, Santhoshini ( September 2022 , Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022))

   Chakrabarti, Amit ; Swamy, Chaitanya (Ed.)

   A Boolean maximum constraint satisfaction problem, Max-CSP(f), is specified by a predicate f:{-1,1}^k → {0,1}. An n-variable instance of Max-CSP(f) consists of a list of constraints, each of which applies f to k distinct literals drawn from the n variables. For k = 2, Chou, Golovnev, and Velusamy [Chou et al., 2020] obtained explicit ratios characterizing the √ n-space streaming approximability of every predicate. For k ≥ 3, Chou, Golovnev, Sudan, and Velusamy [Chou et al., 2022] proved a general dichotomy theorem for √ n-space sketching algorithms: For every f, there exists α(f) ∈ (0,1] such that for every ε > 0, Max-CSP(f) is (α(f)-ε)-approximable by an O(log n)-space linear sketching algorithm, but (α(f)+ε)-approximation sketching algorithms require Ω(√n) space. In this work, we give closed-form expressions for the sketching approximation ratios of multiple families of symmetric Boolean functions. Letting α'_k = 2^{-(k-1)} (1-k^{-2})^{(k-1)/2}, we show that for odd k ≥ 3, α(kAND) = α'_k, and for even k ≥ 2, α(kAND) = 2α'_{k+1}. Thus, for every k, kAND can be (2-o(1))2^{-k}-approximated by O(log n)-space sketching algorithms; we contrast this with a lower bound of Chou, Golovnev, Sudan, Velingker, and Velusamy [Chou et al., 2022] implying that streaming (2+ε)2^{-k}-approximations require Ω(n) space! We also resolve the ratio for the "at-least-(k-1)-1’s" function for all even k; the "exactly-(k+1)/2-1’s" function for odd k ∈ {3,…,51}; and fifteen other functions. We stress here that for general f, the dichotomy theorem in [Chou et al., 2022] only implies that α(f) can be computed to arbitrary precision in PSPACE, and thus closed-form expressions need not have existed a priori. Our analyses involve identifying and exploiting structural "saddle-point" properties of this dichotomy. Separately, for all threshold functions, we give optimal "bias-based" approximation algorithms generalizing [Chou et al., 2020] while simplifying [Chou et al., 2022]. Finally, we investigate the √ n-space streaming lower bounds in [Chou et al., 2022], and show that they are incomplete for 3AND, i.e., they fail to rule out (α(3AND})-ε)-approximations in o(√ n) space. 

   more » « less
2. Linear space streaming lower bounds for approximating CSPs

   https://doi.org/10.1145/3519935.3519983  

   Chou, Chi-Ning ; Golovnev, Alexander ; Sudan, Madhu ; Velingker, Ameya ; Velusamy, Santhoshini ( June 2022 , {STOC} '22: 54th Annual {ACM} {SIGACT} Symposium on Theory of Computing)

   Leonardi, Stefano ; Gupta, Anupam (Ed.)

   We consider the approximability of constraint satisfaction problems in the streaming setting. For every constraint satisfaction problem (CSP) on n variables taking values in {0,…,q−1}, we prove that improving over the trivial approximability by a factor of q requires Ω(n) space even on instances with O(n) constraints. We also identify a broad subclass of problems for which any improvement over the trivial approximability requires Ω(n) space. The key technical core is an optimal, q−(k−1)-inapproximability for the Max k-LIN-mod q problem, which is the Max CSP problem where every constraint is given by a system of k−1 linear equations mod q over k variables. Our work builds on and extends the breakthrough work of Kapralov and Krachun (Proc. STOC 2019) who showed a linear lower bound on any non-trivial approximation of the MaxCut problem in graphs. MaxCut corresponds roughly to the case of Max k-LIN-mod q with k=q=2. For general CSPs in the streaming setting, prior results only yielded Ω(√n) space bounds. In particular no linear space lower bound was known for an approximation factor less than 1/2 for any CSP. Extending the work of Kapralov and Krachun to Max k-LIN-mod q to k>2 and q>2 (while getting optimal hardness results) is the main technical contribution of this work. Each one of these extensions provides non-trivial technical challenges that we overcome in this work. 

   more » « less
3. The Quest for Strong Inapproximability Results with Perfect Completeness

   https://doi.org/10.1145/3459668  

   Brakensiek, Joshua ; Guruswami, Venkatesan ( August 2021 , ACM Transactions on Algorithms)

   The Unique Games Conjecture has pinned down the approximability of all constraint satisfaction problems (CSPs), showing that a natural semidefinite programming relaxation offers the optimal worst-case approximation ratio for any CSP. This elegant picture, however, does not apply for CSP instances that are perfectly satisfiable, due to the imperfect completeness inherent in the Unique Games Conjecture. This work is motivated by the pursuit of a better understanding of the approximability of perfectly satisfiable instances of CSPs. We prove that an “almost Unique” version of Label Cover can be approximated within a constant factor on satisfiable instances. Our main conceptual contribution is the formulation of a (hypergraph) version of Label Cover that we call V Label Cover . Assuming a conjecture concerning the inapproximability of V Label Cover on perfectly satisfiable instances, we prove the following implications: • There is an absolute constant c 0 such that for k ≥ 3, given a satisfiable instance of Boolean k -CSP, it is hard to find an assignment satisfying more than c 0 k 2 /2 k fraction of the constraints. • Given a k -uniform hypergraph, k ≥ 2, for all ε > 0, it is hard to tell if it is q -strongly colorable or has no independent set with an ε fraction of vertices, where q =⌈ k +√ k -1/2⌉. • Given a k -uniform hypergraph, k ≥ 3, for all ε > 0, it is hard to tell if it is ( k -1)-rainbow colorable or has no independent set with an ε fraction of vertices. 

   more » « less
4. Triplet Reconstruction and all other Phylogenetic CSPs are Approximation Resistant

   https://doi.org/10.1109/FOCS57990.2023.00024  

   Chatziafratis, Vaggos ; Makarychev, Konstantin ( November 2023 , IEEE)

   We study the natural problem of Triplet Reconstruction (also known as Rooted Triplets Consistency or Triplet Clustering), originally motivated by applications in computational biology and relational databases (Aho, Sagiv, Szymanski, and Ullman, 1981) [2]: given n datapoints, we want to embed them onto the n leaves of a rooted binary tree (also known as a hierarchical clustering, or ultrametric embedding) such that a given set of m triplet constraints is satisfied. A triplet constraint i j · k for points i, j, k indicates that 'i, j are more closely related to each other than to k,' (in terms of distances d(i, j) ≤ d(i, k) and d(i, j) ≤ d(j, k)) and we say that a tree satisfies the triplet i j · k if the distance in the tree between i, j is smaller than the distance between i, k (or j, k). Among all possible trees with n leaves, can we efficiently find one that satisfies a large fraction of the m given triplets? Aho et al. (1981) [2] studied the decision version and gave an elegant polynomial-time algorithm that determines whether or not there exists a tree that satisfies all of the m constraints. Moreover, it is straightforward to see that a random binary tree achieves a constant 13-approximation, since there are only 3 distinct triplets i j|k, i k| j, j k · i (each will be satisfied w.p. 13). Unfortunately, despite more than four decades of research by various communities, there is no better approximation algorithm for this basic Triplet Reconstruction problem.Our main theorem-which captures Triplet Reconstruction as a special case-is a general hardness of approximation result about Constraint Satisfaction Problems (CSPs) over infinite domains (CSPs where instead of boolean values {0,1} or a fixed-size domain, the variables can be mapped to any of the n leaves of a tree). Specifically, we prove that assuming the Unique Games Conjecture [57], Triplet Reconstruction and more generally, every Constraint Satisfaction Problem (CSP) over hierarchies is approximation resistant, i.e., there is no polynomial-time algorithm that does asymptotically better than a biased random assignment.Our result settles the approximability not only for Triplet Reconstruction, but for many interesting problems that have been studied by various scientific communities such as the popular Quartet Reconstruction and Subtree/Supertree Aggregation Problems. More broadly, our result significantly extends the list of approximation resistant predicates by pointing to a large new family of hard problems over hierarchies. Our main theorem is a generalization of Guruswami, Håstad, Manokaran, Raghavendra, and Charikar (2011) [36], who showed that ordering CSPs (CSPs over permutations of n elements, e.g., Max Acyclic Subgraph, Betweenness, Non-Betweenness) are approximation resistant. The main challenge in our analyses stems from the fact that trees have topology (in contrast to permutations and ordering CSPs) and it is the tree topology that determines whether a given constraint on the variables is satisfied or not. As a byproduct, we also present some of the first CSPs where their approximation resistance is proved against biased random assignments, instead of uniformly random assignments. 

   more » « less
5. Conditional Dichotomy of Boolean Ordered Promise CSPs

   https://doi.org/10.46298/theoretics.23.2  

   Brakensiek, Joshua ; Guruswami, Venkatesan ; Sandeep, Sai ( January 2023 , TheoretiCS)

   Promise Constraint Satisfaction Problems (PCSPs) are a generalization ofConstraint Satisfaction Problems (CSPs) where each predicate has a strong and aweak form and given a CSP instance, the objective is to distinguish if thestrong form can be satisfied vs. even the weak form cannot be satisfied. Sincetheir formal introduction by Austrin, Guruswami, and H\aa stad, there has beena flurry of works on PCSPs [BBKO19,KO19,WZ20]. The key tool in studying PCSPsis the algebraic framework developed in the context of CSPs where the closureproperties of the satisfying solutions known as the polymorphisms are analyzed. The polymorphisms of PCSPs are much richer than CSPs. In the Boolean case, westill do not know if dichotomy for PCSPs exists analogous to Schaefer'sdichotomy result for CSPs. In this paper, we study a special case of BooleanPCSPs, namely Boolean Ordered PCSPs where the Boolean PCSPs have the predicate$x \leq y$. In the algebraic framework, this is the special case of BooleanPCSPs when the polymorphisms are monotone functions. We prove that BooleanOrdered PCSPs exhibit a computational dichotomy assuming the Rich 2-to-1Conjecture [BKM21] which is a perfect completeness surrogate of the UniqueGames Conjecture. Assuming the Rich 2-to-1 Conjecture, we prove that a Boolean Ordered PCSP canbe solved in polynomial time if for every $\epsilon>0$, it has polymorphismswhere 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 thatBoolean monotone functions with each coordinate having low Shapley value havearbitrarily large threshold functions as minors. The hardness part proceeds byshowing that the Shapley value is consistent under a uniformly random 2-to-1minor. Of independent interest, we show that the Shapley value can beinconsistent under an adversarial 2-to-1 minor. 

   more » « less