Lane A. Hemaspaandra

Lane A. Hemachandra

List of publications from the DBLP Bibliography Server - FAQ

Coauthor Index - Ask others: ACM DL/Guide - CiteSeer - CSB - Google - MSN - Yahoo

2009

222 EE Piotr Faliszewski, Lane A. Hemaspaandra: The complexity of power-index comparison. Theor. Comput. Sci. 410(1): 101-107 (2009)

2008

221 EE Piotr Faliszewski, Edith Hemaspaandra, Lane A. Hemaspaandra, Jörg Rothe: Copeland Voting Fully Resists Constructive Control. AAIM 2008: 165-176

220 EE Piotr Faliszewski, Lane A. Hemaspaandra: The Complexity of Power-Index Comparison. AAIM 2008: 177-187

219 EE Piotr Faliszewski, Lane A. Hemaspaandra: The Complexity of Power-Index Comparison CoRR abs/0801.4585: (2008)

218 EE Gábor Erdélyi, Lane A. Hemaspaandra, Jörg Rothe, Holger Spakowski: Frequency of Correctness versus Average-Case Polynomial Time and Generalized Juntas CoRR abs/0806.2555: (2008)

217 EE Piotr Faliszewski, Edith Hemaspaandra, Lane A. Hemaspaandra, Jörg Rothe: Llull and Copeland Voting Computationally Resist Bribery and Control CoRR abs/0809.4484: (2008)

216 EE Piotr Faliszewski, Lane A. Hemaspaandra: The consequences of eliminating NP solutions. Computer Science Review 2(1): 40-54 (2008)

215 EE Lane A. Hemaspaandra: SIGACT news complexity theory column 59: introduction. SIGACT News 39(2): 50 (2008)

214 EE Lane A. Hemaspaandra, Jörg Rothe, Amitabh Saxena: Enforcing and defying associativity, commutativity, totality, and strong noninvertibility for worst-case one-way functions. Theor. Comput. Sci. 401(1-3): 27-35 (2008)

2007

213 Piotr Faliszewski, Edith Hemaspaandra, Lane A. Hemaspaandra, Jörg Rothe: Llull and Copeland Voting Broadly Resist Bribery and Control. AAAI 2007: 724-730

212 EE Gábor Erdélyi, Lane A. Hemaspaandra, Jörg Rothe, Holger Spakowski: On Approximating Optimal Weighted Lobbying, and Frequency of Correctness Versus Average-Case Polynomial Time. FCT 2007: 300-311

211 EE Edith Hemaspaandra, Lane A. Hemaspaandra, Till Tantau, Osamu Watanabe: On the Complexity of Kings. FCT 2007: 328-340

210 EE Edith Hemaspaandra, Lane A. Hemaspaandra, Jörg Rothe: Hybrid Elections Broaden Complexity-Theoretic Resistance to Control. IJCAI 2007: 1308-1314

209 EE Edith Hemaspaandra, Lane A. Hemaspaandra, Jörg Rothe: Anyone but him: The complexity of precluding an alternative. Artif. Intell. 171(5-6): 255-285 (2007)

208 EE Piotr Faliszewski, Edith Hemaspaandra, Lane A. Hemaspaandra, Jörg Rothe: Copeland Voting Fully Resists Constructive Control CoRR abs/0711.4759: (2007)

207 EE Gábor Erdélyi, Lane A. Hemaspaandra, Jörg Rothe, Holger Spakowski: On Approximating Optimal Weighted Lobbying, and Frequency of Correctness versus Average-Case Polynomial Time CoRR abs/cs/0703097: (2007)

206 EE Edith Hemaspaandra, Lane A. Hemaspaandra, Stanislaw P. Radziszowski, Rahul Tripathi: Complexity results in graph reconstruction. Discrete Applied Mathematics 155(2): 103-118 (2007)

205 EE Lane A. Hemaspaandra, Christopher M. Homan, Sven Kosub: Cluster computing and the power of edge recognition. Inf. Comput. 205(8): 1274-1293 (2007)

204 EE Edith Hemaspaandra, Lane A. Hemaspaandra: Dichotomy for voting systems. J. Comput. Syst. Sci. 73(1): 73-83 (2007)

203 EE Lane A. Hemaspaandra, Christopher M. Homan, Sven Kosub, Klaus W. Wagner: The Complexity of Computing the Size of an Interval. SIAM J. Comput. 36(5): 1264-1300 (2007)

202 EE Lane A. Hemaspaandra: Introduction. SIGACT News 38(3): 34-38 (2007)

201 EE Lane A. Hemaspaandra: Introduction. SIGACT News 38(4): 39-40 (2007)

200 EE Lane A. Hemaspaandra, Mayur Thakur: Query-monotonic Turing reductions. Theor. Comput. Sci. 383(2-3): 153-186 (2007)

2006

199 Piotr Faliszewski, Edith Hemaspaandra, Lane A. Hemaspaandra: The Complexity of Bribery in Elections. AAAI 2006

198 EE Christopher M. Homan, Lane A. Hemaspaandra: Guarantees for the Success Frequency of an Algorithm for Finding Dodgson-Election Winners. MFCS 2006: 528-539

197 EE Lane A. Hemaspaandra, Leen Torenvliet: P-Selectivity, Immunity, and the Power of One Bit. SOFSEM 2006: 323-331

196 EE Lane A. Hemaspaandra, Christopher M. Homan, Sven Kosub: Cluster Computing and the Power of Edge Recognition. TAMC 2006: 283-294

195 EE Lane A. Hemaspaandra, Mayur Thakur: Query-Monotonic Turing Reductions CoRR abs/cs/0602001: (2006)

194 EE Piotr Faliszewski, Lane A. Hemaspaandra: The Consequences of Eliminating NP Solutions CoRR abs/cs/0606009: (2006)

193 EE Edith Hemaspaandra, Lane A. Hemaspaandra, Jörg Rothe: Hybrid Elections Broaden Complexity-Theoretic Resistance to Control CoRR abs/cs/0608057: (2006)

192 EE Piotr Faliszewski, Edith Hemaspaandra, Lane A. Hemaspaandra: How Hard Is Bribery in Elections? CoRR abs/cs/0608081: (2006)

191 EE Piotr Faliszewski, Edith Hemaspaandra, Lane A. Hemaspaandra, Jörg Rothe: A Richer Understanding of the Complexity of Election Systems CoRR abs/cs/0609112: (2006)

190 EE Piotr Faliszewski, Lane A. Hemaspaandra: Open questions in the theory of semifeasible computation. SIGACT News 37(1): 47-65 (2006)

189 EE Lane A. Hemaspaandra: SIGACT news complexity theory column 51. SIGACT News 37(2): 31-46 (2006)

188 EE Lane A. Hemaspaandra: SIGACT news complexity theory column 52. SIGACT News 37(3): 36-54 (2006)

187 EE Lane A. Hemaspaandra: SIGACT news complexity theory column 53. SIGACT News 37(4): 47-55 (2006)

186 EE Lane A. Hemaspaandra, Kari Pasanen, Jörg Rothe: If P neq NP then some strongly noninvertible functions are invertible. Theor. Comput. Sci. 362(1-3): 54-62 (2006)

185 EE Lane A. Hemaspaandra, Mitsunori Ogihara, Mohammed J. Zaki, Marius Zimand: The Complexity of Finding Top-Toda-Equivalence-Class Members. Theory Comput. Syst. 39(5): 669-684 (2006)

2005

184 Edith Hemaspaandra, Lane A. Hemaspaandra, Jörg Rothe: Anyone but Him: The Complexity of Precluding an Alternative. AAAI 2005: 95-101

183 EE Lane A. Hemaspaandra, Mayur Thakur: Query-Monotonic Turing Reductions. COCOON 2005: 895-904

182 EE Lane A. Hemaspaandra, Jörg Rothe, Amitabh Saxena: Enforcing and Defying Associativity, Commutativity, Totality, and Strong Noninvertibility for One-Way Functions in Complexity Theory. ICTCS 2005: 265-279

181 EE Lane A. Hemaspaandra, Harald Hempel, Arfst Nickelsen: Algebraic Properties for Selector Functions CoRR abs/cs/0501022: (2005)

180 EE Lane A. Hemaspaandra, Christopher M. Homan, Sven Kosub, Klaus W. Wagner: The Complexity of Computing the Size of an Interval CoRR abs/cs/0502058: (2005)

179 EE Lane A. Hemaspaandra, Jörg Rothe, Amitabh Saxena: Enforcing and Defying Associativity, Commutativity, Totality, and Strong Noninvertibility for One-Way Functions in Complexity Theory CoRR abs/cs/0503049: (2005)

178 EE Edith Hemaspaandra, Lane A. Hemaspaandra: Dichotomy for Voting Systems CoRR abs/cs/0504075: (2005)

177 EE Lane A. Hemaspaandra, Leen Torenvliet: P-Selectivity, Immunity, and the Power of One Bit CoRR abs/cs/0504096: (2005)

176 EE Edith Hemaspaandra, Lane A. Hemaspaandra, Osamu Watanabe: The Complexity of Kings CoRR abs/cs/0506055: (2005)

175 EE Piotr Faliszewski, Lane A. Hemaspaandra: Open Questions in the Theory of Semifeasible Computation CoRR abs/cs/0506082: (2005)

174 EE Edith Hemaspaandra, Lane A. Hemaspaandra, Jörg Rothe: Anyone but Him: The Complexity of Precluding an Alternative CoRR abs/cs/0507027: (2005)

173 EE Lane A. Hemaspaandra, Christopher M. Homan, Sven Kosub: Cluster Computing and the Power of Edge Recognition CoRR abs/cs/0509060: (2005)

172 EE Christopher M. Homan, Lane A. Hemaspaandra: Guarantees for the Success Frequency of an Algorithm for Finding Dodgson-Election Winners CoRR abs/cs/0509061: (2005)

171 EE Jin-yi Cai, Venkatesan T. Chakaravarthy, Lane A. Hemaspaandra, Mitsunori Ogihara: Competing provers yield improved Karp-Lipton collapse results. Inf. Comput. 198(1): 1-23 (2005)

170 EE Lane A. Hemaspaandra, Proshanto Mukherji, Till Tantau: Context-free languages can be accepted with absolutely no space overhead. Inf. Comput. 203(2): 163-180 (2005)

169 EE Piotr Faliszewski, Lane A. Hemaspaandra: Advice for semifeasible sets and the complexity-theoretic cost(lessness) of algebraic properties. Int. J. Found. Comput. Sci. 16(5): 913-928 (2005)

168 EE Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel: Extending Downward Collapse from 1-versus-2 Queries to m-versus-m + 1 Queries. SIAM J. Comput. 34(6): 1352-1369 (2005)

167 EE Lane A. Hemaspaandra: SIGACT news complexity theory column 48. SIGACT News 36(3): 24-38 (2005)

166 EE Lane A. Hemaspaandra: SIGACT news complexity theory column 49. SIGACT News 36(4): 24-35 (2005)

165 EE Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel: All superlinear inverse schemes are coNP-hard. Theor. Comput. Sci. 345(2-3): 345-358 (2005)

2004

164 EE Lane A. Hemaspaandra, Mitsunori Ogihara, Mohammed Javeed Zaki, Marius Zimand: The Complexity of Finding Top-Toda-Equivalence-Class Members. LATIN 2004: 90-99

163 EE Edith Hemaspaandra, Lane A. Hemaspaandra, Stanislaw P. Radziszowski, Rahul Tripathi: Complexity Results in Graph Reconstruction. MFCS 2004: 287-297

162 EE Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel: All Superlinear Inverse Schemes Are coNP-Hard. MFCS 2004: 368-379

