{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:19:00Z","timestamp":1750306740837,"version":"3.41.0"},"reference-count":7,"publisher":"Association for Computing Machinery (ACM)","issue":"10","license":[{"start":{"date-parts":[[2014,9,23]],"date-time":"2014-09-23T00:00:00Z","timestamp":1411430400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001736","name":"German-Israeli Foundation for Scientific Research and Development","doi-asserted-by":"publisher","award":["2282-2222.6\/2011"],"award-info":[{"award-number":["2282-2222.6\/2011"]}],"id":[{"id":"10.13039\/501100001736","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["827\/12"],"award-info":[{"award-number":["827\/12"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Alon Fellowship"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Commun. ACM"],"published-print":{"date-parts":[[2014,9,23]]},"abstract":"<jats:p>\n            Combinatorial search problems are usually described by a collection of possible states, a list of possible actions which map each current state into some next state, and a pair of initial and final states. The algorithmic problem is to find a sequence of actions which maps the given initial state into the desired final state. In this paper, we introduce the new notion of\n            <jats:italic>bicomposite search problems<\/jats:italic>\n            , and show that they can be solved with improved combinations of time and space complexities by using a new algorithmic paradigm called\n            <jats:italic>dissection<\/jats:italic>\n            . To demonstrate the broad applicability of our new paradigm, we show how to use it in order to untangle Rubik's cube and to solve a typical NP-complete partition problem with algorithms which are better than any previously described algorithm for these problems.\n          <\/jats:p>","DOI":"10.1145\/2661434","type":"journal-article","created":{"date-parts":[[2014,10,1]],"date-time":"2014-10-01T13:34:59Z","timestamp":1412170499000},"page":"98-105","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Dissection"],"prefix":"10.1145","volume":"57","author":[{"given":"Itai","family":"Dinur","sequence":"first","affiliation":[{"name":"The Weizmann Institute, Rehovot, Israel"}]},{"given":"Orr","family":"Dunkelman","sequence":"additional","affiliation":[{"name":"University of Haifa, Israel"}]},{"given":"Nathan","family":"Keller","sequence":"additional","affiliation":[{"name":"Bar-Ilan University, Israel"}]},{"given":"Adi","family":"Shamir","sequence":"additional","affiliation":[{"name":"The Weizmann Institute, Rehovot, Israel"}]}],"member":"320","published-online":{"date-parts":[[2014,9,23]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"God's number is 20","author":"Davidson M.","year":"2010","unstructured":"Davidson , M. , Dethridge , J. , Kociemba , H. , Rokicki , T. God's number is 20 , 2010 . http:\/\/cube20.org. Davidson, M., Dethridge, J., Kociemba, H., Rokicki, T. God's number is 20, 2010. http:\/\/cube20.org."},{"key":"e_1_2_1_2_1","volume-title":"Volume 7417 of Lecture Notes in Computer Science","author":"Dinur I.","year":"2012","unstructured":"Dinur , I. , Dunkelman , O. , Keller , N. , Shamir , A. Efficient dissection of composite problems, with applications to cryptanalysis, knapsacks, and combinatorial search problems . In CRYPTO, R. Safavi-Naini and R. Canetti, eds. Volume 7417 of Lecture Notes in Computer Science ( 2012 ). Springer , 719--740. Dinur, I., Dunkelman, O., Keller, N., Shamir, A. Efficient dissection of composite problems, with applications to cryptanalysis, knapsacks, and combinatorial search problems. In CRYPTO, R. Safavi-Naini and R. Canetti, eds. Volume 7417 of Lecture Notes in Computer Science (2012). Springer, 719--740."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63490"},{"key":"e_1_2_1_4_1","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey M.R.","year":"1979","unstructured":"Garey , M.R. , Johnson , D.S. Computers and Intractability: A Guide to the Theory of NP-Completeness . W. H. Freeman , 1979 . Garey, M.R., Johnson, D.S. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/321812.321823"},{"key":"e_1_2_1_6_1","volume-title":"Stories, Solutions","author":"Slocum J.","year":"2011","unstructured":"Slocum , J. The Cube: The Ultimate Guide to the World's Bestselling Puzzle---Secrets , Stories, Solutions . Black Dog & Leventhal Publishers , 2011 . Slocum, J. The Cube: The Ultimate Guide to the World's Bestselling Puzzle---Secrets, Stories, Solutions. Black Dog & Leventhal Publishers, 2011."},{"key":"e_1_2_1_7_1","series-title":"Lecture Notes in Computer Science","volume-title":"M.J. Improving implementable meet-in-the-middle attacks by orders of magnitude","author":"van Oorschot P.C.","year":"1996","unstructured":"van Oorschot , P.C. , Wiener , M.J. Improving implementable meet-in-the-middle attacks by orders of magnitude . In CRYPTO, N. Koblitz, ed. Volume 1109 of Lecture Notes in Computer Science ( 1996 ). Springer , 229--236. van Oorschot, P.C., Wiener, M.J. Improving implementable meet-in-the-middle attacks by orders of magnitude. In CRYPTO, N. Koblitz, ed. Volume 1109 of Lecture Notes in Computer Science (1996). Springer, 229--236."}],"container-title":["Communications of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2661434","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2661434","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:28:14Z","timestamp":1750231694000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2661434"}},"subtitle":["a new paradigm for solving bicomposite search problems"],"short-title":[],"issued":{"date-parts":[[2014,9,23]]},"references-count":7,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2014,9,23]]}},"alternative-id":["10.1145\/2661434"],"URL":"https:\/\/doi.org\/10.1145\/2661434","relation":{},"ISSN":["0001-0782","1557-7317"],"issn-type":[{"type":"print","value":"0001-0782"},{"type":"electronic","value":"1557-7317"}],"subject":[],"published":{"date-parts":[[2014,9,23]]},"assertion":[{"value":"2014-09-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}