6 citations · 10 across the 5 of their papers we have counts for
6 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…
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…
All Superlinear Inverse Schemes are coNP-Hard
Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel
How hard is it to invert NP-problems? We show that all superlinearly certified inverses of NP problems are coNP-hard. To do so, we develop a novel proof technique that builds diago…