Thomas Thierauf

Kilian Rothmund

Electron. Colloquium Comput. Complex., 2025

2024

Weighted Sum-of-Squares Lower Bounds for Univariate Polynomials Imply VP ≠q VNP.

[BibT_eX]

[DOI]

Nitin Saxena

Comput. Complex., June, 2024

Derandomizing Multivariate Polynomial Factoring for Low Degree Factors.

[BibT_eX]

[DOI]

Amit Sinhababu

Proceedings of the Approximation, 2024

2022

The Complexity of Poset Games.

[BibT_eX]

[DOI]

J. Graph Algorithms Appl., 2022

The complexity of regex crosswords.

[BibT_eX]

[DOI]

Daniel Padé

Inf. Comput., 2022

2021

A Largish Sum-Of-Squares Implies Circuit Hardness and Derandomization.

[BibT_eX]

[DOI]

Nitin Saxena

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

2020

Lower bounds on the sum of 25th-powers of univariates lead to complete derandomization of PIT.

[BibT_eX]

[DOI]

Nitin Saxena

Electron. Colloquium Comput. Complex., 2020

Impossibility of Derandomizing the Isolation Lemma for all Families.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2020

Depth-2 QAC circuits cannot simulate quantum parity.

[BibT_eX]

[DOI]

CoRR, 2020

Factorization of Polynomials Given By Arithmetic Branching Programs.

[BibT_eX]

[DOI]

Amit Sinhababu

Proceedings of the 35th Computational Complexity Conference, 2020

2019

A deterministic parallel algorithm for bipartite perfect matching.

[BibT_eX]

[DOI]

Commun. ACM, 2019

2018

Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces.

[BibT_eX]

[DOI]

Nisheeth K. Vishnoi

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

2017

Guest Column: Parallel Algorithms for Perfect Matching.

[BibT_eX]

[DOI]

SIGACT News, 2017

Linear matroid intersection is in quasi-NC.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Simon Straub

Theory Comput. Syst., 2016

Algebraic Methods in Computational Complexity (Dagstuhl Seminar 16411).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2016

Bipartite perfect matching is in quasi-NC.

[BibT_eX]

[DOI]

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

2015

Game Values and Computational Complexity: An Analysis via Black-White Combinatorial Games.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation - 26th International Symposium, 2015

Deterministic Identity Testing for Sum of Read-once Oblivious Arithmetic Branching Programs.

[BibT_eX]

[DOI]

Proceedings of the 30th Conference on Computational Complexity, 2015

2014

Counting the Number of Perfect Matchings in K5-free Graphs.

[BibT_eX]

[DOI]

Simon Straub

Electron. Colloquium Comput. Complex., 2014

Deterministic Identity Testing for Sum of Read Once ABPs.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

Algebra in Computational Complexity (Dagstuhl Seminar 14391).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2014

Reachability in K{3, 3}-free and K5-free Graphs is in Unambiguous Logspace.

[BibT_eX]

[DOI]

Chic. J. Theor. Comput. Sci., 2014

Counting the Number of Perfect Matchings in K5-Free Graphs.

[BibT_eX]

[DOI]

Simon Straub

Proceedings of the IEEE 29th Conference on Computational Complexity, 2014

2013

Exact Perfect Matching in Complete Graphs.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

On Two-Level Poset Games.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

2012

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

[BibT_eX]

[DOI]

Christopher Umans

Dagstuhl Reports, 2012

Planarizing Gadgets for Perfect Matching Do Not Exist.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2012, 2012

2011

A Kolmogorov Complexity Proof of the Lovász Local Lemma for Satisfiability.

[BibT_eX]

[DOI]

Jochen Messner

Proceedings of the Computing and Combinatorics - 17th Annual International Conference, 2011

2010

A note on the search for k elements via quantum walk.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2010

Graph Isomorphism for K3,3-free and K5-free graphs is in Log-space.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

2009

The quantum query complexity of the determinant.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2009

Reachability in K3,3-free Graphs and K5-free Graphs is in Unambiguous Log-Space.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2009

Graph Isomorphism for K_{3, 3}-free and K_5-free graphs is in Log-space.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory, 17th International Symposium, 2009

09421 Executive Summary - Algebraic Methods in Computational Complexity.

[BibT_eX]

[DOI]

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

09421 Abstracts Collection - Algebraic Methods in Computational Complexity.

[BibT_eX]

[DOI]

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

Planar Graph Isomorphism is in Log-Space.

[BibT_eX]

[DOI]

Proceedings of the 24th Annual IEEE Conference on Computational Complexity, 2009

2008

A Log-space Algorithm for Canonization of Planar Graphs

[BibT_eX]

[DOI]

CoRR, 2008

The Isomorphism Problem for Planar 3-Connected Graphs is in Unambiguous Logspace.

[BibT_eX]

[DOI]

Proceedings of the STACS 2008, 2008

The Quantum Complexity of Group Testing.

[BibT_eX]

[DOI]

Proceedings of the SOFSEM 2008: Theory and Practice of Computer Science, 2008

2007

The Polynomially Bounded Perfect Matching Problem Is in NC 2.

[BibT_eX]

[DOI]

Proceedings of the STACS 2007, 2007

