{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,3]],"date-time":"2025-12-03T17:04:41Z","timestamp":1764781481801,"version":"3.46.0"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2025,7,22]],"date-time":"2025-07-22T00:00:00Z","timestamp":1753142400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,7,22]],"date-time":"2025-07-22T00:00:00Z","timestamp":1753142400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2025,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    We consider the\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$P$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mi>P<\/mml:mi>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    -CSP problem for 3-ary predicates\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$P$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mi>P<\/mml:mi>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    on satisfiable instances. We show that under certain conditions on\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$P$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mi>P<\/mml:mi>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    and a\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$(1,s)$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:mn>1<\/mml:mn>\n                            <mml:mo>,<\/mml:mo>\n                            <mml:mi>s<\/mml:mi>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    integrality gap instance of the\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$P$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mi>P<\/mml:mi>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    -CSP problem, it can be translated into a dictatorship vs. quasirandomness test with perfect completeness and soundness\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$s+\\epsilon$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>s<\/mml:mi>\n                            <mml:mo>+<\/mml:mo>\n                            <mml:mi>\u03f5<\/mml:mi>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    , for every constant\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\epsilon&gt;0$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>\u03f5<\/mml:mi>\n                            <mml:mo>&gt;<\/mml:mo>\n                            <mml:mn>0<\/mml:mn>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    . Compared to Ragahvendra (in: Proceedings of the fortieth annual ACM\nsymposium on theory of computing (STOC), pp 245\u2013254, 2008), we do not lose perfect completeness. This is particularly interesting as this test implies new hardness results on satisfiable constraint satisfaction problems, assuming the Rich 2-to-1 Games Conjecture by Braverman et al. (in: Lee JR (ed) Volume 185 of Leibniz international proceedings\nin informatics (LIPIcs), 27:1\u201327:20. Schloss Dagstuhl\u2013Leibniz-Zentrum\nf\u00fcr Informatik, Dagstuhl, 2021b.\n                    <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"https:\/\/drops.dagstuhl.de\/opus\/volltexte\/2021\/13566\" ext-link-type=\"uri\">https:\/\/drops.dagstuhl.de\/opus\/volltexte\/2021\/13566<\/jats:ext-link>\n                    ).Our result can be seen as the first step of a potentially long-term challenging program of characterizing optimal inapproximability of every satisfiable\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$k$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mi>k<\/mml:mi>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    -ary  CSP.\n                  <\/jats:p>\n                  <jats:p>At the heart of the reduction is our main analytical lemma for a class of 3-ary predicates, which is a generalization of a lemma by  Mossel (Geom Funct Anal 19(6):1713\u20131756, 2010). The lemma and a further generalization of it that we conjecture may be of independent interest.<\/jats:p>","DOI":"10.1007\/s00037-025-00267-6","type":"journal-article","created":{"date-parts":[[2025,7,22]],"date-time":"2025-07-22T03:46:20Z","timestamp":1753155980000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On approximability of Satisfiable $$k$$-CSPs: I"],"prefix":"10.1007","volume":"34","author":[{"given":"Amey","family":"Bhangale","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Subhash","family":"Khot","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dor","family":"Minzer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,7,22]]},"reference":[{"key":"267_CR1","doi-asserted-by":"crossref","unstructured":"Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan\n& Mario Szegedy (1998). Proof Verification and the Hardness\nof Approximation Problems. J. ACM 45(3), 501\u2013555. (Preliminary\nversion in 33rd FOCS, 1992).","DOI":"10.1145\/278298.278306"},{"key":"267_CR2","doi-asserted-by":"crossref","unstructured":"Sanjeev Arora & Shmuel Safra (1998). Probabilistic Checking\nof Proofs: A New Characterization of NP. J. ACM 45(1), 70\u2013122.\n(Preliminary version in 33rd FOCS, 1992).","DOI":"10.1145\/273865.273901"},{"key":"267_CR3","doi-asserted-by":"crossref","unstructured":"Per Austrin & Elchanan Mossel (2009). Approximation resistant\npredicates from pairwise independence. Computational Complexity\n18(2), 249\u2013271.","DOI":"10.1007\/s00037-009-0272-6"},{"key":"267_CR4","doi-asserted-by":"crossref","unstructured":"Amey Bhangale & Subhash Khot (2021). Optimal Inapproximability\nof Satisfiable K-LIN over Non-Abelian Groups. In Proceedings of\nthe 53rd Annual ACM SIGACT Symposium on Theory of Computing,\nSTOC 2021, 1615-1628. Association for Computing Machinery, New\nYork, NY, USA. ISBN 9781450380539. URL https:\/\/doi.org\/10.1145\/3406325.3451003.","DOI":"10.1145\/3406325.3451003"},{"key":"267_CR5","doi-asserted-by":"crossref","unstructured":"Mark Braverman, Subhash Khot, Noam Lifshitz & Dor\nMinzer (2021a). An Invariance Principle for the Multi-slice, with Applications.\nIn 62nd IEEE Annual Symposium on Foundations of Computer\nScience (FOCS), 228\u2013236.","DOI":"10.1109\/FOCS52979.2021.00030"},{"key":"267_CR6","unstructured":"Mark Braverman, Subhash Khot & Dor Minzer (2021b). On\nRich 2-to-1 Games. In 12th Innovations in Theoretical Computer Science\nConference (ITCS 2021), James R. Lee, editor, volume 185 of\nLeibniz International Proceedings in Informatics (LIPIcs), 27:1\u201327:20.\nSchloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany.\nISBN 978-3-95977-177-1. ISSN 1868-8969. URL https:\/\/drops.dagstuhl.de\/opus\/volltexte\/2021\/13566."},{"key":"267_CR7","doi-asserted-by":"crossref","unstructured":"Andrei A. Bulatov (2017). A Dichotomy Theorem for Nonuniform\nCSPs. In 58th IEEE Annual Symposium on Foundations of Computer\nScience (FOCS), 319\u2013330.","DOI":"10.1109\/FOCS.2017.37"},{"key":"267_CR8","doi-asserted-by":"crossref","unstructured":"Fan Chung (2005). Laplacians and the Cheeger inequality for directed\ngraphs. Annals of Combinatorics 9, 1\u201319.","DOI":"10.1007\/s00026-005-0237-z"},{"key":"267_CR9","doi-asserted-by":"crossref","unstructured":"Persi Diaconis (1998). Group representations in probability and\nstatistics, volume 11 of IMS Lecture Notes Monogr. Ser. Institute\nof Mathematical Statistics. URL https:\/\/doi.org\/10.1214\/lnms\/1215467411.","DOI":"10.1214\/lnms\/1215467411"},{"key":"267_CR10","doi-asserted-by":"crossref","unstructured":"Toms Feder & Moshe Y. Vardi (1998). The Computational Structure\nof Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory. SIAM Journal on Computing\n28(1), 57\u2013104.","DOI":"10.1137\/S0097539794266766"},{"key":"267_CR11","doi-asserted-by":"crossref","unstructured":"Uriel Feige, Shafi Goldwasser, Laszlo Lov\u00e1sz, Shmuel Safra\n& Mario Szegedy (1996). Interactive proofs and the hardness of\napproximating cliques. Journal of the ACM (JACM) 43(2), 268\u2013292.","DOI":"10.1145\/226643.226652"},{"key":"267_CR12","doi-asserted-by":"crossref","unstructured":"Michel X. Goemans & David P. Williamson (1995). Improved Approximation\nAlgorithms for Maximum Cut and Satisfiability Problems\nUsing Semidefinite Programming. J. ACM 42(6), 1115-1145. ISSN\n0004-5411.","DOI":"10.1145\/227683.227684"},{"key":"#cr-split#-267_CR13.1","doi-asserted-by":"crossref","unstructured":"Johan H\u00e5stad (2001). Some optimal inapproximability results. J.","DOI":"10.1145\/502090.502098"},{"key":"#cr-split#-267_CR13.2","unstructured":"ACM 48(4), 798-859. (Preliminary version in 29th STOC, 1997)."},{"key":"267_CR14","doi-asserted-by":"crossref","unstructured":"Subhash Khot (2002). On the power of unique 2-prover 1-round\ngames. In Proc. 34th Annual ACM symposium on Theory of computing\n(STOC), 767\u2013775. ACM.","DOI":"10.1145\/509907.510017"},{"key":"267_CR15","doi-asserted-by":"crossref","unstructured":"Subhash Khot, Guy Kindler, Elchanan Mossel & Ryan ODonnell\n(2007). Optimal Inapproximability Results for MAXCUT and\nOther 2-Variable CSPs? SIAM Journal on Computing 37(1), 319\u2013357.","DOI":"10.1137\/S0097539705447372"},{"key":"267_CR16","doi-asserted-by":"crossref","unstructured":"Elchanan Mossel (2010). Gaussian bounds for noise correlation of\nfunctions. Geometric and Functional Analysis 19(6), 1713\u20131756.","DOI":"10.1007\/s00039-010-0047-x"},{"key":"267_CR17","doi-asserted-by":"crossref","unstructured":"Elchanan Mossel, Ryan O\u2019Donnell & Krzysztof Oleszkiewicz\n(2005). Noise stability of functions with low influences: invariance and\noptimality. In Proc. 46th Annual IEEE Symposium on Foundations of\nComputer Science (FOCS), 21\u201330. IEEE.","DOI":"10.1109\/SFCS.2005.53"},{"key":"267_CR18","doi-asserted-by":"crossref","unstructured":"Prasad Raghavendra (2008). Optimal algorithms and inapproximability\nresults for every CSP? In Proceedings of the fortieth annual ACM\nsymposium on Theory of computing (STOC), 245\u2013254.","DOI":"10.1145\/1374376.1374414"},{"key":"267_CR19","unstructured":"Prasad Raghavendra (2009). Approximating np-hard problems efficient\nalgorithms and their limits. University of Washington."},{"key":"267_CR20","doi-asserted-by":"crossref","unstructured":"Thomas J. Schaefer (1978). The Complexity of Satisfiability Problems.\nIn Proceedings of the Tenth Annual ACM Symposium on Theory\nof Computing, STOC \u201978, 216-226. Association for Computing Machinery,\nNew York, NY, USA. ISBN 9781450374378. URL https:\/\/doi.org\/10.1145\/800133.804350.","DOI":"10.1145\/800133.804350"},{"key":"267_CR21","doi-asserted-by":"crossref","unstructured":"Dmitriy Zhuk (2020). A Proof of the CSP Dichotomy Conjecture.\nJ. ACM 67(5). ISSN 0004-5411. URL https:\/\/doi.org\/10.1145\/3402029.","DOI":"10.1145\/3402029"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-025-00267-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00037-025-00267-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-025-00267-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,3]],"date-time":"2025-12-03T17:00:07Z","timestamp":1764781207000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00037-025-00267-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,22]]},"references-count":22,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,12]]}},"alternative-id":["267"],"URL":"https:\/\/doi.org\/10.1007\/s00037-025-00267-6","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"type":"print","value":"1016-3328"},{"type":"electronic","value":"1420-8954"}],"subject":[],"published":{"date-parts":[[2025,7,22]]},"assertion":[{"value":"4 July 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 July 2025","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"8"}}