11 citations · 18 across the 6 of their papers we have counts for
4 papers · 2 filters
Isomorphic Implication
Michael Bauland, Edith Hemaspaandra
We study the isomorphic implication problem for Boolean constraints. We show that this is a natural analog of the subgraph isomorphism problem. We prove that, depending on the set…
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…
Dichotomy Theorems for Alternation-Bounded Quantified Boolean Formulas
Edith Hemaspaandra
In 1978, Schaefer proved his famous dichotomy theorem for generalized satisfiability problems. He defined an infinite number of propositional satisfiability problems, showed that a…