Harald Hempel

Affiliations:
  • University of Jena, Germany


According to our database1, Harald Hempel authored at least 33 papers between 1997 and 2012.

Collaborative distances:
  • Dijkstra number2 of four.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2012
Inverse Hamiltonian Cycle and inverse 3Dimensional Matching are coNP-complete.
Theor. Comput. Sci., 2012

2009
Aspects of Persistent Computations.
Int. J. Found. Comput. Sci., 2009

Reoptimization of Traveling Salesperson Problems: Changing Single Edge-Weights.
Proceedings of the Language and Automata Theory and Applications, 2009

2008
Persistent Computations of Turing Machines.
Proceedings of the Implementation and Applications of Automata, 2008

Inverse Problems Have Inverse Complexity.
Proceedings of the Fifth IFIP International Conference On Theoretical Computer Science, 2008

Approximating Alternative Solutions.
Proceedings of the Computing and Combinatorics, 14th Annual International Conference, 2008

2006
Randomized Algorithms and Complexity Theory.
J. Univers. Comput. Sci., 2006

Inverse HAMILTONIAN CYCLE and Inverse 3-D MATCHING Are coNP-Complete.
Proceedings of the Algorithms and Computation, 17th International Symposium, 2006

2005
All superlinear inverse schemes are coNP-hard.
Theor. Comput. Sci., 2005

Extending Downward Collapse from 1-versus-2 Queries to m-versus-m + 1 Queries.
SIAM J. Comput., 2005

2004
Algebraic Properties for Selector Functions.
SIAM J. Comput., 2004

2003
P-immune sets with holes lack self-reducibility properties.
Theor. Comput. Sci., 2003

On Functions and Relations.
Proceedings of the Discrete Mathematics and Theoretical Computer Science, 2003

2002
Optimal Series-Parallel Trade-offs for Reducing a Function to Its Own Graph.
Inf. Comput., 2002

On claw-free asteroidal triple-free graphs.
Discret. Appl. Math., 2002

2001
Using the No-Search Easy-Hard Technique for Downward Collapse
CoRR, 2001

Algebraic Properties for P-Selectivity.
Proceedings of the Computing and Combinatorics, 7th Annual International Conference, 2001

1999
Self-Specifying Machines.
Int. J. Found. Comput. Sci., 1999

Translating Equality Downwards
CoRR, 1999

R<sub>1-tt</sub><sup>SN</sup>(NP) Distinguishes Robust Many-One and Turing Completeness
CoRR, 1999

Extending Downward Collapse from 1-versus-2 Queries to j-versus-j+1 Queries.
Proceedings of the STACS 99, 1999

1998
What's up with downward collapse: using the easy-hard technique to link Boolean and polynomial hierarchy collapses.
SIGACT News, 1998

Query Order.
SIAM J. Comput., 1998

A Downward Collapse within the Polynomial Hierarchy.
SIAM J. Comput., 1998

R<sup><i>S N</i></sup><sub>1-tt</sub> (NP) Distinguishes Robust Many-One and Turing Completeness.
Theory Comput. Syst., 1998

Query Order and the Polynomial Hierarchy.
J. Univers. Comput. Sci., 1998

Downward Collapse from a Weaker Hypothesis
CoRR, 1998

Boolean hierarchies - on collapse properties and query order.
PhD thesis, 1998

1997
The Operators min and max on the Polynomial Hierarchy
Electron. Colloquium Comput. Complex., 1997

An Introduction to Query Order.
Bull. EATCS, 1997

A Downward Translation in the Polynomial Hierarchy.
Proceedings of the STACS 97, 14th Annual Symposium on Theoretical Aspects of Computer Science, Lübeck, Germany, February 27, 1997

Query Order in the Polynomial Hierarchy.
Proceedings of the Fundamentals of Computation Theory, 11th International Symposium, 1997

R<sup>SN</sup><sub>1-tt</sub>(NP) Distinguishes Robust Many-One and Turing Completeness.
Proceedings of the Algorithms and Complexity, Third Italian Conference, 1997


  Loading...