×

Hemaspaandra, Lane A.

Compute Distance To:
Author ID: hemaspaandra.lane-a Recent zbMATH articles by "Hemaspaandra, Lane A."
Published as: Hemaspaandra, Lane A.; Hemachandra, Lane A.; Hemaspaandra, L. A.; Hemachandra, Lane; Hemaspaandra, Lane; Hemachandra, L.; Hemachandra, L. A.
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

Publications by Year

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.91091
Faliszewski, P.; Hemaspaandra, E.; Hemaspaandra, L. A.; Rothe, J.
62
2009
The Boolean hierarchy. I: Structural properties. Zbl 0676.68011
Cai, 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.91090
Faliszewski, P.; Hemaspaandra, E.; Hemaspaandra, L. A.
52
2009
Anyone but him: the complexity of precluding an alternative. Zbl 1168.91346
Hemaspaandra, 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.68111
Hemaspaandra, Edith; Hemaspaandra, Lane A.; Rothe, Jörg
43
1997
The strong exponential hierarchy collapses. Zbl 0693.03022
Hemachandra, Lane A.
36
1989
The complexity theory companion. Zbl 0993.68042
Hemaspaandra, Lane A.; Ogihara, Mitsunori
35
2002
Complexity classes without machines: on complete languages for UP. Zbl 0655.68044
Hartmanis, Juris; Hemachandra, Lane A.
35
1988
On the power of parity polynomial time. Zbl 0718.68038
Cai, Jin-yi; Hemachandra, Lane A.
33
1990
A complexity theory for feasible closure properties. Zbl 0798.68060
Ogiwara, Mitsunori; Hemachandra, Lane A.
31
1993
A richer understanding of the complexity of election systems. Zbl 1167.91339
Faliszewski, Piotr; Hemaspaandra, Edith; Hemaspaandra, Lane A.; Rothe, Jörg
30
2009
The Boolean hierarchy. II: Applications. Zbl 0676.68012
Cai, Jin-Yi; Gundermann, Thomas; Hartmanis, Juris; Hemachandra, Lane A.; Sewelson, Vivian; Wagner, Klaus; Wechsung, Gerd
27
1989
Dichotomy for voting systems. Zbl 1154.91381
Hemaspaandra, Edith; Hemaspaandra, Lane A.
24
2007
Multimode control attacks on elections. Zbl 1242.91055
Faliszewski, 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.91042
Faliszewski, Piotr; Hemaspaandra, Edith; Hemaspaandra, Lane A.; Rothe, Jörg
22
2011
Hybrid elections broaden complexity-theoretic resistance to control. Zbl 1177.91066
Hemaspaandra, Edith; Hemaspaandra, Lane A.; Rothe, Jörg
20
2009
Computational aspects of approval voting. Zbl 1348.91101
Baumeister, Dorothea; Erdélyi, Gábor; Hemaspaandra, Edith; Hemaspaandra, Lane A.; Rothe, Jörg
19
2010
Enumerative counting is hard. Zbl 0679.68072
Cai, Jin-Yi; Hemachandra, Lane A.
19
1989
Computing solutions uniquely collapses the polynomial hierarchy. Zbl 0857.68045
Hemaspaandra, Lane A.; Naik, Ashish V.; Ogihara, Mitsunori; Selman, Alan L.
18
1996
Reductions to sets of low information content. Zbl 0794.68058
Arvind, 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.03031
Hartmanis, Juris; Hemachandra, Lane A.
17
1991
The complexity of manipulative attacks in nearly single-peaked electorates. Zbl 1334.68098
Faliszewski, Piotr; Hemaspaandra, Edith; Hemaspaandra, Lane A.
16
2014
Bypassing combinatorial protections: polynomial-time algorithms for single-peaked electorates. Zbl 1337.91039
Brandt, Felix; Brill, Markus; Hemaspaandra, Edith; Hemaspaandra, Lane A.
13
2015
Competing provers yield improved Karp-Lipton collapse results. Zbl 1066.68050
Cai, Jin-Yi; Chakaravarthy, Venkatesan T.; Hemaspaandra, Lane A.; Ogihara, Mitsunori
13
2005
Threshold computation and cryptographic security. Zbl 0868.68056
Han, Yenjo; Hemaspaandra, Lane A.; Thierauf, Thomas
13
1997
Search versus decision for election manipulation problems. Zbl 1354.91054
Hemaspaandra, Edith; Hemaspaandra, Lane A.; Menton, Curtis
13
2013
On the complexity of ranking. Zbl 0708.68020
Hemachandra, Lane A.; Rudich, Steven
12
1990
Lower bounds for the low hierarchy. Zbl 0799.68081
Allender, Eric; Hemachandra, Lane A.
11
1992
Easy sets and hard certificate schemes. Zbl 0883.68072
Hemaspaandra, 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.68036
Hemaspaandra, Lane A.; Rothe, Jörg
11
1999
Probabilistic polynomial time is closed under parity reductions. Zbl 0714.68031
Beigel, Richard; Hemachandra, Lane A.; Wechsung, Gerd
11
1991
Guarantees for the success frequency of an algorithm for finding Dodgson-election winners. Zbl 1188.91062
Homan, Christopher M.; Hemaspaandra, Lane A.
10
2009
A note on enumerative counting. Zbl 0733.68030
Cai, Jinyi; Hemachandra, Lane A.
10
1991
Weighted electoral control. Zbl 1328.91068
Faliszewski, Piotr; Hemaspaandra, Edith; Hemaspaandra, Lane A.
9
2015
Copeland voting fully resists constructive control. Zbl 1143.91320
Faliszewski, Piotr; Hemaspaandra, Edith; Hemaspaandra, Lane A.; Rothe, Jörg
9
2008
More natural models of electoral control by partition. Zbl 1405.91151
Erdélyi, Gábor; Hemaspaandra, Edith; Hemaspaandra, Lane A.
8
2015
Relating equivalence and reducibility to sparse sets. Zbl 0761.68039
Allender, Eric; Hemachandra, Lane A.; Ogiwara, Mitsunori; Watanabe, Osamu
8
1992
A downward collapse within the polynomial hierarchy. Zbl 0915.68070
Hemaspaandra, Edith; Hemaspaandra, Lane A.; Hempel, Harald
8
1998
Theory of semi-feasible algorithms. Zbl 1021.68042
Hemaspaandra, Lane A.; Torenvliet, Leen
8
2003
Banishing robust Turing completeness. Zbl 0802.68049
Hemaspaandra, Lane A.; Jain, Sanjay; Vereshchagin, Nikolaj K.
7
1993
Nondeterministically selective sets. Zbl 0843.68031
Hemaspaandra, Lane A.; Hoene, Albrecht; Naik, Ashish V.; Ogihara, Mitsunori; Selman, Alan L.; Thierauf, Thomas; Wang, Jie
7
1995
Query order. Zbl 0915.68071
Hemaspaandra, Lane A.; Hempel, Harald; Wechsung, Gerd
7
1998
The complexity of computing the size of an interval. Zbl 1123.68041
Hemaspaandra, Lane A.; Homan, Christopher M.; Kosub, Sven; Wagner, Klaus W.
7
2006
Robust machines accept easy sets. Zbl 0701.68028
Hartmanis, Juris; Hemachandra, Lane A.
7
1990
Schulze and ranked-pairs voting are fixed-parameter tractable to bribe, manipulate, and control. Zbl 1346.91072
Hemaspaandra, Lane A.; Lavaee, Rahman; Menton, Curtis
6
2016
On the complexity of graph reconstruction. Zbl 0806.05051
Kratsch, Dieter; Hemaspaandra, Lane A.
6
1994
Near-testable sets. Zbl 0738.68031
Goldsmith, Judy; Hemachandra, Lane A.; Joseph, Deborah; Young, Paul
6
1991
On sets with efficient implicit membership tests. Zbl 0738.68032
Hemachandra, Lane A.; Hoene, Albrecht
6
1991
Using inductive counting to simulate nondeterministic computation. Zbl 0769.68028
Buntrock, Gerhard; Hemachandra, Lane A.; Siefkes, Dirk
6
1993
Defying upward and downward separation. Zbl 0832.68046
Hemaspaandra, Lane A.; Jha, Sudhir K.
6
1995
The complexity of power-index comparison. Zbl 1155.91013
Faliszewski, Piotr; Hemaspaandra, Lane
6
2009
Computational politics: Electoral systems. Zbl 0996.68065
Hemaspaandra, Edith; Hemaspaandra, Lane A.
6
2000
Generalized juntas and NP-hard sets. Zbl 1171.68012
Erdélyi, Gábor; Hemaspaandra, Lane A.; Rothe, Jörg; Spakowski, Holger
6
2009
The complexity of online manipulation of sequential elections. Zbl 1285.68223
Hemaspaandra, Edith; Hemaspaandra, Lane A.; Rothe, Jörg
6
2014
On sparse oracles separating feasible complexity classes. Zbl 0658.68055
Hartmanis, Juris; Hemachandra, Lane
6
1988
The Boolean hierarchy: Hardware over NP. Zbl 0611.68018
Chai, Jinyi; Hemachandra, Lane
5
1986
Characterizing the existence of one-way permutations. Zbl 0945.68053
Hemaspaandra, L. A.; Rothe, J.
5
2000
On generating solved instances of computational problems. Zbl 0792.68045
Abadi, Martín; Allender, Eric; Broder, Andrei; Feigenbaum, Joan; Hemachandra, Lane A.
5
1990
Simultaneous strong separations of probabilistic and unambiguous complexity classes. Zbl 0766.68038
Eppstein, David; Hemachandra, Lane A.; Tisdall, James; Yener, Bülent
5
1992
On the limitations of locally robust positive reductions. Zbl 0746.68034
Hemachandra, Lane A.; Jain, Sanjay
5
1991
Polynomial-time compression. Zbl 0752.68039
Goldsmith, Judy; Hemachandra, Lane A.; Kunen, Kenneth
5
1992
P-selectivity: Intersections and indices. Zbl 0873.68065
Hemaspaandra, Lane A.; Jiang, Zhigen
5
1995
Unambiguous computation: Boolean hierarchies and sparse Turing-complete sets. Zbl 0870.68070
Hemaspaandra, Lane A.; Rothe, Jörg
5
1997
Strong self-reducibility precludes strong immunity. Zbl 0857.68046
Hemaspaandra, L. A.; Zimand, M.
5
1996
The complexity of controlling candidate-sequential elections. Zbl 1371.91053
Hemaspaandra, Edith; Hemaspaandra, Lane A.; Rothe, Jörg
5
2017
Query order and the polynomial hierarchy. Zbl 0961.68052
Hemaspaandra, Edith; Hemaspaandra, Lane A.; Hempel, Harald
4
1998
Algorithms from complexity theory: Polynomial-time operations for complex sets. Zbl 0819.68063
Hemachandra, Lane A.
4
1990
Optimal advice. Zbl 0872.68042
Hemaspaandra, Lane A.; Torenvliet, Leen
4
1996
Boolean operations, joins, and the extended low hierarchy. Zbl 0913.68077
Hemaspaandra, 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.91399
Homan, Christopher M.; Hemaspaandra, Lane A.
4
2006
On the complexity of graph reconstruction. Zbl 0925.05059
Kratsch, Dieter; Hemachandra, Lane A.
4
1991
Competing provers yield improved Karp-Lipton collapse results. Zbl 1035.68053
Cai, Jin-Yi; Chakaravarthy, Venkatesan T.; Hemaspaandra, Lane A.; Ogihara, Mitsunori
4
2003
Three hierarchies of simple games parameterized by “resource” parameters. Zbl 1282.91029
Gvozdeva, Tatiana; Hemaspaandra, Lane A.; Slinko, Arkadii
4
2013
The complexity of power-index comparison. Zbl 1143.91321
Faliszewski, Piotr; Hemaspaandra, Lane A.
4
2008
On approximating optimal weighted lobbying, and frequency of correctness versus average-case polynomial time. Zbl 1135.91343
Erdélyi, Gábor; Hemaspaandra, Lane A.; Rothe, Jörg; Spakowski, Holger
4
2007
Online voter control in sequential elections. Zbl 1327.68119
Hemaspaandra, Edith; Hemaspaandra, Lane A.; Rothe, Jörg
4
2012
On sparse oracles separating feasible complexity classes. Zbl 0605.68034
Hartmanis, Juris; Hemachandra, Lane
3
1986
Robust reductions. Zbl 0946.68053
Cai, J.-Y.; Hemaspaandra, L. A.; Wechsung, G.
3
1999
Promises and fault-tolerant database access. Zbl 0794.68059
Cai, Jin-yi; Hemachandra, Lane A.; Vyskoč, Jozef
3
1993
Space-efficient recognition of sparse self-reducible languages. Zbl 0812.68073
Hemaspaandra, Lane A.; Ogihara, Mitsunori; Toda, Seinosuke
3
1994
On sets polynomially enumerable by iteration. Zbl 0745.68047
Hemachandra, Lane A.; Hoene, Albrecht; Siefkes, Dirk; Young, Paul
3
1991
Reducibility classes of P-selective sets. Zbl 0872.68043
Hemaspaandra, Lane A.; Hoene, Albrecht; Ogihara, Mitsunori
3
1996
An introduction to query order. Zbl 0889.68061
Hemaspaandra, Edith; Hemaspaandra, Lane A.; Hempel, Harald
3
1997
Easily checked generalized self-reducibility. Zbl 0830.68045
Hemaspaandra, Lane A.; Silvestri, Riccardo
3
1995
Complexity results in graph reconstruction. Zbl 1117.05078
Hemaspaandra, Edith; Hemaspaandra, Lane A.; Radziszowski, Stanisław P.; Tripathi, Rahul
3
2007
On characterizing the existence of partial one-way permutations. Zbl 1013.68082
Rothe, Jörg; Hemaspaandra, Lane A.
3
2002
Almost-everywhere superiority for quantum polynomial time. Zbl 1012.68067
Hemaspaandra, Edith; Hemaspaandra, Lane A.; Zimand, Marius
3
2002
Complexity classes without machines: on complete languages for UP. Zbl 0655.68043
Hartmanis, Juris; Hemachandra, Lane
3
1986
If P \(\neq\) NP then some strongly noninvertible functions are invertible. Zbl 1100.68038
Hemaspaandra, Lane A.; Pasanen, Kari; Rothe, Jörg
3
2006
Frequency of correctness versus average polynomial time. Zbl 1200.68124
Erdélyi, Gábor; Hemaspaandra, Lane A.; Rothe, Jörg; Spakowski, Holger
3
2009
Fault-tolerance and complexity (extended abstract). Zbl 1418.68075
Hemachandra, Lane A.
2
1993
Manipulation complexity of same-system runoff elections. Zbl 1346.91071
Fitzsimmons, Zack; Hemaspaandra, Edith; Hemaspaandra, Lane A.
2
2016
Computing solutions uniquely collapses the polynomial hierarchy. Zbl 0953.68541
Hemaspaandra, Lane A.; Naik, Ashish V.; Ogihara, Mitsunori; Selman, Alan L.
2
1994
Restrictive acceptance suffices for equivalence problems. Zbl 0948.68091
Borchert, Bernd; Hemaspaandra, Lane A.; Rothe, Jörg
2
1999
A second step towards complexity-theoretic analogs of Rice’s Theorem. Zbl 0945.68103
Hemaspaandra, L. A.; Rothe, J.
2
2000
Polynomial-time multi-selectivity. Zbl 0960.68078
Hemaspaandra, Lane A.; Jiang, Zhigen; Rothe, Joerg; Watanabe, Osamu
2
1997
Defying upward and downward separation. Zbl 0802.68050
Hemachandra, Lane A.; Jha, Sudhir K.
2
1993
Polynomial-time functions generate SAT: On P-splinters. Zbl 0755.68067
Hemachandra, Lane A.; Hoene, Albrecht; Siefkes, Dirk
2
1989
Extending downward collapse from 1-versus-2 queries to \(j\)-versus-\(j+1\) queries. Zbl 0936.68048
Hemaspaandra, Edith; Hemaspaandra, Lane A.; Hempel, Harald
2
1999
The complexity of computing the size of an interval. Zbl 0986.68043
Hemaspaandra, Lane A.; Kosub, Sven; Wagner, Klaus W.
2
2001
The complexity of online bribery in sequential elections (extended abstract). Zbl 07450032
Hemaspaandra, Edith; Hemaspaandra, Lane A.; Rothe, Jörg
2
2019
Recursion-theoretic ranking and compression. Zbl 1459.03059
Hemaspaandra, Lane A.; Rubery, Daniel
1
2019
Closure and nonclosure properties of the compressible and rankable sets. Zbl 1425.03014
Abascal, Jackson; Hemaspaandra, Lane A.; Maimon, Shir; Rubery, Daniel
1
2019
The complexity of controlling candidate-sequential elections. Zbl 1371.91053
Hemaspaandra, 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.91072
Hemaspaandra, Lane A.; Lavaee, Rahman; Menton, Curtis
6
2016
Manipulation complexity of same-system runoff elections. Zbl 1346.91071
Fitzsimmons, Zack; Hemaspaandra, Edith; Hemaspaandra, Lane A.
2
2016
Dogson’s rule and Yong’s rule. Zbl 1452.91124
Caragiannis, Ioannis; Hemaspaandra, Edith; Hemaspaandra, Lane A.
2
2016
Bypassing combinatorial protections: polynomial-time algorithms for single-peaked electorates. Zbl 1337.91039
Brandt, Felix; Brill, Markus; Hemaspaandra, Edith; Hemaspaandra, Lane A.
13
2015
Weighted electoral control. Zbl 1328.91068
Faliszewski, Piotr; Hemaspaandra, Edith; Hemaspaandra, Lane A.
9
2015
More natural models of electoral control by partition. Zbl 1405.91151
Erdélyi, Gábor; Hemaspaandra, Edith; Hemaspaandra, Lane A.
8
2015
The complexity of manipulative attacks in nearly single-peaked electorates. Zbl 1334.68098
Faliszewski, Piotr; Hemaspaandra, Edith; Hemaspaandra, Lane A.
16
2014
The complexity of online manipulation of sequential elections. Zbl 1285.68223
Hemaspaandra, Edith; Hemaspaandra, Lane A.; Rothe, Jörg
6
2014
Search versus decision for election manipulation problems. Zbl 1354.91054
Hemaspaandra, Edith; Hemaspaandra, Lane A.; Menton, Curtis
13
2013
Three hierarchies of simple games parameterized by “resource” parameters. Zbl 1282.91029
Gvozdeva, Tatiana; Hemaspaandra, Lane A.; Slinko, Arkadii
4
2013
Online voter control in sequential elections. Zbl 1327.68119
Hemaspaandra, Edith; Hemaspaandra, Lane A.; Rothe, Jörg
4
2012
Multimode control attacks on elections. Zbl 1242.91055
Faliszewski, 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.91042
Faliszewski, Piotr; Hemaspaandra, Edith; Hemaspaandra, Lane A.; Rothe, Jörg
22
2011
Computational aspects of approval voting. Zbl 1348.91101
Baumeister, 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.91091
Faliszewski, P.; Hemaspaandra, E.; Hemaspaandra, L. A.; Rothe, J.
62
2009
How hard is bribery in elections? Zbl 1180.91090
Faliszewski, P.; Hemaspaandra, E.; Hemaspaandra, L. A.
52
2009
A richer understanding of the complexity of election systems. Zbl 1167.91339
Faliszewski, Piotr; Hemaspaandra, Edith; Hemaspaandra, Lane A.; Rothe, Jörg
30
2009
Hybrid elections broaden complexity-theoretic resistance to control. Zbl 1177.91066
Hemaspaandra, Edith; Hemaspaandra, Lane A.; Rothe, Jörg
20
2009
Guarantees for the success frequency of an algorithm for finding Dodgson-election winners. Zbl 1188.91062
Homan, Christopher M.; Hemaspaandra, Lane A.
10
2009
The complexity of power-index comparison. Zbl 1155.91013
Faliszewski, Piotr; Hemaspaandra, Lane
6
2009
Generalized juntas and NP-hard sets. Zbl 1171.68012
Erdélyi, Gábor; Hemaspaandra, Lane A.; Rothe, Jörg; Spakowski, Holger
6
2009
Frequency of correctness versus average polynomial time. Zbl 1200.68124
Erdélyi, Gábor; Hemaspaandra, Lane A.; Rothe, Jörg; Spakowski, Holger
3
2009
Copeland voting fully resists constructive control. Zbl 1143.91320
Faliszewski, Piotr; Hemaspaandra, Edith; Hemaspaandra, Lane A.; Rothe, Jörg
9
2008
The complexity of power-index comparison. Zbl 1143.91321
Faliszewski, Piotr; Hemaspaandra, Lane A.
4
2008
Enforcing and defying associativity, commutativity, totality, and strong noninvertibility for worst-case one-way functions. Zbl 1146.68036
Hemaspaandra, Lane A.; Rothe, Jörg; Saxena, Amitabh
1
2008
The consequences of eliminating NP solutions. Zbl 1302.68124
Faliszewski, Piotr; Hemaspaandra, Lane A.
1
2008
Anyone but him: the complexity of precluding an alternative. Zbl 1168.91346
Hemaspaandra, Edith; Hemaspaandra, Lane A.; Rothe, Jörg
44
2007
Dichotomy for voting systems. Zbl 1154.91381
Hemaspaandra, Edith; Hemaspaandra, Lane A.
24
2007
On approximating optimal weighted lobbying, and frequency of correctness versus average-case polynomial time. Zbl 1135.91343
Erdélyi, Gábor; Hemaspaandra, Lane A.; Rothe, Jörg; Spakowski, Holger
4
2007
Complexity results in graph reconstruction. Zbl 1117.05078
Hemaspaandra, Edith; Hemaspaandra, Lane A.; Radziszowski, Stanisław P.; Tripathi, Rahul
3
2007
Cluster computing and the power of edge recognition. Zbl 1121.68099
Hemaspaandra, Lane A.; Homan, Christopher M.; Kosub, Sven
1
2007
On the complexity of kings. Zbl 1135.68517
Hemaspaandra, Edith; Hemaspaandra, Lane A.; Tantau, Till; Watanabe, Osamu
1
2007
The complexity of computing the size of an interval. Zbl 1123.68041
Hemaspaandra, 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.91399
Homan, Christopher M.; Hemaspaandra, Lane A.
4
2006
If P \(\neq\) NP then some strongly noninvertible functions are invertible. Zbl 1100.68038
Hemaspaandra, Lane A.; Pasanen, Kari; Rothe, Jörg
3
2006
The complexity of finding top-Toda-equivalence-class members. Zbl 1100.68033
Hemaspaandra, Lane A.; Ogihara, Mitsunori; Zaki, Mohammed J.; Zimand, Marius
2
2006
P-selectivity, immunity, and the power of one bit. Zbl 1175.03024
Hemaspaandra, Lane A.; Torenvliet, Leen
1
2006
Competing provers yield improved Karp-Lipton collapse results. Zbl 1066.68050
Cai, 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.68482
Hemaspaandra, 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.68035
Hemaspaandra, Edith; Hemaspaandra, Lane A.; Hempel, Harald
1
2005
All superlinear inverse schemes are coNP-hard. Zbl 1079.68041
Hemaspaandra, Edith; Hemaspaandra, Lane A.; Hempel, Harald
1
2005
Query-monotonic Turing reductions. Zbl 1123.68333
Hemaspaandra, Lane A.; Thakur, Mayur
1
2005
Context-free languages can be accepted with absolutely no space overhead. Zbl 1101.68655
Hemaspaandra, Lane A.; Mukherji, Proshanto; Tantau, Till
1
2005
Lower bounds and the hardness of counting properties. Zbl 1105.68048
Hemaspaandra, Lane A.; Thakur, Mayur
1
2004
Algebraic properties for selector functions. Zbl 1101.68596
Hemaspaandra, Lane A.; Hempel, Harald; Nickelsen, Arfst
1
2004
All superlinear inverse schemes are coNP-hard. Zbl 1096.68064
Hemaspaandra, Edith; Hemaspaandra, Lane A.; Hempel, Harald
1
2004
Theory of semi-feasible algorithms. Zbl 1021.68042
Hemaspaandra, Lane A.; Torenvliet, Leen
8
2003
Competing provers yield improved Karp-Lipton collapse results. Zbl 1035.68053
Cai, Jin-Yi; Chakaravarthy, Venkatesan T.; Hemaspaandra, Lane A.; Ogihara, Mitsunori
4
2003
P-immune sets with holes lack self-reducibility properties. Zbl 1044.68068
Hemaspaandra, Lane A.; Hempel, Harald
2
2003
Computation with absolutely no space overhead. Zbl 1037.68060
Hemaspaandra, Lane A.; Mukherji, Proshanto; Tantau, Till
2
2003
The complexity theory companion. Zbl 0993.68042
Hemaspaandra, Lane A.; Ogihara, Mitsunori
35
2002
On characterizing the existence of partial one-way permutations. Zbl 1013.68082
Rothe, Jörg; Hemaspaandra, Lane A.
3
2002
Almost-everywhere superiority for quantum polynomial time. Zbl 1012.68067
Hemaspaandra, Edith; Hemaspaandra, Lane A.; Zimand, Marius
3
2002
Reducing the number of solutions of NP functions. Zbl 1018.68032
Hemaspaandra, Lane A.; Ogihara, Mitsunori; Wechsung, Gerd
1
2002
The complexity of computing the size of an interval. Zbl 0986.68043
Hemaspaandra, Lane A.; Kosub, Sven; Wagner, Klaus W.
2
2001
If \(\text{P} \neq \text{NP}\) then some strongly noninvertible functions are invertible. Zbl 0999.68076
Hemaspaandra, Lane A.; Pasanen, Kari; Rothe, Jörg
1
2001
Computational politics: Electoral systems. Zbl 0996.68065
Hemaspaandra, Edith; Hemaspaandra, Lane A.
6
2000
Characterizing the existence of one-way permutations. Zbl 0945.68053
Hemaspaandra, L. A.; Rothe, J.
5
2000
A second step towards complexity-theoretic analogs of Rice’s Theorem. Zbl 0945.68103
Hemaspaandra, L. A.; Rothe, J.
2
2000
Restrictive acceptance suffices for equivalence problems. Zbl 0951.68041
Borchert, 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.68036
Hemaspaandra, Lane A.; Rothe, Jörg
11
1999
Robust reductions. Zbl 0946.68053
Cai, J.-Y.; Hemaspaandra, L. A.; Wechsung, G.
3
1999
Restrictive acceptance suffices for equivalence problems. Zbl 0948.68091
Borchert, 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.68048
Hemaspaandra, Edith; Hemaspaandra, Lane A.; Hempel, Harald
2
1999
Self-specifying machines. Zbl 1319.68083
Hemaspaandra, Lane A.; Hempel, Harald; Wechsung, Gerd
1
1999
A downward collapse within the polynomial hierarchy. Zbl 0915.68070
Hemaspaandra, Edith; Hemaspaandra, Lane A.; Hempel, Harald
8
1998
Query order. Zbl 0915.68071
Hemaspaandra, Lane A.; Hempel, Harald; Wechsung, Gerd
7
1998
Query order and the polynomial hierarchy. Zbl 0961.68052
Hemaspaandra, Edith; Hemaspaandra, Lane A.; Hempel, Harald
4
1998
Boolean operations, joins, and the extended low hierarchy. Zbl 0913.68077
Hemaspaandra, 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.68060
Hemaspaandra, 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.68082
Hemaspaandra, Lane A.; Nasipak, Christopher; Parkins, Keith
1
1998
Robust reductions. Zbl 0912.68051
Cai, 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.68111
Hemaspaandra, Edith; Hemaspaandra, Lane A.; Rothe, Jörg
43
1997
Threshold computation and cryptographic security. Zbl 0868.68056
Han, Yenjo; Hemaspaandra, Lane A.; Thierauf, Thomas
13
1997
Easy sets and hard certificate schemes. Zbl 0883.68072
Hemaspaandra, Lane A.; Rothe, Jörg; Wechsung, Gerd
11
1997
Unambiguous computation: Boolean hierarchies and sparse Turing-complete sets. Zbl 0870.68070
Hemaspaandra, Lane A.; Rothe, Jörg
5
1997
An introduction to query order. Zbl 0889.68061
Hemaspaandra, Edith; Hemaspaandra, Lane A.; Hempel, Harald
3
1997
Polynomial-time multi-selectivity. Zbl 0960.68078
Hemaspaandra, 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.68097
Hemaspaandra, Edith; Hemaspaandra, Lane A.; Rothe, Jörg
1
1997
Logspace reducibility: Models and equivalences. Zbl 0870.68087
Hemaspaandra, Lane A.; Jiang, Zhigen
1
1997
Witness-isomorphic reductions and local search. Zbl 0883.03023
Fischer, Sophie; Hemaspaandra, Lane; Torenvliet, Leen
1
1997
Universally serializable computation. Zbl 0901.68065
Hemaspaandra, Lane A.; Ogihara, Mitsunori
1
1997
Computing solutions uniquely collapses the polynomial hierarchy. Zbl 0857.68045
Hemaspaandra, Lane A.; Naik, Ashish V.; Ogihara, Mitsunori; Selman, Alan L.
18
1996
Strong self-reducibility precludes strong immunity. Zbl 0857.68046
Hemaspaandra, L. A.; Zimand, M.
5
1996
Optimal advice. Zbl 0872.68042
Hemaspaandra, Lane A.; Torenvliet, Leen
4
1996
Reducibility classes of P-selective sets. Zbl 0872.68043
Hemaspaandra, Lane A.; Hoene, Albrecht; Ogihara, Mitsunori
3
1996
Nondeterministically selective sets. Zbl 0843.68031
Hemaspaandra, 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.68046
Hemaspaandra, Lane A.; Jha, Sudhir K.
6
1995
P-selectivity: Intersections and indices. Zbl 0873.68065
Hemaspaandra, Lane A.; Jiang, Zhigen
5
1995
Easily checked generalized self-reducibility. Zbl 0830.68045
Hemaspaandra, Lane A.; Silvestri, Riccardo
3
1995
Pseudorandom generators and the frequency of simplicity. Zbl 1379.68186
Han, Yenjo; Hemaspaandra, Lane A.
1
1995
On the complexity of graph reconstruction. Zbl 0806.05051
Kratsch, Dieter; Hemaspaandra, Lane A.
6
1994
Space-efficient recognition of sparse self-reducible languages. Zbl 0812.68073
Hemaspaandra, Lane A.; Ogihara, Mitsunori; Toda, Seinosuke
3
1994
Computing solutions uniquely collapses the polynomial hierarchy. Zbl 0953.68541
Hemaspaandra, Lane A.; Naik, Ashish V.; Ogihara, Mitsunori; Selman, Alan L.
2
1994
Quasi-injective reductions. Zbl 0811.68079
Hemaspaandra, Edith; Hemaspaandra, Lane A.
1
1994
A complexity theory for feasible closure properties. Zbl 0798.68060
Ogiwara, Mitsunori; Hemachandra, Lane A.
31
1993
...and 40 more Documents
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

Citations by Year