{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T08:38:11Z","timestamp":1758271091774,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":29,"publisher":"ACM","license":[{"start":{"date-parts":[[2019,6,23]],"date-time":"2019-06-23T00:00:00Z","timestamp":1561248000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2019,6,23]]},"DOI":"10.1145\/3313276.3316347","type":"proceedings-article","created":{"date-parts":[[2019,6,20]],"date-time":"2019-06-20T12:19:08Z","timestamp":1561033148000},"page":"568-577","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Bridging between 0\/1 and linear programming via random walks"],"prefix":"10.1145","author":[{"given":"Joshua","family":"Brakensiek","sequence":"first","affiliation":[{"name":"Stanford University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Venkatesan","family":"Guruswami","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,6,23]]},"reference":[{"key":"e_1_3_2_1_1_1","unstructured":"Per Austrin Venkatesan Guruswami and Johan H\u00e5stad. 2017.  Per Austrin Venkatesan Guruswami and Johan H\u00e5stad. 2017."},{"key":"e_1_3_2_1_2_1","volume-title":"1554\u20131573","author":"Comput Sat Is","year":"2017","unstructured":"(2+ \u03f5)- Sat Is NP-hard. SIAM J. Comput . 46, 5 ( 2017 ), 1554\u20131573 . (2+ \u03f5)-Sat Is NP-hard. SIAM J. Comput. 46, 5 (2017), 1554\u20131573."},{"key":"e_1_3_2_1_3_1","unstructured":"Libor Barto Andrei A. Krokhin and Ross Willard. 2017.  Libor Barto Andrei A. Krokhin and Ross Willard. 2017."},{"volume-title":"The Constraint Satisfaction Problem: Complexity and Approximability, Andrei A","author":"Use Them How","key":"e_1_3_2_1_4_1","unstructured":"Polymorphisms, and How to Use Them . In The Constraint Satisfaction Problem: Complexity and Approximability, Andrei A . Krokhin and Stanislav Zivny (Eds.). Dagstuhl Follow-Ups, Vol . 7. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 1\u201344. U.Vol 7.15301.1 Polymorphisms, and How to Use Them. In The Constraint Satisfaction Problem: Complexity and Approximability, Andrei A. Krokhin and Stanislav Zivny (Eds.). Dagstuhl Follow-Ups, Vol. 7. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 1\u201344. U.Vol7.15301.1"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/3310435.3310463"},{"key":"e_1_3_2_1_6_1","unstructured":"A. Bulatov P. Jeavons and A. Krokhin. 2005.  A. Bulatov P. Jeavons and A. Krokhin. 2005."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700376676"},{"key":"e_1_3_2_1_8_1","unstructured":"Hubie Chen. 2009.  Hubie Chen. 2009."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1592451.1592453"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2925416"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1015705430513"},{"key":"e_1_3_2_1_12_1","unstructured":"William Feller. 1968.  William Feller. 1968."},{"key":"e_1_3_2_1_13_1","unstructured":"An Introduction to Probability Theory and Its Applications. Vol. 1. John Wiley & Sons.  An Introduction to Probability Theory and Its Applications. Vol. 1. John Wiley & Sons."},{"key":"e_1_3_2_1_14_1","unstructured":"Martin Gr\u00f6tschel L\u00e1szl\u00f3 Lov\u00e1sz and Alexander Schrijver. 1993.  Martin Gr\u00f6tschel L\u00e1szl\u00f3 Lov\u00e1sz and Alexander Schrijver. 1993."},{"volume-title":"Springer Science &amp","author":"Algorithms Geometric","key":"e_1_3_2_1_15_1","unstructured":"Geometric Algorithms and Combinatorial Optimization . Vol. 2. Springer Science &amp ; Business Media . Geometric Algorithms and Combinatorial Optimization. Vol. 2. Springer Science & Business Media."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/120868177"},{"key":"e_1_3_2_1_17_1","unstructured":"Russell Impagliazzo Shachar Lovett Ramamohan Paturi and Stefan Schneider. 2014.  Russell Impagliazzo Shachar Lovett Ramamohan Paturi and Stefan Schneider. 2014."},{"key":"e_1_3_2_1_18_1","volume-title":"arXiv preprint arXiv:1401.5512","author":"Linear Integer Linear","year":"2014","unstructured":"0-1 Integer Linear Programming with a Linear Number of Constraints . arXiv preprint arXiv:1401.5512 ( 2014 ). 0-1 Integer Linear Programming with a Linear Number of Constraints. arXiv preprint arXiv:1401.5512 (2014)."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627817.2627909"},{"key":"e_1_3_2_1_21_1","volume-title":"Which NP-Hard SAT and CSP Problems Admit Exponentially Improved Algorithms? CoRR abs\/1801.09488","author":"Lagerkvist Victor","year":"2018","unstructured":"Victor Lagerkvist and Magnus Wahlstr\u00f6m . 2018. Which NP-Hard SAT and CSP Problems Admit Exponentially Improved Algorithms? CoRR abs\/1801.09488 ( 2018 ). http:\/\/arxiv.org\/abs\/1801.09488 Victor Lagerkvist and Magnus Wahlstr\u00f6m. 2018. Which NP-Hard SAT and CSP Problems Admit Exponentially Improved Algorithms? CoRR abs\/1801.09488 (2018). http:\/\/arxiv.org\/abs\/1801.09488"},{"key":"e_1_3_2_1_22_1","unstructured":"Gregory F Lawler and Vlada Limic. 2010.  Gregory F Lawler and Vlada Limic. 2010."},{"volume-title":"a Modern Introduction","author":"Walk Random","key":"e_1_3_2_1_23_1","unstructured":"Random Walk : a Modern Introduction . Vol. 123 . Cambridge University Press . Random Walk: a Modern Introduction. Vol. 123. Cambridge University Press."},{"volume-title":"Algorithm. In Proceedings of the Forty-third Annual ACM Symposium on Theory of Computing (STOC \u201911)","author":"Robin","key":"e_1_3_2_1_24_1","unstructured":"Robin A. Moser and Dominik Scheder. 2011. A Full Derandomization of Sch\u00f6ning\u2019s k-SAT Algorithm. In Proceedings of the Forty-third Annual ACM Symposium on Theory of Computing (STOC \u201911) . ACM, New York, NY, USA, 245\u2013252. Robin A. Moser and Dominik Scheder. 2011. A Full Derandomization of Sch\u00f6ning\u2019s k-SAT Algorithm. In Proceedings of the Forty-third Annual ACM Symposium on Theory of Computing (STOC \u201911). ACM, New York, NY, USA, 245\u2013252."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066100.1066101"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/795665.796524"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01448847"},{"key":"e_1_3_2_1_28_1","unstructured":"Magnus Wahlstr\u00f6m. 2007.  Magnus Wahlstr\u00f6m. 2007."},{"key":"e_1_3_2_1_30_1","unstructured":"Gerhard J. Woeginger. 2003.  Gerhard J. Woeginger. 2003."}],"event":{"name":"STOC '19: 51st Annual ACM SIGACT Symposium on the Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Phoenix AZ USA","acronym":"STOC '19"},"container-title":["Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313276.3316347","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3313276.3316347","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:54:32Z","timestamp":1750204472000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313276.3316347"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,23]]},"references-count":29,"alternative-id":["10.1145\/3313276.3316347","10.1145\/3313276"],"URL":"https:\/\/doi.org\/10.1145\/3313276.3316347","relation":{},"subject":[],"published":{"date-parts":[[2019,6,23]]},"assertion":[{"value":"2019-06-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}