6 citations · 12 across the 7 of their papers we have counts for
37 papers
Cluster Computing and the Power of Edge Recognition
Lane A. Hemaspaandra, Christopher M. Homan, Sven Kosub
We study the robustness--the invariance under definition changes--of the cluster class CL#P [HHKW05]. This class contains each #P function that is computed by a balanced Turing mac…
Open Questions in the Theory of Semifeasible Computation
Piotr Faliszewski, Lane A. Hemaspaandra
The study of semifeasible algorithms was initiated by Selman's work a quarter of century ago [Sel79,Sel81,Sel82]. Informally put, this research stream studies the power of those se…
The Complexity of Kings
Edith Hemaspaandra, Lane A. Hemaspaandra, Osamu Watanabe
A king in a directed graph is a node from which each node in the graph can be reached via paths of length at most two. There is a broad literature on tournaments (completely orient…
Dichotomy for Voting Systems
Edith Hemaspaandra, Lane A. Hemaspaandra
Scoring protocols are a broad class of voting systems. Each is defined by a vector , , of integers such that each voter contribu…
P-Selectivity, Immunity, and the Power of One Bit
Lane A. Hemaspaandra, Leen Torenvliet
We prove that P-sel, the class of all P-selective sets, is EXP-immune, but is not EXP/1-immune. That is, we prove that some infinite P-selective set has no infinite EXP-time subset…
Algebraic Properties for Selector Functions
Lane A. Hemaspaandra, Harald Hempel, Arfst Nickelsen
The nondeterministic advice complexity of the P-selective sets is known to be exactly linear. Regarding the deterministic advice complexity of the P-selective sets--i.e., the amoun…