Please note: This is a beta version of the new dblp website.
You can find the classic dblp view of this page here.
You can find the classic dblp view of this page here.
Thomas Thierauf
2010 – today
- 2013
[i18]Stephen A. Fenner, Rohit Gurjar, Arpita Korwar, Thomas Thierauf: On Two-Level Poset Games. Electronic Colloquium on Computational Complexity (ECCC) 20: 19 (2013)- [i17]Rohit Gurjar, Arpita Korwar, Jochen Messner, Thomas Thierauf: Exact Perfect Matching in Complete Graphs. Electronic Colloquium on Computational Complexity (ECCC) 20: 112 (2013)
- 2012
- [j21]Jochen Messner, Thomas Thierauf: A Kolmogorov complexity proof of the Lovász Local Lemma for satisfiability. Theor. Comput. Sci. 461: 55-64 (2012)
- [c33]Rohit Gurjar, Arpita Korwar, Jochen Messner, Simon Straub, Thomas Thierauf: Planarizing Gadgets for Perfect Matching Do Not Exist. MFCS 2012: 478-490
- [i16]Manindra Agrawal, Thomas Thierauf, Christopher Umans: Algebraic and Combinatorial Methods in Computational Complexity (Dagstuhl Seminar 12421). Dagstuhl Reports 2(10): 60-78 (2012)
- 2011
- [c32]Jochen Messner, Thomas Thierauf: A Kolmogorov Complexity Proof of the Lovász Local Lemma for Satisfiability. COCOON 2011: 168-179
- [i15]Jochen Messner, Thomas Thierauf: A Kolmogorov Complexity Proof of the Lovász Local Lemma for Satisfiability. Electronic Colloquium on Computational Complexity (ECCC) 18: 18 (2011)
- [i14]Rohit Gurjar, Arpita Korwar, Jochen Messner, Simon Straub, Thomas Thierauf: Planarizing Gadgets for Perfect Matching do not Exist. Electronic Colloquium on Computational Complexity (ECCC) 18: 148 (2011)
- 2010
- [j20]Thanh Minh Hoang, Thomas Thierauf: The Complexity of the Inertia. Computational Complexity 19(4): 559-580 (2010)
- [j19]Sebastian Dörn, Thomas Thierauf: A note on the search for k elements via quantum walk. Inf. Process. Lett. 110(22): 975-978 (2010)
- [j18]Thomas Thierauf, Fabian Wagner: The Isomorphism Problem for Planar 3-Connected Graphs Is in Unambiguous Logspace. Theory Comput. Syst. 47(3): 655-673 (2010)
- [i13]Samir Datta, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner: Graph Isomorphism for K{3, 3}-free and K5-free graphs is in Log-space. Electronic Colloquium on Computational Complexity (ECCC) 17: 50 (2010)
2000 – 2009
- 2009
- [j17]Sebastian Dörn, Thomas Thierauf: The quantum query complexity of the determinant. Inf. Process. Lett. 109(6): 325-328 (2009)
- [c31]Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner: Planar Graph Isomorphism is in Log-Space. IEEE Conference on Computational Complexity 2009: 203-214
- [c30]Thomas Thierauf, Fabian Wagner: Reachability in K3, 3-Free Graphs and K5-Free Graphs Is in Unambiguous Log-Space. FCT 2009: 323-334
- [c29]Samir Datta, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner: Graph Isomorphism for K_{3, 3}-free and K_5-free graphs is in Log-space. FSTTCS 2009: 145-156
- [i12]Fabian Wagner, Thomas Thierauf: Reachability in K_{3, 3}-free Graphs and K_5-free Graphs is in Unambiguous Log-Space. Electronic Colloquium on Computational Complexity (ECCC) 16: 29 (2009)
- [i11]Fabian Wagner, Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf: Planar Graph Isomorphism is in Log-space. Electronic Colloquium on Computational Complexity (ECCC) 16: 52 (2009)
- 2008
- [c28]
- [c27]Thomas Thierauf, Fabian Wagner: The Isomorphism Problem for Planar 3-Connected Graphs is in Unambiguous Logspace. STACS 2008: 633-644
- [e2]Manindra Agrawal, Harry Buhrman, Lance Fortnow, Thomas Thierauf (Eds.): Algebraic Methods in Computational Complexity, 07.10. - 12.10.2007. Dagstuhl Seminar Proceedings 07411, Internationales Begegnungs- und Forschungszentrum fuer Informatik (IBFI), Schloss Dagstuhl, Germany 2008
- [i10]Thomas Thierauf, Fabian Wagner: The Isomorphism Problem for Planar 3-Connected Graphs is in Unambiguous Logspace. CoRR abs/0802.2825 (2008)
- [i9]Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner: A Log-space Algorithm for Canonization of Planar Graphs. CoRR abs/0809.2319 (2008)
- 2007
- [c26]Manindra Agrawal, Harry Buhrman, Lance Fortnow, Thomas Thierauf: 07411 Executive Summary -- Algebraic Methods in Computational Complexity. Algebraic Methods in Computational Complexity 2007
- [c25]Manindra Agrawal, Harry Buhrman, Lance Fortnow, Thomas Thierauf: 07411 Abstracts Collection -- Algebraic Methods in Computational Complexity. Algebraic Methods in Computational Complexity 2007
- [c24]Sebastian Dörn, Thomas Thierauf: The Quantum Query Complexity of Algebraic Properties. FCT 2007: 250-260
- [c23]Manindra Agrawal, Thanh Minh Hoang, Thomas Thierauf: The Polynomially Bounded Perfect Matching Problem Is in NC 2. STACS 2007: 489-499
- [i8]Thomas Thierauf, Fabian Wagner: The Isomorphism Problem for Planar 3-Connected Graphs is in Unambiguous Logspace. Electronic Colloquium on Computational Complexity (ECCC) 14(068) (2007)
- 2006
- [c22]Thanh Minh Hoang, Meena Mahajan, Thomas Thierauf: On the Bipartite Unique Perfect Matching Problem. ICALP (1) 2006: 453-464
- [i7]Manindra Agrawal, Thanh Minh Hoang, Thomas Thierauf: The polynomially bounded perfect matching problem is in NC^2. Electronic Colloquium on Computational Complexity (ECCC) 13(129) (2006)
- 2005
- [c21]Thanh Minh Hoang, Thomas Thierauf: The Complexity of the Inertia and Some Closure Properties of GapL. IEEE Conference on Computational Complexity 2005: 28-37
- [e1]Harry Buhrman, Lance Fortnow, Thomas Thierauf (Eds.): Algebraic Methods in Computational Complexity, 10.-15. October 2004. Dagstuhl Seminar Proceedings 04421, IBFI, Schloss Dagstuhl, Germany 2005
- 2004
- [j16]Thanh Minh Hoang, Thomas Thierauf: On The Minimal Polynomial Of A Matrix. Int. J. Found. Comput. Sci. 15(1): 89-105 (2004)
- [j15]Thanh Minh Hoang, Thomas Thierauf: Erratum: On The Minimal Polynomial Of A Matrix. Int. J. Found. Comput. Sci. 15(4): 685 (2004)
- [c20]Harry Buhrman, Lance Fortnow, Thomas Thierauf: 04421 Abstracts Collection - Algebraic Methods in Computational Complexity. Algebraic Methods in Computational Complexity 2004
- [i6]Thomas Thierauf, Thanh Minh Hoang: On Closure Properties of GapL. Electronic Colloquium on Computational Complexity (ECCC)(024) (2004)
- 2003
- [j14]Thanh Minh Hoang, Thomas Thierauf: The complexity of the characteristic and the minimal polynomial. Theor. Comput. Sci. 295: 205-222 (2003)
- 2002
- [c19]
- [c18]
- 2001
- [c17]
- [i5]Thanh Minh Hoang, Thomas Thierauf: The Complexity of the Minimal Polynomial. Electronic Colloquium on Computational Complexity (ECCC) 8(28) (2001)
- 2000
- [b2]Thomas Thierauf: The Computational Complexity of Equivalence and Isomorphism Problems. Lecture Notes in Computer Science 1852, Springer 2000, ISBN 3-540-41032-5
- [j13]Manindra Agrawal, Thomas Thierauf: The Formula Isomorphism Problem. SIAM J. Comput. 30(3): 990-1009 (2000)
- [c16]Thanh Minh Hoang, Thomas Thierauf: The Complexity of Verifying the Characteristic Polynomial and Testing Similarity. IEEE Conference on Computational Complexity 2000: 87-
1990 – 1999
- 1999
- [j12]Stephen A. Fenner, Frederic Green, Steven Homer, Alan L. Selman, Thomas Thierauf, Heribert Vollmer: Complements of Multivalued Functions. Chicago J. Theor. Comput. Sci. 1999 (1999)
- 1998
- [j11]Thomas Thierauf: The Isomorphism Problem for Read-Once Branching Programs and Arithmetic Circuits. Chicago J. Theor. Comput. Sci. 1998 (1998)
- [j10]Harry Buhrman, Jim Kadin, Thomas Thierauf: Functions Computable with Nonadaptive Queries to NP. Theory Comput. Syst. 31(1): 77-92 (1998)
- [c15]Harry Buhrman, Lance Fortnow, Thomas Thierauf: Nonrelativizing Separations. IEEE Conference on Computational Complexity 1998: 8-12
- [c14]Manindra Agrawal, Thomas Thierauf: The Satisfiability Problem for Probabilistic Ordered Branching Programs. IEEE Conference on Computational Complexity 1998: 81-
- 1997
- [j9]Yenjo Han, Lane A. Hemaspaandra, Thomas Thierauf: Threshold Computation and Cryptographic Security. SIAM J. Comput. 26(1): 59-78 (1997)
- [i4]Manindra Agrawal, Thomas Thierauf: The Satisfiability Problem for Probabilistic Ordered Branching Programs. Electronic Colloquium on Computational Complexity (ECCC) 4(60) (1997)
- 1996
- [j8]Yenjo Han, Thomas Thierauf: Restricted Information from Nonadaptive Queries to NP. Inf. Comput. 128(2): 119-125 (1996)
- [j7]Thomas Thierauf, Seinosuke Toda, Osamu Watanabe: On Sets Bounded Truth-Table Reducible to P-Selective Sets. ITA 30(2): 135-154 (1996)
- [j6]Mitsunori Ogihara, Thomas Thierauf, Seinosuke Toda, Osamu Watanabe: On Closure Properties of #P in the Context of PF ° #P. J. Comput. Syst. Sci. 53(2): 171-179 (1996)
- [j5]Jin-yi Cai, Frederic Green, Thomas Thierauf: On the Correlation of Symmetric Functions. Mathematical Systems Theory 29(3): 245-258 (1996)
- [c13]Stephen A. Fenner, Frederic Green, Steven Homer, Alan L. Selman, Thomas Thierauf, Heribert Vollmer: Complements of Multivalued Functions. IEEE Conference on Computational Complexity 1996: 260-269
- [c12]
- [c11]Manindra Agrawal, Richard Beigel, Thomas Thierauf: Pinpointing Computation with Modular Queries in the Boolean Hierarchy. FSTTCS 1996: 322-334
- [c10]Harry Buhrman, Thomas Thierauf: The Complexity of Generating and Checking Proffs of Membership. STACS 1996: 75-86
- [i3]Manindra Agrawal, Richard Beigel, Thomas Thierauf: Modulo Information from Nonadaptive Queries to NP. Electronic Colloquium on Computational Complexity (ECCC) 3(1) (1996)
- [i2]Manindra Agrawal, Thomas Thierauf: The Boolean Isomorphism Problem. Electronic Colloquium on Computational Complexity (ECCC) 3(32) (1996)
- [i1]Thomas Thierauf: The Isomorphismproblem for One-Time-Only Branching Programs. Electronic Colloquium on Computational Complexity (ECCC) 3(40) (1996)
- 1995
- [j4]Lane A. Hemaspaandra, Albrecht Hoene, Ashish V. Naik, Mitsunori Ogihara, Alan L. Selman, Thomas Thierauf, Jie Wang: Nondeterministically Selective Sets. Int. J. Found. Comput. Sci. 6(4): 403-416 (1995)
- [c9]Yenjo Han, Thomas Thierauf: Restricted Information from Nonadaptive Queries to NP. Structure in Complexity Theory Conference 1995: 206-213
- 1994
- [j3]Thomas Thierauf, Seinosuke Toda, Osamu Watanabe: On Closure Properties of GapP. Computational Complexity 4: 242-261 (1994)
- [j2]Meena Mahajan, Thomas Thierauf, N. V. Vinodchandran: A Note on SpanP Functions. Inf. Process. Lett. 51(1): 7-10 (1994)
- [j1]Johannes Köbler, Thomas Thierauf: Complexity-Restricted Advice Functions. SIAM J. Comput. 23(2): 261-275 (1994)
- [c8]Harry Buhrman, Jim Kadin, Thomas Thierauf: On Functions Computable with Nonadaptive Queries to NP. Structure in Complexity Theory Conference 1994: 43-52
- [c7]Thomas Thierauf, Seinosuke Toda, Osamu Watanabe: On Sets Bounded Truth-Table Reducible to P-selective Sets. STACS 1994: 427-438
- 1993
- [c6]Mitsunori Ogiwara, Thomas Thierauf, Seinosuke Toda, Osamu Watanabe: On Closure Properties of #P in the Context of PF°#P. Structure in Complexity Theory Conference 1993: 139-146
- [c5]Lane A. Hemachandra, Albrecht Hoene, Mitsunori Ogiwara, Alan L. Selman, Thomas Thierauf, Jie Wang: Selectivity. ICCI 1993: 55-59
- [c4]Yenjo Han, Lane A. Hemaspaandra, Thomas Thierauf: Threshold Computation and Cryptographic Security. ISAAC 1993: 230-239
- 1992
- [c3]Vikraman Arvind, Yenjo Han, Lane A. Hemachandra, Johannes Köbler, Antoni Lozano, Martin Mundhenk, Mitsunori Ogiwara, Uwe Schöning, Riccardo Silvestri, Thomas Thierauf: Reductions to Sets of Low Information Content. Complexity Theory: Current Research 1992: 1-46
- [c2]Vikraman Arvind, Yenjo Han, Lane A. Hemachandra, Johannes Köbler, Antoni Lozano, Martin Mundhenk, Mitsunori Ogiwara, Uwe Schöning, Riccardo Silvestri, Thomas Thierauf: Reductions to Sets of Low Information Content. ICALP 1992: 162-173
- 1990
- [b1]Thomas Thierauf: NP-uniforme Komplexitätsklassen. Universität Ulm 1990, pp. 1-92
- [c1]Johannes Köbler, Thomas Thierauf: Complexity Classes with Advice. Structure in Complexity Theory Conference 1990: 305-315
Coauthor Index
data released under the ODC-BY 1.0 license. See also our legal information page
last updated on 2013-10-02 11:05 CEST by the dblp team