×

zbMATH — the first resource for mathematics

Hemaspaandra, Lane A.

Compute Distance To:
Author ID: hemaspaandra.lane-a Recent zbMATH articles by "Hemaspaandra, Lane A."
Published as: Hemachandra, L.; Hemachandra, L. A.; Hemachandra, Lane; Hemachandra, Lane A.; Hemaspaandra, L. A.; Hemaspaandra, Lane; Hemaspaandra, Lane A.
Documents Indexed: 165 Publications since 1986, including 3 Books
all top 5

Co-Authors

5 single-authored
38 Hemaspaandra, Edith
30 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
6 Han, Yenjo
6 Watanabe, Osamu
5 Erdélyi, Gábor
5 Homan, Christopher M.
5 Ogiwara, Mitsunori
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 Spakowski, Holger
4 Tantau, Till
4 Wagner, Klaus W.
4 Zimand, Marius
3 Allender, Eric W.
3 Goldsmith, Judy
3 Naik, Ashish V.
3 Thakur, Mayur
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 Menton, Curtis
2 Mukherji, Proshanto
2 Mundhenk, Martin
2 Nickelsen, Arfst
2 Pasanen, Kari
2 Radziszowski, Stanisław P.
2 Rubery, Daniel
2 Saxena, Amitabh
2 Schöning, Uwe
2 Sewelson, Vivian
2 Tripathi, Rahul
2 Vereshchagin, Nikolai K.
2 Young, Paul Thomas
2 Zaki, Mohammed Javeed
1 Abadi, Martín
1 Abascal, Jackson
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 Maimon, Shir
1 Narváez, David E.
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 Wang, Jie
1 Yener, Bülent

Publications by Year

Citations contained in zbMATH Open

