6 citations · 12 across the 7 of their papers we have counts for
3 papers · 1 filter
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…
Complexity Results in Graph Reconstruction
Edith Hemaspaandra, Lane A. Hemaspaandra, Stanislaw P. Radziszowski +1
We investigate the relative complexity of the graph isomorphism problem (GI) and problems related to the reconstruction of a graph from its vertex-deleted or edge-deleted subgraphs…