161 EE Edith Hemaspaandra, Lane A. Hemaspaandra, Stanislaw P. Radziszowski, Rahul Tripathi: Complexity Results in Graph Reconstruction CoRR cs.CC/0410021: (2004)

160 EE Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel: All Superlinear Inverse Schemes are coNP-Hard CoRR cs.CC/0410023: (2004)

159 EE Lane A. Hemaspaandra, Proshanto Mukherji, Till Tantau: Overhead-Free Computation, DCFLs, and CFLs CoRR cs.CC/0410035: (2004)

158 EE Lane A. Hemaspaandra, Harald Hempel, Arfst Nickelsen: Algebraic Properties for Selector Functions. SIAM J. Comput. 33(6): 1309-1337 (2004)

157 EE Lane A. Hemaspaandra: SIGACT news complexity theory column 43. SIGACT News 35(1): 22-35 (2004)

156 EE Lane A. Hemaspaandra, Mayur Thakur: Lower bounds and the hardness of counting properties. Theor. Comput. Sci. 326(1-3): 1-28 (2004)

2003

155 EE Lane A. Hemaspaandra, Proshanto Mukherji, Till Tantau: Computation with Absolutely No Space Overhead. Developments in Language Theory 2003: 325-336

154 EE Jin-yi Cai, Venkatesan T. Chakaravarthy, Lane A. Hemaspaandra, Mitsunori Ogihara: Competing Provers Yield Improved Karp-Lipton Collapse Results. STACS 2003: 535-546

153 EE Lane A. Hemaspaandra, Harald Hempel: P-immune sets with holes lack self-reducibility properties. Theor. Comput. Sci. 302(1-3): 457-466 (2003)

2002

152 Lane A. Hemaspaandra, Mayur Thakur: Lower Bounds and the Hardness of Counting Properties. IFIP TCS 2002: 217-229

151 EE Richard Beigel, Lane A. Hemaspaandra, Harald Hempel, Jörg Vogel: Optimal Series-Parallel Trade-offs for Reducing a Function to Its Own Graph. Inf. Comput. 173(2): 123-131 (2002)

150 EE Edith Hemaspaandra, Lane A. Hemaspaandra, Marius Zimand: Almost-Everywhere Superiority for Quantum Polynomial Time. Inf. Comput. 175(2): 171-181 (2002)

149 EE Jörg Rothe, Lane A. Hemaspaandra: On characterizing the existence of partial one-way permutations. Inf. Process. Lett. 82(3): 165-171 (2002)

148 EE Lane A. Hemaspaandra, Mitsunori Ogihara, Gerd Wechsung: Reducing the Number of Solutions of NP Functions. J. Comput. Syst. Sci. 64(2): 311-328 (2002)

2001

147 EE Lane A. Hemaspaandra, Harald Hempel, Arfst Nickelsen: Algebraic Properties for P-Selectivity. COCOON 2001: 49-58

146 EE Lane A. Hemaspaandra, Kari Pasanen, Jörg Rothe: If P != NP Then Some Strongly Noninvertible Functions Are Invertible. FCT 2001: 162-171

145 EE Lane A. Hemaspaandra, Sven Kosub, Klaus W. Wagner: The Complexity of Computing the Size of an Interval. ICALP 2001: 1040-1051

144 EE Lane A. Hemaspaandra, Harald Hempel: P-Immune Sets with Holes Lack Self-Reducibility Properties CoRR cs.CC/0102024: (2001)

143 EE Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel: Using the No-Search Easy-Hard Technique for Downward Collapse CoRR cs.CC/0106037: (2001)

2000

142 EE Lane A. Hemaspaandra, Mitsunori Ogihara, Gerd Wechsung: Reducing the Number of Solutions of NP Functions. MFCS 2000: 394-404

141 EE Edith Hemaspaandra, Lane A. Hemaspaandra: Computational Politics: Electoral Systems. MFCS 2000: 64-83

140 EE Christian Glaßer, Lane A. Hemaspaandra: A Moment of Perfect Clarity I: The Parallel Census Technique CoRR cs.CC/0007025: (2000)

139 EE Lane A. Hemaspaandra, Kari Pasanen, Jörg Rothe: If P \neq NP then Some Strongly Noninvertible Functions are Invertible CoRR cs.CC/0010011: (2000)

138 EE Christian Glaßer, Lane A. Hemaspaandra: A Moment of Perfect Clarity II: Consequences of Sparse Sets Hard for NP with Respect to Weak Reductions CoRR cs.CC/0011019: (2000)

137 EE Lane A. Hemaspaandra: Take-home Complexity CoRR cs.CY/0001016: (2000)

136 EE Lane A. Hemaspaandra, Albrecht Hoene, Mitsunori Ogihara: Erratum to "Reducibility classes of P-selective sets". Theor. Comput. Sci. 234(1-2): 323 (2000)

135 EE Lane A. Hemaspaandra, Jörg Rothe: A second step towards complexity-theoretic analogs of Rice's Theorem. Theor. Comput. Sci. 244(1-2): 205-217 (2000)

134 EE Lane A. Hemaspaandra, Jörg Rothe: Characterizing the existence of one-way permutations. Theor. Comput. Sci. 244(1-2): 257-261 (2000)

1999

133 EE Bernd Borchert, Lane A. Hemaspaandra, Jörg Rothe: Restrictive Acceptance Suffices for Equivalence Problems. FCT 1999: 124-135

132 EE Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel: Extending Downward Collapse from 1-versus-2 Queries to j-versus-j+1 Queries. STACS 1999: 269-280

131 EE Jin-yi Cai, Lane A. Hemaspaandra, Gerd Wechsung: Robust Reductions CoRR cs.CC/9906033: (1999)

130 EE Lane A. Hemaspaandra, Jörg Rothe: Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets CoRR cs.CC/9907033: (1999)

129 EE Lane A. Hemaspaandra, Zhigen Jiang, Jörg Rothe, Osamu Watanabe: Polynomial-Time Multi-Selectivity CoRR cs.CC/9907034: (1999)

128 EE Lane A. Hemaspaandra, Jörg Rothe, Gerd Wechsung: Easy Sets and Hard Certificate Schemes CoRR cs.CC/9907035: (1999)

127 EE Edith Hemaspaandra, Lane A. Hemaspaandra, Jörg Rothe: Exact Analysis of Dodgson Elections: Lewis Carroll's 1876 Voting System is Complete for Parallel Access to NP CoRR cs.CC/9907036: (1999)

126 EE Lane A. Hemaspaandra, Zhigen Jiang, Jörg Rothe, Osamu Watanabe: Boolean Operations, Joins, and the Extended Low Hierarchy CoRR cs.CC/9907037: (1999)

125 EE Lane A. Hemaspaandra, Jörg Rothe: A Second Step Towards Complexity-Theoretic Analogs of Rice's Theorem CoRR cs.CC/9907038: (1999)

124 EE Edith Hemaspaandra, Lane A. Hemaspaandra, Jörg Rothe: Raising NP Lower Bounds to Parallel NP Lower Bounds CoRR cs.CC/9907039: (1999)

123 EE Jörg Rothe, Lane A. Hemaspaandra: Characterizations of the Existence of Partial and Total One-Way Permutations CoRR cs.CC/9907040: (1999)

122 EE Bernd Borchert, Lane A. Hemaspaandra, Jörg Rothe: Restrictive Acceptance Suffices for Equivalence Problems CoRR cs.CC/9907041: (1999)

121 EE Lane A. Hemaspaandra, Harald Hempel, Gerd Wechsung: Query Order CoRR cs.CC/9909020: (1999)

120 EE Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel: What's Up with Downward Collapse: Using the Easy-Hard Technique to Link Boolean and Polynomial Hierarchy Collapses CoRR cs.CC/9910002: (1999)

119 EE Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel: R_1-tt^SN(NP) Distinguishes Robust Many-One and Turing Completeness CoRR cs.CC/9910003: (1999)

118 EE Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel: An Introduction to Query Order CoRR cs.CC/9910004: (1999)

117 EE Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel: Query Order and the Polynomial Hierarchy CoRR cs.CC/9910005: (1999)

116 EE Lane A. Hemaspaandra, Harald Hempel, Gerd Wechsung: Self-Specifying Machines CoRR cs.CC/9910006: (1999)

115 EE Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel: A Downward Collapse within the Polynomial Hierarchy CoRR cs.CC/9910007: (1999)

114 EE Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel: Translating Equality Downwards CoRR cs.CC/9910008: (1999)

113 EE Alina Beygelzimer, Lane A. Hemaspaandra, Christopher M. Homan, Jörg Rothe: One-Way Functions in Worst-Case Cryptography: Algebraic and Security Properties CoRR cs.CC/9911007: (1999)

112 EE Russell Bent, Michael Schear, Lane A. Hemaspaandra, Gabriel Istrate: On Bounded-Weight Error-Correcting Codes CoRR cs.OH/9906001: (1999)

111 EE Edith Hemaspaandra, Lane A. Hemaspaandra, Marius Zimand: Almost-Everywhere Superiority for Quantum Computing CoRR quant-ph/9910033: (1999)

110 Lane A. Hemaspaandra, Harald Hempel, Gerd Wechsung: Self-Specifying Machines. Int. J. Found. Comput. Sci. 10(3): 263-276 (1999)

109 Lane A. Hemaspaandra, Jörg Rothe: Creating Strong, Total, Commutative, Associative One-Way Functions from Any One-Way Function in Complexity Theory. J. Comput. Syst. Sci. 58(3): 648-659 (1999)

108 EE Russell Bent, Michael Schear, Lane A. Hemaspaandra, Gabriel Istrate: A Note on Bounded-Weight Error-Correcting Codes. J. UCS 5(12): 817-827 (1999)

107 EE Jin-yi Cai, Lane A. Hemaspaandra, Gerd Wechsung: Robust Reductions. Theory Comput. Syst. 32(6): 625-647 (1999)

1998

106 EE Jin-yi Cai, Lane A. Hemaspaandra, Gerd Wechsung: Robust Reductions. COCOON 1998: 174-183

105 EE Lane A. Hemaspaandra, Jörg Rothe: A Second Step Towards Circuit Complexity-Theoretic Analogs of Rice's Theorem. MFCS 1998: 418-426

104 EE Lane A. Hemaspaandra, Kulathur S. Rajasethupathy, Prasanna Sethupathy, Marius Zimand: Power Balance and Apportionment Algorithms for the United States Congress. ACM Journal of Experimental Algorithmics 3: 1 (1998)

103 EE Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel: Downward Collapse from a Weaker Hypothesis CoRR cs.CC/9808002: (1998)

102 EE Lane A. Hemaspaandra, Jörg Rothe: Creating Strong Total Commutative Associative Complexity-Theoretic One-Way Functions from Any Complexity-Theoretic One-Way Function CoRR cs.CC/9808003: (1998)

101 EE Lane A. Hemaspaandra, Alan L. Selman: Writing and Editing Complexity Theory: Tales and Tools CoRR cs.GL/9811005: (1998)

100 EE Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel: Query Order and the Polynomial Hierarchy. J. UCS 4(6): 574-588 (1998)

99 EE Lane A. Hemaspaandra, Christopher Nasipak, Keith Parkins: A Note on Linear-Nondeterminism, Linear-Sized, Karp-Lipton Advice for the P-Selective Sets. J. UCS 4(8): 670-674 (1998)

98 Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel: A Downward Collapse within the Polynomial Hierarchy. SIAM J. Comput. 28(2): 383-393 (1998)

97 Lane A. Hemaspaandra, Harald Hempel, Gerd Wechsung: Query Order. SIAM J. Comput. 28(2): 637-651 (1998)

