Analyzing refutations of the well known 0pebbling formulas Peb$(G)$ we prove some new strong connections between pebble games and algebraic proof system, showing that there is a parallelism between the reversible, black and black-white pebbling games on one side, and the three algebraic proof systems Nullstellensatz, Monomial Calculus and Polynomial Calculus on the other side. In particular we prove that for any DAG $G$ with a single sink, if there is a Monomial Calculus refutation for Peb$(G)$ having simultaneously degree $s$ and size $t$ then there is a black pebbling strategy on $G$ with space $s$ and time $t+s$. Also if there is a black pebbling strategy for $G$ with space $s$ and time $t$ it is possible to extract from it a MC refutation for Peb$(G)$ having simultaneously degree $s$ and size $ts$. These results are analogous to those proven in {deRezende et al.21} for the case of reversible pebbling and Nullstellensatz. Using them we prove degree separations between NS, MC and PC, as well as strong degree-size tradeoffs for MC. We also notice that for any directed acyclic graph $G$ the space needed in a pebbling strategy on $G$, for the three versions of the game, reversible, black and black-white, exactly matches the variable space complexity of a refutation of the corresponding pebbling formula Peb$(G)$ in each of the algebraic proof systems NS, MC and PC. Using known pebbling bounds on graphs, this connection implies separations between the corresponding variable space measures.

The width complexity measure plays a central role in resolution and other propositional proof systems like Polynomial Calculus (under the name of degree). The study of width lower bounds is the most used method for proving size lower bounds, and it is known that for the mentioned proof systems, proofs with small width also imply the existence of proofs with small size. Not much has been studied, however, about the width parameter in the cutting planes (CP) proof system, a measure that was introduced by Dantchev and Martin in 2009 under the name of CP cutwidth. In this article, we study the width complexity of CP refutations of graph isomorphism formulas. For a pair of non-isomorphic graphs \(G\) and \(H\) , we show a direct connection between the Weisfeiler–Leman differentiation number \(\mathsf{WL}(G,H)\) of the graphs and the width of a CP refutation for the corresponding isomorphism formula \(\mathrm{Iso}(G,H)\) . In particular, we show that if \(\mathsf{WL}(G,H)\leq k\) , then there is a CP refutation of \(\mathrm{Iso}(G,H)\) with width \(k\) , and if \(\mathsf{WL}(G,H) \gt k\) , then there are no CP refutations of \(\mathrm{Iso}(G,H)\) with width \(k-2\) . Similar results are known for other proof systems, like Resolution, Sherali–Adams, or Polynomial Calculus. We also obtain polynomial-length CP refutations from our width bound for isomorphism formulas for graphs with constant Weisfeiler–Leman dimension. Furthermore, we notice that a length lower bound for refuting graph isomorphism formulas in the subsystem of tree-like cutting planes with polynomially bounded coefficients follows from known results.

We show that the number of variables and the quantifier depth needed to distinguish a pair of graphs by first-order logic sentences exactly match the complexity measures of clause width and depth needed to refute the corresponding graph isomorphism formula in propositional narrow resolution. Using this connection, we obtain upper and lower bounds for refuting graph isomorphism formulas in (normal) resolution. In particular, we show that if k is the minimum number of variables needed to distinguish two graphs with n vertices each, then there is an n O ( k ) resolution refutation size upper bound for the corresponding isomorphism formula, as well as lower bounds of 2 k -1 and k for the treelike resolution size and resolution clause space for this formula. We also show a (normal) resolution size lower bound of exp (Ω ( k 2 / n )) for the case of colored graphs with constant color class sizes. Applying these results, we prove the first exponential lower bound for graph isomorphism formulas in the proof system SRC-1, a system that extends resolution with a global symmetry rule, thereby answering an open question posed by Schweitzer and Seebach.

