{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,3]],"date-time":"2026-08-03T21:49:33Z","timestamp":1785793773261,"version":"3.56.0"},"reference-count":63,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2020,2,11]],"date-time":"2020-02-11T00:00:00Z","timestamp":1581379200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100005156","name":"Alexander von Humboldt-Stiftung","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100005156","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-0915702 and CCF-1101452"],"award-info":[{"award-number":["CCF-0915702 and CCF-1101452"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2020,3,31]]},"abstract":"<jats:p>Most theoretical definitions about the complexity of manipulating elections focus on the decision problem of recognizing which instances can be successfully manipulated rather than the search problem of finding the successful manipulative actions. Since the latter is a far more natural goal for manipulators, that definitional focus may be misguided if these two complexities can differ. Our main result is that they probably do differ: If P \u2260 NP \u2229 coNP (which itself is well known to hold if integer factoring is hard), then for election manipulation, election bribery, and some types of election control, there are election systems for which the problem of recognizing which instances can be successfully manipulated is polynomial-time solvable, yet the task of producing the successful manipulations cannot be done in polynomial time.<\/jats:p>","DOI":"10.1145\/3369937","type":"journal-article","created":{"date-parts":[[2020,2,25]],"date-time":"2020-02-25T12:28:17Z","timestamp":1582633697000},"page":"1-42","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Search versus Decision for Election Manipulation Problems"],"prefix":"10.1145","volume":"12","author":[{"given":"Edith","family":"Hemaspaandra","sequence":"first","affiliation":[{"name":"Rochester Institute of Technology, Rochester, NY, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lane A.","family":"Hemaspaandra","sequence":"additional","affiliation":[{"name":"University of Rochester, Rochester, NY, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Curtis","family":"Menton","sequence":"additional","affiliation":[{"name":"Google Inc., CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,2,11]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1089023.1089025"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00183045"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00295861"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00303169"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0895-7177(92)90085-Y"},{"key":"e_1_2_1_6_1","volume-title":"Handbook on Approval Voting, Jean-Fran\u00e7ois Laslier and M","author":"Baumeister Dorothea"},{"key":"e_1_2_1_7_1","volume-title":"Economics and Computation: An Introduction to Algorithmic Game Theory, Computational Social Choice, and Fair Division, J\u00f6rg Rothe (Ed.)","author":"Baumeister Dorothea"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792228289"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/0206023"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1987.30"},{"key":"e_1_2_1_11_1","volume-title":"Demers","author":"Borodin Allan","year":"1976"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28409"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(92)90048-K"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1236457.1236461"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 10th International World Wide Web Conference. ACM Press, 613--622","author":"Dwork Cynthia"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1018924209812"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2014.11.002"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1002\/malq.200810020"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/1641503.1641514"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1839676.1839696"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/2016945.2016954"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2013.11.004"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/2831407.2831419"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1613\/jair.2697"},{"key":"e_1_2_1_25_1","volume-title":"Fundamental Problems in Computing: Essays in Honor of Professor Daniel J","author":"Faliszewski Piotr"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2010.09.001"},{"key":"e_1_2_1_27_1","volume-title":"Handbook of Computational Social Choice, Felix Brandt, Vincent Conitzer, Ulle Endriss, J\u00e9r\u00f4me Lang, and Ariel D","author":"Faliszewski Piotr"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0890-5401(03)00119-6"},{"key":"e_1_2_1_29_1","volume-title":"Johnson","author":"Garey Michael R.","year":"1979"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/301136.301303"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1686"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(88)90022-9"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(90)90138-8"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the 30th Annual Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics","volume":"20","author":"Hemaspaandra Edith","year":"2013"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2007.01.005"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0061"},{"key":"e_1_2_1_38_1","unstructured":"Lane A. Hemaspaandra. 2017. CSC 286\/486. Retrieved from http:\/\/www.cs.rochester.edu\/u\/lane\/course-notes-csc486-2017.pdf.  Lane A. Hemaspaandra. 2017. CSC 286\/486. Retrieved from http:\/\/www.cs.rochester.edu\/u\/lane\/course-notes-csc486-2017.pdf."},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of the 32nd AAAI Conference on Artificial Intelligence. AAAI Press, 7971--7977","author":"Hemaspaandra Lane A.","year":"2018"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10472-015-9479-1"},{"key":"e_1_2_1_41_1","volume-title":"Narv\u00e1ez","author":"Hemaspaandra Lane A.","year":"2017"},{"key":"e_1_2_1_42_1","volume-title":"Narv\u00e1ez","author":"Hemaspaandra Lane A.","year":"2019"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002360050109"},{"key":"e_1_2_1_44_1","volume-title":"Hemaspaandra and Leen Torenvliet","author":"Lane","year":"2003"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01184814"},{"key":"e_1_2_1_46_1","volume-title":"Ullman","author":"Hopcroft John E.","year":"1979"},{"key":"e_1_2_1_47_1","volume-title":"Proceedings of the 8th Innovations in Theoretical Computer Science Conference. Leibniz International Proceedings in Informatics","volume":"67","author":"Hub\u00e1\u010dek Pavel","year":"2017"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/SCT.1988.5260"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(98)00150-1"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.5555\/49981.49986"},{"key":"e_1_2_1_51_1","unstructured":"Shiva Kintali. 2010. NP intersect coNP. Retrieved from kintali.wordpress.com\/2010\/06\/06\/np-intersect-conp.  Shiva Kintali. 2010. NP intersect coNP. Retrieved from kintali.wordpress.com\/2010\/06\/06\/np-intersect-conp."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(75)90016-X"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10472-017-9565-7"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90200-L"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-012-9441-0"},{"key":"e_1_2_1_56_1","volume-title":"Proceedings of the 23rd International Joint Conference on Artificial Intelligence. AAAI Press, 286--292","author":"Menton Curtis","year":"2013"},{"key":"e_1_2_1_58_1","volume-title":"Proceedings of the 31st AAAI Conference on Artificial Intelligence. AAAI Press, 3029--3035","author":"Neveling Marc","year":"2017"},{"key":"e_1_2_1_59_1","volume-title":"Parkes and Lirong Xia","author":"David","year":"2012"},{"key":"e_1_2_1_60_1","volume-title":"Friedrich-Schiller-Universit\u00e4t Jena","author":"Rothe J\u00f6rg"},{"key":"e_1_2_1_61_1","volume-title":"Proceedings of the 3rd International Colloquium on Automata, Languages, and Programming","author":"Schnorr Claus-Peter","year":"1976"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795293172"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02125350"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(76)90097-1"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/1998037.1998053"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3369937","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3369937","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3369937","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:44:27Z","timestamp":1750203867000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3369937"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,11]]},"references-count":63,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,3,31]]}},"alternative-id":["10.1145\/3369937"],"URL":"https:\/\/doi.org\/10.1145\/3369937","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,2,11]]},"assertion":[{"value":"2018-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-02-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}