1.4k citations
- D. Merritt28 · h 78
- D. Axon21 · h 52
- C. O’Dea2 profiles20 · h 55
- J. Kastner2 profiles20 · h 41
- S. Baum3 profiles19 · h 62
- C. Lousto17 · h 82
- Y. Zlochower17 · h 49
- B. Krishnan3 profiles16 · h 78
- M. Smith2 profiles16 · h 43
- N. Mavalvala3 profiles16 · h 100
- D. Hammer3 profiles15 · h 47
- R. Taylor4 profiles15 · h 74
- University of RochesterUS33 papers
- Space Telescope Science InstituteUS27 papers
- California Institute of TechnologyUS26 papers
- Pennsylvania State UniversityUS26 papers
- Goddard Space Flight CenterUS21 papers
- Massachusetts Institute of TechnologyUS20 papers
- Max Planck Institute for Gravitational PhysicsDE20 papers
- National Astronomical Observatory of JapanJP19 papers
- Australian National UniversityAU18 papers
- University of MichiganUS18 papers
- University of SouthamptonGB17 papers
- Washington State UniversityUS17 papers
7 papers · 1 filter
Minimization for Generalized Boolean Formulas
Edith Hemaspaandra, Henning Schnoor
The minimization problem for propositional formulas is an important optimization problem in the second level of the polynomial hierarchy. In general, the problem is Sigma-2-complet…
Dichotomy Results for Fixed Point Counting in Boolean Dynamical Systems
Christopher M. Homan, Sven Kosub
We present dichotomy theorems regarding the computational complexity of counting fixed points in boolean (discrete) dynamical systems, i.e., finite discrete dynamical systems over…
Generalized Modal Satisfiability
Edith Hemaspaandra, Henning Schnoor, Ilka Schnoor
It is well known that modal satisfiability is PSPACE-complete (Ladner 1977). However, the complexity may decrease if we restrict the set of propositional operators used. Note that…
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…
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…