In this paper we show lower bounds for a certain large class of algorithms solving the Graph Isomorphism problem, even on expander graph instances. Spielman [25] shows an algorithm for isomorphism of strongly regular expander graphs that runs in time exp(O(n^(1/3)) (this bound was recently improved to expf O(n^(1/5) [5]). It has since been an open question to remove the requirement that the graph be strongly regular. Recent algorithmic results show that for many problems the Lasserre hierarchy works surprisingly well when the underlying graph has expansion properties. Moreover, recent work of Atserias and Maneva [3] shows that k rounds of the Lasserre hierarchy is a generalization of the k-dimensional Weisfeiler-Lehman algorithm for Graph Isomorphism. These two facts combined make the Lasserre hierarchy a good candidate for solving graph isomorphism on expander graphs. Our main result rules out this promising direction by showing that even Omega(n) rounds of the Lasserre semidefinite program hierarchy fail to solve the Graph Isomorphism problem even on expander graphs.

Abstract We show a new connection between the clause space measure in tree-like resolution and the reversible pebble game on graphs. Using this connection, we provide several formula classes for which there is a logarithmic factor separation between the clause space complexity measure in tree-like and general resolution. We also provide upper bounds for tree-like resolution clause space in terms of general resolution clause and variable space. In particular, we show that for any formula F, its tree-like resolution clause space is upper bounded by space $$(\pi)$$ ( π ) $$(\log({\rm time}(\pi))$$ ( log ( time ( π ) ) , where $$\pi$$ π is any general resolution refutation of F. This holds considering as space $$(\pi)$$ ( π ) the clause space of the refutation as well as considering its variable space. For the concrete case of Tseitin formulas, we are able to improve this bound to the optimal bound space $$(\pi)\log n$$ ( π ) log n , where n is the number of vertices of the corresponding graph

Lubiw showed that several variants of Graph Isomorphism are NP-complete, where the solutions are required to satisfy certain additional constraints [SICOMP 10, 1981]. One of these, called Isomorphism With Restrictions, is to decide for two given graphs X_1=(V,E_1) and X_2=(V,E_2) and a subset R\subseteq V\times V of forbidden pairs whether there is an isomorphism \pi from X_1 to X_2 such that i^\pi\ne j for all (i,j)\in R. We prove that this problem and several of its generalizations are in fact in \FPT: - The problem of deciding whether there is an isomorphism between two graphs that moves k vertices and satisfies Lubiw-style constraints is in FPT, with k and the size of R as parameters. The problem remains in FPT even if a conjunction of disjunctions of such constraints is allowed. As a consequence of the main result it follows that the problem to decide whether there is an isomorphism that moves exactly k vertices is in FPT. This solves a question left open in our article on exact weight automorphisms [STACS 2017]. - When the number of moved vertices is unrestricted, finding isomorphisms that satisfy a CNF of Lubiw-style constraints can be solved in FPT with access to a GI oracle. - Checking if there is an isomorphism π between two graphs with complexity t is also in FPT with t as parameter, where the complexity of a permutation is the Cayley measure defined as the minimum number t such that \pi can be expressed as a product of t transpositions. - We consider a more general problem in which the vertex set of a graph X is partitioned into Red and Blue, and we are interested in an automorphism that stabilizes Red and Blue and moves exactly k vertices in Blue, where k is the parameter. This problem was introduced by [Downey and Fellows 1999], and we showed [STACS 2017] that it is W[1]-hard even with color classes of size 4 inside Red. Now, for color classes of size at most 3 inside Red, we show the problem is in FPT. In the non-parameterized setting, all these problems are NP-complete. Also, they all generalize in several ways the problem to decide whether there is an isomorphism between two graphs that moves at most k vertices, shown to be in FPT by Schweitzer [ESA 2011].

We show that checking if a given hypergraph has an automorphism that moves exactly k vertices is fixed parameter tractable, using k and additionally either the maximum hyperedge size or the maximum color class size as parameters. In particular, it suffices to use k as parameter if the hyperedge size is at most polylogarithmic in the size of the given hypergraph. As a building block for our algorithms, we generalize Schweitzer's FPT algorithm [ESA 2011] that, given two graphs on the same vertex set and a parameter k, decides whether there is an isomorphism between the two graphs that moves at most k vertices. We extend this result to hypergraphs, using the maximum hyperedge size as a second parameter. Another key component of our algorithm is an orbit-shrinking technique that preserves permutations that move few points and that may be of independent interest. Applying it to a suitable subgroup of the automorphism group allows us to switch from bounded hyperedge size to bounded color classes in the exactly-k case.

The Graph Isomorphism problem restricted to graphs of bounded treewidth or bounded tree distance width are known to be solvable in polynomial time. We give restricted space algorithms for these problems proving the following results: • Isomorphism for bounded tree distance width graphs is in L and thus complete for the class. We also show that for this kind of graphs a canon can be computed within logspace. • For bounded treewidth graphs, when both input graphs are given together with a tree decomposition, the problem of whether there is an isomorphism which respects the decompositions (i.e. when only isomorphisms are considered, mapping bags in one decomposition blockwise onto bags in the other decomposition) is in L. • For bounded treewidth graphs, when one of the input graphs is given with a tree decomposition the isomorphism problem is in LogCFL. • As a corollary the isomorphism problem for bounded treewidth graphs is in LogCFL. This improves the known TC 1 upper bound for the problem given by Grohe and Verbitsky.

The group isomorphism problem consists in deciding whether two input groups G/sup 1/ and G/sup 2/ given by their multiplication tables are isomorphic. We first give a 2-round Arthur-Merlin protocol for the group non-isomorphism problem such that on input groups (G/sup 1/, G/sup 2/) of size n, Arthur uses O(log/sup 6/ n) random bits and Merlin uses O(log/sup 2/ n) nondeterministic bits. We derandomize this protocol for the case of solvable groups showing the following two results: (a) We give a uniform NP machine for solvable group non-isomorphism, that works correctly on all but 2/sup polylog(n)/ inputs of any length n. Furthermore, this NP machine is always correct when the input groups are nonisomorphic. The NP machine is obtained by an unconditional derandomization of the AM protocol. (b) Under the assumption that EXP /spl nsube/ i.o.PSPACE we get a complete derandomization of the above AM protocol. Thus, EXP /spl nsube/ i.o.PSPACE implies that group isomorphism for solvable groups is in NP /spl cap/ coNP.

We show that the graph isomorphism problem is hard under DLOGTIME uniform AC{$^0$} many-one reductions for the complexity classes NL, PL (probabilistic logarithmic space) for every logarithmic space modular class {Mod}$_k$L and for the class DET of problems NC{$^1$} reducible to the determinant. These are the strongest known hardness results for the graph isomorphism problem and imply a randomized logarithmic space reduction from the perfect matching problem to graph isomorphism. We also investigate hardness results for the graph automorphism problem.

We show that the graph isomorphism problem is hard under logarithmic space many-one reductions for the complexity classes NL, PL (probabilistic logarithmic space), for every logarithmic space modular class Mod/sub k/L and for the class DET of problems NC/sup 1/ reducible to the determinant. These are the strongest existing hardness results for the graph isomorphism problem, and imply a randomized logarithmic space reduction from the perfect matching problem to graph isomorphism.

We prove that the tree isomorphism problem, when trees are encoded as strings, is NC/sup 1/-hard under DLOGTIME-reductions. NC/sup 1/-completeness thus follows from Buss's recent NC/sup 1/ upper bound. By contrast, we prove that testing isomorphism of two trees encoded as pointer lists is L-complete.

In this paper we design a nonadaptive NC checker for permutation group intersection, sharpening a result from M. Blum and S. Kannan (1995). This is a consequence of two results. First we show that a nontrivial permutation in the intersection of two given permutation groups (described by lists of generators) can be computed by an NC algorithm with one round of parallel queries to the group intersection problem. Next we design a two-round interactive proof system for the complement of the group intersection problem, for which the honest prover can be simulated by an NC algorithm with one round of parallel queries to group intersection. As a consequence we also have nonadaptive NC checkers for some related group-theoretic problems. On the technical side, we define a generalization of wreath products of permutation groups. This product plays a crucial role in the design of the nonadaptive checkers.

We study the polynomial time counting hierarchy, a hierarchy of complexity classes related to the notion of counting. We investigate some of their structural properties, settling many open questions dealing with oracle characterizations, closure under boolean operations, and relations with other complexity classes. We develop a new combinatorial technique to obtain relativized separations for some of the studied classes, which imply absolute separations for some logarithmic time bounded complexity classes.

We introduce a new combinatorial technique to obtain relativized separations of certain complexity classes related to the idea of counting, like PP, G (exact counting), and ¿P (parity). To demonstrate its usefulness we present three relativizations separating NP from G, NP from ¿P and ¿P from PP. Other separations follow from these results, and as a consequence we obtain an oracle separating PP from PSPACE, thus solving an open problem proposed by Angluin in [An,80]. From the relativized separations to obtain absolute separations for counting complexity classes with log-time bounded computation time.