| 2026 | STACS | 2D Minimal Graph Rigidity is in NC for One-Crossing-Minor-Free Graphs. | Rohit Gurjar, Kilian Rothmund, Thomas Thierauf |
| 2018 | ICALP | Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces. | Rohit Gurjar, Thomas Thierauf, Nisheeth K. Vishnoi |
| 2017 | STOC | Linear matroid intersection is in quasi-NC. | Rohit Gurjar, Thomas Thierauf |
| 2016 | STOC | Bipartite perfect matching is in quasi-NC. | Stephen A. Fenner, Rohit Gurjar, Thomas Thierauf |
| 2015 | ISAAC | Game Values and Computational Complexity: An Analysis via Black-White Combinatorial Games. | Stephen A. Fenner, Daniel Grier, Jochen Messner, Luke Schaeffer, Thomas Thierauf |
| 2012 | MFCS | Planarizing Gadgets for Perfect Matching Do Not Exist. | Rohit Gurjar, Arpita Korwar, Jochen Messner, Simon Straub, Thomas Thierauf |
| 2011 | COCOON | A Kolmogorov Complexity Proof of the Lovsz Local Lemma for Satisfiability. | Jochen Messner, Thomas Thierauf |
| 2009 | FCT | Reachability in | Thomas Thierauf, Fabian Wagner |
| 2008 | STACS | The Isomorphism Problem for Planar 3-Connected Graphs is in Unambiguous Logspace. | Thomas Thierauf, Fabian Wagner |
| 2008 | SOFSEM | The Quantum Complexity of Group Testing. | Sebastian Drn, Thomas Thierauf |
| 2007 | FCT | The Quantum Query Complexity of Algebraic Properties. | Sebastian Drn, Thomas Thierauf |
| 2007 | STACS | The Polynomially Bounded Perfect Matching Problem Is in NC | Manindra Agrawal, Thanh Minh Hoang, Thomas Thierauf |
| 2006 | ICALP | On the Bipartite Unique Perfect Matching Problem. | Thanh Minh Hoang, Meena Mahajan, Thomas Thierauf |
| 2002 | COCOON | On the Minimal Polynomial of a Matrix. | Thanh Minh Hoang, Thomas Thierauf |
| 2001 | MFCS | The Complexity of the Minimal Polynomial. | Thanh Minh Hoang, Thomas Thierauf |
| 1996 | FOCS | The Boolean Isomorphism Problem. | Manindra Agrawal, Thomas Thierauf |
| 1996 | STACS | The Complexity of Generating and Checking Proffs of Membership. | Harry Buhrman, Thomas Thierauf |
| 1994 | STACS | On Sets Bounded Truth-Table Reducible to P-selective Sets. | Thomas Thierauf, Seinosuke Toda, Osamu Watanabe |
| 1993 | ICCI | Selectivity. | Lane A. Hemachandra, Albrecht Hoene, Mitsunori Ogiwara, Alan L. Selman, Thomas Thierauf, Jie Wang |
| 1993 | ISAAC | Threshold Computation and Cryptographic Security. | Yenjo Han, Lane A. Hemaspaandra, Thomas Thierauf |
| 1992 | ICALP | Reductions to Sets of Low Information Content. | Vikraman Arvind, Yenjo Han, Lane A. Hemachandra, Johannes Kbler, Antoni Lozano, Martin Mundhenk, Mitsunori Ogiwara, Uwe Schning, Riccardo Silvestri, Thomas Thierauf |