List of Publications
Publications in Scientific Journals
- All Superlinear Inverse Schemes Are coNP-hard.
- E. Hemaspaandra, L. Hemaspaandra and H. Hempel.
- Theoretical Computer Science A,
345, 324-358, 2005.
- Extending Downward Collapse from 1-versus-2 Queries to
m-versus-m+1 Queries.
- E. Hemaspaandra, L. Hemaspaandra, and H. Hempel.
- SIAM Journal on Computing, 34, 1352-1369, 2005.
- Algebraic Properties for Selector Functions.
- L. Hemaspaandra, H. Hempel, and A. Nickelsen.
- SIAM Journal on Computing, 33, 1309-1337, 2004.
- P-Immune Sets with Holes Lack Self-Reducibility Properties.
- L. Hemaspaandra and H. Hempel.
- Theoretical Computer Science A,
302, 457-466, 2003.
- On Claw-free Asteroidal Triple-free graphs.
- H. Hempel and D. Kratsch.
- Discrete Applied Mathematics, 121, 155-180, 2002.
- Optimal Series-Parallel Tradeoffs for Reducing a
Function to Its Own Graph.
- R. Beigel, L. Hemaspaandra, H. Hempel and J. Vogel.
- Information and Computation, 173, 123-131, 2002.
- The operators min and max on the Polynomial Hierarchy.
- H. Hempel and G. Wechsung.
- International Journal of Foundations of Computer Science,
11 (2), 315-342, 2000.
- Self-Specifying Machines.
- L. Hemaspaandra, H. Hempel, and G. Wechsung.
- International Journal of Foundations of Computer Science, 10 (3),
263-276, 1999.
- Query Order.
- L. Hemaspaandra, H. Hempel, and G. Wechsung.
- SIAM Journal on Computing, 28, 637-651, 1999.
- A Downward Collapse within the Polynomial Hierarchy.
- E. Hemaspaandra, L. Hemaspaandra, and H. Hempel.
- SIAM Journal on Computing, 28, 383-393, 1999.
- RSN1-tt(NP)
Distinguishes Robust Many-One and Turing Completeness.
- E. Hemaspaandra, L. Hemaspaandra, and H. Hempel.
- Theory of Computing Systems, 31, 307-325, 1998.
- Query Order and the Polynomial Hierarchy.
- E. Hemaspaandra, L. Hemaspaandra, and H. Hempel.
- Journal of Universal Computer Science, 4, 574-588, 1998.
Publications in Conference Proceedings
- Inverse Problems Have Inverse Complexity.
- T. Berg and H. Hempel.
- In Proceedings of the
5th IFIP International Conference on Theoretical Computer Science (TCS 2008),
Springer-Verlag Science and Business Media, September 2008, to appear.
- Persistent Computations.
- H. Hempel and M. Kimmritz.
- In Proceedings of the
13th International Conference on Implementation and Application of Automata (CIAA 2008),
Springer-Verlag Lecture Notes in Computer Science 5148, 171-180, July 2008.
- Approximating Alternative Solutions.
- M. Krüger and H. Hempel.
- In Proceedings of the
14th Annual International Computing and Combinatorics Conference (COCOON 2008),
Springer-Verlag Lecture Notes in Computer Science 5092, 203-214, June 2008.
- Inverse HAMILTONIAN CYCLE and Inverse 3-D MATCHING are coNP-Complete.
- M. Krüger and H. Hempel.
- In Proceedings of the
17th International Symposium on Algorithms and Computation (ISAAC 2006),
Springer-Verlag Lecture Notes in Computer Science 4288, 243-252, December 2006 .
- All Superlinear Inverse Schemes are coNP-Hard.
- E. Hemaspaandra, L. Hemaspaandra, and H. Hempel.
- In Proceedings of the
29th International Symposium on
Mathematical Foundations of Computer Science (MFCS'04),
Springer-Verlag Lecture Notes in Computer Science 3153, 368-379, August 2004.
- All Superlinear Inverse Schemes are coNP-Hard.
- E. Hemaspaandra, L. Hemaspaandra, and H. Hempel.
- In Proceedings of the
29th International Symposium on
Mathematical Foundations of Computer Science (MFCS'04),
Springer-Verlag Lecture Notes in Computer Science 3153, 368-379, August 2004.
- On Functions and Relations.
- A. Große and H. Hempel.
- In Proceedings of the
Forth International Conference
"Discrete Mathematics and Theoretical Computer Science" (DMTCS'03),
Springer-Verlag Lecture Notes in Computer Science 2731, 181-192, July 2003.
- P-Immune Sets with Holes Lack Self-Reducibility Properties.
- L. Hemaspaandra and H. Hempel.
- In Proceedings of the
Third International Conference
"Discrete Mathematics and Theoretical Computer Science" (DMTCS'01),
Springer-Verlag DMTCS Series, 115-124, July 2001.
- Algebraic Properties for P-Selectivity.
- L. Hemaspaandra, H. Hempel, and A.Nickelsen.
- In Proceedings of the
7th Annual International Computing and Combinatorics Conference (COCOON '01),
Springer-Verlag Lecture Notes in Computer Sciences 2108, 49-58,
August 2001.
- On Claw-free Asteroidal Triple-free graphs.
- H. Hempel and
D. Kratsch.
- In Proceedings of the
25th International Workshop on Graph-Theoretic
Concepts in Computer Science (WG'99),
Springer-Verlag Lecture Notes in Computer Sciences 1665, 377-390,
June 1999.
- Extending Downward Collapse from 1-versus-2 Queries to j-versus-j+1 Queries.
- E. Hemaspaandra,
L. Hemaspaandra, and H. Hempel.
- In Proceedings of the
16th Symposium on Theoretical Aspects of Computer Science (STACS'99),
Springer-Verlag Lecture Notes in Computer Sciences 1563, 270-280,
March 1999.
- Downward Collapse from a Weaker Hypothesis.
- E. Hemaspaandra, L. Hemaspaandra, and H. Hempel.
- In Proceedings of the
6th Italian Conference on Theoretical Computer Science (ICTCS'98),
253-264, World Scientific Press,
November 1998.
- Query Order in the Polynomial Hierarchy.
- E. Hemaspaandra, L. Hemaspaandra, and H. Hempel.
- In Proceedings of the
11th International Symposium on Fundamentals of
Computation Theory (FCT'97).
Springer-Verlag Lecture Notes in Computer Sciences 1279, 222-232,
September 1997.
- RSN1-tt(NP)
Distinguishes Robust Many-One and Turing Completeness.
- E. Hemaspaandra, L. Hemaspaandra, and H. Hempel.
- In Proceedings of the
Third Italian Conference on Algorithms and Complexity (CIAC'97).
Springer-Verlag Lecture Notes in Computer Sciences 1203, 49-60,
March 1997.
- The Operators min and max on the Polynomial Hierarchy.
- H. Hempel and
G. Wechsung .
- In Proceedings of the
14th Symposium on Theoretical Aspects of Computer Science (STACS'97).
Springer-Verlag Lecture Notes in Computer Sciences 1200, 93-104,
February 1997.
- A Downward Translation in the Polynomial Hierarchy.
- E. Hemaspaandra, L. Hemaspaandra, and H. Hempel.
- In Proceedings of the
14th Symposium on Theoretical Aspects of Computer Science (STACS'97).
Springer-Verlag Lecture Notes in Computer Sciences 1200, 319-328,
February 1997.
Other Publications
- Randomized Algorithms and Complexity Theory.
- H. Hempel.
- Journal of
Universal Computer Science, 12, 746-761, August 2006.
- Wechsung in Jena.
- H. Hempel.
- Ein Sammelband mit Erinnerungen an das Wirken von Gerd Wechsung an der alma mater jenensis, Jena, February 2004.
- On Functions in Complexity Theory.
(Full Version)
- H. Hempel.
- Habilitation Thesis, Fakultät für Mathematik und Informatik,
Friedrich-Schiller-Universität Jena, July 2003.
- Boolean Hierarchies -
- On Collapse Properties and Query Order.
(Extended Abstract in German)
- H. Hempel.
- In Ausgezeichnete Informatikdissertationen 1998.
Teubner, 62-71, 1999.
- Boolean Hierarchies -
- On Collapse Properties and Query Order.
(Full Version)
- H. Hempel.
- PhD Thesis, Fakultät für Mathematik und Informatik,
Friedrich-Schiller-Universität Jena, August 1998.
- What's Up with Downward Collapse:
- Using the Easy-Hard Technique to Link Boolean and Polynomial Hierarchy Collapses.
- E. Hemaspaandra, L. Hemaspaandra, and H. Hempel.
- SIGACT News, 29, 10-22, September 1998.
- An Introduction to Query Order.
- E. Hemaspaandra, L. Hemaspaandra, and H. Hempel.
- Bulletin of the EATCS, 63, 93-107, October 1997.
Technical Reports
- All Superlinear Inverse Schemes are coNP-Hard.
- E. Hemaspaandra, L. Hemaspaandra, and H. Hempel.
- Technical Report TR 841, Department of Computer Science,
University of Rochester, July 2004.
- On Functions and Relations.
- A. Große and H. Hempel.
- Technical Report Math/Inf/01/03, Institut für Informatik,
Friedrich-Schiller-Universität Jena, January 2003.
- Algebraic Properties for Deterministic and Nondeterministic
Selectivity.
- L. Hemaspaandra, H. Hempel, and A. Nickelsen.
- Technical Report TR 778, Department of Computer Science,
University of Rochester, May 2002.
- Using the No-Search Easy-Hard Technique for Downward Collapse.
- E. Hemaspaandra, L. Hemaspaandra, and H. Hempel.
- Technical Report TR 752, Department of Computer Science,
University of Rochester, June 2001.
- Algebraic Properties for Deterministic Selectivity.
- L. Hemaspaandra, H. Hempel, and A. Nickelsen.
- Technical Report TR 746, Department of Computer Science,
University of Rochester, April 2001.
- P-Immune Sets with Holes Lack Self-Reducibility Properties.
- L. Hemaspaandra and H. Hempel.
- Technical Report TR 742, Department of Computer Science,
University of Rochester, February 2001.
- Algebraic Properties for P-Selectivity.
- L. Hemaspaandra and H. Hempel.
- Technical Report TR 730, Department of Computer Science,
University of Rochester, April 2000.
- A Note on Query Order: Solving the Missing Case.
- H. Hempel.
- Technical Report Math/Inf/99/15, Institut für Informatik,
Friedrich-Schiller-Universität Jena, April 1999.
- On Claw-free Asteroidal Triple-free Graphs.
- H. Hempel and D. Kratsch.
- Technical Report Math/Inf/99/09, Institut für Informatik,
Friedrich-Schiller-Universität Jena, March 1999.
- Optimal Separations for Parallel versus Sequential Self-Checking:
- Parallelism Can Exponentially Increase Self-Checking Cost.
- L. Hemaspaandra, H. Hempel, and Jörg Vogel.
- Technical Report TR 691, Department of Computer Science,
University of Rochester, May 1998.
- What's Up with Downward Collapse:
- Using the Easy-Hard Technique to Link Boolean and Polynomial Hierarchy Collapses.
- E. Hemaspaandra, L. Hemaspaandra, and H. Hempel.
- Technical Report TR 682, Department of Computer Science,
University of Rochester, February 1998.
- Downward Collapse from a Weaker Hypothesis.
- E. Hemaspaandra, L. Hemaspaandra, and H. Hempel.
- Technical Report TR 681, Department of Computer Science,
University of Rochester, February 1998.
- An Introduction to Query Order.
- E. Hemaspaandra, L. Hemaspaandra, and H. Hempel.
- Technical Report TR 665, Department of Computer Science,
University of Rochester, August 1997.
- Translating Equality Downwards.
- E. Hemaspaandra, L. Hemaspaandra, and H. Hempel.
- Technical Report TR 657, Department of Computer Science,
University of Rochester, April 1997.
- Self-Specifying Machines.
- L. Hemaspaandra, H. Hempel, and G. Wechsung.
- Technical Report TR 654, Department of Computer Science,
University of Rochester, April 1997.
- On the Power of #P Reductions.
- H. Hempel and G. Wechsung.
- Technical Report Math/Inf/97/02, Institut für Informatik,
Friedrich-Schiller-Universität Jena, January 1997.
- RSN1-tt(NP)
Distinguishes Robust Many-One and Turing Completeness.
- E. Hemaspaandra, L. Hemaspaandra, and H. Hempel.
- Technical Report TR 635, Department of Computer Science,
University of Rochester, September 1996.
- Query Order in the Polynomial Hierarchy.
- E. Hemaspaandra, L. Hemaspaandra, and H. Hempel.
- Technical Report TR 634, Department of Computer Science,
University of Rochester, September 1996 (revised August 1997).
- A Downward Translation in the Polynomial Hierarchy.
- E. Hemaspaandra, L. Hemaspaandra, and H. Hempel.
- Technical Report Math/Inf/96/18, Institut für Informatik,
Friedrich-Schiller-Universität Jena, July 1996.
- An Upward Separation in the Polynomial Hierarchy.
- E. Hemaspaandra, L. Hemaspaandra, and H. Hempel.
- Technical Report Math/Inf/96/15, Institut für Informatik,
Friedrich-Schiller-Universität Jena, June 1996.
- The Operators min and max on the Polynomial Time Hierarchy.
- H. Hempel and G. Wechsung.
- Technical Report Math/Inf/96/8, Institut für Informatik,
Friedrich-Schiller-Universität Jena,
April 1996 (revised December 1997).
- Query Order and Self-Specifying Machines.
- L. Hemaspaandra, H. Hempel, and G. Wechsung.
- Technical Report Math/Inf/95/13, Institut für Informatik,
Friedrich-Schiller-Universität Jena, October 1995.
Harald Hempel,
email to: hempel at informatik.uni-jena.de