Number of Variables for Graph Differentiation and the Resolution of GI Formulas. | 0 | 0.34 | 2022 |
Pure Nash Equilibria in a Generalization of Congestion Games Allowing Resource Failures. | 0 | 0.34 | 2021 |
Reversible Pebble Games and the Relation Between Tree-Like and General Resolution Space | 0 | 0.34 | 2019 |
Cops-Robber Games and the Resolution of Tseitin Formulas. | 0 | 0.34 | 2018 |
Algebraic Methods in Computational Complexity (Dagstuhl Seminar 16411). | 0 | 0.34 | 2018 |
Parameterized Complexity of Small Weight Automorphisms. | 0 | 0.34 | 2017 |
Finding Small Weight Isomorphisms with Additional Constraints is Fixed-Parameter Tractable. | 0 | 0.34 | 2017 |
A Deterministic Algorithm For Testing The Equivalence Of Read-Once Branching Programs With Small Discrepancy | 0 | 0.34 | 2017 |
CNF and DNF succinct graph encodings. | 1 | 0.37 | 2017 |
Solution-Graphs of Boolean Formulas and Isomorphism1 | 0 | 0.34 | 2016 |
Lowness results: the next generation. | 0 | 0.34 | 2015 |
The Graph Isomorphism Problem (Dagstuhl Seminar 15511). | 2 | 0.39 | 2015 |
Succinct Encodings of Graph Isomorphism. | 4 | 0.42 | 2014 |
Solving Linear Equations Parameterized by Hamming Weight. | 0 | 0.34 | 2014 |
On the resolution complexity of graph non-isomorphism | 4 | 0.41 | 2013 |
Solvable Group Isomorphism Is (Almost) in NP ∩ coNP | 6 | 0.51 | 2011 |
Graph Isomorphism is Not AC0-Reducible to Group Isomorphism | 3 | 0.43 | 2010 |
Restricted space algorithms for isomorphism on bounded treewidth graphs | 7 | 0.46 | 2009 |
The Complexity of Planar Graph Isomorphism. | 2 | 0.38 | 2009 |
Reductions to Graph Isomorphism | 0 | 0.34 | 2007 |
The complexity of quasigroup isomorphism and the minimum generating set problem | 1 | 0.37 | 2006 |
Corrigendum to “Completeness results for graph isomorphism” [J. Comput. System Sci. 66 (2003) 549–566] | 0 | 0.34 | 2006 |
A note on the size of Craig Interpolants | 2 | 0.36 | 2006 |
Arthur-Merlin games and the problem of isomorphism testing | 0 | 0.34 | 2005 |
Isomorphism Testing: Perspective and Open Problems | 15 | 0.69 | 2005 |
Solvable Group Isomorphism | 2 | 0.40 | 2004 |
Solvable Group Isomorphism is (almost) in NP\cap coNP | 2 | 0.39 | 2004 |
On the hardness of graph isomorphism | 34 | 1.94 | 2004 |
Space and Width in Propositional Resolution (Column: Computational Complexity) | 1 | 0.35 | 2004 |
Optimal proof systems imply complete sets for promise classes | 25 | 0.94 | 2003 |
A combinatorial characterization of treelike resolution space | 18 | 0.73 | 2003 |
Completeness results for graph isomorphism | 27 | 0.98 | 2003 |
The Complexity of Graph Isomorphism for Colored Graphs with Color Classes of Size 2 and 3 | 2 | 0.40 | 2002 |
Space bounds for resolution | 58 | 1.94 | 2001 |
Minimally Unsatisfiable CNF Formulas | 5 | 0.41 | 2001 |
Nondeterministic Instance Complexity and Hard-to-Prove Tautologies | 2 | 0.42 | 2000 |
Lower Bounds for Space in Resolution | 12 | 0.69 | 1999 |
Sparse Sets, Approximable Sets, and Parallel Queries to NP | 3 | 0.38 | 1998 |
A nonadaptive NC checker for permutation group intersection | 3 | 0.40 | 1997 |
Optimal Proof Systems for Propositional Logic and Complete Sets | 13 | 0.86 | 1997 |
The power of the middle bit of a #P function | 28 | 1.18 | 1995 |
Computing functions with parallel queries to NP | 31 | 1.82 | 1993 |
Parallel Approximation Schemes for problems on planar graphs (Extended Abstract) | 0 | 0.34 | 1993 |
On the nonuniform complexity of the graph isomorphism problem | 13 | 0.82 | 1992 |
The power of the middle bit | 13 | 1.62 | 1992 |
Graph Isomorphism is Low for PP | 22 | 2.46 | 1992 |
Complexity classes defined by counting quantifiers | 70 | 3.06 | 1991 |
The Minsumcut Problem | 12 | 0.81 | 1991 |
Self-Reducible Sets of Small Sensity | 1 | 0.37 | 1991 |
Classes of Bounded Nondeterminism. | 34 | 2.91 | 1990 |