{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:30:02Z","timestamp":1750221002430,"version":"3.41.0"},"reference-count":17,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2019,9,12]],"date-time":"2019-09-12T00:00:00Z","timestamp":1568246400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Science Foundation of China","doi-asserted-by":"crossref","award":["61502300"],"award-info":[{"award-number":["61502300"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2019,12,31]]},"abstract":"<jats:p>\n            We show that for\n            <jats:italic>k<\/jats:italic>\n            \u2265 5, the PPSZ algorithm for\n            <jats:italic>k<\/jats:italic>\n            -SAT runs exponentially faster if there is an exponential number of satisfying assignments. More precisely, we show that for every\n            <jats:italic>k<\/jats:italic>\n            \u2265 5, there is a strictly increasing function\n            <jats:italic>f<\/jats:italic>\n            : [0,1] \u2192 R with\n            <jats:italic>f<\/jats:italic>\n            (0) = 0 that has the following property. If\n            <jats:italic>F<\/jats:italic>\n            is a\n            <jats:italic>k<\/jats:italic>\n            -CNF formula over\n            <jats:italic>n<\/jats:italic>\n            variables and |sat(F)| = 2\n            <jats:sup>\n              \u03b4\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sup>\n            solutions, then PPSZ finds a satisfying assignment with probability at least 2\n            <jats:sup>\n              \u2212\n              <jats:italic>c<\/jats:italic>\n              <jats:sub>\n                <jats:italic>k<\/jats:italic>\n              <\/jats:sub>\n              <jats:italic>n<\/jats:italic>\n              \u2212\n              <jats:italic>o<\/jats:italic>\n              (\n              <jats:italic>n<\/jats:italic>\n              ) +\n              <jats:italic>f<\/jats:italic>\n              (\u03b4)\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sup>\n            . Here, 2\n            <jats:sup>\n              \u2212\n              <jats:italic>c<\/jats:italic>\n              <jats:sub>\n                <jats:italic>k<\/jats:italic>\n              <\/jats:sub>\n              <jats:italic>n<\/jats:italic>\n              \u2212\n              <jats:italic>o<\/jats:italic>\n              (\n              <jats:italic>n<\/jats:italic>\n              )\n            <\/jats:sup>\n            is the success probability proved by Paturi et al. [11] for\n            <jats:italic>k<\/jats:italic>\n            -CNF formulas with a unique satisfying assignment.\n          <\/jats:p>\n          <jats:p>\n            Our proof rests on a combinatorial lemma: given a set\n            <jats:italic>S<\/jats:italic>\n            \u2286 { 0,1}\n            <jats:sup>\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sup>\n            , we can partition { 0,1}\n            <jats:sup>\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sup>\n            into subcubes such that each subcube\n            <jats:italic>B<\/jats:italic>\n            contains exactly one element of\n            <jats:italic>S<\/jats:italic>\n            . Such a partition\n            <jats:italic>B<\/jats:italic>\n            induces a distribution on itself, via Pr [\n            <jats:italic>B<\/jats:italic>\n            ] = |B| \/ 2\n            <jats:sup>\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sup>\n            for each\n            <jats:italic>B<\/jats:italic>\n            \u2208\n            <jats:italic>B<\/jats:italic>\n            . We are interested in partitions that induce a distribution of high entropy. We show that, in a certain sense, the worst case (min\n            <jats:sub>\n              <jats:italic>S<\/jats:italic>\n              : |S| =\n              <jats:italic>s<\/jats:italic>\n            <\/jats:sub>\n            max\n            <jats:sub>\n              <jats:italic>B<\/jats:italic>\n            <\/jats:sub>\n            <jats:italic>H<\/jats:italic>\n            (\n            <jats:italic>B<\/jats:italic>\n            )) is achieved if\n            <jats:italic>S<\/jats:italic>\n            is a Hamming ball. This lemma implies that every set\n            <jats:italic>S<\/jats:italic>\n            of exponential size allows a partition of linear entropy. This in turn leads to an exponential improvement of the success probability of PPSZ.\n          <\/jats:p>","DOI":"10.1145\/3349613","type":"journal-article","created":{"date-parts":[[2019,9,13]],"date-time":"2019-09-13T12:28:56Z","timestamp":1568377736000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["PPSZ for\n            <i>k<\/i>\n            \u2265 5: More Is Better"],"prefix":"10.1145","volume":"11","author":[{"given":"Dominik","family":"Scheder","sequence":"first","affiliation":[{"name":"Shanghai Jiao Tong University, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,9,12]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 6th International Conference on Theory and Applications of Satisfiability Testing (SAT\u201903)","volume":"2919","author":"Baumer Sven","year":"2003"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/7228"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.06.015"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.22"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43948-7_50"},{"volume-title":"Proceedings of the 19th Annual Symposium on Theoretical Aspects of Computer Science (STACS\u201911)","year":"2011","author":"Hertli Timon","key":"e_1_2_1_6_1"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/646516.696139"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17517-6_9"},{"volume-title":"Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM","year":"2004","author":"Iwama Kazuo","key":"e_1_2_1_9_1"},{"key":"e_1_2_1_10_1","unstructured":"Ramamohan Paturi. {n.d.}. Personal communication.  Ramamohan Paturi. {n.d.}. Personal communication."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066100.1066101"},{"key":"e_1_2_1_12_1","unstructured":"Ramamohan Paturi Pavel Pudl\u00e1k and Francis Zane. 1999. Satisfiability coding lemma. Chicago J. Theoret. Comput. Sci. (1999).  Ramamohan Paturi Pavel Pudl\u00e1k and Francis Zane. 1999. Satisfiability coding lemma. Chicago J. Theoret. Comput. Sci. (1999)."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.3233\/SAT190005"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(72)90019-2"},{"volume":"79","volume-title":"Proceedings of the 32nd Computational Complexity Conference (CCC\u201917)","author":"Scheder Dominik","key":"e_1_2_1_15_1"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/795665.796524"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1972.41.247"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3349613","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3349613","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:25:46Z","timestamp":1750206346000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3349613"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9,12]]},"references-count":17,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,12,31]]}},"alternative-id":["10.1145\/3349613"],"URL":"https:\/\/doi.org\/10.1145\/3349613","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2019,9,12]]},"assertion":[{"value":"2018-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-09-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}