Reachability in K3,3-free Graphs and K5-free Graphs is in Unambiguous Log-Space
Thomas Thierauf and Fabian Wagner
Technical Report, ECCC TR09-029, 2009.
BibTeX
Planar Graph Isomorphism is in Log-Space
Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf and Fabian Wagner
Technical Report, arXiv:0809.2319v1 , 2008.
To appear at 24th Computational Complexity Conference (CCC), 2009.
The Isomorphism Problem for Planar 3-Connected Graphs is in Unambiguous Logspace
Thomas Thierauf and Fabian Wagner
In Proceedings of 25th Symposium on Theoretical Aspects of Computer Science (STACS),
http://www.stacs-conf.org/publications.php, 633-644, 2008.
An earlier version appeared as
Technical Report, ECCC TR07-068, 2007.
BibTeX
The Quantum Query Complexity of the Determinant.
Sebastian Dörn and Thomas Thierauf
Information Processing Letters,
to appear, 2008.
Search for $k$ Elements via Quantum Walk
Sebastian Dörn and Thomas Thierauf
Submitted for publication, 2008.
The Polynomially Bounded Perfect Matching Problem is in NC2
Manindra Agrawal, Thanh Minh Hoang and Thomas Thierauf
24th Symposium on Theoretical Aspects of Computer Science (STACS),
Springer Verlag, LNCS 4349, 489-499, 2007.
BibTeX
The Quantum Complexity of Group Testing
Sebastian Dörn and Thomas Thierauf
In Proceedings of the 34th International Conference on
Current Trends in Theory and Practice of Computer Science (SOFSEM).
Springer-Verlag, LNCS 4910, 506-518, 2008.
BibTeX
The Quantum Query Complexity of Algebraic Properties
Sebastian Dörn and Thomas Thierauf
In Proceedings of the
16th International Symposium on Fundamentals of Computation Theory (FCT),
Springer-Verlag, LNCS 4639, 250-260, 2007.
BibTeX
On the Bipartite Unique Perfect Matching Problem
Thanh Minh Hoang, Meena Mahajan, and Thomas Thierauf
33rd International Colloquium on Automata, Languages and Programming (ICALP),
Springer-Verlag, LNCS 4052, 453-464, 2006.
BibTeX
The Complexity of the Inertia and some Closure Properties of GapL
Thanh Minh Hoang and Thomas Thierauf
20th Computational Complexity Conference (CCC),
IEEE Computer Society, 28 - 37, 2005.
BibTeX
On Closure Properties of GapL
Thanh Minh Hoang and Thomas Thierauf
ECCC Report TR04-24, 2004.
BibTeX
On the Minimal Polynomial of a Matrix
Thanh Minh Hoang and Thomas Thierauf
International Journal of Foundations of Computer Science 15 (1), 89-105, 2004
BibTeX
The Complexity of the Characteristic and the Minimal Polynomial
Thanh Minh Hoang and Thomas Thierauf
Theoretical Computer Science 295, 205-222, 2003.
BibTeX
The Complexity of the Inertia
Thanh Minh Hoang and Thomas Thierauf
22nd Foundations of Software Technology and Theoretical Computer Science (FSTTCS),
Springer Verlag, LNCS 2556, 206-217, 2002.
BibTeX
The Complexity of the Minimal Polynomial
Thanh Minh Hoang and Thomas Thierauf
26th International Symposium on Mathematical Foundations of Computer Science (MFCS)
Springer Verlag, LNCS 2136, 408-420, 2001.
BibTeX
The Satisfiability Problem for
Probabilistic Ordered Branching Programs
Manindra Agrawal and Thomas Thierauf
Theory of Computing Systems (TOCS) 34, 471-487, 2001.
BibTeX
The Formula Isomorphism Problem
Manindra Agrawal and Thomas Thierauf
SIAM Journal on Computing 30(3), 990-1009, 2000.
BibTeX
The Complexity of Verifying the Characteristic Polynomial and Testing Similarity
Thanh Minh Hoang and Thomas Thierauf
15th IEEE Conference on Computational Complexity (CCC), 87-95, 2000.
BibTeX
The Computational Complexity of Equivalence and Isomorphism Problems
Thomas Thierauf
Habilitation Thesis.
Springer LNCS series, volume 1852, August 2000.
Nonrelativizing Separations
Harry Buhrman, Lance Fortnow, and Thomas Thierauf
13th IEEE Conference on Computational Complexity (CCC), 8-12, 1998.
BibTeX
The Isomorphism Problem for Read-Once Branching Programs and Arithmetic Circuits
Thomas Thierauf
Chicago Journal of Theoretical Computer Science
Article 1 of Volume 1998, 10 March 1998.
BibTeX
Complements of Multivalued Functions
Steve Fenner, Fred Green, Steve Homer, Alan Selman, Thomas Thierauf, Heribert Vollmer
Chicago Journal of Theoretical Computer Science.
Article 3 of Volume 1999, 19 March 1999.
On Functions Computable with Parallel Queries to NP
Harry Buhrman, Jim Kadin, and Thomas Thierauf
Theory of Computing Systems (TOCS) 31 (1), 77-92, 1998.
Formerly
Mathematical System Theory (MST).
Threshold Computation and Cryptographic Security
Yenjo Han, Lane A. Hemaspaandra, and Thomas Thierauf
SIAM Journal on Computing 26(1), 59-78, 1997.
Pinpointing Computation with Modular Queries in the Boolean Hierarchy
Manindra Agrawal, Richard Beigel, and Thomas Thierauf
Foundation of Software Technology and Theoretical Computer Science 16 (FST&TCS) ,
Springer Verlag, LNCS 1180, 322-334, 1996.
The Complexity of Generating and Checking Proofs of Membership
Harry Buhrman and Thomas Thierauf
Symposium on Theoretical Aspects of Computer Science (STACS) 96,
Springer-Verlag, LNCS 1046, 75-86, 1996.
On the Correlation of Symmetric Functions
Jin-Yi Cai, Frederic Green, and Thomas Thierauf
Mathematical System Theory (MST) 29, 245-258, 1996.
Information from Nonadaptive Queries to NP
Yenjo Han and Thomas Thierauf
Information and Computation 128(2), 119-125, 1996.
On Sets Bounded Truth-Table Reducible to P-selective Sets
Thomas Thierauf, Seinosuke Toda, and Osamu Watanabe
Informatique Theorique et Applications/Theoretical Informatics and Applications 30(2), 135-154, 1996.
On Closure Properties of #P in the Context of PF(#P)
Mitsunori Ogihara, Thomas Thierauf, Seinosuke Toda, and Osamu Watanabe
Journal of Computer and System Sciences (JCSS) 53(2), 171-179, 1996.
Nondeterministically Selective Sets.
L. Hemaspaandra, A. Hoene, A. Naik, M. Ogihara, A. Selman, T. Thierauf, and J. Wang
Journal on Foundations of Computer Science 6(4)
,
403-416, 1995.
A Note on SpanP Functions
Meena Mahajan, Thomas Thierauf, and Vinodchandran N.V.
Information Processing Letters (IPL) 51, 7-10, 1994.
On Closure Properties of GapP
Thomas Thierauf, Seinosuke Toda, and Osamu Watanabe
Journal of Computational Complexity 4, 242-261, 1994.
Complexity-Restricted Advice Functions
Johannes Köbler and Thomas Thierauf
SIAM Journal on Computing 23(2), 261-275, 1994.
Reductions to Sets of Low Information Content
V.Arvind, Y. Han, L. Hemachandra, J. Köbler, A. Lozano, M. Mundhenk, A. Ogiwara, U. Schöning, R. Silvestri, and T. Thierauf
Recent Developments in Complexity Theory,
Cambridge University Press, 1993.