96 EE Lane A. Hemaspaandra, Zhigen Jiang, Jörg Rothe, Osamu Watanabe: Boolean Operations, Joins, and the Extended Low Hierarchy. Theor. Comput. Sci. 205(1-2): 317-327 (1998)

95 Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel: R^{S N}_1-tt (NP) Distinguishes Robust Many-One and Turing Completeness. Theory Comput. Syst. 31(3): 307-325 (1998)

1997

94 Lane A. Hemaspaandra, Jörg Rothe, Gerd Wechsung: On Sets with Easy Certificates and the Existence of One-Way Permutations. CIAC 1997: 264-275

93 Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel: R^SN_1-tt(NP) Distinguishes Robust Many-One and Turing Completeness. CIAC 1997: 49-60

92 Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel: Query Order in the Polynomial Hierarchy. FCT 1997: 222-232

91 Edith Hemaspaandra, Lane A. Hemaspaandra, Jörg Rothe: Exact Analysis of Dodgson Elections: Lewis Carroll's 1876 Voting System is Complete for Parallel Access to NP. ICALP 1997: 214-224

90 Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel: A Downward Translation in the Polynomial Hierarchy. STACS 1997: 319-328

89 EE Lane A. Hemaspaandra, Jörg Rothe, Gerd Wechsung: Easy Sets and Hard Certificate Schemes. Acta Inf. 34(11): 859-879 (1997)

88 Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel: An Introduction to Query Order. Bulletin of the EATCS 63: (1997)

87 Lane A. Hemaspaandra, Z. Jiang: Logspace Reducibility: Models and Equivalences. Int. J. Found. Comput. Sci. 8(1): 95- (1997)

86 EE Edith Hemaspaandra, Lane A. Hemaspaandra, Jörg Rothe: Exact analysis of Dodgson elections: Lewis Carroll's 1876 voting system is complete for parallel access to NP. J. ACM 44(6): 806-825 (1997)

85 Lane A. Hemaspaandra, Mitsunori Ogihara: Universally Serializable Computation. J. Comput. Syst. Sci. 55(3): 547-560 (1997)

84 EE Lane A. Hemaspaandra, Zhigen Jiang, Jörg Rothe, Osamu Watanabe: Polynomial-Time Multi-Selectivity. J. UCS 3(3): 197-229 (1997)

83 Yenjo Han, Lane A. Hemaspaandra, Thomas Thierauf: Threshold Computation and Cryptographic Security. SIAM J. Comput. 26(1): 59-78 (1997)

82 Lane A. Hemaspaandra, Jörg Rothe: Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets. SIAM J. Comput. 26(3): 634-653 (1997)

1996

81 Lane A. Hemaspaandra, Zhigen Jiang, Jörg Rothe, Osamu Watanabe: The Join Can Lower Complexity. COCOON 1996: 260-267

80 EE Lane A. Hemaspaandra, Ashish V. Naik, Mitsunori Ogihara, Alan L. Selman: Computing Solutions Uniquely Collapses the Polynomial Hierarchy Electronic Colloquium on Computational Complexity (ECCC) 3(27): (1996)

79 EE Bernd Borchert, Lane A. Hemaspaandra, Jörg Rothe: Powers-of-Two Acceptance Suffices for Equivalence and Bounded Ambiguity Problems Electronic Colloquium on Computational Complexity (ECCC) 3(45): (1996)

78 Yenjo Han, Lane A. Hemaspaandra: Pseudorandom Generators and the Frequency of Simplicity. J. Cryptology 9(4): 251-261 (1996)

77 Lane A. Hemaspaandra, Marius Zimand: Strong Self-Reducibility Precludes Strong Immunity. Mathematical Systems Theory 29(5): 535-548 (1996)

76 Lane A. Hemaspaandra, Ashish V. Naik, Mitsunori Ogihara, Alan L. Selman: Computing Solutions Uniquely Collapses the Polynomial Hierarchy. SIAM J. Comput. 25(4): 697-708 (1996)

75 EE Lane A. Hemaspaandra, Leen Torenvliet: Optimal Advice. Theor. Comput. Sci. 154(2): 367-377 (1996)

74 EE Lane A. Hemaspaandra, Albrecht Hoene, Mitsunori Ogihara: Reducibility Classes of P-Selective Sets. Theor. Comput. Sci. 155(2): 447-457 (1996)

1995

73 Lane A. Hemaspaandra, Jörg Rothe: Intersection Suffices for Boolean Hierarchy Equivalence. COCOON 1995: 430-435

72 Sophie Fischer, Lane A. Hemaspaandra, Leen Torenvliet: Witness-Isomorphic Reductions and the Local Search Problem (Extended Abstract). MFCS 1995: 277-287

71 Yenjo Han, Lane A. Hemaspaandra: Pseudorandom Generators and the Frequency of Simplicity. STACS 1995: 50-59

70 Lane A. Hemaspaandra, Sudhir K. Jha: Defying Upward and Downward Separation Inf. Comput. 121(1): 1-13 (1995)

69 Lane A. Hemaspaandra, Albrecht Hoene, Ashish V. Naik, Mitsunori Ogihara, Alan L. Selman, Thomas Thierauf, Jie Wang: Nondeterministically Selective Sets. Int. J. Found. Comput. Sci. 6(4): 403-416 (1995)

68 Lane A. Hemaspaandra, Riccardo Silvestri: Easily Checked Generalized Self-Reducibility. SIAM J. Comput. 24(4): 840-858 (1995)

67 EE Lane A. Hemaspaandra, Zhigen Jiang: P-Selectivity: Intersections and Indices. Theor. Comput. Sci. 145(1&2): 371-380 (1995)

1994

66 Lane A. Hemaspaandra, Ashish V. Naik, Mitsunori Ogihara, Alan L. Selman: Computing Solutions Uniquely collapses the Polynomial Hierarchy. ISAAC 1994: 56-64

65 Lane A. Hemaspaandra, Mitsunori Ogihara, Seinosuke Toda: Space-Efficient Recognition of Sparse Self-Reducible Languages. Computational Complexity 4: 262-296 (1994)

64 Dieter Kratsch, Lane A. Hemaspaandra: On the Complexity of Graph Reconstruction. Mathematical Systems Theory 27(3): 257-273 (1994)

63 Edith Hemaspaandra, Lane A. Hemaspaandra: Quasi-injective Reductions. Theor. Comput. Sci. 123(2): 407-413 (1994)

1993

62 Lane A. Hemachandra, Riccardo Silvestri: Easity Checked Self-Reducibility (Extended Abstract). FCT 1993: 289-298

61 Lane A. Hemachandra: Fault-Tolerance and Complexity (Extended Abstract). ICALP 1993: 189-202

60 Lane A. Hemachandra, Albrecht Hoene, Mitsunori Ogiwara, Alan L. Selman, Thomas Thierauf, Jie Wang: Selectivity. ICCI 1993: 55-59

59 Yenjo Han, Lane A. Hemaspaandra, Thomas Thierauf: Threshold Computation and Cryptographic Security. ISAAC 1993: 230-239

58 Lane A. Hemachandra, Sudhir K. Jha: Defying Upward and Downward Separation. STACS 1993: 185-195

57 Gerhard Buntrock, Lane A. Hemachandra, Dirk Siefkes: Using Inductive Counting to Simulate Nondeterministic Computation Inf. Comput. 102(1): 102-117 (1993)

56 William I. Gasarch, Lane A. Hemachandra, Albrecht Hoene: On Checking Versus Evaluation of Multiple Queries Inf. Comput. 105(1): 72-93 (1993)

55 Lane A. Hemaspaandra, Sanjay Jain, Nikolai K. Vereshchagin: Banishing Robust Turing Completeness. Int. J. Found. Comput. Sci. 4(3): 245-265 (1993)

54 Mitsunori Ogiwara, Lane A. Hemachandra: A Complexity Theory for Feasible Closure Properties. J. Comput. Syst. Sci. 46(3): 295-325 (1993)

53 Lane A. Hemachandra, Albrecht Hoene: Collapsing Degrees via Strong Computation. J. Comput. Syst. Sci. 46(3): 363-380 (1993)

1992

52 Vikraman Arvind, Yenjo Han, Lane A. Hemachandra, Johannes Köbler, Antoni Lozano, Martin Mundhenk, Mitsunori Ogiwara, Uwe Schöning, Riccardo Silvestri, Thomas Thierauf: Reductions to Sets of Low Information Content. Complexity Theory: Current Research 1992: 1-46

51 Jin-yi Cai, Lane A. Hemachandra, Jozef Vyskoc: Promise Problems and Guarded Access to Unambiguous Computation. Complexity Theory: Current Research 1992: 101-146

50 Vikraman Arvind, Yenjo Han, Lane A. Hemachandra, Johannes Köbler, Antoni Lozano, Martin Mundhenk, Mitsunori Ogiwara, Uwe Schöning, Riccardo Silvestri, Thomas Thierauf: Reductions to Sets of Low Information Content. ICALP 1992: 162-173

49 Lane A. Hemachandra, Sanjay Jain, Nikolai K. Vereshchagin: Banishing Robust Turing Completeness. LFCS 1992: 186-197

48 Jin-yi Cai, Lane A. Hemachandra, Jozef Vyskoc: Promise Problems and Access to Unambiguous Computation. MFCS 1992: 162-171

47 Lane A. Hemachandra, Mitsunori Ogiwara, Osamu Watanabe: How Hard Are Sparse Sets? Structure in Complexity Theory Conference 1992: 222-238

46 Lane A. Hemachandra, Mitsunori Ogiwara: Is #P Closed under Substraction? Bulletin of the EATCS 46: 107-123 (1992)

45 Judy Goldsmith, Lane A. Hemachandra, Kenneth Kunen: Polynomial-Time Compression. Computational Complexity 2: 18-39 (1992)

44 EE Eric Allender, Lane A. Hemachandra: Lower Bounds for the Low Hierarchy. J. ACM 39(1): 234-251 (1992)

43 David Eppstein, Lane A. Hemachandra, James Tisdall, Bülent Yener: Simultaneous Strong Separations of Probabilistic and Unambiguous Complexity Classes. Mathematical Systems Theory 25(1): 23-36 (1992)

42 Eric Allender, Lane A. Hemachandra, Mitsunori Ogiwara, Osamu Watanabe: Relating Equivalence and Reducibility to Sparse Sets. SIAM J. Comput. 21(3): 521-539 (1992)

41 Lane A. Hemachandra, Roy S. Rubinstein: Separating Complexity Classes With Tally Oracles. Theor. Comput. Sci. 92(2): 309-318 (1992)

1991

40 Dieter Kratsch, Lane A. Hemachandra: On the Complexity of Graph Reconstruction. FCT 1991: 318-328

39 Judy Goldsmith, Lane A. Hemachandra, Kenneth Kunen: On the Structure and Complexity of Infinite Sets with Minimal Perfect Hash Functions. FSTTCS 1991: 212-223

38 Lane A. Hemachandra, Albrecht Hoene: Collapsing Degrees via Strong Computation (Extended Abstract). ICALP 1991: 393-404

37 Mitsunori Ogiwara, Lane A. Hemachandra: A Complexity Theory for Feasible Closure Properties. Structure in Complexity Theory Conference 1991: 16-29

36 Eric Allender, Lane A. Hemachandra, Mitsunori Ogiwara, Osamu Watanabe: Relating Equivalence and Reducibility to Sparse Sets. Structure in Complexity Theory Conference 1991: 220-229

35 Richard Beigel, Lane A. Hemachandra, Gerd Wechsung: Probabilistic Polynomial Time is Closed under Parity Reductions. Inf. Process. Lett. 37(2): 91-94 (1991)

34 Jin-yi Cai, Lane A. Hemachandra: A Note on Enumarative Counting. Inf. Process. Lett. 38(4): 215-219 (1991)

