Thomas Thierauf

According to our database1, Thomas Thierauf authored at least 80 papers between 1990 and 2019.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepage:

On csauthors.net:

Bibliography

2019
A deterministic parallel algorithm for bipartite perfect matching.
Commun. ACM, 2019

2018
Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces.
Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

2017
Exact Perfect Matching in Complete Graphs.
TOCT, 2017

Guest Column: Parallel Algorithms for Perfect Matching.
SIGACT News, 2017

Linear matroid intersection is in quasi-NC.
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

2016
Counting the Number of Perfect Matchings in K 5-Free Graphs.
Theory Comput. Syst., 2016

Algebraic Methods in Computational Complexity (Dagstuhl Seminar 16411).
Dagstuhl Reports, 2016

Bipartite perfect matching is in quasi-NC.
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

2015
Reachability in K3,3-free and K5-free Graphs is in Unambiguous Logspace.
Chicago J. Theor. Comput. Sci., 2015

Game Values and Computational Complexity: An Analysis via Black-White Combinatorial Games.
Proceedings of the Algorithms and Computation - 26th International Symposium, 2015

Deterministic Identity Testing for Sum of Read-once Oblivious Arithmetic Branching Programs.
Proceedings of the 30th Conference on Computational Complexity, 2015

2014
Counting the Number of Perfect Matchings in K5-free Graphs.
Electronic Colloquium on Computational Complexity (ECCC), 2014

Deterministic Identity Testing for Sum of Read Once ABPs.
Electronic Colloquium on Computational Complexity (ECCC), 2014

Algebra in Computational Complexity (Dagstuhl Seminar 14391).
Dagstuhl Reports, 2014

Reachability in K{3, 3}-free and K5-free Graphs is in Unambiguous Logspace.
Chicago J. Theor. Comput. Sci., 2014

Counting the Number of Perfect Matchings in K5-Free Graphs.
Proceedings of the IEEE 29th Conference on Computational Complexity, 2014

2013
Exact Perfect Matching in Complete Graphs.
Electronic Colloquium on Computational Complexity (ECCC), 2013

On Two-Level Poset Games.
Electronic Colloquium on Computational Complexity (ECCC), 2013

2012
Algebraic and Combinatorial Methods in Computational Complexity (Dagstuhl Seminar 12421).
Dagstuhl Reports, 2012

Planarizing Gadgets for Perfect Matching Do Not Exist.
Proceedings of the Mathematical Foundations of Computer Science 2012, 2012

2011
A Kolmogorov Complexity Proof of the Lovász Local Lemma for Satisfiability.
Proceedings of the Computing and Combinatorics - 17th Annual International Conference, 2011

2010
A note on the search for k elements via quantum walk.
Inf. Process. Lett., 2010

Graph Isomorphism for K{3, 3}-free and K5-free graphs is in Log-space.
Electronic Colloquium on Computational Complexity (ECCC), 2010

2009
The quantum query complexity of the determinant.
Inf. Process. Lett., 2009

Reachability in K_{3, 3}-free Graphs and K_5-free Graphs is in Unambiguous Log-Space.
Electronic Colloquium on Computational Complexity (ECCC), 2009

Planar Graph Isomorphism is in Log-space.
Electronic Colloquium on Computational Complexity (ECCC), 2009

Graph Isomorphism for K_{3, 3}-free and K_5-free graphs is in Log-space.
Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2009

Reachability in K3, 3-Free Graphs and K5-Free Graphs Is in Unambiguous Log-Space.
Proceedings of the Fundamentals of Computation Theory, 17th International Symposium, 2009

Planar Graph Isomorphism is in Log-Space.
Proceedings of the Algebraic Methods in Computational Complexity, 11.10. - 16.10.2009, 2009

09421 Executive Summary - Algebraic Methods in Computational Complexity.
Proceedings of the Algebraic Methods in Computational Complexity, 11.10. - 16.10.2009, 2009

09421 Abstracts Collection - Algebraic Methods in Computational Complexity.
Proceedings of the Algebraic Methods in Computational Complexity, 11.10. - 16.10.2009, 2009

Planar Graph Isomorphism is in Log-Space.
Proceedings of the 24th Annual IEEE Conference on Computational Complexity, 2009

2008
The Isomorphism Problem for Planar 3-Connected Graphs is in Unambiguous Logspace.
Proceedings of the STACS 2008, 2008

The Quantum Complexity of Group Testing.
Proceedings of the SOFSEM 2008: Theory and Practice of Computer Science, 2008

2007
The Polynomially Bounded Perfect Matching Problem Is in NC 2.
Proceedings of the STACS 2007, 2007

The Quantum Query Complexity of Algebraic Properties.
Proceedings of the Fundamentals of Computation Theory, 16th International Symposium, 2007

07411 Abstracts Collection -- Algebraic Methods in Computational Complexity.
Proceedings of the Algebraic Methods in Computational Complexity, 07.10. - 12.10.2007, 2007