The Quantum Query Complexity of Algebraic Properties.

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory, 16th International Symposium, 2007

07411 Abstracts Collection -- Algebraic Methods in Computational Complexity.

[BibT_eX]

[DOI]

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

07411 Executive Summary -- Algebraic Methods in Computational Complexity.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2006

On the Bipartite Unique Perfect Matching Problem.

[BibT_eX]

[DOI]

Meena Mahajan

Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

2005

The Complexity of the Inertia and Some Closure Properties of GapL.

[BibT_eX]

[DOI]

Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 2005

2004

Erratum: On The Minimal Polynomial Of A Matrix.

[BibT_eX]

[DOI]

Int. J. Found. Comput. Sci., 2004

On Closure Properties of GapL

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2004

04421 Abstracts Collection - Algebraic Methods in Computational Complexity.

[BibT_eX]

[DOI]

Lance Fortnow

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

2003

The complexity of the characteristic and the minimal polynomial.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2003

2002

The Complexity of the Inertia.

[BibT_eX]

[DOI]

Proceedings of the FST TCS 2002: Foundations of Software Technology and Theoretical Computer Science, 2002

On the Minimal Polynomial of a Matrix.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics, 8th Annual International Conference, 2002

2001

The Complexity of the Minimal Polynomial.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2001, 2001

2000

The Formula Isomorphism Problem.

[BibT_eX]

[DOI]

SIAM J. Comput., 2000

The Complexity of Verifying the Characteristic Polynomial and Testing Similarity.

[BibT_eX]

[DOI]

Proceedings of the 15th Annual IEEE Conference on Computational Complexity, 2000

The Computational Complexity of Equivalence and Isomorphism Problems

[BibT_eX]

[DOI]

Lecture Notes in Computer Science 1852, Springer, ISBN: 3-540-41032-5, 2000

1998

The Isomorphism Problem for Read-Once Branching Programs and Arithmetic Circuits.

[BibT_eX]

[DOI]

Chic. J. Theor. Comput. Sci., 1998

Nonrelativizing Separations.

[BibT_eX]

[DOI]

Lance Fortnow

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

The Satisfiability Problem for Probabilistic Ordered Branching Programs.

[BibT_eX]

[DOI]

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

1996

On the Correlation of Symmetric Functions.

[BibT_eX]

[DOI]

Jin-yi Cai

Frederic Green

Math. Syst. Theory, 1996

The Isomorphismproblem for One-Time-Only Branching Programs

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1996

Modulo Information from Nonadaptive Queries to NP

[BibT_eX]

[DOI]

Richard Beigel

Electron. Colloquium Comput. Complex., 1996

The Complexity of Generating and Checking Proffs of Membership.

[BibT_eX]

[DOI]

Proceedings of the STACS 96, 1996

Pinpointing Computation with Modular Queries in the Boolean Hierarchy.

[BibT_eX]

[DOI]

Richard Beigel

Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1996

The Boolean Isomorphism Problem.

[BibT_eX]

[DOI]

Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

Complements of Multivalued Functions.

[BibT_eX]

[DOI]

Proceedings of the Eleveth Annual IEEE Conference on Computational Complexity, 1996

1995

Nondeterministically Selective Sets.

[BibT_eX]

[DOI]

Int. J. Found. Comput. Sci., 1995

Restricted Information from Nonadaptive Queries to NP.

[BibT_eX]

[DOI]

Yenjo Han

Proceedings of the Tenth Annual Structure in Complexity Theory Conference, 1995

1994

Complexity-Restricted Advice Functions.

[BibT_eX]

[DOI]

Johannes Köbler

SIAM J. Comput., 1994

A Note on SpanP Functions.

[BibT_eX]

[DOI]

Meena Mahajan

N. V. Vinodchandran

Inf. Process. Lett., 1994

On Closure Properties of GapP.

[BibT_eX]

[DOI]

Seinosuke Toda

Osamu Watanabe

Comput. Complex., 1994

On Sets Bounded Truth-Table Reducible to P-selective Sets.

[BibT_eX]

[DOI]

Seinosuke Toda

Osamu Watanabe

Proceedings of the STACS 94, 1994

On Functions Computable with Nonadaptive Queries to NP.

[BibT_eX]

[DOI]

Jim Kadin

Proceedings of the Ninth Annual Structure in Complexity Theory Conference, Amsterdam, The Netherlands, June 28, 1994

1993

Threshold Computation and Cryptographic Security.

[BibT_eX]

[DOI]

Yenjo Han

Lane A. Hemaspaandra

Proceedings of the Algorithms and Computation, 4th International Symposium, 1993

Selectivity.

[BibT_eX]

Proceedings of the Computing and Information, 1993

On Closure Properties of #P in the Context of PF°#P.

[BibT_eX]

[DOI]

Proceedings of the Eigth Annual Structure in Complexity Theory Conference, 1993

1992

Reductions to Sets of Low Information Content.

[BibT_eX]

Proceedings of the Complexity Theory: Current Research, 1992

1990

Complexity Classes with Advice.

[BibT_eX]

[DOI]

Johannes Köbler

Proceedings of the Proceedings: Fifth Annual Structure in Complexity Theory Conference, 1990

NP-uniforme Komplexitätsklassen.

[BibT_eX]

[DOI]