33 Lane A. Hemachandra, Sanjay Jain: On the Limitations of Locally Robust Positive Reductions. Int. J. Found. Comput. Sci. 2(3): 237-255 (1991)

32 Judy Goldsmith, Lane A. Hemachandra, Deborah Joseph, Paul Young: Near-Testable Sets. SIAM J. Comput. 20(3): 506-523 (1991)

31 Lane A. Hemachandra, Albrecht Hoene: On Sets with Efficient Implicit Membership Tests. SIAM J. Comput. 20(6): 1148-1156 (1991)

30 Lane A. Hemachandra, Albrecht Hoene, Dirk Siefkes, Paul Young: On Sets Polynomially Enumerable by Iteration. Theor. Comput. Sci. 80(2): 203-225 (1991)

29 Juris Hartmanis, Lane A. Hemachandra: One-Way Functions and the Nonisomorphism of NP-Complete Sets. Theor. Comput. Sci. 81(1): 155-163 (1991)

28 Lane A. Hemachandra, Gerd Wechsung: Kolmogorov Characterizations of Complexity Classes. Theor. Comput. Sci. 83(2): 313-322 (1991)

1990

27 Gerhard Buntrock, Lane A. Hemachandra, Dirk Siefkes: Using Inductive Counting to Simulate Nondeterministic Computation. MFCS 1990: 187-194

26 William I. Gasarch, Lane A. Hemachandra, Albrecht Hoene: On Checking Versus Evaluation of Multiple Queries. MFCS 1990: 261-268

25 Lane A. Hemachandra: Algorithms from Complexity Theory: Polynominal-Time Operations for Complex Sets. SIGAL International Symposium on Algorithms 1990: 221-231

24 Lane A. Hemachandra, Albrecht Hoene: On Sets with Efficient Implicit Membership Tests. Structure in Complexity Theory Conference 1990: 11-19

23 Lane A. Hemachandra, Roy S. Rubinstein: A Note on Relativizing Complexity Classes with Tally Oracles. Structure in Complexity Theory Conference 1990: 287-294

22 Lane A. Hemachandra, Steven Rudich: On the Complexity of Ranking. J. Comput. Syst. Sci. 41(2): 251-271 (1990)

21 Jin-yi Cai, Lane A. Hemachandra: On the Power of Parity Polynomial Time. Mathematical Systems Theory 23(2): 95-106 (1990)

20 Juris Hartmanis, Lane A. Hemachandra: Robust Machines Accept Easy Sets. Theor. Comput. Sci. 74(2): 217-225 (1990)

1989

19 Lane A. Hemachandra, Sanjay Jain: On the Limitations of Locally Robust Positive Reductions. FSTTCS 1989: 193-203

18 Eric Allender, Lane A. Hemachandra: Lower Bounds for the Low Hierarchy (Extended Abstract). ICALP 1989: 31-45

17 Lane A. Hemachandra, Gerd Wechsung: Using Randomness to Characterize the Complexity of Computation. IFIP Congress 1989: 281-286

16 Lane A. Hemachandra, Albrecht Hoene, Dirk Siefkes: Polynomial-Time Functions Generate SAT: On P-Splinters. MFCS 1989: 259-269

15 Jin-yi Cai, Lane A. Hemachandra: On the Power of Parity Polynomial Time. STACS 1989: 229-239

14 Richard Beigel, Lane A. Hemachandra, Gerd Wechsung: On the Power of Probabilistic Polynomial Time: P^NP[log] subseteq PP. Structure in Complexity Theory Conference 1989: 225-227

13 Jin-yi Cai, Lane A. Hemachandra: Enumerative Counting Is Hard Inf. Comput. 82(1): 34-44 (1989)

12 Lane A. Hemachandra: The Strong Exponential Hierarchy Collapses. J. Comput. Syst. Sci. 39(3): 299-322 (1989)

11 Jin-yi Cai, Thomas Gundermann, Juris Hartmanis, Lane A. Hemachandra, Vivian Sewelson, Klaus W. Wagner, Gerd Wechsung: The Boolean Hierarchy II: Applications. SIAM J. Comput. 18(1): 95-111 (1989)

1988

10 EE Martín Abadi, Eric Allender, Andrei Z. Broder, Joan Feigenbaum, Lane A. Hemachandra: On Generating Solved Instances of Computational Problems. CRYPTO 1988: 297-310

9 Lane A. Hemachandra: Structure of Complexity Classes: Separations, Collapses, and Completeness. MFCS 1988: 59-72

8 Juris Hartmanis, Lane A. Hemachandra: On Sparse Oracles Separating Feasible Complexity Classes. Inf. Process. Lett. 28(6): 291-295 (1988)

7 Jin-yi Cai, Thomas Gundermann, Juris Hartmanis, Lane A. Hemachandra, Vivian Sewelson, Klaus W. Wagner, Gerd Wechsung: The Boolean Hierarchy I: Structural Properties. SIAM J. Comput. 17(6): 1232-1252 (1988)

6 Juris Hartmanis, Lane A. Hemachandra: Complexity Classes without Machines: On Complete Languages for UP. Theor. Comput. Sci. 58: 129-142 (1988)

1987

5 Lane A. Hemachandra: The Strong Exponential Hierarchy Collapses STOC 1987: 110-122

4 Abbas A. El Gamal, Lane A. Hemachandra, Itzhak Shperling, Victor K.-W. Wei: Using simulated annealing to design good codes. IEEE Transactions on Information Theory 33(1): 116-123 (1987)

1986

3 Juris Hartmanis, Lane A. Hemachandra: Complexity Classes Without Machines: On Complete Languages for UP. ICALP 1986: 123-135

2 Juris Hartmanis, Lane A. Hemachandra: On Sparse Oracles Separating Feasible Complexity Classes. STACS 1986: 321-333

1 Jin-yi Cai, Lane A. Hemachandra: The Boolean Hierarchy: Hardware over NP. Structure in Complexity Theory Conference 1986: 105-124

