Optimal inapproximability with universal factor graphs
2021 (English)In: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, Association for Computing Machinery , 2021, p. 434-453Conference paper, Published paper (Refereed)
Abstract [en]
The factor graph of an instance of a constraint satisfaction problem (CSP) is the bipartite graph indicating which variables appear in each constraint. An instance of the CSP is given by the factor graph together with a list of which predicate is applied for each constraint. We establish that many Max-CSPs remain as hard to approximate as in the general case even when the factor graph is fixed (depending only on the size of the instance) and known in advance. Examples of results obtained for this restricted setting are: 1. Optimal inapproximability for Max-3-Lin and Max-3-Sat (Håstad, J. ACM 2001). 2. Approximation resistance for predicates supporting pairwise independent subgroups (Chan, J. ACM 2016). 3. Hardness of the “(2 + ε)-Sat” problem and other Promise CSPs (Austrin et al., SIAM J. Comput. 2017). The main technical tool used to establish these results is a new way of folding the long code which we call “functional folding”.
Place, publisher, year, edition, pages
Association for Computing Machinery , 2021. p. 434-453
Keywords [en]
Optimization, Bipartite graphs, Factor graphs, Long codes, Optimal inapproximability, Technical tools, Constraint satisfaction problems
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:kth:diva-309245Scopus ID: 2-s2.0-85105336082OAI: oai:DiVA.org:kth-309245DiVA, id: diva2:1640679
Conference
32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, 10 January 2021 through 13 January 2021, Alexandria, Virtual
Note
QC 20220225
Part of proceedings ISBN: 9781611976465
2022-02-252022-02-252022-06-25Bibliographically approved