Edit Profile (opens in new tab) Hemaspaandra, Lane A. Compute Distance To: Compute Author ID: hemaspaandra.lane-a Published as: Hemaspaandra, Lane A.; Hemachandra, Lane A.; Hemaspaandra, L. A.; Hemachandra, Lane; Hemaspaandra, Lane; Hemachandra, L.; Hemachandra, L. A. Documents Indexed: 170 Publications since 1986, including 2 Books 1 Contribution as Editor Co-Authors: 85 Co-Authors with 165 Joint Publications 1,682 Co-Co-Authors all top 5 Co-Authors 6 single-authored 41 Hemaspaandra, Edith 32 Rothe, Jörg-Matthias 15 Hempel, Harald 13 Ogihara, Mitsunori 12 Faliszewski, Piotr 11 Wechsung, Gerd 10 Cai, Jin-Yi 9 Hoene, Albrecht 8 Hartmanis, Juris 7 Watanabe, Osamu 6 Han, Yenjo 5 Erdélyi, Gábor 5 Homan, Christopher M. 5 Ogiwara, Mitsunori 5 Spakowski, Holger 5 Thierauf, Thomas 5 Torenvliet, Leen 4 Jain, Sanjay 4 Jiang, Zhigen 4 Kosub, Sven 4 Selman, Alan L. 4 Siefkes, Dirk 4 Silvestri, Riccardo 4 Tantau, Till 4 Wagner, Klaus W. 4 Zimand, Marius 3 Allender, Eric W. 3 Goldsmith, Judy 3 Naik, Ashish V. 3 Rubery, Daniel 3 Thakur, Mayur 2 Abascal, Jackson 2 Arvind, Vikraman 2 Beigel, Richard 2 Borchert, Bernd 2 Buntrock, Gerhard 2 Chakaravarthy, Venkatesan T. 2 Fischer, Sophie Titia 2 Gasarch, William Ian 2 Gundermann, Thomas 2 Jha, Sudhir K. 2 Köbler, Johannes 2 Kratsch, Dieter 2 Kunen, Kenneth 2 Lozano, Antoni 2 Maimon, Shir 2 Menton, Curtis 2 Mukherji, Proshanto 2 Mundhenk, Martin 2 Narváez, David E. 2 Nickelsen, Arfst 2 Pasanen, Kari 2 Radziszowski, Stanisław P. 2 Saxena, Amitabh 2 Schöning, Uwe 2 Sewelson, Vivian 2 Tripathi, Rahul 2 Vereshchagin, Nikolai K. 2 Zaki, Mohammed Javeed 1 Abadi, Martín 1 Baumeister, Dorothea 1 Bent, Russell W. 1 Brandt, Felix 1 Brill, Markus 1 Broder, Andrei Z. 1 Caragiannis, Ioannis 1 Chai, Jinyi 1 Eppstein, David Arthur 1 Feigenbaum, Joan 1 Fitzsimmons, Zack 1 Gvozdeva, Tatiana 1 Istrate, Gabriel I. 1 Joseph, Deborah 1 Lavaee, Rahman 1 Nasipak, Christopher 1 Parkins, Keith 1 Rubinstein, Roy S. 1 Rudich, Steven 1 Schear, Michael 1 Slinko, Arkadii M. 1 Tisdall, James 1 Toda, Seinosuke 1 Vogel, Jörg 1 Vyskoč, Jozef 1 Yener, Bülent all top 5 Serials 23 Theoretical Computer Science 14 SIAM Journal on Computing 12 Journal of Computer and System Sciences 11 Information and Computation 6 International Journal of Foundations of Computer Science 5 Information Processing Letters 5 The Journal of Artificial Intelligence Research (JAIR) 4 Mathematical Systems Theory 4 Journal of Universal Computer Science 3 Computational Complexity 3 Theory of Computing Systems 2 Artificial Intelligence 2 Bulletin of the European Association for Theoretical Computer Science (EATCS) 2 Annals of Mathematics and Artificial Intelligence 1 Acta Informatica 1 Discrete Applied Mathematics 1 International Journal of Game Theory 1 Journal of the Association for Computing Machinery 1 Journal of Cryptology 1 Mathematical Logic Quarterly (MLQ) 1 Journal of Heuristics 1 Journal of the ACM 1 Bulletin of the European Association for Theoretical Computer Science EATCS 1 LMS Journal of Computation and Mathematics 1 Computer Science Review 1 Texts in Theoretical Computer Science. An EATCS Series 1 Monographs in Theoretical Computer Science. An EATCS Series all top 5 Fields 164 Computer science (68-XX) 47 Mathematical logic and foundations (03-XX) 31 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 8 Information and communication theory, circuits (94-XX) 6 Combinatorics (05-XX) 1 General and overarching topics; collections (00-XX) 1 History and biography (01-XX) 1 Order, lattices, ordered algebraic structures (06-XX) 1 Numerical analysis (65-XX) 1 Quantum theory (81-XX) 1 Operations research, mathematical programming (90-XX) Publications by Year all cited Publications top 5 cited Publications Citations contained in zbMATH Open 140 Publications have been cited 1,158 times in 462 Documents Cited by ▼ Year ▼ Llull and Copeland voting computationally resist bribery and constructive control. Zbl 1180.91091Faliszewski, P.; Hemaspaandra, E.; Hemaspaandra, L. A.; Rothe, J. 62 2009 The Boolean hierarchy. I: Structural properties. Zbl 0676.68011Cai, Jin-yi; Gundermann, Thomas; Hartmanis, Juris; Hemachandra, Lane A.; Sewelson, Vivian; Wagner, Klaus; Wechsung, Gerd 54 1988 How hard is bribery in elections? Zbl 1180.91090Faliszewski, P.; Hemaspaandra, E.; Hemaspaandra, L. A. 52 2009 Anyone but him: the complexity of precluding an alternative. Zbl 1168.91346Hemaspaandra, Edith; Hemaspaandra, Lane A.; Rothe, Jörg 44 2007 Exact analysis of Dodgson elections: Lewis Carroll’s 1876 voting system is complete for parallel access to NP. Zbl 0904.68111Hemaspaandra, Edith; Hemaspaandra, Lane A.; Rothe, Jörg 43 1997 The strong exponential hierarchy collapses. Zbl 0693.03022Hemachandra, Lane A. 36 1989 The complexity theory companion. Zbl 0993.68042Hemaspaandra, Lane A.; Ogihara, Mitsunori 35 2002 Complexity classes without machines: on complete languages for UP. Zbl 0655.68044Hartmanis, Juris; Hemachandra, Lane A. 35 1988 On the power of parity polynomial time. Zbl 0718.68038Cai, Jin-yi; Hemachandra, Lane A. 33 1990 A complexity theory for feasible closure properties. Zbl 0798.68060Ogiwara, Mitsunori; Hemachandra, Lane A. 31 1993 A richer understanding of the complexity of election systems. Zbl 1167.91339Faliszewski, Piotr; Hemaspaandra, Edith; Hemaspaandra, Lane A.; Rothe, Jörg 30 2009 The Boolean hierarchy. II: Applications. Zbl 0676.68012Cai, Jin-Yi; Gundermann, Thomas; Hartmanis, Juris; Hemachandra, Lane A.; Sewelson, Vivian; Wagner, Klaus; Wechsung, Gerd 27 1989 Dichotomy for voting systems. Zbl 1154.91381Hemaspaandra, Edith; Hemaspaandra, Lane A. 24 2007 Multimode control attacks on elections. Zbl 1242.91055Faliszewski, Piotr; Hemaspaandra, Edith; Hemaspaandra, Lane A. 23 2011 The shield that never was: societies with single-peaked preferences are more open to manipulation and control. Zbl 1218.91042Faliszewski, Piotr; Hemaspaandra, Edith; Hemaspaandra, Lane A.; Rothe, Jörg 22 2011 Hybrid elections broaden complexity-theoretic resistance to control. Zbl 1177.91066Hemaspaandra, Edith; Hemaspaandra, Lane A.; Rothe, Jörg 20 2009 Computational aspects of approval voting. Zbl 1348.91101Baumeister, Dorothea; Erdélyi, Gábor; Hemaspaandra, Edith; Hemaspaandra, Lane A.; Rothe, Jörg 19 2010 Enumerative counting is hard. Zbl 0679.68072Cai, Jin-Yi; Hemachandra, Lane A. 19 1989 Computing solutions uniquely collapses the polynomial hierarchy. Zbl 0857.68045Hemaspaandra, Lane A.; Naik, Ashish V.; Ogihara, Mitsunori; Selman, Alan L. 18 1996 Reductions to sets of low information content. Zbl 0794.68058Arvind, V.; Han, Y.; Hemachandra, L.; Köbler, J.; Lozano, A.; Mundhenk, M.; Ogiwara, M.; Schöning, U.; Silvestri, R.; Thierauf, T. 17 1993 One-way functions and the nonisomorphism of NP-complete sets. Zbl 0718.03031Hartmanis, Juris; Hemachandra, Lane A. 17 1991 The complexity of manipulative attacks in nearly single-peaked electorates. Zbl 1334.68098Faliszewski, Piotr; Hemaspaandra, Edith; Hemaspaandra, Lane A. 16 2014 Bypassing combinatorial protections: polynomial-time algorithms for single-peaked electorates. Zbl 1337.91039Brandt, Felix; Brill, Markus; Hemaspaandra, Edith; Hemaspaandra, Lane A. 13 2015 Competing provers yield improved Karp-Lipton collapse results. Zbl 1066.68050Cai, Jin-Yi; Chakaravarthy, Venkatesan T.; Hemaspaandra, Lane A.; Ogihara, Mitsunori 13 2005 Threshold computation and cryptographic security. Zbl 0868.68056Han, Yenjo; Hemaspaandra, Lane A.; Thierauf, Thomas 13 1997 Search versus decision for election manipulation problems. Zbl 1354.91054Hemaspaandra, Edith; Hemaspaandra, Lane A.; Menton, Curtis 13 2013 On the complexity of ranking. Zbl 0708.68020Hemachandra, Lane A.; Rudich, Steven 12 1990 Lower bounds for the low hierarchy. Zbl 0799.68081Allender, Eric; Hemachandra, Lane A. 11 1992 Easy sets and hard certificate schemes. Zbl 0883.68072Hemaspaandra, Lane A.; Rothe, Jörg; Wechsung, Gerd 11 1997 Creating strong, total, commutative, associative one-way functions from any one-way function in complexity theory. Zbl 0939.68036Hemaspaandra, Lane A.; Rothe, Jörg 11 1999 Probabilistic polynomial time is closed under parity reductions. Zbl 0714.68031Beigel, Richard; Hemachandra, Lane A.; Wechsung, Gerd 11 1991 Guarantees for the success frequency of an algorithm for finding Dodgson-election winners. Zbl 1188.91062Homan, Christopher M.; Hemaspaandra, Lane A. 10 2009 A note on enumerative counting. Zbl 0733.68030Cai, Jinyi; Hemachandra, Lane A. 10 1991 Weighted electoral control. Zbl 1328.91068Faliszewski, Piotr; Hemaspaandra, Edith; Hemaspaandra, Lane A. 9 2015 Copeland voting fully resists constructive control. Zbl 1143.91320Faliszewski, Piotr; Hemaspaandra, Edith; Hemaspaandra, Lane A.; Rothe, Jörg 9 2008 More natural models of electoral control by partition. Zbl 1405.91151Erdélyi, Gábor; Hemaspaandra, Edith; Hemaspaandra, Lane A. 8 2015 Relating equivalence and reducibility to sparse sets. Zbl 0761.68039Allender, Eric; Hemachandra, Lane A.; Ogiwara, Mitsunori; Watanabe, Osamu 8 1992 A downward collapse within the polynomial hierarchy. Zbl 0915.68070Hemaspaandra, Edith; Hemaspaandra, Lane A.; Hempel, Harald 8 1998 Theory of semi-feasible algorithms. Zbl 1021.68042Hemaspaandra, Lane A.; Torenvliet, Leen 8 2003 Banishing robust Turing completeness. Zbl 0802.68049Hemaspaandra, Lane A.; Jain, Sanjay; Vereshchagin, Nikolaj K. 7 1993 Nondeterministically selective sets. Zbl 0843.68031Hemaspaandra, Lane A.; Hoene, Albrecht; Naik, Ashish V.; Ogihara, Mitsunori; Selman, Alan L.; Thierauf, Thomas; Wang, Jie 7 1995 Query order. Zbl 0915.68071Hemaspaandra, Lane A.; Hempel, Harald; Wechsung, Gerd 7 1998 The complexity of computing the size of an interval. Zbl 1123.68041Hemaspaandra, Lane A.; Homan, Christopher M.; Kosub, Sven; Wagner, Klaus W. 7 2006 Robust machines accept easy sets. Zbl 0701.68028Hartmanis, Juris; Hemachandra, Lane A. 7 1990 Schulze and ranked-pairs voting are fixed-parameter tractable to bribe, manipulate, and control. Zbl 1346.91072Hemaspaandra, Lane A.; Lavaee, Rahman; Menton, Curtis 6 2016 On the complexity of graph reconstruction. Zbl 0806.05051Kratsch, Dieter; Hemaspaandra, Lane A. 6 1994 Near-testable sets. Zbl 0738.68031Goldsmith, Judy; Hemachandra, Lane A.; Joseph, Deborah; Young, Paul 6 1991 On sets with efficient implicit membership tests. Zbl 0738.68032Hemachandra, Lane A.; Hoene, Albrecht 6 1991 Using inductive counting to simulate nondeterministic computation. Zbl 0769.68028Buntrock, Gerhard; Hemachandra, Lane A.; Siefkes, Dirk 6 1993 Defying upward and downward separation. Zbl 0832.68046Hemaspaandra, Lane A.; Jha, Sudhir K. 6 1995 The complexity of power-index comparison. Zbl 1155.91013Faliszewski, Piotr; Hemaspaandra, Lane 6 2009 Computational politics: Electoral systems. Zbl 0996.68065Hemaspaandra, Edith; Hemaspaandra, Lane A. 6 2000 Generalized juntas and NP-hard sets. Zbl 1171.68012Erdélyi, Gábor; Hemaspaandra, Lane A.; Rothe, Jörg; Spakowski, Holger 6 2009 The complexity of online manipulation of sequential elections. Zbl 1285.68223Hemaspaandra, Edith; Hemaspaandra, Lane A.; Rothe, Jörg 6 2014 On sparse oracles separating feasible complexity classes. Zbl 0658.68055Hartmanis, Juris; Hemachandra, Lane 6 1988 The Boolean hierarchy: Hardware over NP. Zbl 0611.68018Chai, Jinyi; Hemachandra, Lane 5 1986 Characterizing the existence of one-way permutations. Zbl 0945.68053Hemaspaandra, L. A.; Rothe, J. 5 2000 On generating solved instances of computational problems. Zbl 0792.68045Abadi, Martín; Allender, Eric; Broder, Andrei; Feigenbaum, Joan; Hemachandra, Lane A. 5 1990 Simultaneous strong separations of probabilistic and unambiguous complexity classes. Zbl 0766.68038Eppstein, David; Hemachandra, Lane A.; Tisdall, James; Yener, Bülent 5 1992 On the limitations of locally robust positive reductions. Zbl 0746.68034Hemachandra, Lane A.; Jain, Sanjay 5 1991 Polynomial-time compression. Zbl 0752.68039Goldsmith, Judy; Hemachandra, Lane A.; Kunen, Kenneth 5 1992 P-selectivity: Intersections and indices. Zbl 0873.68065Hemaspaandra, Lane A.; Jiang, Zhigen 5 1995 Unambiguous computation: Boolean hierarchies and sparse Turing-complete sets. Zbl 0870.68070Hemaspaandra, Lane A.; Rothe, Jörg 5 1997 Strong self-reducibility precludes strong immunity. Zbl 0857.68046Hemaspaandra, L. A.; Zimand, M. 5 1996 The complexity of controlling candidate-sequential elections. Zbl 1371.91053Hemaspaandra, Edith; Hemaspaandra, Lane A.; Rothe, Jörg 5 2017 Query order and the polynomial hierarchy. Zbl 0961.68052Hemaspaandra, Edith; Hemaspaandra, Lane A.; Hempel, Harald 4 1998 Algorithms from complexity theory: Polynomial-time operations for complex sets. Zbl 0819.68063Hemachandra, Lane A. 4 1990 Optimal advice. Zbl 0872.68042Hemaspaandra, Lane A.; Torenvliet, Leen 4 1996 Boolean operations, joins, and the extended low hierarchy. Zbl 0913.68077Hemaspaandra, Lane A.; Jiang, Zhigen; Rothe, Jörg; Watanabe, Osamu 4 1998 Guarantees for the success frequency of an algorithm for finding Dodgson-election winners. Zbl 1132.91399Homan, Christopher M.; Hemaspaandra, Lane A. 4 2006 On the complexity of graph reconstruction. Zbl 0925.05059Kratsch, Dieter; Hemachandra, Lane A. 4 1991 Competing provers yield improved Karp-Lipton collapse results. Zbl 1035.68053Cai, Jin-Yi; Chakaravarthy, Venkatesan T.; Hemaspaandra, Lane A.; Ogihara, Mitsunori 4 2003 Three hierarchies of simple games parameterized by “resource” parameters. Zbl 1282.91029Gvozdeva, Tatiana; Hemaspaandra, Lane A.; Slinko, Arkadii 4 2013 The complexity of power-index comparison. Zbl 1143.91321Faliszewski, Piotr; Hemaspaandra, Lane A. 4 2008 On approximating optimal weighted lobbying, and frequency of correctness versus average-case polynomial time. Zbl 1135.91343Erdélyi, Gábor; Hemaspaandra, Lane A.; Rothe, Jörg; Spakowski, Holger 4 2007 Online voter control in sequential elections. Zbl 1327.68119Hemaspaandra, Edith; Hemaspaandra, Lane A.; Rothe, Jörg 4 2012 On sparse oracles separating feasible complexity classes. Zbl 0605.68034Hartmanis, Juris; Hemachandra, Lane 3 1986 Robust reductions. Zbl 0946.68053Cai, J.-Y.; Hemaspaandra, L. A.; Wechsung, G. 3 1999 Promises and fault-tolerant database access. Zbl 0794.68059Cai, Jin-yi; Hemachandra, Lane A.; Vyskoč, Jozef 3 1993 Space-efficient recognition of sparse self-reducible languages. Zbl 0812.68073Hemaspaandra, Lane A.; Ogihara, Mitsunori; Toda, Seinosuke 3 1994 On sets polynomially enumerable by iteration. Zbl 0745.68047Hemachandra, Lane A.; Hoene, Albrecht; Siefkes, Dirk; Young, Paul 3 1991 Reducibility classes of P-selective sets. Zbl 0872.68043Hemaspaandra, Lane A.; Hoene, Albrecht; Ogihara, Mitsunori 3 1996 An introduction to query order. Zbl 0889.68061Hemaspaandra, Edith; Hemaspaandra, Lane A.; Hempel, Harald 3 1997 Easily checked generalized self-reducibility. Zbl 0830.68045Hemaspaandra, Lane A.; Silvestri, Riccardo 3 1995 Complexity results in graph reconstruction. Zbl 1117.05078Hemaspaandra, Edith; Hemaspaandra, Lane A.; Radziszowski, Stanisław P.; Tripathi, Rahul 3 2007 On characterizing the existence of partial one-way permutations. Zbl 1013.68082Rothe, Jörg; Hemaspaandra, Lane A. 3 2002 Almost-everywhere superiority for quantum polynomial time. Zbl 1012.68067Hemaspaandra, Edith; Hemaspaandra, Lane A.; Zimand, Marius 3 2002 Complexity classes without machines: on complete languages for UP. Zbl 0655.68043Hartmanis, Juris; Hemachandra, Lane 3 1986 If P \(\neq\) NP then some strongly noninvertible functions are invertible. Zbl 1100.68038Hemaspaandra, Lane A.; Pasanen, Kari; Rothe, Jörg 3 2006 Frequency of correctness versus average polynomial time. Zbl 1200.68124Erdélyi, Gábor; Hemaspaandra, Lane A.; Rothe, Jörg; Spakowski, Holger 3 2009 Fault-tolerance and complexity (extended abstract). Zbl 1418.68075Hemachandra, Lane A. 2 1993 Manipulation complexity of same-system runoff elections. Zbl 1346.91071Fitzsimmons, Zack; Hemaspaandra, Edith; Hemaspaandra, Lane A. 2 2016 Computing solutions uniquely collapses the polynomial hierarchy. Zbl 0953.68541Hemaspaandra, Lane A.; Naik, Ashish V.; Ogihara, Mitsunori; Selman, Alan L. 2 1994 Restrictive acceptance suffices for equivalence problems. Zbl 0948.68091Borchert, Bernd; Hemaspaandra, Lane A.; Rothe, Jörg 2 1999 A second step towards complexity-theoretic analogs of Rice’s Theorem. Zbl 0945.68103Hemaspaandra, L. A.; Rothe, J. 2 2000 Polynomial-time multi-selectivity. Zbl 0960.68078Hemaspaandra, Lane A.; Jiang, Zhigen; Rothe, Joerg; Watanabe, Osamu 2 1997 Defying upward and downward separation. Zbl 0802.68050Hemachandra, Lane A.; Jha, Sudhir K. 2 1993 Polynomial-time functions generate SAT: On P-splinters. Zbl 0755.68067Hemachandra, Lane A.; Hoene, Albrecht; Siefkes, Dirk 2 1989 Extending downward collapse from 1-versus-2 queries to \(j\)-versus-\(j+1\) queries. Zbl 0936.68048Hemaspaandra, Edith; Hemaspaandra, Lane A.; Hempel, Harald 2 1999 The complexity of computing the size of an interval. Zbl 0986.68043Hemaspaandra, Lane A.; Kosub, Sven; Wagner, Klaus W. 2 2001 The complexity of online bribery in sequential elections (extended abstract). Zbl 07450032Hemaspaandra, Edith; Hemaspaandra, Lane A.; Rothe, Jörg 2 2019 Recursion-theoretic ranking and compression. Zbl 1459.03059Hemaspaandra, Lane A.; Rubery, Daniel 1 2019 Closure and nonclosure properties of the compressible and rankable sets. Zbl 1425.03014Abascal, Jackson; Hemaspaandra, Lane A.; Maimon, Shir; Rubery, Daniel 1 2019 The complexity of controlling candidate-sequential elections. Zbl 1371.91053Hemaspaandra, Edith; Hemaspaandra, Lane A.; Rothe, Jörg 5 2017 Schulze and ranked-pairs voting are fixed-parameter tractable to bribe, manipulate, and control. Zbl 1346.91072Hemaspaandra, Lane A.; Lavaee, Rahman; Menton, Curtis 6 2016 Manipulation complexity of same-system runoff elections. Zbl 1346.91071Fitzsimmons, Zack; Hemaspaandra, Edith; Hemaspaandra, Lane A. 2 2016 Dogson’s rule and Yong’s rule. Zbl 1452.91124Caragiannis, Ioannis; Hemaspaandra, Edith; Hemaspaandra, Lane A. 2 2016 Bypassing combinatorial protections: polynomial-time algorithms for single-peaked electorates. Zbl 1337.91039Brandt, Felix; Brill, Markus; Hemaspaandra, Edith; Hemaspaandra, Lane A. 13 2015 Weighted electoral control. Zbl 1328.91068Faliszewski, Piotr; Hemaspaandra, Edith; Hemaspaandra, Lane A. 9 2015 More natural models of electoral control by partition. Zbl 1405.91151Erdélyi, Gábor; Hemaspaandra, Edith; Hemaspaandra, Lane A. 8 2015 The complexity of manipulative attacks in nearly single-peaked electorates. Zbl 1334.68098Faliszewski, Piotr; Hemaspaandra, Edith; Hemaspaandra, Lane A. 16 2014 The complexity of online manipulation of sequential elections. Zbl 1285.68223Hemaspaandra, Edith; Hemaspaandra, Lane A.; Rothe, Jörg 6 2014 Search versus decision for election manipulation problems. Zbl 1354.91054Hemaspaandra, Edith; Hemaspaandra, Lane A.; Menton, Curtis 13 2013 Three hierarchies of simple games parameterized by “resource” parameters. Zbl 1282.91029Gvozdeva, Tatiana; Hemaspaandra, Lane A.; Slinko, Arkadii 4 2013 Online voter control in sequential elections. Zbl 1327.68119Hemaspaandra, Edith; Hemaspaandra, Lane A.; Rothe, Jörg 4 2012 Multimode control attacks on elections. Zbl 1242.91055Faliszewski, Piotr; Hemaspaandra, Edith; Hemaspaandra, Lane A. 23 2011 The shield that never was: societies with single-peaked preferences are more open to manipulation and control. Zbl 1218.91042Faliszewski, Piotr; Hemaspaandra, Edith; Hemaspaandra, Lane A.; Rothe, Jörg 22 2011 Computational aspects of approval voting. Zbl 1348.91101Baumeister, Dorothea; Erdélyi, Gábor; Hemaspaandra, Edith; Hemaspaandra, Lane A.; Rothe, Jörg 19 2010 Llull and Copeland voting computationally resist bribery and constructive control. Zbl 1180.91091Faliszewski, P.; Hemaspaandra, E.; Hemaspaandra, L. A.; Rothe, J. 62 2009 How hard is bribery in elections? Zbl 1180.91090Faliszewski, P.; Hemaspaandra, E.; Hemaspaandra, L. A. 52 2009 A richer understanding of the complexity of election systems. Zbl 1167.91339Faliszewski, Piotr; Hemaspaandra, Edith; Hemaspaandra, Lane A.; Rothe, Jörg 30 2009 Hybrid elections broaden complexity-theoretic resistance to control. Zbl 1177.91066Hemaspaandra, Edith; Hemaspaandra, Lane A.; Rothe, Jörg 20 2009 Guarantees for the success frequency of an algorithm for finding Dodgson-election winners. Zbl 1188.91062Homan, Christopher M.; Hemaspaandra, Lane A. 10 2009 The complexity of power-index comparison. Zbl 1155.91013Faliszewski, Piotr; Hemaspaandra, Lane 6 2009 Generalized juntas and NP-hard sets. Zbl 1171.68012Erdélyi, Gábor; Hemaspaandra, Lane A.; Rothe, Jörg; Spakowski, Holger 6 2009 Frequency of correctness versus average polynomial time. Zbl 1200.68124Erdélyi, Gábor; Hemaspaandra, Lane A.; Rothe, Jörg; Spakowski, Holger 3 2009 Copeland voting fully resists constructive control. Zbl 1143.91320Faliszewski, Piotr; Hemaspaandra, Edith; Hemaspaandra, Lane A.; Rothe, Jörg 9 2008 The complexity of power-index comparison. Zbl 1143.91321Faliszewski, Piotr; Hemaspaandra, Lane A. 4 2008 Enforcing and defying associativity, commutativity, totality, and strong noninvertibility for worst-case one-way functions. Zbl 1146.68036Hemaspaandra, Lane A.; Rothe, Jörg; Saxena, Amitabh 1 2008 The consequences of eliminating NP solutions. Zbl 1302.68124Faliszewski, Piotr; Hemaspaandra, Lane A. 1 2008 Anyone but him: the complexity of precluding an alternative. Zbl 1168.91346Hemaspaandra, Edith; Hemaspaandra, Lane A.; Rothe, Jörg 44 2007 Dichotomy for voting systems. Zbl 1154.91381Hemaspaandra, Edith; Hemaspaandra, Lane A. 24 2007 On approximating optimal weighted lobbying, and frequency of correctness versus average-case polynomial time. Zbl 1135.91343Erdélyi, Gábor; Hemaspaandra, Lane A.; Rothe, Jörg; Spakowski, Holger 4 2007 Complexity results in graph reconstruction. Zbl 1117.05078Hemaspaandra, Edith; Hemaspaandra, Lane A.; Radziszowski, Stanisław P.; Tripathi, Rahul 3 2007 Cluster computing and the power of edge recognition. Zbl 1121.68099Hemaspaandra, Lane A.; Homan, Christopher M.; Kosub, Sven 1 2007 On the complexity of kings. Zbl 1135.68517Hemaspaandra, Edith; Hemaspaandra, Lane A.; Tantau, Till; Watanabe, Osamu 1 2007 The complexity of computing the size of an interval. Zbl 1123.68041Hemaspaandra, Lane A.; Homan, Christopher M.; Kosub, Sven; Wagner, Klaus W. 7 2006 Guarantees for the success frequency of an algorithm for finding Dodgson-election winners. Zbl 1132.91399Homan, Christopher M.; Hemaspaandra, Lane A. 4 2006 If P \(\neq\) NP then some strongly noninvertible functions are invertible. Zbl 1100.68038Hemaspaandra, Lane A.; Pasanen, Kari; Rothe, Jörg 3 2006 The complexity of finding top-Toda-equivalence-class members. Zbl 1100.68033Hemaspaandra, Lane A.; Ogihara, Mitsunori; Zaki, Mohammed J.; Zimand, Marius 2 2006 P-selectivity, immunity, and the power of one bit. Zbl 1175.03024Hemaspaandra, Lane A.; Torenvliet, Leen 1 2006 Competing provers yield improved Karp-Lipton collapse results. Zbl 1066.68050Cai, Jin-Yi; Chakaravarthy, Venkatesan T.; Hemaspaandra, Lane A.; Ogihara, Mitsunori 13 2005 Enforcing and defying associativity, commutativity, totality, and strong noninvertibility for one-way functions in complexity theory. Zbl 1171.68482Hemaspaandra, Lane A.; Rothe, Jörg; Saxena, Amitabh 2 2005 Extending downward collapse from 1-versus-2 queries to \(m\)-versus-\(m + 1\) queries. Zbl 1082.68035Hemaspaandra, Edith; Hemaspaandra, Lane A.; Hempel, Harald 1 2005 All superlinear inverse schemes are coNP-hard. Zbl 1079.68041Hemaspaandra, Edith; Hemaspaandra, Lane A.; Hempel, Harald 1 2005 Query-monotonic Turing reductions. Zbl 1123.68333Hemaspaandra, Lane A.; Thakur, Mayur 1 2005 Context-free languages can be accepted with absolutely no space overhead. Zbl 1101.68655Hemaspaandra, Lane A.; Mukherji, Proshanto; Tantau, Till 1 2005 Lower bounds and the hardness of counting properties. Zbl 1105.68048Hemaspaandra, Lane A.; Thakur, Mayur 1 2004 Algebraic properties for selector functions. Zbl 1101.68596Hemaspaandra, Lane A.; Hempel, Harald; Nickelsen, Arfst 1 2004 All superlinear inverse schemes are coNP-hard. Zbl 1096.68064Hemaspaandra, Edith; Hemaspaandra, Lane A.; Hempel, Harald 1 2004 Theory of semi-feasible algorithms. Zbl 1021.68042Hemaspaandra, Lane A.; Torenvliet, Leen 8 2003 Competing provers yield improved Karp-Lipton collapse results. Zbl 1035.68053Cai, Jin-Yi; Chakaravarthy, Venkatesan T.; Hemaspaandra, Lane A.; Ogihara, Mitsunori 4 2003 P-immune sets with holes lack self-reducibility properties. Zbl 1044.68068Hemaspaandra, Lane A.; Hempel, Harald 2 2003 Computation with absolutely no space overhead. Zbl 1037.68060Hemaspaandra, Lane A.; Mukherji, Proshanto; Tantau, Till 2 2003 The complexity theory companion. Zbl 0993.68042Hemaspaandra, Lane A.; Ogihara, Mitsunori 35 2002 On characterizing the existence of partial one-way permutations. Zbl 1013.68082Rothe, Jörg; Hemaspaandra, Lane A. 3 2002 Almost-everywhere superiority for quantum polynomial time. Zbl 1012.68067Hemaspaandra, Edith; Hemaspaandra, Lane A.; Zimand, Marius 3 2002 Reducing the number of solutions of NP functions. Zbl 1018.68032Hemaspaandra, Lane A.; Ogihara, Mitsunori; Wechsung, Gerd 1 2002 The complexity of computing the size of an interval. Zbl 0986.68043Hemaspaandra, Lane A.; Kosub, Sven; Wagner, Klaus W. 2 2001 If \(\text{P} \neq \text{NP}\) then some strongly noninvertible functions are invertible. Zbl 0999.68076Hemaspaandra, Lane A.; Pasanen, Kari; Rothe, Jörg 1 2001 Computational politics: Electoral systems. Zbl 0996.68065Hemaspaandra, Edith; Hemaspaandra, Lane A. 6 2000 Characterizing the existence of one-way permutations. Zbl 0945.68053Hemaspaandra, L. A.; Rothe, J. 5 2000 A second step towards complexity-theoretic analogs of Rice’s Theorem. Zbl 0945.68103Hemaspaandra, L. A.; Rothe, J. 2 2000 Restrictive acceptance suffices for equivalence problems. Zbl 0951.68041Borchert, Bernd; Hemaspaandra, Lane A.; Rothe, Jörg 1 2000 Creating strong, total, commutative, associative one-way functions from any one-way function in complexity theory. Zbl 0939.68036Hemaspaandra, Lane A.; Rothe, Jörg 11 1999 Robust reductions. Zbl 0946.68053Cai, J.-Y.; Hemaspaandra, L. A.; Wechsung, G. 3 1999 Restrictive acceptance suffices for equivalence problems. Zbl 0948.68091Borchert, Bernd; Hemaspaandra, Lane A.; Rothe, Jörg 2 1999 Extending downward collapse from 1-versus-2 queries to \(j\)-versus-\(j+1\) queries. Zbl 0936.68048Hemaspaandra, Edith; Hemaspaandra, Lane A.; Hempel, Harald 2 1999 Self-specifying machines. Zbl 1319.68083Hemaspaandra, Lane A.; Hempel, Harald; Wechsung, Gerd 1 1999 A downward collapse within the polynomial hierarchy. Zbl 0915.68070Hemaspaandra, Edith; Hemaspaandra, Lane A.; Hempel, Harald 8 1998 Query order. Zbl 0915.68071Hemaspaandra, Lane A.; Hempel, Harald; Wechsung, Gerd 7 1998 Query order and the polynomial hierarchy. Zbl 0961.68052Hemaspaandra, Edith; Hemaspaandra, Lane A.; Hempel, Harald 4 1998 Boolean operations, joins, and the extended low hierarchy. Zbl 0913.68077Hemaspaandra, Lane A.; Jiang, Zhigen; Rothe, Jörg; Watanabe, Osamu 4 1998 \(R_{1-tt}^{{\mathcal SN}}\)(NP) distinguishes robust many-one and Turing completeness. Zbl 0896.68060Hemaspaandra, E.; Hemaspaandra, L. A.; Hempel, H. 1 1998 A note on linear-nondeterminism, linear-sized, Karp-Lipton advice for the P-selective sets. Zbl 0967.68082Hemaspaandra, Lane A.; Nasipak, Christopher; Parkins, Keith 1 1998 Robust reductions. Zbl 0912.68051Cai, Jin-Yi; Hemaspaandra, Lane A.; Wechsung, Gerd 1 1998 Exact analysis of Dodgson elections: Lewis Carroll’s 1876 voting system is complete for parallel access to NP. Zbl 0904.68111Hemaspaandra, Edith; Hemaspaandra, Lane A.; Rothe, Jörg 43 1997 Threshold computation and cryptographic security. Zbl 0868.68056Han, Yenjo; Hemaspaandra, Lane A.; Thierauf, Thomas 13 1997 Easy sets and hard certificate schemes. Zbl 0883.68072Hemaspaandra, Lane A.; Rothe, Jörg; Wechsung, Gerd 11 1997 Unambiguous computation: Boolean hierarchies and sparse Turing-complete sets. Zbl 0870.68070Hemaspaandra, Lane A.; Rothe, Jörg 5 1997 An introduction to query order. Zbl 0889.68061Hemaspaandra, Edith; Hemaspaandra, Lane A.; Hempel, Harald 3 1997 Polynomial-time multi-selectivity. Zbl 0960.68078Hemaspaandra, Lane A.; Jiang, Zhigen; Rothe, Joerg; Watanabe, Osamu 2 1997 Exact analysis of Dodgson elections: Lewis Carroll’s 1876 voting system is complete for parallel access to NP. Zbl 1401.68097Hemaspaandra, Edith; Hemaspaandra, Lane A.; Rothe, Jörg 1 1997 Logspace reducibility: Models and equivalences. Zbl 0870.68087Hemaspaandra, Lane A.; Jiang, Zhigen 1 1997 Witness-isomorphic reductions and local search. Zbl 0883.03023Fischer, Sophie; Hemaspaandra, Lane; Torenvliet, Leen 1 1997 Universally serializable computation. Zbl 0901.68065Hemaspaandra, Lane A.; Ogihara, Mitsunori 1 1997 Computing solutions uniquely collapses the polynomial hierarchy. Zbl 0857.68045Hemaspaandra, Lane A.; Naik, Ashish V.; Ogihara, Mitsunori; Selman, Alan L. 18 1996 Strong self-reducibility precludes strong immunity. Zbl 0857.68046Hemaspaandra, L. A.; Zimand, M. 5 1996 Optimal advice. Zbl 0872.68042Hemaspaandra, Lane A.; Torenvliet, Leen 4 1996 Reducibility classes of P-selective sets. Zbl 0872.68043Hemaspaandra, Lane A.; Hoene, Albrecht; Ogihara, Mitsunori 3 1996 Nondeterministically selective sets. Zbl 0843.68031Hemaspaandra, Lane A.; Hoene, Albrecht; Naik, Ashish V.; Ogihara, Mitsunori; Selman, Alan L.; Thierauf, Thomas; Wang, Jie 7 1995 Defying upward and downward separation. Zbl 0832.68046Hemaspaandra, Lane A.; Jha, Sudhir K. 6 1995 P-selectivity: Intersections and indices. Zbl 0873.68065Hemaspaandra, Lane A.; Jiang, Zhigen 5 1995 Easily checked generalized self-reducibility. Zbl 0830.68045Hemaspaandra, Lane A.; Silvestri, Riccardo 3 1995 Pseudorandom generators and the frequency of simplicity. Zbl 1379.68186Han, Yenjo; Hemaspaandra, Lane A. 1 1995 On the complexity of graph reconstruction. Zbl 0806.05051Kratsch, Dieter; Hemaspaandra, Lane A. 6 1994 Space-efficient recognition of sparse self-reducible languages. Zbl 0812.68073Hemaspaandra, Lane A.; Ogihara, Mitsunori; Toda, Seinosuke 3 1994 Computing solutions uniquely collapses the polynomial hierarchy. Zbl 0953.68541Hemaspaandra, Lane A.; Naik, Ashish V.; Ogihara, Mitsunori; Selman, Alan L. 2 1994 Quasi-injective reductions. Zbl 0811.68079Hemaspaandra, Edith; Hemaspaandra, Lane A. 1 1994 A complexity theory for feasible closure properties. Zbl 0798.68060Ogiwara, Mitsunori; Hemachandra, Lane A. 31 1993 ...and 40 more Documents all cited Publications top 5 cited Publications all top 5 Cited by 594 Authors 68 Hemaspaandra, Lane A. 41 Rothe, Jörg-Matthias 23 Hemaspaandra, Edith 17 Faliszewski, Piotr 16 Beigel, Richard 12 Köbler, Johannes 12 Ogihara, Mitsunori 10 Allender, Eric W. 10 Niedermeier, Rolf 9 Bredereck, Robert 9 Erdélyi, Gábor 9 Spakowski, Holger 9 Wagner, Klaus W. 9 Watanabe, Osamu 8 Baumeister, Dorothea 8 Betzler, Nadja 8 Cai, Jin-Yi 8 Elkind, Edith 8 Fortnow, Lance J. 8 Guo, Jiong 7 Glaßer, Christian 7 Slinko, Arkadii M. 6 Birget, Jean-Camille 6 Brandt, Felix 6 Dey, Palash 6 Dorn, Britta 6 Gasarch, William Ian 6 Goldsmith, Judy 6 Hartmanis, Juris 6 Hempel, Harald 6 Homan, Christopher M. 6 Silvestri, Riccardo 6 Torenvliet, Leen 6 Wechsung, Gerd 6 Zimand, Marius 5 Arvind, Vikraman 5 Beyersdorff, Olaf 5 Buhrman, Harry 5 Chang, Richard 5 Chen, Jiehua 5 Kosub, Sven 5 Misra, Neeldhara 5 Ogiwara, Mitsunori 5 Procaccia, Ariel D. 5 Rosenschein, Jeffrey S. 5 Schlotter, Ildikó 5 Selman, Alan L. 5 Tantau, Till 5 Toda, Seinosuke 5 Yamakami, Tomoyuki 4 Bachrach, Yoram 4 Borchert, Bernd 4 Cygan, Marek 4 Fellows, Michael Ralph 4 Fu, Bin 4 Mundhenk, Martin 4 Pavan, Aduri 4 Pilipczuk, Marcin L. 4 Pilipczuk, Michał 4 Schend, Lena 4 Selivanov, Viktor L’vovich 4 Skowron, Piotr 4 Talmon, Nimrod 4 Thakur, Mayur 4 Torán, Jacobo 4 Tripathi, Rahul 4 Vinodchandran, N. Variyam 4 Yang, Yongjie 3 Agrawal, Manindra 3 Brill, Markus 3 Caragiannis, Ioannis 3 Dell, Holger 3 Fenner, Stephen A. 3 Fischer, Felix 3 Harrenstein, Paul 3 Hoene, Albrecht 3 Homer, Steven 3 Impagliazzo, Russell 3 Kułakowski, Konrad 3 Kurz, Sascha 3 Lang, Jérôme 3 Liu, Hong 3 Lozano, Antoni 3 Mattei, Nicholas 3 Menton, Curtis 3 Narahari, Yadati 3 Pagourtzis, Aris T. 3 Papadimitriou, Christos Harilaos 3 Sadowski, Zenon 3 Schöning, Uwe 3 Sengupta, Samik 3 Stephan, Frank 3 Thierauf, Thomas 3 Uhlmann, Johannes 3 van Melkebeek, Dieter 3 Vollmer, Heribert 3 Zhang, Liyu 3 Zhu, Daming 3 Zuckerman, Michael 2 Amir, Amihood ...and 494 more Authors all top 5 Cited in 64 Serials 90 Theoretical Computer Science 52 Journal of Computer and System Sciences 36 Information Processing Letters 33 Information and Computation 25 Artificial Intelligence 19 Mathematical Systems Theory 19 Computational Complexity 16 Theory of Computing Systems 13 Annals of Mathematics and Artificial Intelligence 12 Social Choice and Welfare 7 RAIRO. Informatique Théorique et Applications 7 Mathematical Logic Quarterly (MLQ) 6 Algorithmica 6 International Journal of Foundations of Computer Science 5 Mathematical Social Sciences 4 The Journal of Symbolic Logic 4 International Journal of Algebra and Computation 4 The Journal of Artificial Intelligence Research (JAIR) 4 RAIRO. Theoretical Informatics and Applications 3 Annals of Pure and Applied Logic 3 European Journal of Operational Research 3 Journal of Combinatorial Optimization 3 Logical Methods in Computer Science 2 Discrete Applied Mathematics 2 International Journal of Game Theory 2 Semigroup Forum 2 SIAM Journal on Computing 2 International Journal of Approximate Reasoning 2 Computer Science Review 1 Acta Informatica 1 Discrete Mathematics 1 Metrika 1 Reports on Mathematical Physics 1 Journal of Mathematical Economics 1 Journal of Philosophical Logic 1 Order 1 Journal of Symbolic Computation 1 Journal of Global Optimization 1 Automation and Remote Control 1 Linear Algebra and its Applications 1 Archive for Mathematical Logic 1 Mathematical Programming. Series A. Series B 1 Tatra Mountains Mathematical Publications 1 Journal of Mathematical Sciences (New York) 1 Complexity 1 Journal of Heuristics 1 INFORMS Journal on Computing 1 Journal of the ACM 1 Wuhan University Journal of Natural Sciences (WUJNS) 1 Proceedings of the Royal Society of London. Series A. Mathematical, Physical and Engineering Sciences 1 LMS Journal of Computation and Mathematics 1 CEJOR. Central European Journal of Operations Research 1 Review of Economic Design 1 Theory and Practice of Logic Programming 1 Quantum Information Processing 1 Journal of Applied Logic 1 Discrete Optimization 1 Journal of Mathematical Cryptology 1 RAIRO. Theoretical Informatics and Applications 1 ACM Transactions on Algorithms 1 Games 1 ACM Transactions on Computation Theory 1 Proceedings of the Royal Society of London. A. Mathematical, Physical and Engineering Sciences 1 Journal of Combinatorial Algebra all top 5 Cited in 18 Fields 402 Computer science (68-XX) 116 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 73 Mathematical logic and foundations (03-XX) 27 Combinatorics (05-XX) 19 Operations research, mathematical programming (90-XX) 12 Information and communication theory, circuits (94-XX) 10 Quantum theory (81-XX) 7 Group theory and generalizations (20-XX) 4 Statistics (62-XX) 2 Linear and multilinear algebra; matrix theory (15-XX) 1 Order, lattices, ordered algebraic structures (06-XX) 1 General algebraic systems (08-XX) 1 Number theory (11-XX) 1 Dynamical systems and ergodic theory (37-XX) 1 Operator theory (47-XX) 1 Numerical analysis (65-XX) 1 Biology and other natural sciences (92-XX) 1 Systems theory; control (93-XX) Citations by Year