07411 Executive Summary -- Algebraic Methods in Computational Complexity.
Proceedings of the Algebraic Methods in Computational Complexity, 07.10. - 12.10.2007, 2007

2006
The polynomially bounded perfect matching problem is in NC^2.
Electronic Colloquium on Computational Complexity (ECCC), 2006

On the Bipartite Unique Perfect Matching Problem.
Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

2005
The Complexity of the Inertia and Some Closure Properties of GapL.
Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 2005

2004
Erratum: On The Minimal Polynomial Of A Matrix.
Int. J. Found. Comput. Sci., 2004

On Closure Properties of GapL
Electronic Colloquium on Computational Complexity (ECCC), 2004

04421 Abstracts Collection - Algebraic Methods in Computational Complexity.
Proceedings of the Algebraic Methods in Computational Complexity, 10.-15. October 2004, 2004

2003
The complexity of the characteristic and the minimal polynomial.
Theor. Comput. Sci., 2003

2002
The Complexity of the Inertia.
Proceedings of the FST TCS 2002: Foundations of Software Technology and Theoretical Computer Science, 2002

On the Minimal Polynomial of a Matrix.
Proceedings of the Computing and Combinatorics, 8th Annual International Conference, 2002

2001
The Complexity of the Minimal Polynomial
Electronic Colloquium on Computational Complexity (ECCC), 2001

The Complexity of the Minimal Polynomial.
Proceedings of the Mathematical Foundations of Computer Science 2001, 2001

2000
The Formula Isomorphism Problem.
SIAM J. Comput., 2000

The Complexity of Verifying the Characteristic Polynomial and Testing Similarity.
Proceedings of the 15th Annual IEEE Conference on Computational Complexity, 2000

The Computational Complexity of Equivalence and Isomorphism Problems
Lecture Notes in Computer Science 1852, Springer, ISBN: 3-540-41032-5, 2000

1998
Functions Computable with Nonadaptive Queries to NP.
Theory Comput. Syst., 1998

The Isomorphism Problem for Read-Once Branching Programs and Arithmetic Circuits.
Chicago J. Theor. Comput. Sci., 1998

Nonrelativizing Separations.
Proceedings of the 13th Annual IEEE Conference on Computational Complexity, 1998

The Satisfiability Problem for Probabilistic Ordered Branching Programs.
Proceedings of the 13th Annual IEEE Conference on Computational Complexity, 1998

1997
The Satisfiability Problem for Probabilistic Ordered Branching Programs
Electronic Colloquium on Computational Complexity (ECCC), 1997

1996
On the Correlation of Symmetric Functions.
Mathematical Systems Theory, 1996

On Closure Properties of #P in the Context of PF ° #P.
J. Comput. Syst. Sci., 1996

The Isomorphismproblem for One-Time-Only Branching Programs
Electronic Colloquium on Computational Complexity (ECCC), 1996

The Boolean Isomorphism Problem
Electronic Colloquium on Computational Complexity (ECCC), 1996

Modulo Information from Nonadaptive Queries to NP
Electronic Colloquium on Computational Complexity (ECCC), 1996

The Complexity of Generating and Checking Proffs of Membership.
Proceedings of the STACS 96, 1996

Pinpointing Computation with Modular Queries in the Boolean Hierarchy.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1996

The Boolean Isomorphism Problem.
Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

Complements of Multivalued Functions.
Proceedings of the Eleveth Annual IEEE Conference on Computational Complexity, 1996

1995
Nondeterministically Selective Sets.
Int. J. Found. Comput. Sci., 1995

Restricted Information from Nonadaptive Queries to NP.
Proceedings of the Tenth Annual Structure in Complexity Theory Conference, 1995

1994
Complexity-Restricted Advice Functions.
SIAM J. Comput., 1994

A Note on SpanP Functions.
Inf. Process. Lett., 1994

On Closure Properties of GapP.
Computational Complexity, 1994

On Sets Bounded Truth-Table Reducible to P-selective Sets.
Proceedings of the STACS 94, 1994

On Functions Computable with Nonadaptive Queries to NP.
Proceedings of the Ninth Annual Structure in Complexity Theory Conference, Amsterdam, The Netherlands, June 28, 1994

1993
Threshold Computation and Cryptographic Security.
Proceedings of the Algorithms and Computation, 4th International Symposium, 1993

Selectivity.
Proceedings of the Computing and Information, 1993

On Closure Properties of #P in the Context of PF°#P.
Proceedings of the Eigth Annual Structure in Complexity Theory Conference, 1993

1992
Reductions to Sets of Low Information Content.
Proceedings of the Automata, Languages and Programming, 19th International Colloquium, 1992

Reductions to Sets of Low Information Content.
Proceedings of the Complexity Theory: Current Research, 1992

1990
Complexity Classes with Advice.
Proceedings of the Proceedings: Fifth Annual Structure in Complexity Theory Conference, 1990

NP-uniforme Komplexitätsklassen.
PhD thesis, 1990


  Loading...