On-Line Available Papers

Linear Matroid Intersection is in quasi-NC
Rohit Gurjar, Thomas Thierauf
49th ACM Symposium on Theory of Computing (STOC), 2017.
Earlier version:
Technical Report, ECCC TR16-182, 2016
BibTeX

Parallel Algorithms for Perfect Matching
Steve Fenner, Rohit Gurjar, Thomas Thierauf
ACM SIGACT News 48 (1), March 2017

Bipartite Perfect Matching is in quasi-NC
Steve Fenner, Rohit Gurjar, Thomas Thierauf
48th ACM Symposium on Theory of Computing (STOC), 2016.
BibTeX
Earlier version:
Technical Report, ECCC TR15-177, 2015, and arXiv:1601.06319, 2016.

Identity Testing for the Sum of Read-Once Oblivious Arithmetic Branching Programs
Rohit Gurjar, Arpita Korwar, Nitin Saxena, Thomas Thierauf
computational complexity, pp 1-46, 2016.
BibTeX
Earlier version:
30th Conference on Computational Complexity (CCC), 2015.
Technical Report, ECCC TR14-158, 2014.

Game Values and Computational Complexity: An Analysis via Black-White Combinatorial Games
Stephen Fenner, Daniel Grier, Jochen Messner, Luke Schaeffer, and Thomas Thierauf
26th International Symposium on Algorithms and Computation (ISAAC), Lecture Notes in Computer Science 9472, Springer, 689-699, 2015.
BibTeX
Earlier version:
Technical Report, ECCC TR15-021, 2015.

Counting the Number of Perfect Matchings in K5-free Graphs
Simon Straub, Thomas Thierauf, Fabian Wagner
Theory of Computing Systems, Volume 59 (3), pp 416-439, 2016.
BibTeX
Earlier versions:
29th Conference on Computational Complexity (CCC), IEEE Computer Society, 66-77, 2014.
Technical Report, ECCC TR14-079, 2014.

On Two-level Poset Games
Stephen Fenner, Rohit Gurjar, Arpita Korwar, and Thomas Thierauf
Technical Report, ECCC TR13-019, 2013.
BibTeX

Exact Perfect Matching in Complete Graphs
Rohit Gurjar, Arpita Korwar, Jochen Messner, and Thomas Thierauf
Technical Report, ECCC TR13-112, 2013.
BibTeX

Planarizing Gadgets for Perfect Matching do not Exist
Rohit Gurjar, Arpita Korwar, Jochen Messner, Simon Straub, and Thomas Thierauf
ACM Transactions on Computation Theory (TOCT), Volume 8 (4), pp 1-17, 2016.
BibTeX
Earlier versions:
37th International Symposium on Mathematical Foundations of Computer Science (MFCS), Springer-Verlag, Lecture Notes in Computer Science 7464, pp. 478-490, 2012.
Technical Report, ECCC TR11-148, 2011.

Reachability in K3,3-free Graphs and K5-free Graphs is in Unambiguous Logspace
Thomas Thierauf and Fabian Wagner
Chicago Journal of Theoretical Computer Science (CJTCS) 2, 2014.
BibTeX
Earlier versions:
In Proceedings of the 17th International Symposium on Fundamentals of Computation Theory (FCT), Springer-Verlag, LNCS 5699, 323-334, 2009.
Technical Report, ECCC TR09-029, 2009.

A Kolmogorov Complexity Proof of the Lovász Local Lemma for Satisfiability
Jochen Messner and Thomas Thierauf
Theoretical Computer Science, Vol. 461, pp. 55-64, 2012.
BibTeX
Earlier versions:
17th Annual International Computing and Combinatorics Conference (COCOON), 2011.
Technical Report, ECCC TR11-018, 2011.

Isomorphism for K3,3-free Graphs and K5-free Graphs in Log-Space
Samir Datta, Prajakta Nimbhorkar, Thomas Thierauf, and Fabian Wagner
29th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2009. Leibniz International Proceedings in Informatics (LIPIcs)
A full version appeared as Technical Report, ECCC TR10-050, 2010.

The Complexity of the Inertia
Thanh Minh Hoang and Thomas Thierauf
computational complexity 19 (4), 559-580, 2010.
BibTeX
Earlier versions:
20th Computational Complexity Conference (CCC), IEEE Computer Society, 28 - 37, 2005.
22nd Foundations of Software Technology and Theoretical Computer Science (FST&TCS), Springer Verlag, LNCS 2556, 206-217, 2002.

Planar Graph Isomorphism is in Log-Space
Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, and Fabian Wagner
In Proceedings of 24th IEEE Conference on Computational Complexity (CCC), 203-214, 2009.
BibTeX
Earlier versions appeared as Technical Reports ECCC TR09-052, 2009, and arXiv:0809.2319v1 , 2008.

The Isomorphism Problem for Planar 3-Connected Graphs is in Unambiguous Logspace
Thomas Thierauf and Fabian Wagner
Theory of Computing Systems 47 (3), 655 - 673, 2010.
BibTeX
Earlier versions appeared in Proceedings of 25th Symposium on Theoretical Aspects of Computer Science (STACS), http://www.stacs-conf.org/publications.php, 633-644, 2008 and Technical Report, ECCC TR07-068, 2007.

Search for k Elements via Quantum Walk
Sebastian Dörn and Thomas Thierauf
Information Processing Letters 110 (22), 975-978, 2010.
BibTeX

The Quantum Query Complexity of the Determinant
Sebastian Dörn and Thomas Thierauf
Information Processing Letters 109 (6), 325-328, 2009.
BibTeX

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.



Back to homepage