Thomas Thierauf

Daniel Padé

Inf. Comput., 2022

2021

Factorization of Polynomials Given by Arithmetic Branching Programs.

[BibT_eX]

[DOI]

Amit Sinhababu

Comput. Complex., 2021

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

[BibT_eX]

[DOI]

Pranjal Dutta

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]

Pranjal Dutta

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

Linear Matroid Intersection is in Quasi-NC.

[BibT_eX]

[DOI]

Comput. Complex., 2020

2019

A deterministic parallel algorithm for bipartite perfect matching.

[BibT_eX]

[DOI]

Commun. ACM, 2019

2017

Guest Column: Parallel Algorithms for Perfect Matching.

[BibT_eX]

[DOI]

SIGACT News, 2017

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

[BibT_eX]

[DOI]

Nisheeth K. Vishnoi

Electron. Colloquium Comput. Complex., 2017

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

[BibT_eX]

[DOI]

Comput. Complex., 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

2015

Bipartite Perfect Matching is in quasi-NC.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 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

A Kolmogorov complexity proof of the Lovász Local Lemma for satisfiability.

[BibT_eX]

[DOI]

Jochen Messner

Theor. Comput. Sci., 2012

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

[BibT_eX]

[DOI]

Christopher Umans

Dagstuhl Reports, 2012

2011

Planarizing Gadgets for Perfect Matching do not Exist.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 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

The Complexity of the Inertia.

[BibT_eX]

[DOI]

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

Planar Graph Isomorphism is in 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

2008

A Log-space Algorithm for Canonization of Planar Graphs

[BibT_eX]

[DOI]

CoRR, 2008

The Quantum Complexity of Group Testing.

[BibT_eX]

[DOI]

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

2007

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 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 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

2001

The Complexity of the Minimal Polynomial

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 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

1999

Complements of Multivalued Functions.

[BibT_eX]

[DOI]

Chic. J. Theor. Comput. Sci., 1999

1998

Functions Computable with Nonadaptive Queries to NP.

[BibT_eX]

[DOI]

Jim Kadin

Theory Comput. Syst., 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

1997

Threshold Computation and Cryptographic Security.

[BibT_eX]

[DOI]

Yenjo Han

Lane A. Hemaspaandra

SIAM J. Comput., 1997

The Satisfiability Problem for Probabilistic Ordered Branching Programs

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1997

1996

On the Correlation of Symmetric Functions.

[BibT_eX]

[DOI]

Jin-yi Cai

Frederic Green

Math. Syst. Theory, 1996

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

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1996

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

[BibT_eX]

[DOI]

Seinosuke Toda

Osamu Watanabe

RAIRO Theor. Informatics Appl., 1996

Restricted Information from Nonadaptive Queries to NP.

[BibT_eX]

[DOI]

Yenjo Han

Inf. Comput., 1996

The Isomorphismproblem for One-Time-Only Branching Programs

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1996

The Boolean Isomorphism Problem

[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

1995

Nondeterministically Selective Sets.

[BibT_eX]

[DOI]

Int. J. Found. Comput. Sci., 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

1993

Selectivity.

[BibT_eX]

Proceedings of the Computing and Information, 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]