Thomas Thierauf

ORCID

Publication Activity (10 Years)

Years Active: 1990-2024
Publications (10 Years): 32

Top Venues

Electron. Colloquium Comput. Complex.

CoRR

Comput. Complex.

ACM Trans. Comput. Theory

University of Ulm, Germany (PHD)

Education History

University of Ulm, Germany

PHD

Publications

Pranjal Dutta, Nitin Saxena, Thomas Thierauf
Weighted Sum-of-Squares Lower Bounds for Univariate Polynomials Imply VP ≠q VNP. Comput. Complex. 33 (1) (2024)
Stephen A. Fenner, Daniel Padé, Thomas Thierauf
The complexity of regex crosswords. Inf. Comput. 286 (2022)
Stephen A. Fenner, Daniel Grier, Rohit Gurjar, Arpita Korwar, Thomas Thierauf
The Complexity of Poset Games. J. Graph Algorithms Appl. 26 (1) (2022)
Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner
Planar Graph Isomorphism Is in Log-Space. ACM Trans. Comput. Theory 14 (2) (2022)
Amit Sinhababu, Thomas Thierauf
Factorization of Polynomials Given by Arithmetic Branching Programs. Comput. Complex. 30 (2) (2021)
Stephen A. Fenner, Rohit Gurjar, Thomas Thierauf
Bipartite Perfect Matching is in Quasi-NC. SIAM J. Comput. 50 (3) (2021)
Pranjal Dutta, Nitin Saxena, Thomas Thierauf
A Largish Sum-Of-Squares Implies Circuit Hardness and Derandomization. ITCS (2021)
Rohit Gurjar, Thomas Thierauf, Nisheeth K. Vishnoi
Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces. SIAM J. Comput. 50 (2) (2021)
Rohit Gurjar, Thomas Thierauf
Linear Matroid Intersection is in Quasi-NC. Comput. Complex. 29 (2) (2020)
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. 27 (2020)
Amit Sinhababu, Thomas Thierauf
Factorization of Polynomials Given by Arithmetic Branching Programs. Electron. Colloquium Comput. Complex. 27 (2020)
Amit Sinhababu, Thomas Thierauf
Factorization of Polynomials Given By Arithmetic Branching Programs. Computational Complexity Conference (2020)
Manindra Agrawal, Rohit Gurjar, Thomas Thierauf
Impossibility of Derandomizing the Isolation Lemma for all Families. Electron. Colloquium Comput. Complex. 27 (2020)
Daniel Padé, Stephen A. Fenner, Daniel Grier, Thomas Thierauf
Depth-2 QAC circuits cannot simulate quantum parity. CoRR (2020)
Stephen A. Fenner, Rohit Gurjar, Thomas Thierauf
A deterministic parallel algorithm for bipartite perfect matching. Commun. ACM 62 (3) (2019)
Rohit Gurjar, Thomas Thierauf, Nisheeth K. Vishnoi
Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces. ICALP (2018)
Rohit Gurjar, Thomas Thierauf, Nisheeth K. Vishnoi
Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces. Electron. Colloquium Comput. Complex. 24 (2017)
Stephen A. Fenner, Rohit Gurjar, Thomas Thierauf
Guest Column: Parallel Algorithms for Perfect Matching. SIGACT News 48 (1) (2017)
Rohit Gurjar, Thomas Thierauf, Nisheeth K. Vishnoi
Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces. CoRR (2017)
Rohit Gurjar, Thomas Thierauf
Linear matroid intersection is in quasi-NC. STOC (2017)
Rohit Gurjar, Arpita Korwar, Nitin Saxena, Thomas Thierauf
Deterministic Identity Testing for Sum of Read-Once Oblivious Arithmetic Branching Programs. Comput. Complex. 26 (4) (2017)
Rohit Gurjar, Arpita Korwar, Jochen Messner, Thomas Thierauf
Exact Perfect Matching in Complete Graphs. ACM Trans. Comput. Theory 9 (2) (2017)
Rohit Gurjar, Arpita Korwar, Jochen Messner, Simon Straub, Thomas Thierauf
Planarizing Gadgets for Perfect Matching Do Not Exist. ACM Trans. Comput. Theory 8 (4) (2016)
Stephen A. Fenner, Rohit Gurjar, Thomas Thierauf
Bipartite perfect matching is in quasi-NC. STOC (2016)
Simon Straub, Thomas Thierauf, Fabian Wagner
Counting the Number of Perfect Matchings in K 5-Free Graphs. Theory Comput. Syst. 59 (3) (2016)
Stephen A. Fenner, Rohit Gurjar, Thomas Thierauf
Bipartite Perfect Matching is in quasi-NC. CoRR (2016)
Valentine Kabanets, Thomas Thierauf, Jacobo Torán, Christopher Umans
Algebraic Methods in Computational Complexity (Dagstuhl Seminar 16411). Dagstuhl Reports 6 (10) (2016)
Rohit Gurjar, Thomas Thierauf
Linear Matroid Intersection is in quasi-NC. Electron. Colloquium Comput. Complex. 23 (2016)
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)
Rohit Gurjar, Arpita Korwar, Nitin Saxena, Thomas Thierauf
Deterministic Identity Testing for Sum of Read-once Oblivious Arithmetic Branching Programs. Computational Complexity Conference (2015)
Stephen A. Fenner, Rohit Gurjar, Thomas Thierauf
Bipartite Perfect Matching is in quasi-NC. Electron. Colloquium Comput. Complex. 22 (2015)
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. 22 (2015)
Simon Straub, Thomas Thierauf, Fabian Wagner
-free Graphs. Electron. Colloquium Comput. Complex. 21 (2014)
Manindra Agrawal, Valentine Kabanets, Thomas Thierauf, Christopher Umans
Algebra in Computational Complexity (Dagstuhl Seminar 14391). Dagstuhl Reports 4 (9) (2014)
Rohit Gurjar, Arpita Korwar, Nitin Saxena, Thomas Thierauf
Deterministic Identity Testing for Sum of Read Once ABPs. Electron. Colloquium Comput. Complex. 21 (2014)
Thomas Thierauf, Fabian Wagner
-free Graphs is in Unambiguous Logspace. Chic. J. Theor. Comput. Sci. 2014 (2014)
Simon Straub, Thomas Thierauf, Fabian Wagner
Counting the Number of Perfect Matchings in K5-Free Graphs. Computational Complexity Conference (2014)
Rohit Gurjar, Arpita Korwar, Nitin Saxena, Thomas Thierauf
Deterministic Identity Testing for Sum of Read Once ABPs. CoRR (2014)
Rohit Gurjar, Arpita Korwar, Jochen Messner, Thomas Thierauf
Exact Perfect Matching in Complete Graphs. Electron. Colloquium Comput. Complex. 20 (2013)
Stephen A. Fenner, Rohit Gurjar, Arpita Korwar, Thomas Thierauf
On Two-Level Poset Games. Electron. Colloquium Comput. Complex. 20 (2013)
Jochen Messner, Thomas Thierauf
A Kolmogorov complexity proof of the Lovász Local Lemma for satisfiability. Theor. Comput. Sci. 461 (2012)
Rohit Gurjar, Arpita Korwar, Jochen Messner, Simon Straub, Thomas Thierauf
Planarizing Gadgets for Perfect Matching Do Not Exist. MFCS (2012)
Manindra Agrawal, Thomas Thierauf, Christopher Umans
Algebraic and Combinatorial Methods in Computational Complexity (Dagstuhl Seminar 12421). Dagstuhl Reports 2 (10) (2012)
Jochen Messner, Thomas Thierauf
A Kolmogorov Complexity Proof of the Lovász Local Lemma for Satisfiability. COCOON (2011)
Jochen Messner, Thomas Thierauf
A Kolmogorov Complexity Proof of the Lovász Local Lemma for Satisfiability. Electron. Colloquium Comput. Complex. 18 (2011)
Rohit Gurjar, Arpita Korwar, Jochen Messner, Simon Straub, Thomas Thierauf
Planarizing Gadgets for Perfect Matching do not Exist. Electron. Colloquium Comput. Complex. 18 (2011)
Sebastian Dörn, Thomas Thierauf
A note on the search for k elements via quantum walk. Inf. Process. Lett. 110 (22) (2010)
Thomas Thierauf, Fabian Wagner
The Isomorphism Problem for Planar 3-Connected Graphs Is in Unambiguous Logspace. Theory Comput. Syst. 47 (3) (2010)
Samir Datta, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner
-free graphs is in Log-space. Electron. Colloquium Comput. Complex. 17 (2010)
Thanh Minh Hoang, Thomas Thierauf
The Complexity of the Inertia. Comput. Complex. 19 (4) (2010)
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)
Thomas Thierauf, Fabian Wagner
-Free Graphs Is in Unambiguous Log-Space. FCT (2009)
Fabian Wagner, Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf
Planar Graph Isomorphism is in Log-space. Electron. Colloquium Comput. Complex. 16 (2009)
Fabian Wagner, Thomas Thierauf
Reachability in K_{3, 3}-free Graphs and K_5-free Graphs is in Unambiguous Log-Space. Electron. Colloquium Comput. Complex. 16 (2009)
Manindra Agrawal, Lance Fortnow, Thomas Thierauf, Christopher Umans
09421 Abstracts Collection - Algebraic Methods in Computational Complexity. Algebraic Methods in Computational Complexity (2009)
Sebastian Dörn, Thomas Thierauf
The quantum query complexity of the determinant. Inf. Process. Lett. 109 (6) (2009)
Manindra Agrawal, Lance Fortnow, Thomas Thierauf, Christopher Umans
09421 Executive Summary - Algebraic Methods in Computational Complexity. Algebraic Methods in Computational Complexity (2009)
Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner
Planar Graph Isomorphism is in Log-Space. Computational Complexity Conference (2009)
Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner
Planar Graph Isomorphism is in Log-Space. Algebraic Methods in Computational Complexity (2009)
Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner
A Log-space Algorithm for Canonization of Planar Graphs CoRR (2008)
Thomas Thierauf, Fabian Wagner
The Isomorphism Problem for Planar 3-Connected Graphs is in Unambiguous Logspace CoRR (2008)
Thomas Thierauf, Fabian Wagner
The Isomorphism Problem for Planar 3-Connected Graphs is in Unambiguous Logspace. STACS (2008)
Sebastian Dörn, Thomas Thierauf
The Quantum Complexity of Group Testing. SOFSEM (2008)
Manindra Agrawal, Harry Buhrman, Lance Fortnow, Thomas Thierauf
07411 Abstracts Collection -- Algebraic Methods in Computational Complexity. Algebraic Methods in Computational Complexity (2007)
Manindra Agrawal, Harry Buhrman, Lance Fortnow, Thomas Thierauf
07411 Executive Summary -- Algebraic Methods in Computational Complexity. Algebraic Methods in Computational Complexity (2007)
Manindra Agrawal, Thanh Minh Hoang, Thomas Thierauf
. STACS (2007)
Sebastian Dörn, Thomas Thierauf
The Quantum Query Complexity of Algebraic Properties. FCT (2007)
Thomas Thierauf, Fabian Wagner
The Isomorphism Problem for Planar 3-Connected Graphs is in Unambiguous Logspace. Electron. Colloquium Comput. Complex. 14 (068) (2007)
Manindra Agrawal, Thanh Minh Hoang, Thomas Thierauf
The polynomially bounded perfect matching problem is in NC^2. Electron. Colloquium Comput. Complex. 13 (129) (2006)
Thanh Minh Hoang, Meena Mahajan, Thomas Thierauf
On the Bipartite Unique Perfect Matching Problem. ICALP (1) (2006)
Thanh Minh Hoang, Thomas Thierauf
The Complexity of the Inertia and Some Closure Properties of GapL. Computational Complexity Conference (2005)
Thanh Minh Hoang, Thomas Thierauf
Erratum: On The Minimal Polynomial Of A Matrix. Int. J. Found. Comput. Sci. 15 (4) (2004)
Thanh Minh Hoang, Thomas Thierauf
On The Minimal Polynomial Of A Matrix. Int. J. Found. Comput. Sci. 15 (1) (2004)
Harry Buhrman, Lance Fortnow, Thomas Thierauf
04421 Abstracts Collection - Algebraic Methods in Computational Complexity. Algebraic Methods in Computational Complexity (2004)
Thomas Thierauf, Thanh Minh Hoang
On Closure Properties of GapL Electron. Colloquium Comput. Complex. (024) (2004)
Thanh Minh Hoang, Thomas Thierauf
The complexity of the characteristic and the minimal polynomial. Theor. Comput. Sci. 295 (2003)
Thanh Minh Hoang, Thomas Thierauf
On the Minimal Polynomial of a Matrix. COCOON (2002)
Thanh Minh Hoang, Thomas Thierauf
The Complexity of the Inertia. FSTTCS (2002)
Thanh Minh Hoang, Thomas Thierauf
The Complexity of the Minimal Polynomial. MFCS (2001)
Thanh Minh Hoang, Thomas Thierauf
The Complexity of the Minimal Polynomial Electron. Colloquium Comput. Complex. 8 (28) (2001)
Manindra Agrawal, Thomas Thierauf
The Formula Isomorphism Problem. SIAM J. Comput. 30 (3) (2000)
Thanh Minh Hoang, Thomas Thierauf
The Complexity of Verifying the Characteristic Polynomial and Testing Similarity. Computational Complexity Conference (2000)
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)
Thomas Thierauf
The Isomorphism Problem for Read-Once Branching Programs and Arithmetic Circuits. Chic. J. Theor. Comput. Sci. 1998 (1998)
Manindra Agrawal, Thomas Thierauf
The Satisfiability Problem for Probabilistic Ordered Branching Programs. Computational Complexity Conference (1998)
Harry Buhrman, Lance Fortnow, Thomas Thierauf
Nonrelativizing Separations. Computational Complexity Conference (1998)
Harry Buhrman, Jim Kadin, Thomas Thierauf
Functions Computable with Nonadaptive Queries to NP. Theory Comput. Syst. 31 (1) (1998)
Manindra Agrawal, Thomas Thierauf
The Satisfiability Problem for Probabilistic Ordered Branching Programs Electron. Colloquium Comput. Complex. 4 (60) (1997)
Yenjo Han, Lane A. Hemaspaandra, Thomas Thierauf
Threshold Computation and Cryptographic Security. SIAM J. Comput. 26 (1) (1997)
Jin-yi Cai, Frederic Green, Thomas Thierauf
On the Correlation of Symmetric Functions. Math. Syst. Theory 29 (3) (1996)
Manindra Agrawal, Richard Beigel, Thomas Thierauf
Modulo Information from Nonadaptive Queries to NP Electron. Colloquium Comput. Complex. 3 (1) (1996)
Stephen A. Fenner, Frederic Green, Steven Homer, Alan L. Selman, Thomas Thierauf, Heribert Vollmer
Complements of Multivalued Functions. Computational Complexity Conference (1996)
Manindra Agrawal, Thomas Thierauf
The Boolean Isomorphism Problem Electron. Colloquium Comput. Complex. 3 (32) (1996)
Thomas Thierauf
The Isomorphismproblem for One-Time-Only Branching Programs Electron. Colloquium Comput. Complex. 3 (40) (1996)
Thomas Thierauf, Seinosuke Toda, Osamu Watanabe
On Sets Bounded Truth-Table Reducible to P-Selective Sets. RAIRO Theor. Informatics Appl. 30 (2) (1996)
Yenjo Han, Thomas Thierauf
Restricted Information from Nonadaptive Queries to NP. Inf. Comput. 128 (2) (1996)
Harry Buhrman, Thomas Thierauf
The Complexity of Generating and Checking Proffs of Membership. STACS (1996)
Manindra Agrawal, Richard Beigel, Thomas Thierauf
Pinpointing Computation with Modular Queries in the Boolean Hierarchy. FSTTCS (1996)
Manindra Agrawal, Thomas Thierauf
The Boolean Isomorphism Problem. FOCS (1996)
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) (1996)

Thomas Thierauf.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Thomas Thierauf