default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDThomas Thierauf
Person information
- affiliation: Aalen University of Applied Sciences, Germany
- affiliation: University of Ulm, Germany
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
[j36]Pranjal Dutta, Nitin Saxena, Thomas Thierauf:
Weighted Sum-of-Squares Lower Bounds for Univariate Polynomials Imply VP ≠q VNP. Comput. Complex. 33(1): 3 (2024)- [c39]Pranjal Dutta, Amit Sinhababu, Thomas Thierauf:
Derandomizing Multivariate Polynomial Factoring for Low Degree Factors. APPROX/RANDOM 2024: 75:1-75:20 - 2022
- [j35]Stephen A. Fenner, Daniel Padé, Thomas Thierauf:
The complexity of regex crosswords. Inf. Comput. 286: 104777 (2022) - [j34]Stephen A. Fenner, Daniel Grier, Rohit Gurjar, Arpita Korwar, Thomas Thierauf:
The Complexity of Poset Games. J. Graph Algorithms Appl. 26(1): 1-14 (2022) - [j33]Samir Datta
, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner:
Planar Graph Isomorphism Is in Log-Space. ACM Trans. Comput. Theory 14(2): 8:1-8:33 (2022) - 2021
- [j32]Amit Sinhababu, Thomas Thierauf:
Factorization of Polynomials Given by Arithmetic Branching Programs. Comput. Complex. 30(2): 15 (2021) - [j31]Rohit Gurjar, Thomas Thierauf, Nisheeth K. Vishnoi:
Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces. SIAM J. Comput. 50(2): 636-661 (2021) - [j30]Stephen A. Fenner, Rohit Gurjar, Thomas Thierauf:
Bipartite Perfect Matching is in Quasi-NC. SIAM J. Comput. 50(3) (2021) - [c38]Pranjal Dutta, Nitin Saxena, Thomas Thierauf:
A Largish Sum-Of-Squares Implies Circuit Hardness and Derandomization. ITCS 2021: 23:1-23:21 - 2020
- [j29]Rohit Gurjar, Thomas Thierauf:
Linear Matroid Intersection is in Quasi-NC. Comput. Complex. 29(2): 9 (2020) - [c37]Amit Sinhababu, Thomas Thierauf:
Factorization of Polynomials Given By Arithmetic Branching Programs. CCC 2020: 33:1-33:19 - [i39]Daniel Padé, Stephen A. Fenner, Daniel Grier, Thomas Thierauf:
Depth-2 QAC circuits cannot simulate quantum parity. CoRR abs/2005.12169 (2020) - [i38]Manindra Agrawal, Rohit Gurjar, Thomas Thierauf:
Impossibility of Derandomizing the Isolation Lemma for all Families. Electron. Colloquium Comput. Complex. TR20 (2020) - [i37]Pranjal Dutta, Nitin Saxena, Thomas Thierauf:
Lower bounds on the sum of 25th-powers of univariates lead to complete derandomization of PIT. Electron. Colloquium Comput. Complex. TR20 (2020) - [i36]Amit Sinhababu, Thomas Thierauf:
Factorization of Polynomials Given by Arithmetic Branching Programs. Electron. Colloquium Comput. Complex. TR20 (2020)
2010 – 2019
- 2019
- [j28]Stephen A. Fenner, Rohit Gurjar, Thomas Thierauf:
A deterministic parallel algorithm for bipartite perfect matching. Commun. ACM 62(3): 109-115 (2019) - 2018
- [c36]Rohit Gurjar, Thomas Thierauf, Nisheeth K. Vishnoi:
Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces. ICALP 2018: 74:1-74:14 - 2017
- [j27]Rohit Gurjar, Arpita Korwar, Nitin Saxena, Thomas Thierauf:
Deterministic Identity Testing for Sum of Read-Once Oblivious Arithmetic Branching Programs. Comput. Complex. 26(4): 835-880 (2017) - [j26]Stephen A. Fenner, Rohit Gurjar, Thomas Thierauf:
Guest Column: Parallel Algorithms for Perfect Matching. SIGACT News 48(1): 102-109 (2017) - [j25]Rohit Gurjar, Arpita Korwar, Jochen Messner, Thomas Thierauf:
Exact Perfect Matching in Complete Graphs. ACM Trans. Comput. Theory 9(2): 8:1-8:20 (2017) - [c35]Rohit Gurjar, Thomas Thierauf:
Linear matroid intersection is in quasi-NC. STOC 2017: 821-830 - [i35]Rohit Gurjar, Thomas Thierauf, Nisheeth K. Vishnoi:
Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces. CoRR abs/1708.02222 (2017) - [i34]Rohit Gurjar, Thomas Thierauf, Nisheeth K. Vishnoi:
Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces. Electron. Colloquium Comput. Complex. TR17 (2017) - 2016
- [j24]Simon Straub, Thomas Thierauf, Fabian Wagner:
Counting the Number of Perfect Matchings in K 5-Free Graphs. Theory Comput. Syst. 59(3): 416-439 (2016) - [j23]Rohit Gurjar, Arpita Korwar, Jochen Messner, Simon Straub, Thomas Thierauf:
Planarizing Gadgets for Perfect Matching Do Not Exist. ACM Trans. Comput. Theory 8(4): 14:1-14:15 (2016) - [c34]Stephen A. Fenner, Rohit Gurjar, Thomas Thierauf:
Bipartite perfect matching is in quasi-NC. STOC 2016: 754-763 - [i33]Stephen A. Fenner, Rohit Gurjar, Thomas Thierauf:
Bipartite Perfect Matching is in quasi-NC. CoRR abs/1601.06319 (2016) - [i32]Valentine Kabanets, Thomas Thierauf, Jacobo Torán, Christopher Umans:
Algebraic Methods in Computational Complexity (Dagstuhl Seminar 16411). Dagstuhl Reports 6(10): 13-32 (2016) - [i31]Rohit Gurjar, Thomas Thierauf:
Linear Matroid Intersection is in quasi-NC. Electron. Colloquium Comput. Complex. TR16 (2016) - 2015
- [c33]Rohit Gurjar, Arpita Korwar, Nitin Saxena, Thomas Thierauf:
Deterministic Identity Testing for Sum of Read-once Oblivious Arithmetic Branching Programs. CCC 2015: 323-346 - [c32]Stephen A. Fenner, Daniel Grier, Jochen Messner, Luke Schaeffer, Thomas Thierauf:
Game Values and Computational Complexity: An Analysis via Black-White Combinatorial Games. ISAAC 2015: 689-699 - [i30]Stephen A. Fenner, Daniel Grier, Jochen Messner, Luke Schaeffer, Thomas Thierauf:
Game Values and Computational Complexity: An Analysis via Black-White Combinatorial Games. Electron. Colloquium Comput. Complex. TR15 (2015) - [i29]Stephen A. Fenner, Rohit Gurjar, Thomas Thierauf:
Bipartite Perfect Matching is in quasi-NC. Electron. Colloquium Comput. Complex. TR15 (2015) - 2014
- [j22]Thomas Thierauf, Fabian Wagner:
Reachability in K{3, 3}-free and K5-free Graphs is in Unambiguous Logspace. Chic. J. Theor. Comput. Sci. 2014 (2014) - [c31]Simon Straub, Thomas Thierauf, Fabian Wagner:
Counting the Number of Perfect Matchings in K5-Free Graphs. CCC 2014: 66-77 - [i28]Rohit Gurjar, Arpita Korwar, Nitin Saxena, Thomas Thierauf:
Deterministic Identity Testing for Sum of Read Once ABPs. CoRR abs/1411.7341 (2014) - [i27]Manindra Agrawal, Valentine Kabanets, Thomas Thierauf, Christopher Umans:
Algebra in Computational Complexity (Dagstuhl Seminar 14391). Dagstuhl Reports 4(9): 85-105 (2014) - [i26]Rohit Gurjar, Arpita Korwar, Nitin Saxena, Thomas Thierauf:
Deterministic Identity Testing for Sum of Read Once ABPs. Electron. Colloquium Comput. Complex. TR14 (2014) - [i25]Simon Straub, Thomas Thierauf, Fabian Wagner:
Counting the Number of Perfect Matchings in K5-free Graphs. Electron. Colloquium Comput. Complex. TR14 (2014) - 2013
- [i24]Stephen A. Fenner, Rohit Gurjar, Arpita Korwar, Thomas Thierauf:
On Two-Level Poset Games. Electron. Colloquium Comput. Complex. TR13 (2013) - [i23]Rohit Gurjar, Arpita Korwar, Jochen Messner, Thomas Thierauf:
Exact Perfect Matching in Complete Graphs. Electron. Colloquium Comput. Complex. TR13 (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) - [c30]Rohit Gurjar, Arpita Korwar, Jochen Messner, Simon Straub, Thomas Thierauf:
Planarizing Gadgets for Perfect Matching Do Not Exist. MFCS 2012: 478-490 - [i22]Manindra Agrawal, Thomas Thierauf, Christopher Umans:
Algebraic and Combinatorial Methods in Computational Complexity (Dagstuhl Seminar 12421). Dagstuhl Reports 2(10): 60-78 (2012) - 2011
- [c29]Jochen Messner, Thomas Thierauf:
A Kolmogorov Complexity Proof of the Lovász Local Lemma for Satisfiability. COCOON 2011: 168-179 - [i21]Rohit Gurjar, Arpita Korwar, Jochen Messner, Simon Straub, Thomas Thierauf:
Planarizing Gadgets for Perfect Matching do not Exist. Electron. Colloquium Comput. Complex. TR11 (2011) - [i20]Jochen Messner, Thomas Thierauf:
A Kolmogorov Complexity Proof of the Lovász Local Lemma for Satisfiability. Electron. Colloquium Comput. Complex. TR11 (2011) - 2010
- [j20]Thanh Minh Hoang, Thomas Thierauf:
The Complexity of the Inertia. Comput. Complex. 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) - [i19]Samir Datta, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner:
Graph Isomorphism for K3,3-free and K5-free graphs is in Log-space. Electron. Colloquium Comput. Complex. TR10 (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) - [c28]Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner:
Planar Graph Isomorphism is in Log-Space. CCC 2009: 203-214 - [c27]Thomas Thierauf, Fabian Wagner:
Reachability in K3, 3-Free Graphs and K5-Free Graphs Is in Unambiguous Log-Space. FCT 2009: 323-334 - [c26]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 - [e3]Manindra Agrawal, Lance Fortnow, Thomas Thierauf, Christopher Umans:
Algebraic Methods in Computational Complexity, 11.10. - 16.10.2009. Dagstuhl Seminar Proceedings 09421, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Germany 2009 [contents] - [i18]Manindra Agrawal, Lance Fortnow, Thomas Thierauf, Christopher Umans:
09421 Abstracts Collection - Algebraic Methods in Computational Complexity. Algebraic Methods in Computational Complexity 2009 - [i17]Manindra Agrawal, Lance Fortnow, Thomas Thierauf, Christopher Umans:
09421 Executive Summary - Algebraic Methods in Computational Complexity. Algebraic Methods in Computational Complexity 2009 - [i16]Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner:
Planar Graph Isomorphism is in Log-Space. Algebraic Methods in Computational Complexity 2009 - [i15]Fabian Wagner, Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf:
Planar Graph Isomorphism is in Log-space. Electron. Colloquium Comput. Complex. TR09 (2009) - [i14]Fabian Wagner, Thomas Thierauf:
Reachability in K3,3-free Graphs and K5-free Graphs is in Unambiguous Log-Space. Electron. Colloquium Comput. Complex. TR09 (2009) - 2008
- [c25]Sebastian Dörn, Thomas Thierauf:
The Quantum Complexity of Group Testing. SOFSEM 2008: 506-518 - [c24]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:
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 [contents] - [i13]Thomas Thierauf, Fabian Wagner:
The Isomorphism Problem for Planar 3-Connected Graphs is in Unambiguous Logspace. CoRR abs/0802.2825 (2008) - [i12]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
- [c23]Sebastian Dörn, Thomas Thierauf:
The Quantum Query Complexity of Algebraic Properties. FCT 2007: 250-260 - [c22]Manindra Agrawal, Thanh Minh Hoang, Thomas Thierauf:
The Polynomially Bounded Perfect Matching Problem Is in NC 2. STACS 2007: 489-499 - [i11]Manindra Agrawal, Harry Buhrman, Lance Fortnow, Thomas Thierauf:
07411 Executive Summary -- Algebraic Methods in Computational Complexity. Algebraic Methods in Computational Complexity 2007 - [i10]Manindra Agrawal, Harry Buhrman, Lance Fortnow, Thomas Thierauf:
07411 Abstracts Collection -- Algebraic Methods in Computational Complexity. Algebraic Methods in Computational Complexity 2007 - [i9]Thomas Thierauf, Fabian Wagner:
The Isomorphism Problem for Planar 3-Connected Graphs is in Unambiguous Logspace. Electron. Colloquium Comput. Complex. TR07 (2007) - 2006
- [c21]Thanh Minh Hoang, Meena Mahajan, Thomas Thierauf:
On the Bipartite Unique Perfect Matching Problem. ICALP (1) 2006: 453-464 - [i8]Manindra Agrawal, Thanh Minh Hoang, Thomas Thierauf:
The polynomially bounded perfect matching problem is in NC^2. Electron. Colloquium Comput. Complex. TR06 (2006) - 2005
- [c20]Thanh Minh Hoang, Thomas Thierauf:
The Complexity of the Inertia and Some Closure Properties of GapL. CCC 2005: 28-37 - [e1]Harry Buhrman, Lance Fortnow, Thomas Thierauf:
Algebraic Methods in Computational Complexity, 10.-15. October 2004. Dagstuhl Seminar Proceedings 04421, IBFI, Schloss Dagstuhl, Germany 2005 [contents] - 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) - [i7]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. Electron. Colloquium Comput. Complex. TR04 (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]Thanh Minh Hoang, Thomas Thierauf:
On the Minimal Polynomial of a Matrix. COCOON 2002: 37-46 - [c18]Thanh Minh Hoang, Thomas Thierauf:
The Complexity of the Inertia. FSTTCS 2002: 206-217 - 2001
- [c17]Thanh Minh Hoang, Thomas Thierauf:
The Complexity of the Minimal Polynomial. MFCS 2001: 408-420 - [i5]Thanh Minh Hoang, Thomas Thierauf:
The Complexity of the Minimal Polynomial. Electron. Colloquium Comput. Complex. TR01 (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. CCC 2000: 87-
1990 – 1999
- 1999
- [j12]Stephen A. Fenner, Frederic Green, Steven Homer, Alan L. Selman, Thomas Thierauf, Heribert Vollmer:
Complements of Multivalued Functions. Chic. J. Theor. Comput. Sci. 1999 (1999) - 1998
- [j11]Thomas Thierauf:
The Isomorphism Problem for Read-Once Branching Programs and Arithmetic Circuits. Chic. 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. CCC 1998: 8-12 - [c14]Manindra Agrawal, Thomas Thierauf:
The Satisfiability Problem for Probabilistic Ordered Branching Programs. CCC 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. Electron. Colloquium Comput. Complex. TR97 (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. RAIRO Theor. Informatics Appl. 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. Math. Syst. 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. CCC 1996: 260-269 - [c12]Manindra Agrawal, Thomas Thierauf:
The Boolean Isomorphism Problem. FOCS 1996: 422-430 - [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. Electron. Colloquium Comput. Complex. TR96 (1996) - [i2]Manindra Agrawal, Thomas Thierauf:
The Boolean Isomorphism Problem. Electron. Colloquium Comput. Complex. TR96 (1996) - [i1]Thomas Thierauf:
The Isomorphismproblem for One-Time-Only Branching Programs. Electron. Colloquium Comput. Complex. TR96 (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. SCT 1995: 206-213 - 1994
- [j3]Thomas Thierauf, Seinosuke Toda, Osamu Watanabe:
On Closure Properties of GapP. Comput. Complex. 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. SCT 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. SCT 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. University of Ulm, Germany, 1990, pp. 1-92 - [c1]Johannes Köbler, Thomas Thierauf:
Complexity Classes with Advice. SCT 1990: 305-315
Coauthor Index