139 Publications have been cited 1,130 times in 447 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.
57
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
53
1988
How hard is bribery in elections? Zbl 1180.91090
Faliszewski, P.; Hemaspaandra, E.; Hemaspaandra, L. A.
44
2009
Anyone but him: the complexity of precluding an alternative. Zbl 1168.91346
Hemaspaandra, Edith; Hemaspaandra, Lane A.; Rothe, Jörg
42
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
40
1997
The complexity theory companion. Zbl 0993.68042
Hemaspaandra, Lane A.; Ogihara, Mitsunori
35
2002
On the power of parity polynomial time. Zbl 0718.68038
Cai, Jin-yi; Hemachandra, Lane A.
34
1990
The strong exponential hierarchy collapses. Zbl 0693.03022
Hemachandra, Lane A.
34
1989
Complexity classes without machines: on complete languages for UP. Zbl 0655.68044
Hartmanis, Juris; Hemachandra, Lane A.
34
1988
A complexity theory for feasible closure properties. Zbl 0798.68060
Ogiwara, Mitsunori; Hemachandra, Lane A.
32
1993
A richer understanding of the complexity of election systems. Zbl 1167.91339
Faliszewski, Piotr; Hemaspaandra, Edith; Hemaspaandra, Lane A.; Rothe, Jörg
29
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
26
1989
Multimode control attacks on elections. Zbl 1242.91055
Faliszewski, Piotr; Hemaspaandra, Edith; Hemaspaandra, Lane A.
25
2011
Dichotomy for voting systems. Zbl 1154.91381
Hemaspaandra, Edith; Hemaspaandra, Lane A.
21
2007
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
20
2011
Enumerative counting is hard. Zbl 0679.68072
Cai, Jin-Yi; Hemachandra, Lane A.
19
1989
Computational aspects of approval voting. Zbl 1348.91101
Baumeister, Dorothea; Erdélyi, Gábor; Hemaspaandra, Edith; Hemaspaandra, Lane A.; Rothe, Jörg
18
2010
Hybrid elections broaden complexity-theoretic resistance to control. Zbl 1177.91066
Hemaspaandra, Edith; Hemaspaandra, Lane A.; Rothe, Jörg
18
2009
Computing solutions uniquely collapses the polynomial hierarchy. Zbl 0857.68045
Hemaspaandra, Lane A.; Naik, Ashish V.; Ogihara, Mitsunori; Selman, Alan L.
18
1996
One-way functions and the nonisomorphism of NP-complete sets. Zbl 0718.03031
Hartmanis, Juris; Hemachandra, Lane A.
18
1991
Bypassing combinatorial protections: polynomial-time algorithms for single-peaked electorates. Zbl 1337.91039
Brandt, Felix; Brill, Markus; Hemaspaandra, Edith; Hemaspaandra, Lane A.
17
2015
The complexity of manipulative attacks in nearly single-peaked electorates. Zbl 1334.68098
Faliszewski, Piotr; Hemaspaandra, Edith; Hemaspaandra, Lane A.
17
2014
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
Search versus decision for election manipulation problems. Zbl 1354.91054
Hemaspaandra, Edith; Hemaspaandra, Lane A.; Menton, Curtis
13
2013
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
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
Lower bounds for the low hierarchy. Zbl 0799.68081
Allender, Eric; Hemachandra, Lane A.
11
1992
Probabilistic polynomial time is closed under parity reductions. Zbl 0714.68031
Beigel, Richard; Hemachandra, Lane A.; Wechsung, Gerd
11
1991
On the complexity of ranking. Zbl 0708.68020
Hemachandra, Lane A.; Rudich, Steven
11
1990
Guarantees for the success frequency of an algorithm for finding Dodgson-election winners. Zbl 1188.91062
Homan, Christopher M.; Hemaspaandra, Lane A.
10
2009
Theory of semi-feasible algorithms. Zbl 1021.68042
Hemaspaandra, Lane A.; Torenvliet, Leen
10
2003
A downward collapse within the polynomial hierarchy. Zbl 0915.68070
Hemaspaandra, Edith; Hemaspaandra, Lane A.; Hempel, Harald
10
1998
Easy sets and hard certificate schemes. Zbl 0883.68072
Hemaspaandra, Lane A.; Rothe, Jörg; Wechsung, Gerd
10
1997
A note on enumerative counting. Zbl 0733.68030
Cai, Jinyi; Hemachandra, Lane A.
10
1991
Relating equivalence and reducibility to sparse sets. Zbl 0761.68039
Allender, Eric; Hemachandra, Lane A.; Ogiwara, Mitsunori; Watanabe, Osamu
8
1992
The Boolean hierarchy: Hardware over NP. Zbl 0611.68018
Chai, Jinyi; Hemachandra, Lane
8
1986
Schulze and ranked-pairs voting are fixed-parameter tractable to bribe, manipulate, and control. Zbl 1346.91072
Hemaspaandra, Lane A.; Lavaee, Rahman; Menton, Curtis
7
2016
More natural models of electoral control by partition. Zbl 1405.91151
Erdélyi, Gábor; Hemaspaandra, Edith; Hemaspaandra, Lane A.
7
2015
Copeland voting fully resists constructive control. Zbl 1143.91320
Faliszewski, Piotr; Hemaspaandra, Edith; Hemaspaandra, Lane A.; Rothe, Jörg
7
2008
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
Query order. Zbl 0915.68071
Hemaspaandra, Lane A.; Hempel, Harald; Wechsung, Gerd
7
1998
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
Banishing robust Turing completeness. Zbl 0802.68049
Hemaspaandra, Lane A.; Jain, Sanjay; Vereshchagin, Nikolaj K.
7
1993
Robust machines accept easy sets. Zbl 0701.68028
Hartmanis, Juris; Hemachandra, Lane A.
7
1990
Weighted electoral control. Zbl 1328.91068
Faliszewski, Piotr; Hemaspaandra, Edith; Hemaspaandra, Lane A.
6
2015
Computational politics: Electoral systems. Zbl 0996.68065
Hemaspaandra, Edith; Hemaspaandra, Lane A.
6
2000
Defying upward and downward separation. Zbl 0832.68046
Hemaspaandra, Lane A.; Jha, Sudhir K.
6
1995
Using inductive counting to simulate nondeterministic computation. Zbl 0769.68028
Buntrock, Gerhard; Hemachandra, Lane A.; Siefkes, Dirk
6
1993
On sets with efficient implicit membership tests. Zbl 0738.68032
Hemachandra, Lane A.; Hoene, Albrecht
6
1991
Near-testable sets. Zbl 0738.68031
Goldsmith, Judy; Hemachandra, Lane A.; Joseph, Deborah; Young, Paul
6
1991
On sparse oracles separating feasible complexity classes. Zbl 0658.68055
Hartmanis, Juris; Hemachandra, Lane
6
1988
The complexity of controlling candidate-sequential elections. Zbl 1371.91053
Hemaspaandra, Edith; Hemaspaandra, Lane A.; Rothe, Jörg
5
2017
Frequency of correctness versus average polynomial time. Zbl 1200.68124
Erdélyi, Gábor; Hemaspaandra, Lane A.; Rothe, Jörg; Spakowski, Holger
5
2009
Generalized juntas and NP-hard sets. Zbl 1171.68012
Erdélyi, Gábor; Hemaspaandra, Lane A.; Rothe, Jörg; Spakowski, Holger
5
2009
Characterizing the existence of one-way permutations. Zbl 0945.68053
Hemaspaandra, L. A.; Rothe, J.
5
2000
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
P-selectivity: Intersections and indices. Zbl 0873.68065
Hemaspaandra, Lane A.; Jiang, Zhigen
5
1995
On the complexity of graph reconstruction. Zbl 0806.05051
Kratsch, Dieter; Hemaspaandra, Lane A.
5
1994
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
On generating solved instances of computational problems. Zbl 0792.68045
Abadi, Martín; Allender, Eric; Broder, Andrei; Feigenbaum, Joan; Hemachandra, Lane A.
5
1990
Complexity classes without machines: on complete languages for UP. Zbl 0655.68043
Hartmanis, Juris; Hemachandra, Lane
5
1986
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 1155.91013
Faliszewski, Piotr; Hemaspaandra, Lane
4
2009
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
Guarantees for the success frequency of an algorithm for finding Dodgson-election winners. Zbl 1132.91399
Homan, Christopher M.; Hemaspaandra, Lane A.
4
2006
Competing provers yield improved Karp-Lipton collapse results. Zbl 1035.68053
Cai, Jin-Yi; Chakaravarthy, Venkatesan T.; Hemaspaandra, Lane A.; Ogihara, Mitsunori
4
2003
Query order and the polynomial hierarchy. Zbl 0961.68052
Hemaspaandra, Edith; Hemaspaandra, Lane A.; Hempel, Harald
4
1998
An introduction to query order. Zbl 0889.68061
Hemaspaandra, Edith; Hemaspaandra, Lane A.; Hempel, Harald
4
1997
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
4
1996
Computing solutions uniquely collapses the polynomial hierarchy. Zbl 0953.68541
Hemaspaandra, Lane A.; Naik, Ashish V.; Ogihara, Mitsunori; Selman, Alan L.
4
1994
Promises and fault-tolerant database access. Zbl 0794.68059
Cai, Jin-yi; Hemachandra, Lane A.; Vyskoč, Jozef
4
1993
Polynomial-time compression. Zbl 0752.68039
Goldsmith, Judy; Hemachandra, Lane A.; Kunen, Kenneth
4
1992
Algorithms from complexity theory: Polynomial-time operations for complex sets. Zbl 0819.68063
Hemachandra, Lane A.
4
1990
The complexity of online manipulation of sequential elections. Zbl 1285.68223
Hemaspaandra, Edith; Hemaspaandra, Lane A.; Rothe, Jörg
3
2014
Online voter control in sequential elections. Zbl 1327.68119
Hemaspaandra, Edith; Hemaspaandra, Lane A.; Rothe, Jörg
3
2012
If P \(\neq\) NP then some strongly noninvertible functions are invertible. Zbl 1100.68038
Hemaspaandra, Lane A.; Pasanen, Kari; Rothe, Jörg
3
2006
Almost-everywhere superiority for quantum polynomial time. Zbl 1012.68067
Hemaspaandra, Edith; Hemaspaandra, Lane A.; Zimand, Marius
3
2002
On characterizing the existence of partial one-way permutations. Zbl 1013.68082
Rothe, Jörg; Hemaspaandra, Lane A.
3
2002
Robust reductions. Zbl 0946.68053
Cai, J.-Y.; Hemaspaandra, L. A.; Wechsung, G.
3
1999
Boolean operations, joins, and the extended low hierarchy. Zbl 0913.68077
Hemaspaandra, Lane A.; Jiang, Zhigen; Rothe, Jörg; Watanabe, Osamu
3
1998
Easily checked generalized self-reducibility. Zbl 0830.68045
Hemaspaandra, Lane A.; Silvestri, Riccardo
3
1995
Space-efficient recognition of sparse self-reducible languages. Zbl 0812.68073
Hemaspaandra, Lane A.; Ogihara, Mitsunori; Toda, Seinosuke
3
1994
On the complexity of graph reconstruction. Zbl 0925.05059
Kratsch, Dieter; Hemachandra, Lane A.
3
1991
On sets polynomially enumerable by iteration. Zbl 0745.68047
Hemachandra, Lane A.; Hoene, Albrecht; Siefkes, Dirk; Young, Paul
3
1991
On sparse oracles separating feasible complexity classes. Zbl 0605.68034
Hartmanis, Juris; Hemachandra, Lane
3
1986
Complexity results in graph reconstruction. Zbl 1117.05078
Hemaspaandra, Edith; Hemaspaandra, Lane A.; Radziszowski, Stanisław P.; Tripathi, Rahul
2
2007
The complexity of finding top-Toda-equivalence-class members. Zbl 1100.68033
Hemaspaandra, Lane A.; Ogihara, Mitsunori; Zaki, Mohammed J.; Zimand, Marius
2
2006
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
Computation with absolutely no space overhead. Zbl 1037.68060
Hemaspaandra, Lane A.; Mukherji, Proshanto; Tantau, Till
2
2003
P-immune sets with holes lack self-reducibility properties. Zbl 1044.68068
Hemaspaandra, Lane A.; Hempel, Harald
2
2003
If \(\text{P} \neq \text{NP}\) then some strongly noninvertible functions are invertible. Zbl 0999.68076
Hemaspaandra, Lane A.; Pasanen, Kari; Rothe, Jörg
2
2001
The complexity of computing the size of an interval. Zbl 0986.68043
Hemaspaandra, Lane A.; Kosub, Sven; Wagner, Klaus W.
2
2001
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 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
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
7
2016
Dogson’s rule and Yong’s rule. Zbl 1452.91124
Caragiannis, Ioannis; Hemaspaandra, Edith; Hemaspaandra, Lane A.
1
2016
Manipulation complexity of same-system runoff elections. Zbl 1346.91071
Fitzsimmons, Zack; Hemaspaandra, Edith; Hemaspaandra, Lane A.
1
2016
Bypassing combinatorial protections: polynomial-time algorithms for single-peaked electorates. Zbl 1337.91039
Brandt, Felix; Brill, Markus; Hemaspaandra, Edith; Hemaspaandra, Lane A.
17
2015
More natural models of electoral control by partition. Zbl 1405.91151
Erdélyi, Gábor; Hemaspaandra, Edith; Hemaspaandra, Lane A.
7
2015
Weighted electoral control. Zbl 1328.91068
Faliszewski, Piotr; Hemaspaandra, Edith; Hemaspaandra, Lane A.
6
2015
The complexity of manipulative attacks in nearly single-peaked electorates. Zbl 1334.68098
Faliszewski, Piotr; Hemaspaandra, Edith; Hemaspaandra, Lane A.
17
2014
The complexity of online manipulation of sequential elections. Zbl 1285.68223
Hemaspaandra, Edith; Hemaspaandra, Lane A.; Rothe, Jörg
3
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
3
2012
Multimode control attacks on elections. Zbl 1242.91055
Faliszewski, Piotr; Hemaspaandra, Edith; Hemaspaandra, Lane A.
25
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
20
2011
Computational aspects of approval voting. Zbl 1348.91101
Baumeister, Dorothea; Erdélyi, Gábor; Hemaspaandra, Edith; Hemaspaandra, Lane A.; Rothe, Jörg
18
2010
Llull and Copeland voting computationally resist bribery and constructive control. Zbl 1180.91091
Faliszewski, P.; Hemaspaandra, E.; Hemaspaandra, L. A.; Rothe, J.
57
2009
How hard is bribery in elections? Zbl 1180.91090
Faliszewski, P.; Hemaspaandra, E.; Hemaspaandra, L. A.
44
2009
A richer understanding of the complexity of election systems. Zbl 1167.91339
Faliszewski, Piotr; Hemaspaandra, Edith; Hemaspaandra, Lane A.; Rothe, Jörg
29
2009
Hybrid elections broaden complexity-theoretic resistance to control. Zbl 1177.91066
Hemaspaandra, Edith; Hemaspaandra, Lane A.; Rothe, Jörg
18
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
Frequency of correctness versus average polynomial time. Zbl 1200.68124
Erdélyi, Gábor; Hemaspaandra, Lane A.; Rothe, Jörg; Spakowski, Holger
5
2009
Generalized juntas and NP-hard sets. Zbl 1171.68012
Erdélyi, Gábor; Hemaspaandra, Lane A.; Rothe, Jörg; Spakowski, Holger
5
2009
The complexity of power-index comparison. Zbl 1155.91013
Faliszewski, Piotr; Hemaspaandra, Lane
4
2009
Copeland voting fully resists constructive control. Zbl 1143.91320
Faliszewski, Piotr; Hemaspaandra, Edith; Hemaspaandra, Lane A.; Rothe, Jörg
7
2008
The complexity of power-index comparison. Zbl 1143.91321
Faliszewski, Piotr; Hemaspaandra, Lane A.
4
2008
The consequences of eliminating NP solutions. Zbl 1302.68124
Faliszewski, Piotr; Hemaspaandra, Lane A.
1
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
Anyone but him: the complexity of precluding an alternative. Zbl 1168.91346
Hemaspaandra, Edith; Hemaspaandra, Lane A.; Rothe, Jörg
42
2007
Dichotomy for voting systems. Zbl 1154.91381
Hemaspaandra, Edith; Hemaspaandra, Lane A.
21
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
2
2007
On the complexity of kings. Zbl 1135.68517
Hemaspaandra, Edith; Hemaspaandra, Lane A.; Tantau, Till; Watanabe, Osamu
1
2007
Cluster computing and the power of edge recognition. Zbl 1121.68099
Hemaspaandra, Lane A.; Homan, Christopher M.; Kosub, Sven
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
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
All superlinear inverse schemes are coNP-hard. Zbl 1079.68041
Hemaspaandra, Edith; Hemaspaandra, Lane A.; Hempel, Harald
1
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 1096.68064
Hemaspaandra, Edith; Hemaspaandra, Lane A.; Hempel, Harald
1
2004
Algebraic properties for selector functions. Zbl 1101.68596
Hemaspaandra, Lane A.; Hempel, Harald; Nickelsen, Arfst
1
2004
Lower bounds and the hardness of counting properties. Zbl 1105.68048
Hemaspaandra, Lane A.; Thakur, Mayur
1
2004
Theory of semi-feasible algorithms. Zbl 1021.68042
Hemaspaandra, Lane A.; Torenvliet, Leen
10
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
Computation with absolutely no space overhead. Zbl 1037.68060
Hemaspaandra, Lane A.; Mukherji, Proshanto; Tantau, Till
2
2003
P-immune sets with holes lack self-reducibility properties. Zbl 1044.68068
Hemaspaandra, Lane A.; Hempel, Harald
2
2003
The complexity theory companion. Zbl 0993.68042
Hemaspaandra, Lane A.; Ogihara, Mitsunori
35
2002
Almost-everywhere superiority for quantum polynomial time. Zbl 1012.68067
Hemaspaandra, Edith; Hemaspaandra, Lane A.; Zimand, Marius
3
2002
On characterizing the existence of partial one-way permutations. Zbl 1013.68082
Rothe, Jörg; Hemaspaandra, Lane A.
3
2002
Reducing the number of solutions of NP functions. Zbl 1018.68032
Hemaspaandra, Lane A.; Ogihara, Mitsunori; Wechsung, Gerd
1
2002
If \(\text{P} \neq \text{NP}\) then some strongly noninvertible functions are invertible. Zbl 0999.68076
Hemaspaandra, Lane A.; Pasanen, Kari; Rothe, Jörg
2
2001
The complexity of computing the size of an interval. Zbl 0986.68043
Hemaspaandra, Lane A.; Kosub, Sven; Wagner, Klaus W.
2
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
10
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
3
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
\(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
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
40
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
10
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
4
1997
Polynomial-time multi-selectivity. Zbl 0960.68078
Hemaspaandra, Lane A.; Jiang, Zhigen; Rothe, Joerg; Watanabe, Osamu
2
1997
Universally serializable computation. Zbl 0901.68065
Hemaspaandra, Lane A.; Ogihara, Mitsunori
1
1997
Witness-isomorphic reductions and local search. Zbl 0883.03023
Fischer, Sophie; Hemaspaandra, Lane; Torenvliet, Leen
1
1997
Logspace reducibility: Models and equivalences. Zbl 0870.68087
Hemaspaandra, Lane A.; Jiang, Zhigen
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
4
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.
5
1994
Computing solutions uniquely collapses the polynomial hierarchy. Zbl 0953.68541
Hemaspaandra, Lane A.; Naik, Ashish V.; Ogihara, Mitsunori; Selman, Alan L.
4
1994
Space-efficient recognition of sparse self-reducible languages. Zbl 0812.68073
Hemaspaandra, Lane A.; Ogihara, Mitsunori; Toda, Seinosuke
3
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.
32
1993
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
Banishing robust Turing completeness. Zbl 0802.68049
Hemaspaandra, Lane A.; Jain, Sanjay; Vereshchagin, Nikolaj K.
7
1993
Using inductive counting to simulate nondeterministic computation. Zbl 0769.68028
Buntrock, Gerhard; Hemachandra, Lane A.; Siefkes, Dirk
6
1993
Promises and fault-tolerant database access. Zbl 0794.68059
Cai, Jin-yi; Hemachandra, Lane A.; Vyskoč, Jozef
4
1993
...and 39 more Documents
all top 5

Cited by 567 Authors

64 Hemaspaandra, Lane A.
36 Rothe, Jörg-Matthias
19 Hemaspaandra, Edith
16 Beigel, Richard
15 Faliszewski, Piotr
13 Ogihara, Mitsunori
12 Köbler, Johannes
10 Allender, Eric W.
10 Cai, Jin-Yi
9 Erdélyi, Gábor
9 Niedermeier, Rolf
9 Wagner, Klaus W.
8 Betzler, Nadja
8 Bredereck, Robert
8 Fortnow, Lance J.
8 Guo, Jiong
8 Spakowski, Holger
8 Watanabe, Osamu
7 Baumeister, Dorothea
7 Elkind, Edith
7 Glaßer, Christian
7 Slinko, Arkadii M.
6 Birget, Jean-Camille
6 Brandt, Felix
6 Chen, Jiehua
6 Dorn, Britta
6 Gasarch, William Ian
6 Goldsmith, Judy
6 Hartmanis, Juris
6 Hempel, Harald
6 Homan, Christopher M.
6 Selman, Alan L.
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 Kosub, Sven
5 Ogiwara, Mitsunori
5 Procaccia, Ariel D.
5 Rosenschein, Jeffrey S.
5 Schlotter, Ildikó
5 Tantau, Till
5 Toda, Seinosuke
5 Yamakami, Tomoyuki
4 Bachrach, Yoram
4 Borchert, Bernd
4 Cygan, Marek
4 Dey, Palash
4 Fellows, Michael Ralph
4 Fu, Bin
4 Homer, Steven
4 Misra, Neeldhara
4 Mundhenk, Martin
4 Pavan, Aduri
4 Pilipczuk, Marcin
4 Pilipczuk, Michał
4 Schend, Lena
4 Selivanov, Viktor L’vovich
4 Skowron, Piotr
4 Thakur, Mayur
4 Torán, Jacobo
4 Tripathi, Rahul
4 Vinodchandran, N. Variyam
4 Yang, Yongjie
3 Agrawal, Manindra
3 Caragiannis, Ioannis
3 Dell, Holger
3 Fenner, Stephen A.
3 Fischer, Felix
3 Harrenstein, Paul
3 Hoene, Albrecht
3 Impagliazzo, Russell
3 Jenner, Birgit
3 Kułakowski, Konrad
3 Kurz, Sascha
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 Talmon, Nimrod
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
2 Bakali, Eleni
...and 467 more Authors
all top 5

Cited in 64 Serials

89 Theoretical Computer Science
51 Journal of Computer and System Sciences
37 Information Processing Letters
35 Information and Computation
19 Mathematical Systems Theory
19 Computational Complexity
17 Artificial Intelligence
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 International Journal of Foundations of Computer Science
5 Mathematical Social Sciences
5 Algorithmica
4 The Journal of Symbolic Logic
4 Annals of Pure and Applied Logic
4 International Journal of Algebra and Computation
4 RAIRO. Theoretical Informatics and Applications
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 SIAM Journal on Discrete Mathematics
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 The Journal of Artificial Intelligence Research (JAIR)
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 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