2009
222	EE	Piotr Faliszewski, Lane A. Hemaspaandra: The complexity of power-index comparison. Theor. Comput. Sci. 410(1): 101-107 (2009)
2008
221	EE	Piotr Faliszewski, Edith Hemaspaandra, Lane A. Hemaspaandra, Jörg Rothe: Copeland Voting Fully Resists Constructive Control. AAIM 2008: 165-176
220	EE	Piotr Faliszewski, Lane A. Hemaspaandra: The Complexity of Power-Index Comparison. AAIM 2008: 177-187
219	EE	Piotr Faliszewski, Lane A. Hemaspaandra: The Complexity of Power-Index Comparison CoRR abs/0801.4585: (2008)
218	EE	Gábor Erdélyi, Lane A. Hemaspaandra, Jörg Rothe, Holger Spakowski: Frequency of Correctness versus Average-Case Polynomial Time and Generalized Juntas CoRR abs/0806.2555: (2008)
217	EE	Piotr Faliszewski, Edith Hemaspaandra, Lane A. Hemaspaandra, Jörg Rothe: Llull and Copeland Voting Computationally Resist Bribery and Control CoRR abs/0809.4484: (2008)
216	EE	Piotr Faliszewski, Lane A. Hemaspaandra: The consequences of eliminating NP solutions. Computer Science Review 2(1): 40-54 (2008)
215	EE	Lane A. Hemaspaandra: SIGACT news complexity theory column 59: introduction. SIGACT News 39(2): 50 (2008)
214	EE	Lane A. Hemaspaandra, Jörg Rothe, Amitabh Saxena: Enforcing and defying associativity, commutativity, totality, and strong noninvertibility for worst-case one-way functions. Theor. Comput. Sci. 401(1-3): 27-35 (2008)
2007
213		Piotr Faliszewski, Edith Hemaspaandra, Lane A. Hemaspaandra, Jörg Rothe: Llull and Copeland Voting Broadly Resist Bribery and Control. AAAI 2007: 724-730
212	EE	Gábor Erdélyi, Lane A. Hemaspaandra, Jörg Rothe, Holger Spakowski: On Approximating Optimal Weighted Lobbying, and Frequency of Correctness Versus Average-Case Polynomial Time. FCT 2007: 300-311
211	EE	Edith Hemaspaandra, Lane A. Hemaspaandra, Till Tantau, Osamu Watanabe: On the Complexity of Kings. FCT 2007: 328-340
210	EE	Edith Hemaspaandra, Lane A. Hemaspaandra, Jörg Rothe: Hybrid Elections Broaden Complexity-Theoretic Resistance to Control. IJCAI 2007: 1308-1314
209	EE	Edith Hemaspaandra, Lane A. Hemaspaandra, Jörg Rothe: Anyone but him: The complexity of precluding an alternative. Artif. Intell. 171(5-6): 255-285 (2007)
208	EE	Piotr Faliszewski, Edith Hemaspaandra, Lane A. Hemaspaandra, Jörg Rothe: Copeland Voting Fully Resists Constructive Control CoRR abs/0711.4759: (2007)
207	EE	Gábor Erdélyi, Lane A. Hemaspaandra, Jörg Rothe, Holger Spakowski: On Approximating Optimal Weighted Lobbying, and Frequency of Correctness versus Average-Case Polynomial Time CoRR abs/cs/0703097: (2007)
206	EE	Edith Hemaspaandra, Lane A. Hemaspaandra, Stanislaw P. Radziszowski, Rahul Tripathi: Complexity results in graph reconstruction. Discrete Applied Mathematics 155(2): 103-118 (2007)
205	EE	Lane A. Hemaspaandra, Christopher M. Homan, Sven Kosub: Cluster computing and the power of edge recognition. Inf. Comput. 205(8): 1274-1293 (2007)
204	EE	Edith Hemaspaandra, Lane A. Hemaspaandra: Dichotomy for voting systems. J. Comput. Syst. Sci. 73(1): 73-83 (2007)
203	EE	Lane A. Hemaspaandra, Christopher M. Homan, Sven Kosub, Klaus W. Wagner: The Complexity of Computing the Size of an Interval. SIAM J. Comput. 36(5): 1264-1300 (2007)
202	EE	Lane A. Hemaspaandra: Introduction. SIGACT News 38(3): 34-38 (2007)
201	EE	Lane A. Hemaspaandra: Introduction. SIGACT News 38(4): 39-40 (2007)
200	EE	Lane A. Hemaspaandra, Mayur Thakur: Query-monotonic Turing reductions. Theor. Comput. Sci. 383(2-3): 153-186 (2007)
2006
199		Piotr Faliszewski, Edith Hemaspaandra, Lane A. Hemaspaandra: The Complexity of Bribery in Elections. AAAI 2006
198	EE	Christopher M. Homan, Lane A. Hemaspaandra: Guarantees for the Success Frequency of an Algorithm for Finding Dodgson-Election Winners. MFCS 2006: 528-539
197	EE	Lane A. Hemaspaandra, Leen Torenvliet: P-Selectivity, Immunity, and the Power of One Bit. SOFSEM 2006: 323-331
196	EE	Lane A. Hemaspaandra, Christopher M. Homan, Sven Kosub: Cluster Computing and the Power of Edge Recognition. TAMC 2006: 283-294
195	EE	Lane A. Hemaspaandra, Mayur Thakur: Query-Monotonic Turing Reductions CoRR abs/cs/0602001: (2006)
194	EE	Piotr Faliszewski, Lane A. Hemaspaandra: The Consequences of Eliminating NP Solutions CoRR abs/cs/0606009: (2006)
193	EE	Edith Hemaspaandra, Lane A. Hemaspaandra, Jörg Rothe: Hybrid Elections Broaden Complexity-Theoretic Resistance to Control CoRR abs/cs/0608057: (2006)
192	EE	Piotr Faliszewski, Edith Hemaspaandra, Lane A. Hemaspaandra: How Hard Is Bribery in Elections? CoRR abs/cs/0608081: (2006)
191	EE	Piotr Faliszewski, Edith Hemaspaandra, Lane A. Hemaspaandra, Jörg Rothe: A Richer Understanding of the Complexity of Election Systems CoRR abs/cs/0609112: (2006)
190	EE	Piotr Faliszewski, Lane A. Hemaspaandra: Open questions in the theory of semifeasible computation. SIGACT News 37(1): 47-65 (2006)
189	EE	Lane A. Hemaspaandra: SIGACT news complexity theory column 51. SIGACT News 37(2): 31-46 (2006)
188	EE	Lane A. Hemaspaandra: SIGACT news complexity theory column 52. SIGACT News 37(3): 36-54 (2006)
187	EE	Lane A. Hemaspaandra: SIGACT news complexity theory column 53. SIGACT News 37(4): 47-55 (2006)
186	EE	Lane A. Hemaspaandra, Kari Pasanen, Jörg Rothe: If P neq NP then some strongly noninvertible functions are invertible. Theor. Comput. Sci. 362(1-3): 54-62 (2006)
185	EE	Lane A. Hemaspaandra, Mitsunori Ogihara, Mohammed J. Zaki, Marius Zimand: The Complexity of Finding Top-Toda-Equivalence-Class Members. Theory Comput. Syst. 39(5): 669-684 (2006)
2005
184		Edith Hemaspaandra, Lane A. Hemaspaandra, Jörg Rothe: Anyone but Him: The Complexity of Precluding an Alternative. AAAI 2005: 95-101
183	EE	Lane A. Hemaspaandra, Mayur Thakur: Query-Monotonic Turing Reductions. COCOON 2005: 895-904
182	EE	Lane A. Hemaspaandra, Jörg Rothe, Amitabh Saxena: Enforcing and Defying Associativity, Commutativity, Totality, and Strong Noninvertibility for One-Way Functions in Complexity Theory. ICTCS 2005: 265-279
181	EE	Lane A. Hemaspaandra, Harald Hempel, Arfst Nickelsen: Algebraic Properties for Selector Functions CoRR abs/cs/0501022: (2005)
180	EE	Lane A. Hemaspaandra, Christopher M. Homan, Sven Kosub, Klaus W. Wagner: The Complexity of Computing the Size of an Interval CoRR abs/cs/0502058: (2005)
179	EE	Lane A. Hemaspaandra, Jörg Rothe, Amitabh Saxena: Enforcing and Defying Associativity, Commutativity, Totality, and Strong Noninvertibility for One-Way Functions in Complexity Theory CoRR abs/cs/0503049: (2005)
178	EE	Edith Hemaspaandra, Lane A. Hemaspaandra: Dichotomy for Voting Systems CoRR abs/cs/0504075: (2005)
177	EE	Lane A. Hemaspaandra, Leen Torenvliet: P-Selectivity, Immunity, and the Power of One Bit CoRR abs/cs/0504096: (2005)
176	EE	Edith Hemaspaandra, Lane A. Hemaspaandra, Osamu Watanabe: The Complexity of Kings CoRR abs/cs/0506055: (2005)
175	EE	Piotr Faliszewski, Lane A. Hemaspaandra: Open Questions in the Theory of Semifeasible Computation CoRR abs/cs/0506082: (2005)
174	EE	Edith Hemaspaandra, Lane A. Hemaspaandra, Jörg Rothe: Anyone but Him: The Complexity of Precluding an Alternative CoRR abs/cs/0507027: (2005)
173	EE	Lane A. Hemaspaandra, Christopher M. Homan, Sven Kosub: Cluster Computing and the Power of Edge Recognition CoRR abs/cs/0509060: (2005)
172	EE	Christopher M. Homan, Lane A. Hemaspaandra: Guarantees for the Success Frequency of an Algorithm for Finding Dodgson-Election Winners CoRR abs/cs/0509061: (2005)
171	EE	Jin-yi Cai, Venkatesan T. Chakaravarthy, Lane A. Hemaspaandra, Mitsunori Ogihara: Competing provers yield improved Karp-Lipton collapse results. Inf. Comput. 198(1): 1-23 (2005)
170	EE	Lane A. Hemaspaandra, Proshanto Mukherji, Till Tantau: Context-free languages can be accepted with absolutely no space overhead. Inf. Comput. 203(2): 163-180 (2005)
169	EE	Piotr Faliszewski, Lane A. Hemaspaandra: Advice for semifeasible sets and the complexity-theoretic cost(lessness) of algebraic properties. Int. J. Found. Comput. Sci. 16(5): 913-928 (2005)
168	EE	Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel: Extending Downward Collapse from 1-versus-2 Queries to m-versus-m + 1 Queries. SIAM J. Comput. 34(6): 1352-1369 (2005)
167	EE	Lane A. Hemaspaandra: SIGACT news complexity theory column 48. SIGACT News 36(3): 24-38 (2005)
166	EE	Lane A. Hemaspaandra: SIGACT news complexity theory column 49. SIGACT News 36(4): 24-35 (2005)
165	EE	Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel: All superlinear inverse schemes are coNP-hard. Theor. Comput. Sci. 345(2-3): 345-358 (2005)
2004
164	EE	Lane A. Hemaspaandra, Mitsunori Ogihara, Mohammed Javeed Zaki, Marius Zimand: The Complexity of Finding Top-Toda-Equivalence-Class Members. LATIN 2004: 90-99
163	EE	Edith Hemaspaandra, Lane A. Hemaspaandra, Stanislaw P. Radziszowski, Rahul Tripathi: Complexity Results in Graph Reconstruction. MFCS 2004: 287-297
162	EE	Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel: All Superlinear Inverse Schemes Are coNP-Hard. MFCS 2004: 368-379
161	EE	Edith Hemaspaandra, Lane A. Hemaspaandra, Stanislaw P. Radziszowski, Rahul Tripathi: Complexity Results in Graph Reconstruction CoRR cs.CC/0410021: (2004)
160	EE	Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel: All Superlinear Inverse Schemes are coNP-Hard CoRR cs.CC/0410023: (2004)
159	EE	Lane A. Hemaspaandra, Proshanto Mukherji, Till Tantau: Overhead-Free Computation, DCFLs, and CFLs CoRR cs.CC/0410035: (2004)
158	EE	Lane A. Hemaspaandra, Harald Hempel, Arfst Nickelsen: Algebraic Properties for Selector Functions. SIAM J. Comput. 33(6): 1309-1337 (2004)
157	EE	Lane A. Hemaspaandra: SIGACT news complexity theory column 43. SIGACT News 35(1): 22-35 (2004)
156	EE	Lane A. Hemaspaandra, Mayur Thakur: Lower bounds and the hardness of counting properties. Theor. Comput. Sci. 326(1-3): 1-28 (2004)
2003
155	EE	Lane A. Hemaspaandra, Proshanto Mukherji, Till Tantau: Computation with Absolutely No Space Overhead. Developments in Language Theory 2003: 325-336
154	EE	Jin-yi Cai, Venkatesan T. Chakaravarthy, Lane A. Hemaspaandra, Mitsunori Ogihara: Competing Provers Yield Improved Karp-Lipton Collapse Results. STACS 2003: 535-546
153	EE	Lane A. Hemaspaandra, Harald Hempel: P-immune sets with holes lack self-reducibility properties. Theor. Comput. Sci. 302(1-3): 457-466 (2003)
2002
152		Lane A. Hemaspaandra, Mayur Thakur: Lower Bounds and the Hardness of Counting Properties. IFIP TCS 2002: 217-229
151	EE	Richard Beigel, Lane A. Hemaspaandra, Harald Hempel, Jörg Vogel: Optimal Series-Parallel Trade-offs for Reducing a Function to Its Own Graph. Inf. Comput. 173(2): 123-131 (2002)
150	EE	Edith Hemaspaandra, Lane A. Hemaspaandra, Marius Zimand: Almost-Everywhere Superiority for Quantum Polynomial Time. Inf. Comput. 175(2): 171-181 (2002)
149	EE	Jörg Rothe, Lane A. Hemaspaandra: On characterizing the existence of partial one-way permutations. Inf. Process. Lett. 82(3): 165-171 (2002)
148	EE	Lane A. Hemaspaandra, Mitsunori Ogihara, Gerd Wechsung: Reducing the Number of Solutions of NP Functions. J. Comput. Syst. Sci. 64(2): 311-328 (2002)
2001
147	EE	Lane A. Hemaspaandra, Harald Hempel, Arfst Nickelsen: Algebraic Properties for P-Selectivity. COCOON 2001: 49-58
146	EE	Lane A. Hemaspaandra, Kari Pasanen, Jörg Rothe: If P != NP Then Some Strongly Noninvertible Functions Are Invertible. FCT 2001: 162-171
145	EE	Lane A. Hemaspaandra, Sven Kosub, Klaus W. Wagner: The Complexity of Computing the Size of an Interval. ICALP 2001: 1040-1051
144	EE	Lane A. Hemaspaandra, Harald Hempel: P-Immune Sets with Holes Lack Self-Reducibility Properties CoRR cs.CC/0102024: (2001)
143	EE	Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel: Using the No-Search Easy-Hard Technique for Downward Collapse CoRR cs.CC/0106037: (2001)
2000
142	EE	Lane A. Hemaspaandra, Mitsunori Ogihara, Gerd Wechsung: Reducing the Number of Solutions of NP Functions. MFCS 2000: 394-404
141	EE	Edith Hemaspaandra, Lane A. Hemaspaandra: Computational Politics: Electoral Systems. MFCS 2000: 64-83
140	EE	Christian Glaßer, Lane A. Hemaspaandra: A Moment of Perfect Clarity I: The Parallel Census Technique CoRR cs.CC/0007025: (2000)
139	EE	Lane A. Hemaspaandra, Kari Pasanen, Jörg Rothe: If P \neq NP then Some Strongly Noninvertible Functions are Invertible CoRR cs.CC/0010011: (2000)
138	EE	Christian Glaßer, Lane A. Hemaspaandra: A Moment of Perfect Clarity II: Consequences of Sparse Sets Hard for NP with Respect to Weak Reductions CoRR cs.CC/0011019: (2000)
137	EE	Lane A. Hemaspaandra: Take-home Complexity CoRR cs.CY/0001016: (2000)
136	EE	Lane A. Hemaspaandra, Albrecht Hoene, Mitsunori Ogihara: Erratum to "Reducibility classes of P-selective sets". Theor. Comput. Sci. 234(1-2): 323 (2000)
135	EE	Lane A. Hemaspaandra, Jörg Rothe: A second step towards complexity-theoretic analogs of Rice's Theorem. Theor. Comput. Sci. 244(1-2): 205-217 (2000)
134	EE	Lane A. Hemaspaandra, Jörg Rothe: Characterizing the existence of one-way permutations. Theor. Comput. Sci. 244(1-2): 257-261 (2000)
1999
133	EE	Bernd Borchert, Lane A. Hemaspaandra, Jörg Rothe: Restrictive Acceptance Suffices for Equivalence Problems. FCT 1999: 124-135
132	EE	Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel: Extending Downward Collapse from 1-versus-2 Queries to j-versus-j+1 Queries. STACS 1999: 269-280
131	EE	Jin-yi Cai, Lane A. Hemaspaandra, Gerd Wechsung: Robust Reductions CoRR cs.CC/9906033: (1999)
130	EE	Lane A. Hemaspaandra, Jörg Rothe: Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets CoRR cs.CC/9907033: (1999)
129	EE	Lane A. Hemaspaandra, Zhigen Jiang, Jörg Rothe, Osamu Watanabe: Polynomial-Time Multi-Selectivity CoRR cs.CC/9907034: (1999)
128	EE	Lane A. Hemaspaandra, Jörg Rothe, Gerd Wechsung: Easy Sets and Hard Certificate Schemes CoRR cs.CC/9907035: (1999)
127	EE	Edith Hemaspaandra, Lane A. Hemaspaandra, Jörg Rothe: Exact Analysis of Dodgson Elections: Lewis Carroll's 1876 Voting System is Complete for Parallel Access to NP CoRR cs.CC/9907036: (1999)
126	EE	Lane A. Hemaspaandra, Zhigen Jiang, Jörg Rothe, Osamu Watanabe: Boolean Operations, Joins, and the Extended Low Hierarchy CoRR cs.CC/9907037: (1999)
125	EE	Lane A. Hemaspaandra, Jörg Rothe: A Second Step Towards Complexity-Theoretic Analogs of Rice's Theorem CoRR cs.CC/9907038: (1999)
124	EE	Edith Hemaspaandra, Lane A. Hemaspaandra, Jörg Rothe: Raising NP Lower Bounds to Parallel NP Lower Bounds CoRR cs.CC/9907039: (1999)
123	EE	Jörg Rothe, Lane A. Hemaspaandra: Characterizations of the Existence of Partial and Total One-Way Permutations CoRR cs.CC/9907040: (1999)
122	EE	Bernd Borchert, Lane A. Hemaspaandra, Jörg Rothe: Restrictive Acceptance Suffices for Equivalence Problems CoRR cs.CC/9907041: (1999)
121	EE	Lane A. Hemaspaandra, Harald Hempel, Gerd Wechsung: Query Order CoRR cs.CC/9909020: (1999)
120	EE	Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel: What's Up with Downward Collapse: Using the Easy-Hard Technique to Link Boolean and Polynomial Hierarchy Collapses CoRR cs.CC/9910002: (1999)
119	EE	Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel: R_1-tt^SN(NP) Distinguishes Robust Many-One and Turing Completeness CoRR cs.CC/9910003: (1999)
118	EE	Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel: An Introduction to Query Order CoRR cs.CC/9910004: (1999)
117	EE	Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel: Query Order and the Polynomial Hierarchy CoRR cs.CC/9910005: (1999)
116	EE	Lane A. Hemaspaandra, Harald Hempel, Gerd Wechsung: Self-Specifying Machines CoRR cs.CC/9910006: (1999)
115	EE	Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel: A Downward Collapse within the Polynomial Hierarchy CoRR cs.CC/9910007: (1999)
114	EE	Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel: Translating Equality Downwards CoRR cs.CC/9910008: (1999)
113	EE	Alina Beygelzimer, Lane A. Hemaspaandra, Christopher M. Homan, Jörg Rothe: One-Way Functions in Worst-Case Cryptography: Algebraic and Security Properties CoRR cs.CC/9911007: (1999)
112	EE	Russell Bent, Michael Schear, Lane A. Hemaspaandra, Gabriel Istrate: On Bounded-Weight Error-Correcting Codes CoRR cs.OH/9906001: (1999)
111	EE	Edith Hemaspaandra, Lane A. Hemaspaandra, Marius Zimand: Almost-Everywhere Superiority for Quantum Computing CoRR quant-ph/9910033: (1999)
110		Lane A. Hemaspaandra, Harald Hempel, Gerd Wechsung: Self-Specifying Machines. Int. J. Found. Comput. Sci. 10(3): 263-276 (1999)
109		Lane A. Hemaspaandra, Jörg Rothe: Creating Strong, Total, Commutative, Associative One-Way Functions from Any One-Way Function in Complexity Theory. J. Comput. Syst. Sci. 58(3): 648-659 (1999)
108	EE	Russell Bent, Michael Schear, Lane A. Hemaspaandra, Gabriel Istrate: A Note on Bounded-Weight Error-Correcting Codes. J. UCS 5(12): 817-827 (1999)
107	EE	Jin-yi Cai, Lane A. Hemaspaandra, Gerd Wechsung: Robust Reductions. Theory Comput. Syst. 32(6): 625-647 (1999)
1998
106	EE	Jin-yi Cai, Lane A. Hemaspaandra, Gerd Wechsung: Robust Reductions. COCOON 1998: 174-183
105	EE	Lane A. Hemaspaandra, Jörg Rothe: A Second Step Towards Circuit Complexity-Theoretic Analogs of Rice's Theorem. MFCS 1998: 418-426
104	EE	Lane A. Hemaspaandra, Kulathur S. Rajasethupathy, Prasanna Sethupathy, Marius Zimand: Power Balance and Apportionment Algorithms for the United States Congress. ACM Journal of Experimental Algorithmics 3: 1 (1998)
103	EE	Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel: Downward Collapse from a Weaker Hypothesis CoRR cs.CC/9808002: (1998)
102	EE	Lane A. Hemaspaandra, Jörg Rothe: Creating Strong Total Commutative Associative Complexity-Theoretic One-Way Functions from Any Complexity-Theoretic One-Way Function CoRR cs.CC/9808003: (1998)
101	EE	Lane A. Hemaspaandra, Alan L. Selman: Writing and Editing Complexity Theory: Tales and Tools CoRR cs.GL/9811005: (1998)
100	EE	Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel: Query Order and the Polynomial Hierarchy. J. UCS 4(6): 574-588 (1998)
99	EE	Lane A. Hemaspaandra, Christopher Nasipak, Keith Parkins: A Note on Linear-Nondeterminism, Linear-Sized, Karp-Lipton Advice for the P-Selective Sets. J. UCS 4(8): 670-674 (1998)
98		Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel: A Downward Collapse within the Polynomial Hierarchy. SIAM J. Comput. 28(2): 383-393 (1998)
97		Lane A. Hemaspaandra, Harald Hempel, Gerd Wechsung: Query Order. SIAM J. Comput. 28(2): 637-651 (1998)
96	EE	Lane A. Hemaspaandra, Zhigen Jiang, Jörg Rothe, Osamu Watanabe: Boolean Operations, Joins, and the Extended Low Hierarchy. Theor. Comput. Sci. 205(1-2): 317-327 (1998)
95		Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel: R^{S N}_1-tt (NP) Distinguishes Robust Many-One and Turing Completeness. Theory Comput. Syst. 31(3): 307-325 (1998)
1997
94		Lane A. Hemaspaandra, Jörg Rothe, Gerd Wechsung: On Sets with Easy Certificates and the Existence of One-Way Permutations. CIAC 1997: 264-275
93		Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel: R^SN_1-tt(NP) Distinguishes Robust Many-One and Turing Completeness. CIAC 1997: 49-60
92		Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel: Query Order in the Polynomial Hierarchy. FCT 1997: 222-232
91		Edith Hemaspaandra, Lane A. Hemaspaandra, Jörg Rothe: Exact Analysis of Dodgson Elections: Lewis Carroll's 1876 Voting System is Complete for Parallel Access to NP. ICALP 1997: 214-224
90		Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel: A Downward Translation in the Polynomial Hierarchy. STACS 1997: 319-328
89	EE	Lane A. Hemaspaandra, Jörg Rothe, Gerd Wechsung: Easy Sets and Hard Certificate Schemes. Acta Inf. 34(11): 859-879 (1997)
88		Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel: An Introduction to Query Order. Bulletin of the EATCS 63: (1997)
87		Lane A. Hemaspaandra, Z. Jiang: Logspace Reducibility: Models and Equivalences. Int. J. Found. Comput. Sci. 8(1): 95- (1997)
86	EE	Edith Hemaspaandra, Lane A. Hemaspaandra, Jörg Rothe: Exact analysis of Dodgson elections: Lewis Carroll's 1876 voting system is complete for parallel access to NP. J. ACM 44(6): 806-825 (1997)
85		Lane A. Hemaspaandra, Mitsunori Ogihara: Universally Serializable Computation. J. Comput. Syst. Sci. 55(3): 547-560 (1997)
84	EE	Lane A. Hemaspaandra, Zhigen Jiang, Jörg Rothe, Osamu Watanabe: Polynomial-Time Multi-Selectivity. J. UCS 3(3): 197-229 (1997)
83		Yenjo Han, Lane A. Hemaspaandra, Thomas Thierauf: Threshold Computation and Cryptographic Security. SIAM J. Comput. 26(1): 59-78 (1997)
82		Lane A. Hemaspaandra, Jörg Rothe: Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets. SIAM J. Comput. 26(3): 634-653 (1997)
1996
81		Lane A. Hemaspaandra, Zhigen Jiang, Jörg Rothe, Osamu Watanabe: The Join Can Lower Complexity. COCOON 1996: 260-267
80	EE	Lane A. Hemaspaandra, Ashish V. Naik, Mitsunori Ogihara, Alan L. Selman: Computing Solutions Uniquely Collapses the Polynomial Hierarchy Electronic Colloquium on Computational Complexity (ECCC) 3(27): (1996)
79	EE	Bernd Borchert, Lane A. Hemaspaandra, Jörg Rothe: Powers-of-Two Acceptance Suffices for Equivalence and Bounded Ambiguity Problems Electronic Colloquium on Computational Complexity (ECCC) 3(45): (1996)
78		Yenjo Han, Lane A. Hemaspaandra: Pseudorandom Generators and the Frequency of Simplicity. J. Cryptology 9(4): 251-261 (1996)
77		Lane A. Hemaspaandra, Marius Zimand: Strong Self-Reducibility Precludes Strong Immunity. Mathematical Systems Theory 29(5): 535-548 (1996)
76		Lane A. Hemaspaandra, Ashish V. Naik, Mitsunori Ogihara, Alan L. Selman: Computing Solutions Uniquely Collapses the Polynomial Hierarchy. SIAM J. Comput. 25(4): 697-708 (1996)
75	EE	Lane A. Hemaspaandra, Leen Torenvliet: Optimal Advice. Theor. Comput. Sci. 154(2): 367-377 (1996)
74	EE	Lane A. Hemaspaandra, Albrecht Hoene, Mitsunori Ogihara: Reducibility Classes of P-Selective Sets. Theor. Comput. Sci. 155(2): 447-457 (1996)
1995
73		Lane A. Hemaspaandra, Jörg Rothe: Intersection Suffices for Boolean Hierarchy Equivalence. COCOON 1995: 430-435
72		Sophie Fischer, Lane A. Hemaspaandra, Leen Torenvliet: Witness-Isomorphic Reductions and the Local Search Problem (Extended Abstract). MFCS 1995: 277-287
71		Yenjo Han, Lane A. Hemaspaandra: Pseudorandom Generators and the Frequency of Simplicity. STACS 1995: 50-59
70		Lane A. Hemaspaandra, Sudhir K. Jha: Defying Upward and Downward Separation Inf. Comput. 121(1): 1-13 (1995)
69		Lane A. Hemaspaandra, Albrecht Hoene, Ashish V. Naik, Mitsunori Ogihara, Alan L. Selman, Thomas Thierauf, Jie Wang: Nondeterministically Selective Sets. Int. J. Found. Comput. Sci. 6(4): 403-416 (1995)
68		Lane A. Hemaspaandra, Riccardo Silvestri: Easily Checked Generalized Self-Reducibility. SIAM J. Comput. 24(4): 840-858 (1995)
67	EE	Lane A. Hemaspaandra, Zhigen Jiang: P-Selectivity: Intersections and Indices. Theor. Comput. Sci. 145(1&2): 371-380 (1995)
1994
66		Lane A. Hemaspaandra, Ashish V. Naik, Mitsunori Ogihara, Alan L. Selman: Computing Solutions Uniquely collapses the Polynomial Hierarchy. ISAAC 1994: 56-64
65		Lane A. Hemaspaandra, Mitsunori Ogihara, Seinosuke Toda: Space-Efficient Recognition of Sparse Self-Reducible Languages. Computational Complexity 4: 262-296 (1994)
64		Dieter Kratsch, Lane A. Hemaspaandra: On the Complexity of Graph Reconstruction. Mathematical Systems Theory 27(3): 257-273 (1994)
63		Edith Hemaspaandra, Lane A. Hemaspaandra: Quasi-injective Reductions. Theor. Comput. Sci. 123(2): 407-413 (1994)
1993
62		Lane A. Hemachandra, Riccardo Silvestri: Easity Checked Self-Reducibility (Extended Abstract). FCT 1993: 289-298
61		Lane A. Hemachandra: Fault-Tolerance and Complexity (Extended Abstract). ICALP 1993: 189-202
60		Lane A. Hemachandra, Albrecht Hoene, Mitsunori Ogiwara, Alan L. Selman, Thomas Thierauf, Jie Wang: Selectivity. ICCI 1993: 55-59
59		Yenjo Han, Lane A. Hemaspaandra, Thomas Thierauf: Threshold Computation and Cryptographic Security. ISAAC 1993: 230-239
58		Lane A. Hemachandra, Sudhir K. Jha: Defying Upward and Downward Separation. STACS 1993: 185-195
57		Gerhard Buntrock, Lane A. Hemachandra, Dirk Siefkes: Using Inductive Counting to Simulate Nondeterministic Computation Inf. Comput. 102(1): 102-117 (1993)
56		William I. Gasarch, Lane A. Hemachandra, Albrecht Hoene: On Checking Versus Evaluation of Multiple Queries Inf. Comput. 105(1): 72-93 (1993)
55		Lane A. Hemaspaandra, Sanjay Jain, Nikolai K. Vereshchagin: Banishing Robust Turing Completeness. Int. J. Found. Comput. Sci. 4(3): 245-265 (1993)
54		Mitsunori Ogiwara, Lane A. Hemachandra: A Complexity Theory for Feasible Closure Properties. J. Comput. Syst. Sci. 46(3): 295-325 (1993)
53		Lane A. Hemachandra, Albrecht Hoene: Collapsing Degrees via Strong Computation. J. Comput. Syst. Sci. 46(3): 363-380 (1993)
1992
52		Vikraman Arvind, Yenjo Han, Lane A. Hemachandra, Johannes Köbler, Antoni Lozano, Martin Mundhenk, Mitsunori Ogiwara, Uwe Schöning, Riccardo Silvestri, Thomas Thierauf: Reductions to Sets of Low Information Content. Complexity Theory: Current Research 1992: 1-46
51		Jin-yi Cai, Lane A. Hemachandra, Jozef Vyskoc: Promise Problems and Guarded Access to Unambiguous Computation. Complexity Theory: Current Research 1992: 101-146
50		Vikraman Arvind, Yenjo Han, Lane A. Hemachandra, Johannes Köbler, Antoni Lozano, Martin Mundhenk, Mitsunori Ogiwara, Uwe Schöning, Riccardo Silvestri, Thomas Thierauf: Reductions to Sets of Low Information Content. ICALP 1992: 162-173
49		Lane A. Hemachandra, Sanjay Jain, Nikolai K. Vereshchagin: Banishing Robust Turing Completeness. LFCS 1992: 186-197
48		Jin-yi Cai, Lane A. Hemachandra, Jozef Vyskoc: Promise Problems and Access to Unambiguous Computation. MFCS 1992: 162-171
47		Lane A. Hemachandra, Mitsunori Ogiwara, Osamu Watanabe: How Hard Are Sparse Sets? Structure in Complexity Theory Conference 1992: 222-238
46		Lane A. Hemachandra, Mitsunori Ogiwara: Is #P Closed under Substraction? Bulletin of the EATCS 46: 107-123 (1992)
45		Judy Goldsmith, Lane A. Hemachandra, Kenneth Kunen: Polynomial-Time Compression. Computational Complexity 2: 18-39 (1992)
44	EE	Eric Allender, Lane A. Hemachandra: Lower Bounds for the Low Hierarchy. J. ACM 39(1): 234-251 (1992)
43		David Eppstein, Lane A. Hemachandra, James Tisdall, Bülent Yener: Simultaneous Strong Separations of Probabilistic and Unambiguous Complexity Classes. Mathematical Systems Theory 25(1): 23-36 (1992)
42		Eric Allender, Lane A. Hemachandra, Mitsunori Ogiwara, Osamu Watanabe: Relating Equivalence and Reducibility to Sparse Sets. SIAM J. Comput. 21(3): 521-539 (1992)
41		Lane A. Hemachandra, Roy S. Rubinstein: Separating Complexity Classes With Tally Oracles. Theor. Comput. Sci. 92(2): 309-318 (1992)
1991
40		Dieter Kratsch, Lane A. Hemachandra: On the Complexity of Graph Reconstruction. FCT 1991: 318-328
39		Judy Goldsmith, Lane A. Hemachandra, Kenneth Kunen: On the Structure and Complexity of Infinite Sets with Minimal Perfect Hash Functions. FSTTCS 1991: 212-223
38		Lane A. Hemachandra, Albrecht Hoene: Collapsing Degrees via Strong Computation (Extended Abstract). ICALP 1991: 393-404
37		Mitsunori Ogiwara, Lane A. Hemachandra: A Complexity Theory for Feasible Closure Properties. Structure in Complexity Theory Conference 1991: 16-29
36		Eric Allender, Lane A. Hemachandra, Mitsunori Ogiwara, Osamu Watanabe: Relating Equivalence and Reducibility to Sparse Sets. Structure in Complexity Theory Conference 1991: 220-229
35		Richard Beigel, Lane A. Hemachandra, Gerd Wechsung: Probabilistic Polynomial Time is Closed under Parity Reductions. Inf. Process. Lett. 37(2): 91-94 (1991)
34		Jin-yi Cai, Lane A. Hemachandra: A Note on Enumarative Counting. Inf. Process. Lett. 38(4): 215-219 (1991)
33		Lane A. Hemachandra, Sanjay Jain: On the Limitations of Locally Robust Positive Reductions. Int. J. Found. Comput. Sci. 2(3): 237-255 (1991)
32		Judy Goldsmith, Lane A. Hemachandra, Deborah Joseph, Paul Young: Near-Testable Sets. SIAM J. Comput. 20(3): 506-523 (1991)
31		Lane A. Hemachandra, Albrecht Hoene: On Sets with Efficient Implicit Membership Tests. SIAM J. Comput. 20(6): 1148-1156 (1991)
30		Lane A. Hemachandra, Albrecht Hoene, Dirk Siefkes, Paul Young: On Sets Polynomially Enumerable by Iteration. Theor. Comput. Sci. 80(2): 203-225 (1991)
29		Juris Hartmanis, Lane A. Hemachandra: One-Way Functions and the Nonisomorphism of NP-Complete Sets. Theor. Comput. Sci. 81(1): 155-163 (1991)
28		Lane A. Hemachandra, Gerd Wechsung: Kolmogorov Characterizations of Complexity Classes. Theor. Comput. Sci. 83(2): 313-322 (1991)
1990
27		Gerhard Buntrock, Lane A. Hemachandra, Dirk Siefkes: Using Inductive Counting to Simulate Nondeterministic Computation. MFCS 1990: 187-194
26		William I. Gasarch, Lane A. Hemachandra, Albrecht Hoene: On Checking Versus Evaluation of Multiple Queries. MFCS 1990: 261-268
25		Lane A. Hemachandra: Algorithms from Complexity Theory: Polynominal-Time Operations for Complex Sets. SIGAL International Symposium on Algorithms 1990: 221-231
24		Lane A. Hemachandra, Albrecht Hoene: On Sets with Efficient Implicit Membership Tests. Structure in Complexity Theory Conference 1990: 11-19
23		Lane A. Hemachandra, Roy S. Rubinstein: A Note on Relativizing Complexity Classes with Tally Oracles. Structure in Complexity Theory Conference 1990: 287-294
22		Lane A. Hemachandra, Steven Rudich: On the Complexity of Ranking. J. Comput. Syst. Sci. 41(2): 251-271 (1990)
21		Jin-yi Cai, Lane A. Hemachandra: On the Power of Parity Polynomial Time. Mathematical Systems Theory 23(2): 95-106 (1990)
20		Juris Hartmanis, Lane A. Hemachandra: Robust Machines Accept Easy Sets. Theor. Comput. Sci. 74(2): 217-225 (1990)
1989
19		Lane A. Hemachandra, Sanjay Jain: On the Limitations of Locally Robust Positive Reductions. FSTTCS 1989: 193-203
18		Eric Allender, Lane A. Hemachandra: Lower Bounds for the Low Hierarchy (Extended Abstract). ICALP 1989: 31-45
17		Lane A. Hemachandra, Gerd Wechsung: Using Randomness to Characterize the Complexity of Computation. IFIP Congress 1989: 281-286
16		Lane A. Hemachandra, Albrecht Hoene, Dirk Siefkes: Polynomial-Time Functions Generate SAT: On P-Splinters. MFCS 1989: 259-269
15		Jin-yi Cai, Lane A. Hemachandra: On the Power of Parity Polynomial Time. STACS 1989: 229-239
14		Richard Beigel, Lane A. Hemachandra, Gerd Wechsung: On the Power of Probabilistic Polynomial Time: P^NP[log] subseteq PP. Structure in Complexity Theory Conference 1989: 225-227
13		Jin-yi Cai, Lane A. Hemachandra: Enumerative Counting Is Hard Inf. Comput. 82(1): 34-44 (1989)
12		Lane A. Hemachandra: The Strong Exponential Hierarchy Collapses. J. Comput. Syst. Sci. 39(3): 299-322 (1989)
11		Jin-yi Cai, Thomas Gundermann, Juris Hartmanis, Lane A. Hemachandra, Vivian Sewelson, Klaus W. Wagner, Gerd Wechsung: The Boolean Hierarchy II: Applications. SIAM J. Comput. 18(1): 95-111 (1989)
1988
10	EE	Martín Abadi, Eric Allender, Andrei Z. Broder, Joan Feigenbaum, Lane A. Hemachandra: On Generating Solved Instances of Computational Problems. CRYPTO 1988: 297-310
9		Lane A. Hemachandra: Structure of Complexity Classes: Separations, Collapses, and Completeness. MFCS 1988: 59-72
8		Juris Hartmanis, Lane A. Hemachandra: On Sparse Oracles Separating Feasible Complexity Classes. Inf. Process. Lett. 28(6): 291-295 (1988)
7		Jin-yi Cai, Thomas Gundermann, Juris Hartmanis, Lane A. Hemachandra, Vivian Sewelson, Klaus W. Wagner, Gerd Wechsung: The Boolean Hierarchy I: Structural Properties. SIAM J. Comput. 17(6): 1232-1252 (1988)
6		Juris Hartmanis, Lane A. Hemachandra: Complexity Classes without Machines: On Complete Languages for UP. Theor. Comput. Sci. 58: 129-142 (1988)
1987
5		Lane A. Hemachandra: The Strong Exponential Hierarchy Collapses STOC 1987: 110-122
4		Abbas A. El Gamal, Lane A. Hemachandra, Itzhak Shperling, Victor K.-W. Wei: Using simulated annealing to design good codes. IEEE Transactions on Information Theory 33(1): 116-123 (1987)
1986
3		Juris Hartmanis, Lane A. Hemachandra: Complexity Classes Without Machines: On Complete Languages for UP. ICALP 1986: 123-135
2		Juris Hartmanis, Lane A. Hemachandra: On Sparse Oracles Separating Feasible Complexity Classes. STACS 1986: 321-333
1		Jin-yi Cai, Lane A. Hemachandra: The Boolean Hierarchy: Hardware over NP. Structure in Complexity Theory Conference 1986: 105-124

