Thomas Thierauf

124 papers A* 5A 16B 7C 1Misc 2Journal 73Unranked 15

Year	Rank	Type	Title / Venue / Authors
2026	A	`conf`	2D Minimal Graph Rigidity is in NC for One-Crossing-Minor-Free Graphs. STACS Rohit Gurjar, Kilian Rothmund, Thomas Thierauf
2025	J	`jnl`	2D Minimal Graph Rigidity is in NC for One-Crossing-Minor-Free Graphs. Electron. Colloquium Comput. Complex. Rohit Gurjar, Kilian Rothmund, Thomas Thierauf
2025	J	`jnl`	Tight bounds on depth-2 QAC-circuits computing parity. CoRR Stephen A. Fenner, Daniel Grier, Daniel Padé, Thomas Thierauf
2024	A	`conf`	Derandomizing Multivariate Polynomial Factoring for Low Degree Factors. APPROX/RANDOM Pranjal Dutta, Amit Sinhababu, Thomas Thierauf
2024	J	`jnl`	Derandomizing Multivariate Polynomial Factoring for Low Degree Factors. CoRR Pranjal Dutta, Amit Sinhababu, Thomas Thierauf
2024	J	`jnl`	Derandomizing Multivariate Polynomial Factoring for Low Degree Factors. Electron. Colloquium Comput. Complex. Pranjal Dutta, Amit Sinhababu, Thomas Thierauf
2024	J	`jnl`	Weighted Sum-of-Squares Lower Bounds for Univariate Polynomials Imply VP ≠q VNP. Comput. Complex. Pranjal Dutta, Nitin Saxena, Thomas Thierauf
2022	J	`jnl`	Planar Graph Isomorphism Is in Log-Space. ACM Trans. Comput. Theory Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner
2022	J	`jnl`	The Complexity of Poset Games. J. Graph Algorithms Appl. Stephen A. Fenner, Daniel Grier, Rohit Gurjar, Arpita Korwar, Thomas Thierauf
2022	J	`jnl`	The complexity of regex crosswords. Inf. Comput. Stephen A. Fenner, Daniel Padé, Thomas Thierauf
2021	A	`conf`	A Largish Sum-Of-Squares Implies Circuit Hardness and Derandomization. ITCS Pranjal Dutta, Nitin Saxena, Thomas Thierauf
2021	J	`jnl`	Bipartite Perfect Matching is in Quasi-NC. SIAM J. Comput. Stephen A. Fenner, Rohit Gurjar, Thomas Thierauf
2021	J	`jnl`	Factorization of Polynomials Given by Arithmetic Branching Programs. Comput. Complex. Amit Sinhababu, Thomas Thierauf
2021	J	`jnl`	Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces. SIAM J. Comput. Rohit Gurjar, Thomas Thierauf, Nisheeth K. Vishnoi
2020	J	`jnl`	Depth-2 QAC circuits cannot simulate quantum parity. CoRR Daniel Padé, Stephen A. Fenner, Daniel Grier, Thomas Thierauf
2020	A	`conf`	Factorization of Polynomials Given By Arithmetic Branching Programs. CCC Amit Sinhababu, Thomas Thierauf
2020	J	`jnl`	Factorization of Polynomials Given by Arithmetic Branching Programs. Electron. Colloquium Comput. Complex. Amit Sinhababu, Thomas Thierauf
2020	J	`jnl`	Impossibility of Derandomizing the Isolation Lemma for all Families. Electron. Colloquium Comput. Complex. Manindra Agrawal, Rohit Gurjar, Thomas Thierauf
2020	J	`jnl`	Linear Matroid Intersection is in Quasi-NC. Comput. Complex. Rohit Gurjar, Thomas Thierauf
2020	J	`jnl`	Lower bounds on the sum of 25th-powers of univariates lead to complete derandomization of PIT. Electron. Colloquium Comput. Complex. Pranjal Dutta, Nitin Saxena, Thomas Thierauf
2019	J	`jnl`	A deterministic parallel algorithm for bipartite perfect matching. Commun. ACM Stephen A. Fenner, Rohit Gurjar, Thomas Thierauf
2018	A*	`conf`	Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces. ICALP Rohit Gurjar, Thomas Thierauf, Nisheeth K. Vishnoi
2017	J	`jnl`	Deterministic Identity Testing for Sum of Read-Once Oblivious Arithmetic Branching Programs. Comput. Complex. Rohit Gurjar, Arpita Korwar, Nitin Saxena, Thomas Thierauf
2017	J	`jnl`	Exact Perfect Matching in Complete Graphs. ACM Trans. Comput. Theory Rohit Gurjar, Arpita Korwar, Jochen Messner, Thomas Thierauf
2017	J	`jnl`	Guest Column: Parallel Algorithms for Perfect Matching. SIGACT News Stephen A. Fenner, Rohit Gurjar, Thomas Thierauf
2017	J	`jnl`	Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces. CoRR Rohit Gurjar, Thomas Thierauf, Nisheeth K. Vishnoi
2017	J	`jnl`	Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces. Electron. Colloquium Comput. Complex. Rohit Gurjar, Thomas Thierauf, Nisheeth K. Vishnoi
2017	A*	`conf`	Linear matroid intersection is in quasi-NC. STOC Rohit Gurjar, Thomas Thierauf
2016	J	`jnl`	Algebraic Methods in Computational Complexity (Dagstuhl Seminar 16411). Dagstuhl Reports Valentine Kabanets, Thomas Thierauf, Jacobo Torán, Christopher Umans
2016	J	`jnl`	Bipartite Perfect Matching is in quasi-NC. CoRR Stephen A. Fenner, Rohit Gurjar, Thomas Thierauf
2016	A*	`conf`	Bipartite perfect matching is in quasi-NC. STOC Stephen A. Fenner, Rohit Gurjar, Thomas Thierauf
2016	J	`jnl`	Counting the Number of Perfect Matchings in K 5-Free Graphs. Theory Comput. Syst. Simon Straub, Thomas Thierauf, Fabian Wagner
2016	J	`jnl`	Linear Matroid Intersection is in quasi-NC. Electron. Colloquium Comput. Complex. Rohit Gurjar, Thomas Thierauf
2016	J	`jnl`	Planarizing Gadgets for Perfect Matching Do Not Exist. ACM Trans. Comput. Theory Rohit Gurjar, Arpita Korwar, Jochen Messner, Simon Straub, Thomas Thierauf
2015	J	`jnl`	Bipartite Perfect Matching is in quasi-NC. Electron. Colloquium Comput. Complex. Stephen A. Fenner, Rohit Gurjar, Thomas Thierauf
2015	A	`conf`	Deterministic Identity Testing for Sum of Read-once Oblivious Arithmetic Branching Programs. CCC Rohit Gurjar, Arpita Korwar, Nitin Saxena, Thomas Thierauf
2015	B	`conf`	Game Values and Computational Complexity: An Analysis via Black-White Combinatorial Games. ISAAC Stephen A. Fenner, Daniel Grier, Jochen Messner, Luke Schaeffer, Thomas Thierauf
2015	J	`jnl`	Game Values and Computational Complexity: An Analysis via Black-White Combinatorial Games. Electron. Colloquium Comput. Complex. Stephen A. Fenner, Daniel Grier, Jochen Messner, Luke Schaeffer, Thomas Thierauf
2014	J	`jnl`	Algebra in Computational Complexity (Dagstuhl Seminar 14391). Dagstuhl Reports Manindra Agrawal, Valentine Kabanets, Thomas Thierauf, Christopher Umans
2014	J	`jnl`	Counting the Number of Perfect Matchings in K Electron. Colloquium Comput. Complex. Simon Straub, Thomas Thierauf, Fabian Wagner
2014	A	`conf`	Counting the Number of Perfect Matchings in K5-Free Graphs. CCC Simon Straub, Thomas Thierauf, Fabian Wagner
2014	J	`jnl`	Deterministic Identity Testing for Sum of Read Once ABPs. CoRR Rohit Gurjar, Arpita Korwar, Nitin Saxena, Thomas Thierauf
2014	J	`jnl`	Deterministic Identity Testing for Sum of Read Once ABPs. Electron. Colloquium Comput. Complex. Rohit Gurjar, Arpita Korwar, Nitin Saxena, Thomas Thierauf
2014	J	`jnl`	Reachability in K Chic. J. Theor. Comput. Sci. Thomas Thierauf, Fabian Wagner
2013	J	`jnl`	Exact Perfect Matching in Complete Graphs. Electron. Colloquium Comput. Complex. Rohit Gurjar, Arpita Korwar, Jochen Messner, Thomas Thierauf
2013	J	`jnl`	On Two-Level Poset Games. Electron. Colloquium Comput. Complex. Stephen A. Fenner, Rohit Gurjar, Arpita Korwar, Thomas Thierauf
2012	J	`jnl`	A Kolmogorov complexity proof of the Lovász Local Lemma for satisfiability. Theor. Comput. Sci. Jochen Messner, Thomas Thierauf
2012	J	`jnl`	Algebraic and Combinatorial Methods in Computational Complexity (Dagstuhl Seminar 12421). Dagstuhl Reports Manindra Agrawal, Thomas Thierauf, Christopher Umans
2012	B	`conf`	Planarizing Gadgets for Perfect Matching Do Not Exist. MFCS Rohit Gurjar, Arpita Korwar, Jochen Messner, Simon Straub, Thomas Thierauf
2011	Misc	`conf`	A Kolmogorov Complexity Proof of the Lovász Local Lemma for Satisfiability. COCOON Jochen Messner, Thomas Thierauf
2011	J	`jnl`	A Kolmogorov Complexity Proof of the Lovász Local Lemma for Satisfiability. Electron. Colloquium Comput. Complex. Jochen Messner, Thomas Thierauf
2011	J	`jnl`	Planarizing Gadgets for Perfect Matching do not Exist. Electron. Colloquium Comput. Complex. Rohit Gurjar, Arpita Korwar, Jochen Messner, Simon Straub, Thomas Thierauf
2010	J	`jnl`	A note on the search for k elements via quantum walk. Inf. Process. Lett. Sebastian Dörn, Thomas Thierauf
2010	J	`jnl`	Graph Isomorphism for K Electron. Colloquium Comput. Complex. Samir Datta, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner
2010	J	`jnl`	The Complexity of the Inertia. Comput. Complex. Thanh Minh Hoang, Thomas Thierauf
2010	J	`jnl`	The Isomorphism Problem for Planar 3-Connected Graphs Is in Unambiguous Logspace. Theory Comput. Syst. Thomas Thierauf, Fabian Wagner
2009	—	`conf`	09421 Abstracts Collection - Algebraic Methods in Computational Complexity. Algebraic Methods in Computational Complexity Manindra Agrawal, Lance Fortnow, Thomas Thierauf, Christopher Umans
2009	—	`conf`	09421 Executive Summary - Algebraic Methods in Computational Complexity. Algebraic Methods in Computational Complexity Manindra Agrawal, Lance Fortnow, Thomas Thierauf, Christopher Umans
2009	—	`ed.`	Algebraic Methods in Computational Complexity, 11.10. - 16.10.2009 Algebraic Methods in Computational Complexity Manindra Agrawal, Lance Fortnow, Thomas Thierauf, Christopher Umans
2009	—	`conf`	Graph Isomorphism for K_{3, 3}-free and K_5-free graphs is in Log-space. FSTTCS Samir Datta, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner
2009	A	`conf`	Planar Graph Isomorphism is in Log-Space. CCC Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner
2009	—	`conf`	Planar Graph Isomorphism is in Log-Space. Algebraic Methods in Computational Complexity Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner
2009	J	`jnl`	Planar Graph Isomorphism is in Log-space. Electron. Colloquium Comput. Complex. Fabian Wagner, Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf
2009	B	`conf`	Reachability in FCT Thomas Thierauf, Fabian Wagner
2009	J	`jnl`	Reachability in K Electron. Colloquium Comput. Complex. Fabian Wagner, Thomas Thierauf
2009	J	`jnl`	The quantum query complexity of the determinant. Inf. Process. Lett. Sebastian Dörn, Thomas Thierauf
2008	J	`jnl`	A Log-space Algorithm for Canonization of Planar Graphs CoRR Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner
2008	—	`ed.`	Algebraic Methods in Computational Complexity, 07.10. - 12.10.2007 Algebraic Methods in Computational Complexity Manindra Agrawal, Harry Buhrman, Lance Fortnow, Thomas Thierauf
2008	J	`jnl`	The Isomorphism Problem for Planar 3-Connected Graphs is in Unambiguous Logspace CoRR Thomas Thierauf, Fabian Wagner
2008	A	`conf`	The Isomorphism Problem for Planar 3-Connected Graphs is in Unambiguous Logspace. STACS Thomas Thierauf, Fabian Wagner
2008	B	`conf`	The Quantum Complexity of Group Testing. SOFSEM Sebastian Dörn, Thomas Thierauf
2007	—	`conf`	07411 Abstracts Collection -- Algebraic Methods in Computational Complexity. Algebraic Methods in Computational Complexity Manindra Agrawal, Harry Buhrman, Lance Fortnow, Thomas Thierauf
2007	—	`conf`	07411 Executive Summary -- Algebraic Methods in Computational Complexity. Algebraic Methods in Computational Complexity Manindra Agrawal, Harry Buhrman, Lance Fortnow, Thomas Thierauf
2007	J	`jnl`	The Isomorphism Problem for Planar 3-Connected Graphs is in Unambiguous Logspace. Electron. Colloquium Comput. Complex. Thomas Thierauf, Fabian Wagner
2007	A	`conf`	The Polynomially Bounded Perfect Matching Problem Is in NC STACS Manindra Agrawal, Thanh Minh Hoang, Thomas Thierauf
2007	B	`conf`	The Quantum Query Complexity of Algebraic Properties. FCT Sebastian Dörn, Thomas Thierauf
2006	—	`conf`	On the Bipartite Unique Perfect Matching Problem. ICALP (1) Thanh Minh Hoang, Meena Mahajan, Thomas Thierauf
2006	J	`jnl`	The polynomially bounded perfect matching problem is in NC^2. Electron. Colloquium Comput. Complex. Manindra Agrawal, Thanh Minh Hoang, Thomas Thierauf
2005	—	`ed.`	Algebraic Methods in Computational Complexity, 10.-15. October 2004 Algebraic Methods in Computational Complexity Harry Buhrman, Lance Fortnow, Thomas Thierauf
2005	A	`conf`	The Complexity of the Inertia and Some Closure Properties of GapL. CCC Thanh Minh Hoang, Thomas Thierauf
2004	—	`conf`	04421 Abstracts Collection - Algebraic Methods in Computational Complexity. Algebraic Methods in Computational Complexity Harry Buhrman, Lance Fortnow, Thomas Thierauf
2004	J	`jnl`	Erratum: On The Minimal Polynomial Of A Matrix. Int. J. Found. Comput. Sci. Thanh Minh Hoang, Thomas Thierauf
2004	J	`jnl`	On Closure Properties of GapL Electron. Colloquium Comput. Complex. Thomas Thierauf, Thanh Minh Hoang
2004	J	`jnl`	On The Minimal Polynomial Of A Matrix. Int. J. Found. Comput. Sci. Thanh Minh Hoang, Thomas Thierauf
2003	J	`jnl`	The complexity of the characteristic and the minimal polynomial. Theor. Comput. Sci. Thanh Minh Hoang, Thomas Thierauf
2002	Misc	`conf`	On the Minimal Polynomial of a Matrix. COCOON Thanh Minh Hoang, Thomas Thierauf
2002	—	`conf`	The Complexity of the Inertia. FSTTCS Thanh Minh Hoang, Thomas Thierauf
2001	J	`jnl`	The Complexity of the Minimal Polynomial Electron. Colloquium Comput. Complex. Thanh Minh Hoang, Thomas Thierauf
2001	B	`conf`	The Complexity of the Minimal Polynomial. MFCS Thanh Minh Hoang, Thomas Thierauf
2000	A	`conf`	The Complexity of Verifying the Characteristic Polynomial and Testing Similarity. CCC Thanh Minh Hoang, Thomas Thierauf
2000	—	`book`	The Computational Complexity of Equivalence and Isomorphism Problems Thomas Thierauf
2000	J	`jnl`	The Formula Isomorphism Problem. SIAM J. Comput. Manindra Agrawal, Thomas Thierauf
1999	J	`jnl`	Complements of Multivalued Functions. Chic. J. Theor. Comput. Sci. Stephen A. Fenner, Frederic Green, Steven Homer, Alan L. Selman, Thomas Thierauf, Heribert Vollmer
1998	J	`jnl`	Functions Computable with Nonadaptive Queries to NP. Theory Comput. Syst. Harry Buhrman, Jim Kadin, Thomas Thierauf
1998	A	`conf`	Nonrelativizing Separations. CCC Harry Buhrman, Lance Fortnow, Thomas Thierauf
1998	J	`jnl`	The Isomorphism Problem for Read-Once Branching Programs and Arithmetic Circuits. Chic. J. Theor. Comput. Sci. Thomas Thierauf
1998	A	`conf`	The Satisfiability Problem for Probabilistic Ordered Branching Programs. CCC Manindra Agrawal, Thomas Thierauf
1997	J	`jnl`	The Satisfiability Problem for Probabilistic Ordered Branching Programs Electron. Colloquium Comput. Complex. Manindra Agrawal, Thomas Thierauf
1997	J	`jnl`	Threshold Computation and Cryptographic Security. SIAM J. Comput. Yenjo Han, Lane A. Hemaspaandra, Thomas Thierauf
1996	A	`conf`	Complements of Multivalued Functions. CCC Stephen A. Fenner, Frederic Green, Steven Homer, Alan L. Selman, Thomas Thierauf, Heribert Vollmer
1996	J	`jnl`	Modulo Information from Nonadaptive Queries to NP Electron. Colloquium Comput. Complex. Manindra Agrawal, Richard Beigel, Thomas Thierauf
1996	J	`jnl`	On Closure Properties of #P in the Context of PF ° #P. J. Comput. Syst. Sci. Mitsunori Ogihara, Thomas Thierauf, Seinosuke Toda, Osamu Watanabe
1996	J	`jnl`	On Sets Bounded Truth-Table Reducible to P-Selective Sets. RAIRO Theor. Informatics Appl. Thomas Thierauf, Seinosuke Toda, Osamu Watanabe
1996	J	`jnl`	On the Correlation of Symmetric Functions. Math. Syst. Theory Jin-Yi Cai, Frederic Green, Thomas Thierauf
1996	—	`conf`	Pinpointing Computation with Modular Queries in the Boolean Hierarchy. FSTTCS Manindra Agrawal, Richard Beigel, Thomas Thierauf
1996	J	`jnl`	Restricted Information from Nonadaptive Queries to NP. Inf. Comput. Yenjo Han, Thomas Thierauf
1996	J	`jnl`	The Boolean Isomorphism Problem Electron. Colloquium Comput. Complex. Manindra Agrawal, Thomas Thierauf
1996	A*	`conf`	The Boolean Isomorphism Problem. FOCS Manindra Agrawal, Thomas Thierauf
1996	A	`conf`	The Complexity of Generating and Checking Proffs of Membership. STACS Harry Buhrman, Thomas Thierauf
1996	J	`jnl`	The Isomorphismproblem for One-Time-Only Branching Programs Electron. Colloquium Comput. Complex. Thomas Thierauf
1995	J	`jnl`	Nondeterministically Selective Sets. Int. J. Found. Comput. Sci. Lane A. Hemaspaandra, Albrecht Hoene, Ashish V. Naik, Mitsunori Ogihara, Alan L. Selman, Thomas Thierauf, Jie Wang
1995	—	`conf`	Restricted Information from Nonadaptive Queries to NP. SCT Yenjo Han, Thomas Thierauf
1994	J	`jnl`	A Note on SpanP Functions. Inf. Process. Lett. Meena Mahajan, Thomas Thierauf, N. V. Vinodchandran
1994	J	`jnl`	Complexity-Restricted Advice Functions. SIAM J. Comput. Johannes Köbler, Thomas Thierauf
1994	J	`jnl`	On Closure Properties of GapP. Comput. Complex. Thomas Thierauf, Seinosuke Toda, Osamu Watanabe
1994	—	`conf`	On Functions Computable with Nonadaptive Queries to NP. SCT Harry Buhrman, Jim Kadin, Thomas Thierauf
1994	A	`conf`	On Sets Bounded Truth-Table Reducible to P-selective Sets. STACS Thomas Thierauf, Seinosuke Toda, Osamu Watanabe
1993	—	`conf`	On Closure Properties of #P in the Context of PF°#P. SCT Mitsunori Ogiwara, Thomas Thierauf, Seinosuke Toda, Osamu Watanabe
1993	C	`conf`	Selectivity. ICCI Lane A. Hemachandra, Albrecht Hoene, Mitsunori Ogiwara, Alan L. Selman, Thomas Thierauf, Jie Wang
1993	B	`conf`	Threshold Computation and Cryptographic Security. ISAAC Yenjo Han, Lane A. Hemaspaandra, Thomas Thierauf
1992	—	`conf`	Reductions to Sets of Low Information Content. Complexity Theory: Current Research Vikraman Arvind, Yenjo Han, Lane A. Hemachandra, Johannes Köbler, Antoni Lozano, Martin Mundhenk, Mitsunori Ogiwara, Uwe Schöning, Riccardo Silvestri, Thomas Thierauf
1992	A*	`conf`	Reductions to Sets of Low Information Content. ICALP Vikraman Arvind, Yenjo Han, Lane A. Hemachandra, Johannes Köbler, Antoni Lozano, Martin Mundhenk, Mitsunori Ogiwara, Uwe Schöning, Riccardo Silvestri, Thomas Thierauf
1990	—	`conf`	Complexity Classes with Advice. SCT Johannes Köbler, Thomas Thierauf
1990	—	`—`	NP-uniforme Komplexitätsklassen. Thomas Thierauf