6 citations · 12 across the 7 of their papers we have counts for
33 papers · 1 filter
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…
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…
Overhead-Free Computation, DCFLs, and CFLs
Lane A. Hemaspaandra, Proshanto Mukherji, Till Tantau
We study Turing machines that are allowed absolutely no space overhead. The only work space the machines have, beyond the fixed amount of memory implicit in their finite-state cont…