Coauthor Index

1 Martín Abadi [10]

2 Eric Allender [10] [18] [36] [42] [44]

3 Vikraman Arvind [50] [52]

4 Richard Beigel [14] [35] [151]

5 Russell Bent [108] [112]

6 Alina Beygelzimer [113]

7 Bernd Borchert [79] [122] [133]

8 Andrei Z. Broder [10]

9 Gerhard Buntrock [27] [57]

10 Jin-yi Cai [1] [7] [11] [13] [15] [21] [34] [48] [51] [106] [107] [131] [154] [171]

11 Venkatesan T. Chakaravarthy [154] [171]

12 David Eppstein [43]

13 Gábor Erdélyi [207] [212] [218]

14 Piotr Faliszewski [169] [175] [190] [191] [192] [194] [199] [208] [213] [216] [217] [219] [220] [221] [222]

15 Joan Feigenbaum [10]

16 Sophie Fischer [72]

17 Abbas El Gamal (Abbas A. El Gamal) [4]

18 William I. Gasarch [26] [56]

19 Christian Glaßer (Christian Glasser) [138] [140]

20 Judy Goldsmith [32] [39] [45]

21 Thomas Gundermann [7] [11]

22 Yenjo Han [50] [52] [59] [71] [78] [83]

23 Juris Hartmanis [2] [3] [6] [7] [8] [11] [20] [29]

