{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T10:18:36Z","timestamp":1743157116185,"version":"3.40.3"},"publisher-location":"Cham","reference-count":24,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030242572"},{"type":"electronic","value":"9783030242589"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019]]},"DOI":"10.1007\/978-3-030-24258-9_28","type":"book-chapter","created":{"date-parts":[[2019,6,28]],"date-time":"2019-06-28T21:02:31Z","timestamp":1561755751000},"page":"406-423","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["On Super Strong ETH"],"prefix":"10.1007","author":[{"given":"Nikhil","family":"Vyas","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ryan","family":"Williams","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,6,29]]},"reference":[{"key":"28_CR1","doi-asserted-by":"crossref","unstructured":"Achlioptas, D., Coja-Oghlan, A.: Algorithmic barriers from phase transitions. In: IEEE 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, pp. 793\u2013802. IEEE (2008)","DOI":"10.1109\/FOCS.2008.11"},{"key":"28_CR2","unstructured":"Ben-Sasson, E., Bilu, Y., Gutfreund, D.: Finding a randomly planted assignment in a random 3CNF (2002, manuscript)"},{"key":"28_CR3","unstructured":"Brakensiek, J., Guruswami, V.: Bridging between 0\/1 and linear programming via random walks. CoRR abs\/1904.04860 (2019). http:\/\/arxiv.org\/abs\/1904.04860"},{"issue":"3","key":"28_CR4","doi-asserted-by":"publisher","first-page":"386","DOI":"10.1016\/j.jcss.2007.06.015","volume":"74","author":"C Calabro","year":"2008","unstructured":"Calabro, C., Impagliazzo, R., Kabanets, V., Paturi, R.: The complexity of unique k-SAT: an isolation lemma for k-CNFs. J. Comput. Syst. Sci. 74(3), 386\u2013393 (2008)","journal-title":"J. Comput. Syst. Sci."},{"key":"28_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/978-3-642-11269-0_6","volume-title":"Parameterized and Exact Computation","author":"C Calabro","year":"2009","unstructured":"Calabro, C., Impagliazzo, R., Paturi, R.: The complexity of satisfiability of small depth circuits. In: Chen, J., Fomin, F.V. (eds.) IWPEC 2009. LNCS, vol. 5917, pp. 75\u201385. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-11269-0_6"},{"key":"28_CR6","doi-asserted-by":"crossref","unstructured":"Chan, T.M., Williams, R.: Deterministic apsp, orthogonal vectors, and more: quickly derandomizing razborov-smolensky. In: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10\u201312 2016, pp. 1246\u20131255 (2016)","DOI":"10.1137\/1.9781611974331.ch87"},{"issue":"3","key":"28_CR7","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1016\/0020-0255(90)90030-E","volume":"51","author":"MT Chao","year":"1990","unstructured":"Chao, M.T., Franco, J.: Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k satisfiability problem. Inf. Sci.: Int. J. 51(3), 289\u2013314 (1990)","journal-title":"Inf. Sci.: Int. J."},{"issue":"7","key":"28_CR8","doi-asserted-by":"publisher","first-page":"2823","DOI":"10.1137\/09076516X","volume":"39","author":"A Coja-Oghlan","year":"2010","unstructured":"Coja-Oghlan, A.: A better algorithm for random k-SAT. SIAM J. Comput. 39(7), 2823\u20132864 (2010)","journal-title":"SIAM J. Comput."},{"key":"28_CR9","doi-asserted-by":"crossref","unstructured":"Coja-Oghlan, A., Krivelevich, M., Vilenchik, D.: Why almost all k-CNF formulas are easy (2007, manuscript)","DOI":"10.46298\/dmtcs.3538"},{"key":"28_CR10","doi-asserted-by":"crossref","unstructured":"Cook, S.A., Mitchell, D.G.: Finding hard instances of the satisfiability problem: a survey. In: Satisfiability Problem: Theory and Applications, Proceedings of a DIMACS Workshop, Piscataway, New Jersey, USA, 11\u201313 March 1996, pp. 1\u201318 (1996)","DOI":"10.1090\/dimacs\/035\/01"},{"key":"28_CR11","doi-asserted-by":"crossref","unstructured":"Ding, J., Sly, A., Sun, N.: Proof of the satisfiability conjecture for large k. In: Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, 14\u201317 June 2015, pp. 59\u201368 (2015)","DOI":"10.1145\/2746539.2746619"},{"key":"28_CR12","doi-asserted-by":"crossref","unstructured":"Feige, U.: Relations between average case complexity and approximation complexity. In: Proceedings on 34th Annual ACM Symposium on Theory of Computing, 19\u201321 May 2002, Montr\u00e9al, Qu\u00e9bec, Canada, pp. 534\u2013543 (2002)","DOI":"10.1145\/509907.509985"},{"issue":"2","key":"28_CR13","doi-asserted-by":"publisher","first-page":"718","DOI":"10.1137\/120868177","volume":"43","author":"T Hertli","year":"2014","unstructured":"Hertli, T.: 3-SAT faster and simpler - unique-SAT bounds for PPSZ hold ingeneral. SIAM J. Comput. 43(2), 718\u2013729 (2014). https:\/\/doi.org\/10.1137\/120868177","journal-title":"SIAM J. Comput."},{"issue":"2","key":"28_CR14","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of k-SAT. J. Comput. Syst. Sci. 62(2), 367\u2013375 (2001). https:\/\/doi.org\/10.1006\/jcss.2000.1727","journal-title":"J. Comput. Syst. Sci."},{"key":"28_CR15","doi-asserted-by":"crossref","unstructured":"Krivelevich, M., Vilenchik, D.: Solving random satisfiable 3CNF formulas in expected polynomial time. In: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2006, Miami, Florida, USA, 22\u201326 January 2006, pp. 454\u2013463 (2006)","DOI":"10.1145\/1109557.1109608"},{"issue":"3","key":"28_CR16","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1145\/1066100.1066101","volume":"52","author":"R Paturi","year":"2005","unstructured":"Paturi, R., Pudl\u00e1k, P., Saks, M.E., Zane, F.: An improved exponential-time algorithm for k-SAT. J. ACM 52(3), 337\u2013364 (2005). https:\/\/doi.org\/10.1145\/1066100.1066101","journal-title":"J. ACM"},{"key":"28_CR17","unstructured":"Paturi, R., Pudl\u00e1k, P., Zane, F.: Satisfiability coding lemma. Chicago J. Theor. Comput. Sci. 1999 (1999). http:\/\/cjtcs.cs.uchicago.edu\/articles\/1999\/11\/contents.html"},{"key":"28_CR18","unstructured":"Pudl\u00e1k, P., Scheder, D., Talebanfard, N.: Tighter hard instances for PPSZ. In: 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, 10\u201314 July 2017, Warsaw, Poland, pp. 85:1\u201385:13 (2017)"},{"key":"28_CR19","unstructured":"Sch\u00f6ning, U.: A probabilistic algorithm for k-SAT and constraint satisfaction problems. In: 40th Annual Symposium on Foundations of Computer Science, FOCS 1999, 17\u201318 October 1999, New York, NY, USA, pp. 410\u2013414 (1999)"},{"issue":"1\u20132","key":"28_CR20","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/0004-3702(95)00045-3","volume":"81","author":"B Selman","year":"1996","unstructured":"Selman, B., Mitchell, D.G., Levesque, H.J.: Generating hard satisfiability problems. Artif. intell. 81(1\u20132), 17\u201329 (1996)","journal-title":"Artif. intell."},{"key":"28_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1007\/978-3-540-79723-4_18","volume-title":"Parameterized and Exact Computation","author":"P Traxler","year":"2008","unstructured":"Traxler, P.: The time complexity of constraint satisfaction. In: Grohe, M., Niedermeier, R. (eds.) IWPEC 2008. LNCS, vol. 5018, pp. 190\u2013201. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-79723-4_18"},{"issue":"3","key":"28_CR22","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0304-3975(86)90135-0","volume":"47","author":"LG Valiant","year":"1986","unstructured":"Valiant, L.G., Vazirani, V.V.: NP is as easy as detecting unique solutions. Theor. Comput. Sci. 47(3), 85\u201393 (1986). https:\/\/doi.org\/10.1016\/0304-3975(86)90135-0","journal-title":"Theor. Comput. Sci."},{"key":"28_CR23","unstructured":"Vilenchik, D.: Personal communication"},{"key":"28_CR24","unstructured":"Williams, R.: Circuit analysis algorithms. Talk at Simons Institute for Theory of Computing, August 2015. https:\/\/youtu.be\/adJvi7tL-qM?t=925"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Satisfiability Testing \u2013 SAT 2019"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-24258-9_28","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,17]],"date-time":"2023-09-17T21:21:27Z","timestamp":1694985687000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-24258-9_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030242572","9783030242589"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-24258-9_28","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"29 June 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SAT","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Theory and Applications of Satisfiability Testing","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Lisbon","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Portugal","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"7 July 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12 July 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sat2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/sat2019.tecnico.ulisboa.pt\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"64","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"19","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"7","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"30% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"6","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}