On-Line Available Papers

Lower Bounds for Constant Depth Arithmetic Circuits: The LST-Bound
Lecture Notes, 2022.

Planar Graph Isomorphism is in Log-Space
Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, and Fabian Wagner
ACM Transactions on Computation Theory (TOCT), Vol. 14(8), 1-33, 2022.

Earlier versions:
Proceedings of 24th IEEE Conference on Computational Complexity (CCC), 203-214, 2009.
Technical Reports ECCC TR09-052, 2009, and arXiv:0809.2319v1 , 2008.

The Complexity of Poset Games
Stephen Fenner, Daniel Grier, Rohit Gurjar, Arpita Korwar, and Thomas Thierauf
Journal of Graph Algorithms and Applications 26(1): 1-14 (2022)

A Largish Sum-of-Squares Implies Circuit Hardness and Derandomization
Pranjal Dutta, Nitin Saxena, Thomas Thierauf
12th Innovations in Theoretical Computer Science (ITCS), LIPIcs - Vol. 185, 23:1-23:21, 2021.

Impossibility of Derandomizing the Isolation Lemma for all Families
Manindra Agrawal, Rohit Gurjar, Thomas Thierauf
Technical Report, ECCC TR20-098, 2020.

Factorization of Polynomials Given by Arithmetic Branching Programs
Amit Sinhababu, Thomas Thierauf
Computational Complexity 30(2), 15, 2021.

Earlier versions:
35th Conference on Computational Complexity (CCC), 33:1--33:19, 2020.
Technical Report, ECCC TR20-077, 2020.

Lower bounds on the sum of 25th-powers of univariates lead to complete derandomization of PIT
Pranjal Dutta, Nitin Saxena, Thomas Thierauf
Technical Report, ECCC TR20-039, 2020.

Depth-2 QAC circuits cannot simulate quantum parity
Stephen Fenner, Daniel Grier, Daniel Padé, Thomas Thierauf
Technical Report, arXiv:2005.12169, 2020.

The Complexity of Regex Crosswords
Stephen Fenner, Daniel Padé, Thomas Thierauf
Information and Computation , Vol. 286, Article 104777, 2022.

Parallel Algorithms for Bipartite Perfect Matching
Steve Fenner, Rohit Gurjar, Thomas Thierauf
Communications of the ACM Research Highlights, Vol. 62, No. 3, 109-115, 2019.

Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces
Rohit Gurjar, Thomas Thierauf, Nisheeth K. Vishnoi
SIAM Journal on Computing, Vol. 50(2), 636-661, 2021.

Earlier versions:
45rd International Colloquium on Automata, Languages and Programming (ICALP), 74:1-74:14, 2018.
Technical Report, ECCC TR17-127, 2017 and arXiv:1708.02222 , 2017.

Linear Matroid Intersection is in quasi-NC
Rohit Gurjar, Thomas Thierauf
Computational Complexity, Vol. 29(2), Article 9, 2020.

Earlier versions:
49th ACM Symposium on Theory of Computing (STOC), 821-830, 2017.
Technical Report, ECCC TR16-182, 2016.

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

Bipartite Perfect Matching is in quasi-NC
Steve Fenner, Rohit Gurjar, Thomas Thierauf
SIAM Journal on Computing 50(3), STOC special issue, 218-235, 2021.
48th ACM Symposium on Theory of Computing (STOC), 754-763, 2016.
BibTeX

Earlier versions:
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 26(4), pp 835-880, 2017.
BibTeX

Earlier versions:
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.

Exact Perfect Matching in Complete Graphs
Rohit Gurjar, Arpita Korwar, Jochen Messner, and Thomas Thierauf
ACM Transactions on Computation Theory (TOCT) 9(2), 8:1-8:20, 2017.

Earlier versions:
Technical Report, ECCC TR13-112, 2013.

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 14:1-14: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.

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

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.

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:
Proceedings of 25th Symposium on Theoretical Aspects of Computer Science (STACS), http://www.stacs-conf.org/publications.php, 633-644, 2008.
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

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

Earlier versions:
8th Annual International Computing and Combinatorics Conference (COCOON),
Springer Verlag, LNCS 2387, 37-46, 2002.

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 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.





Impressum
Datenschutz