24 Edith Hemaspaandra (Edith Spaan) [63] [86] [88] [90] [91] [92] [93] [95] [98] [100] [103] [111] [114] [115] [117] [118] [119] [120] [124] [127] [132] [141] [143] [150] [160] [161] [162] [163] [165] [168] [174] [176] [178] [184] [191] [192] [193] [199] [204] [206] [208] [209] [210] [211] [213] [217] [221]

25 Harald Hempel [88] [90] [92] [93] [95] [97] [98] [100] [103] [110] [114] [115] [116] [117] [118] [119] [120] [121] [132] [143] [144] [147] [151] [153] [158] [160] [162] [165] [168] [181]

26 Albrecht Hoene [16] [24] [26] [30] [31] [38] [53] [56] [60] [69] [74] [136]

27 Christopher Homan (Christopher M. Homan) [113] [172] [173] [180] [196] [198] [203] [205]

28 Gabriel Istrate [108] [112]

29 Sanjay Jain [19] [33] [49] [55]

30 Sudhir K. Jha [58] [70]

31 Z. Jiang [87]

32 Zhigen Jiang [67] [81] [84] [96] [126] [129]

33 Deborah Joseph [32]

34 Johannes Köbler [50] [52]

35 Sven Kosub [145] [173] [180] [196] [203] [205]

36 Dieter Kratsch [40] [64]

37 Kenneth Kunen [39] [45]

38 Antoni Lozano [50] [52]

39 Proshanto Mukherji [155] [159] [170]

40 Martin Mundhenk [50] [52]

41 Ashish V. Naik [66] [69] [76] [80]

42 Christopher Nasipak [99]

43 Arfst Nickelsen [147] [158] [181]

44 Mitsunori Ogihara (Mitsunori Ogiwara) [36] [37] [42] [46] [47] [50] [52] [54] [60] [65] [66] [69] [74] [76] [80] [85] [136] [142] [148] [154] [164] [171] [185]

45 Keith Parkins [99]

46 Kari Pasanen [139] [146] [186]

47 Stanislaw P. Radziszowski [161] [163] [206]

48 Kulathur S. Rajasethupathy [104]

49 Jörg Rothe [73] [79] [81] [82] [84] [86] [89] [91] [94] [96] [102] [105] [109] [113] [122] [123] [124] [125] [126] [127] [128] [129] [130] [133] [134] [135] [139] [146] [149] [174] [179] [182] [184] [186] [191] [193] [207] [208] [209] [210] [212] [213] [214] [217] [218] [221]

50 Roy S. Rubinstein [23] [41]

51 Steven Rudich [22]

52 Amitabh Saxena [179] [182] [214]

53 Michael Schear [108] [112]

54 Uwe Schöning [50] [52]

55 Alan L. Selman [60] [66] [69] [76] [80] [101]

56 Prasanna Sethupathy [104]

57 Vivian Sewelson [7] [11]

58 Itzhak Shperling [4]

59 Dirk Siefkes [16] [27] [30] [57]

60 Riccardo Silvestri [50] [52] [62] [68]

61 Holger Spakowski [207] [212] [218]

62 Till Tantau [155] [159] [170] [211]

63 Mayur Thakur [152] [156] [183] [195] [200]

64 Thomas Thierauf [50] [52] [59] [60] [69] [83]

65 James Tisdall [43]

66 Seinosuke Toda [65]

67 Leen Torenvliet [72] [75] [177] [197]

68 Rahul Tripathi [161] [163] [206]

69 Nikolai K. Vereshchagin [49] [55]

70 Jörg Vogel [151]

71 Jozef Vyskoc [48] [51]

72 Klaus W. Wagner [7] [11] [145] [180] [203]

73 Jie Wang [60] [69]

74 Osamu Watanabe [36] [42] [47] [81] [84] [96] [126] [129] [176] [211]

75 Gerd Wechsung [7] [11] [14] [17] [28] [35] [89] [94] [97] [106] [107] [110] [116] [121] [128] [131] [142] [148]

76 Victor K.-W. Wei (Victor K. Wei, Victor Keh-Wei Wei) [4]

77 Bülent Yener [43]

78 Paul Young [30] [32]

79 Mohammed Javeed Zaki (Mohammed J. Zaki) [164] [185]

80 Marius Zimand [77] [104] [111] [150] [164] [185]

Colors in the list of coauthors

1	Martín Abadi	[10]
2	Eric Allender	[10] [18] [36] [42] [44]
3	Vikraman Arvind	[50] [52]
4	Richard Beigel	[14] [35] [151]
5	Russell Bent	[108] [112]
6	Alina Beygelzimer	[113]
7	Bernd Borchert	[79] [122] [133]
8	Andrei Z. Broder	[10]
9	Gerhard Buntrock	[27] [57]
10	Jin-yi Cai	[1] [7] [11] [13] [15] [21] [34] [48] [51] [106] [107] [131] [154] [171]
11	Venkatesan T. Chakaravarthy	[154] [171]
12	David Eppstein	[43]
13	Gábor Erdélyi	[207] [212] [218]
14	Piotr Faliszewski	[169] [175] [190] [191] [192] [194] [199] [208] [213] [216] [217] [219] [220] [221] [222]
15	Joan Feigenbaum	[10]
16	Sophie Fischer	[72]
17	Abbas El Gamal (Abbas A. El Gamal)	[4]
18	William I. Gasarch	[26] [56]
19	Christian Glaßer (Christian Glasser)	[138] [140]
20	Judy Goldsmith	[32] [39] [45]
21	Thomas Gundermann	[7] [11]
22	Yenjo Han	[50] [52] [59] [71] [78] [83]
23	Juris Hartmanis	[2] [3] [6] [7] [8] [11] [20] [29]
24	Edith Hemaspaandra (Edith Spaan)	[63] [86] [88] [90] [91] [92] [93] [95] [98] [100] [103] [111] [114] [115] [117] [118] [119] [120] [124] [127] [132] [141] [143] [150] [160] [161] [162] [163] [165] [168] [174] [176] [178] [184] [191] [192] [193] [199] [204] [206] [208] [209] [210] [211] [213] [217] [221]
25	Harald Hempel	[88] [90] [92] [93] [95] [97] [98] [100] [103] [110] [114] [115] [116] [117] [118] [119] [120] [121] [132] [143] [144] [147] [151] [153] [158] [160] [162] [165] [168] [181]
26	Albrecht Hoene	[16] [24] [26] [30] [31] [38] [53] [56] [60] [69] [74] [136]
27	Christopher Homan (Christopher M. Homan)	[113] [172] [173] [180] [196] [198] [203] [205]
28	Gabriel Istrate	[108] [112]
29	Sanjay Jain	[19] [33] [49] [55]
30	Sudhir K. Jha	[58] [70]
31	Z. Jiang	[87]
32	Zhigen Jiang	[67] [81] [84] [96] [126] [129]
33	Deborah Joseph	[32]
34	Johannes Köbler	[50] [52]
35	Sven Kosub	[145] [173] [180] [196] [203] [205]
36	Dieter Kratsch	[40] [64]
37	Kenneth Kunen	[39] [45]
38	Antoni Lozano	[50] [52]
39	Proshanto Mukherji	[155] [159] [170]
40	Martin Mundhenk	[50] [52]
41	Ashish V. Naik	[66] [69] [76] [80]
42	Christopher Nasipak	[99]
43	Arfst Nickelsen	[147] [158] [181]
44	Mitsunori Ogihara (Mitsunori Ogiwara)	[36] [37] [42] [46] [47] [50] [52] [54] [60] [65] [66] [69] [74] [76] [80] [85] [136] [142] [148] [154] [164] [171] [185]
45	Keith Parkins	[99]
46	Kari Pasanen	[139] [146] [186]
47	Stanislaw P. Radziszowski	[161] [163] [206]
48	Kulathur S. Rajasethupathy	[104]
49	Jörg Rothe	[73] [79] [81] [82] [84] [86] [89] [91] [94] [96] [102] [105] [109] [113] [122] [123] [124] [125] [126] [127] [128] [129] [130] [133] [134] [135] [139] [146] [149] [174] [179] [182] [184] [186] [191] [193] [207] [208] [209] [210] [212] [213] [214] [217] [218] [221]
50	Roy S. Rubinstein	[23] [41]
51	Steven Rudich	[22]
52	Amitabh Saxena	[179] [182] [214]
53	Michael Schear	[108] [112]
54	Uwe Schöning	[50] [52]
55	Alan L. Selman	[60] [66] [69] [76] [80] [101]
56	Prasanna Sethupathy	[104]
57	Vivian Sewelson	[7] [11]
58	Itzhak Shperling	[4]
59	Dirk Siefkes	[16] [27] [30] [57]
60	Riccardo Silvestri	[50] [52] [62] [68]
61	Holger Spakowski	[207] [212] [218]
62	Till Tantau	[155] [159] [170] [211]
63	Mayur Thakur	[152] [156] [183] [195] [200]
64	Thomas Thierauf	[50] [52] [59] [60] [69] [83]
65	James Tisdall	[43]
66	Seinosuke Toda	[65]
67	Leen Torenvliet	[72] [75] [177] [197]
68	Rahul Tripathi	[161] [163] [206]
69	Nikolai K. Vereshchagin	[49] [55]
70	Jörg Vogel	[151]
71	Jozef Vyskoc	[48] [51]
72	Klaus W. Wagner	[7] [11] [145] [180] [203]
73	Jie Wang	[60] [69]
74	Osamu Watanabe	[36] [42] [47] [81] [84] [96] [126] [129] [176] [211]
75	Gerd Wechsung	[7] [11] [14] [17] [28] [35] [89] [94] [97] [106] [107] [110] [116] [121] [128] [131] [142] [148]
76	Victor K.-W. Wei (Victor K. Wei, Victor Keh-Wei Wei)	[4]
77	Bülent Yener	[43]
78	Paul Young	[30] [32]
79	Mohammed Javeed Zaki (Mohammed J. Zaki)	[164] [185]
80	Marius Zimand	[77] [104] [111] [150] [164] [185]