Author name cluster
Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.
STOC Conference 2019 Conference Paper
We outline how to turn the author's quasipolynomial-time graph isomorphism test into a construction of a canonical form within the same time bound. The proof involves a nontrivial modification of the central symmetry-breaking tool, the construction of a canonical relational structure of logarithmic arity on the ideal domain based on local certificates.
STOC Conference 2016 Conference Paper
We show that the Graph Isomorphism (GI) problem and the more general problems of String Isomorphism (SI) andCoset Intersection (CI) can be solved in quasipolynomial(exp((logn)O(1))) time. The best previous bound for GI was exp(O( √n log n)), where n is the number of vertices (Luks, 1983); for the other two problems, the bound was similar, exp(O~(√ n)), where n is the size of the permutation domain (Babai, 1983). Following the approach of Luks’s seminal 1980/82 paper, the problem we actually address is SI. This problem takes two strings of length n and a permutation group G of degree n (the “ambient group”) as input (G is given by a list of generators) and asks whether or not one of the strings can be transformed into the other by some element of G. Luks’s divide-and-conquer algorithm for SI proceeds by recursion on the ambient group. We build on Luks’s framework and attack the obstructions to efficient Luks recurrence via an interplay between local and global symmetry. We construct group theoretic “local certificates” to certify the presence or absence of local symmetry, aggregate the negative certificates to canonical k-ary relations where k = O(log n), and employ combinatorial canonical partitioning techniques to split the k-ary relational structure for efficient divide-and- conquer. We show that in a well–defined sense, Johnson graphs are the only obstructions to effective canonical partitioning. The central element of the algorithm is the “local certificates” routine which is based on a new group theoretic result, the “Unaffected stabilizers lemma,” that allows us to construct global automorphisms out of local information.
FOCS Conference 2013 Conference Paper
We show that a canonical form for strongly regular (s. r.) graphs can be found in time exp(O~(n1/5)) and therefore isomorphism of s. r. graphs can be tested within the same time bound, where n is the number of vertices and the tilde hides a polylogarithmic factor. The best previous bound for testing isomorphism of s. r. graphs was exp(O~(n1/3)) (Spiel man, STOC 1996) while the bound for GI in general has been standing firmly at exp(O~(n1/2)) for three decades. (These results, too, provided canonical forms.) The previous bounds on isomorphism of s. r. graphs (Babai 1980 and Spiel man 1996) were based on the analysis of the classical individualization/refinement (I/R) heuristic. The present bound depends on a combination of a deeper analysis of the I/R heuristic with Luks's group theoretic divide-and-conquer methods following Babai-Luks (STOC 1983) and Miller (1983). Our analysis builds on Spiel man's work that brought Neumaier's 1979 classification of s. r. graphs to bear on the problem. One of Neumaier's classes, the line-graphs of Steiner 2-designs, has been eliminated as a bottleneck in recent work by the present authors (STOC'13). In the remaining hard cases, we have the benefit of Neumaier's claw bound" and its asymptotic consequences derived by Spiel man, some of which we improve via a new "clique geometry. " We also prove, by an analysis of the I/R heuristic, that, with known (trivial) exceptions, s. r. graphs have exp(O~(n9/37)) automorphisms, improving Spiel man's exp(O~(n1/3)) bound. No knowledge of group theory is required for this paper. The group theoretic method is only used through an easily stated combinatorial consequence (Babai -- Luks, 1983 combined with Miller, 1983). While the bulk of this paper is joint work by the five authors, it also includes two contributions by subsets of the authors: the clique geometry [BW] and the auto orphism bound [CST]. "
STOC Conference 2013 Conference Paper
A Steiner 2-design is a finite geometry consisting of a set of "points" together with a set of "lines" (subsets of points of uniform cardinality) such that each pair of points belongs to exactly one line. In this paper we analyse the individualization/refinement heuristic and conclude that after individualizing O(log n) points (assigning individual colors to them), the refinement process gives each point an individual color. The following consequences are immediate: (a) isomorphism of Steiner 2-designs can be tested in n O(log n) time, where n is the number of lines; (b) a canonical form of Steiner 2-designs can be computed within the same time bound; (c) all isomorphisms between two Steiner 2-designs can be listed within the same time bound; (d) the number of automorphisms of a Steiner 2-design is at most n O(log n) (a fact of interest to finite geometry and group theory.) The best previous bound in each of these four statements was moderately exponential, exp(~O(n 1/4 )) (Spielman, STOC'96). Our result removes an exponential bottleneck from Spielman's analysis of the Graph Isomorphism problem for strongly regular graphs. The results extend to Steiner t-designs for all t≥2. Strongly regular (s.r.) graphs have been known as hard cases for graph isomorphism testing; the best previously known bound for this case is moderately exponential, exp(~O(n 1/3 )) where n is the number of vertices (Spielman, STOC'96). Line graphs of Steiner 2-designs enter as a critical subclass via Neumaier's 1979 classification of s.r. graphs. Previously, n O(log n) isomorphism testing and canonical forms for Steiner 2-designs was known for the case when the lines of the Steiner 2-design have bounded length (Babai and Luks, STOC'83). That paper relied on Luks's group-theoretic divide-and-conquer algorithms and did not yield a subexponential bound on the number of automorphisms. To analyse the individualization/refinement heuristic, we develop a new structure theory of Steiner 2-designs based on the analysis of controlled growth and on an addressing scheme that produces a hierarchy of increasing sets of pairwise independent, uniformly distributed points. This scheme represents a new expression of the structural homogeneity of Steiner 2-designs that allows applications of the second moment method. We also address the problem of reconstruction of Steiner 2-designs from their line-graphs beyond the point of unique reconstructability, in a manner analogous to list-decoding, and as a consequence achieve an exp(~O(n 1/6 )) bound for isomorphism testing for this class of s.r. graphs. Results, essentially identical to our main results, were obtained simultaneously by Xi Chen, Xiaorui Sun, and Shang-Hua Teng, building on a different philosophy and combinatorial structure theory than the present paper. They do not claim an analysis of the individualization/refinement algorithm but of a more complex combinatorial algorithm. We comment on how this paper fits into the overall project of improved isomorphism testing for strongly regular graphs (the ultimate goal being subexponential (exp(n o(1) )) time). In the remaining cases we need to deal with s.r. graphs satisfying "Neumaier's claw bound," permitting the use of a separate set of asymptotic structural tools. In joint work (in progress) with Chen, Sun, and Teng, we address that case and have already pushed the overall bound below exp(~O(n 1/4 )) The present paper is a methodologically distinct and stand-alone part of the overall project.
SODA Conference 2011 Conference Paper
The isomorphism problem for groups given by their multiplication tables has long been known to be solvable in time n log n+O (1). The decades-old quest for a polynomial-time algorithm has focused on the very difficult case of class-2 nilpotent groups (groups whose quotient by their center is abelian), with little success. In this paper we consider the opposite end of the spectrum and initiate a more hopeful program to find a polynomial-time algorithm for semisimple groups, defined as groups without abelian normal subgroups. First we prove that the isomorphism problem for this class can be solved in time n O (log log n ). We then identify certain bottlenecks to polynomial-time solvability and give a polynomial-time solution to a rich subclass, namely the semisimple groups where each minimal normal subgroup has a bounded number of simple factors. We relate the results to the filtration of groups introduced by Babai and Beals (1999). One of our tools is an algorithm for equivalence of (not necessarily linear) codes in simply-exponential time in the length of the code, obtained by modifying Luks's algorithm for hypergraph isomorphism in simply-exponential time in the number of vertices (FOCS 1999). We comment on the complexity of the closely related problem of permutational isomorphism of permutation groups.
MFCS Conference 2010 Conference Paper
Abstract We consider Boolean exact threshold functions defined by linear equations, and in general degree d polynomials. We give upper and lower bounds on the maximum magnitude (absolute value) of the coefficients required to represent such functions. These bounds are very close and in the linear case in particular they are almost matching. The quantity is the same as the maximum magnitude of integer coefficients of linear equations required to express every possible intersection of a hyperplane in R n and the Boolean cube {0, 1} n, or in the general case intersections of hypersurfaces of degree d in R n and the Boolean cube {0, 1} n. In the process we construct new families of ill-conditioned matrices. We further stratify the problem (in the linear case) in terms of the dimension k of the affine subspace spanned by the solutions, and give upper and lower bounds in this case as well. Our bounds here in terms of k leave a substantial gap, a challenge for future work.
STOC Conference 2009 Conference Paper
We consider matrix groups, specified by a list of generators, over finite fields. The two most basic questions about such groups are membership in and the order of the group. Even in the case of abelian groups it is not known how to answer these questions without solving hard number theoretic problems (factoring and discrete log); in fact, constructive membership testing in the case of 1 × 1 matrices is precisely the discrete log problem. So the reasonable question is whether these problems are solvable in randomized polynomial time using number theory oracles. Building on 25 years of work, including remarkable recent developments by several groups of authors, we are now able to determine the order of a matrix group over a finite field of odd characteristic, and to perform constructive membership testing in such groups, in randomized polynomial time, using oracles for factoring and discrete log. One of the new ingredients of this result is the following. A group is called semisimple if it has no abelian normal subgroups. For matrix groups over finite fields, we show that the order of the largest semisimple quotient can be determined in randomized polynomial time (no number theory oracles required and no restriction on parity). As a by-product, we obtain a natural problem that belongs to BPP and is not known to belong either to RP or to coRP. No such problem outside the area of matrix groups appears to be known. The problem is the decision version of the above: Given a list A of nonsingular d × d matrices over a finite field and an integer N, does the group generated by A have a semisimple quotient of order > N? We also make progress in the area of constructive recognition of simple groups, with the corollary that for a large class of matrix groups, our algorithms become Las Vegas.
FOCS Conference 2008 Conference Paper
We give an algorithm to decide isomorphism of hypergraphs of rank k in time exp (Otilde(k 2 radicn)), where n is the number of vertices. (The rank is the maximum size of edges; the tilde refers to a polylogarithmic factor.) The case of bounded k answers a 24-year-old question and removes an obstacle to improving the worst case-bound for Graph Isomorphism testing. The best previously known bound, even for k = 3, was C n (Luks 1999).
SODA Conference 2008 Conference Paper
SODA Conference 2007 Conference Paper
SODA Conference 2006 Conference Paper
SODA Conference 2005 Conference Paper
SODA Conference 2004 Conference Paper
SODA Conference 2004 Conference Paper
FOCS Conference 2003 Conference Paper
Cyclic linear codes of block length n over a finite field F/sub q/ are the linear subspaces of F/sub q//sup n/ that are invariant under a cyclic shift of their coordinates. A family of codes is good if all the codes in the family have constant rate and constant normalized distance (distance divided by block length). It is a long-standing open problem whether there exists a good family of cyclic linear codes based on F. J. MacWilliams and N. J. A. Sloane (1977). A code C is r-testable if there exist a randomized algorithm which, given a word x /spl isin/ F/sub q//sup n/, adaptively selects r positions, checks the entries of x in the selected positions, and makes a decision (accept or reject x) based on the positions selected and the numbers found, such that (i) if x /spl isin/ C then x is surely accepted; (ii) if dist(x, C) /spl ges/ /spl epsi/n then x is probably rejected (dist refers to Hamming distance). A family of codes is locally testable if all members of the family are r-testable for some constant r. This concept arose from holographic proofs/PCPs. O. Goldreich and M. Sudan (2002) asked whether there exist good, locally testable families of codes. In this paper we address the intersection of the two questions stated.
SODA Conference 2000 Conference Paper
STOC Conference 1998 Conference Paper
MFCS Conference 1997 Invited Paper
Abstract We discuss some aspects of two-party and multi-party communication complexity theory. The topics include a sample from the long list of connections of communication complexity to other models of computation which provide strong motivation to the study of this subject; separation results for restricted models such as simultaneous and one-way communication; some counter-intuitive upper bounds in these models; a new model called “communication with help, ” and a lower bound technique in this model, based on discrete Fourier analysis and multi-color discrepancy. Most of the recent results surveyed are joint work with my former and current students Anna Gál, Tom Hayes, Peter Kimmel, Satya V. Lokam.
STOC Conference 1997 Invited Paper
SODA Conference 1997 Conference Paper
STOC Conference 1996 Conference Paper
SODA Conference 1996 Conference Paper
FOCS Conference 1993 Conference Paper
We consider algorithms in finite groups, given by a list of generators. We give polynomial time Las Vegas algorithms (randomized, with guaranteed correct output) for basic problems for finite matrix groups over the rationals (and over algebraic number fields): testing membership, determining the order, finding a presentation (generators and relations), and finding basic building blocks: center, composition factors, and Sylow subgroups. These results extend previous work on permutation groups into the potentially more significant domain of matrix groups. Such an extension has until recently been considered intractable. In case of matrix groups G of characteristic p, there are two basic types of obstacles to polynomial-time computation: number theoretic (factoring, discrete log) and large Lie-type simple groups of the same characteristic p involved in the group. The number theoretic obstacles are inherent and appear already in handling abelian groups. They can be handled by moderately efficient (subexponential) algorithms. We are able to locate all the nonabelian obstacles in a normal subgroup N and solve all problems listed above for G/N. >
FOCS Conference 1993 Conference Paper
We prove the following about the Nearest Lattice Vector Problem (in any l/sub p/ norm), the Nearest Code-word Problem for binary codes, the problem of learning a halfspace in the presence of errors, and some other problems. 1. Approximating the optimum within any constant factor is NP-hard. 2. If for some /spl epsiv/>0 there exists a polynomial time algorithm that approximates the optimum within a factor of 2/sup log(0. 5-/spl epsiv/)/ /sup n/ then NP is in quasi-polynomial deterministic time: NP/spl sube/DTIME(n/sup poly(log/ /sup n)/). Moreover, we show that result 2 also holds for the Shortest Lattice Vector Problem in the l/sub /spl infin// norm. Improving the factor 2/sup log(0. 5-/spl epsiv/)/ /sup n/ to /spl radic/(dim) for either of the lattice problems would imply the hardness of the Shortest Vector Problem in l/sub 2/ norm; an old open problem. Our proofs use reductions from few-prover, one-round interactive proof systems, either directly, or through a set-cover problem. >
SODA Conference 1992 Conference Paper
STOC Conference 1992 Conference Paper
FOCS Conference 1991 Conference Paper
The asymptotic stability and complexity of floating point manipulation of representations of a finite group G are considered, especially splitting them into irreducible constituents and deciding their equivalence. Using rapid mixing estimates for random walks, the authors analyze a classical algorithm by J. Dixon (1970). They find that both its stability and complexity critically depend on the diameter d=diam(G, S) (S is the set that generates G). They propose a worst-case speedup by using Erdos-Renyi generators and modifying the Dixon averaging method. The overall effect in asymptotic complexity is a guaranteed (n log mod G mod )/sup O(1)/ running time. >
STOC Conference 1991 Conference Paper
STOC Conference 1991 Conference Paper
STOC Conference 1991 Conference Paper
FOCS Conference 1990 Conference Paper
Hash P functions are characterized by certain straight-line programs of multivariate polynomials. The power of this characterization is illustrated by a number of consequences. These include a somewhat simplified proof of S. Toda's (1989) theorem that PH contained in P/sup Hash P/, as well as an infinite class of potentially inequivalent checkable functions. >
FOCS Conference 1990 Conference Paper
The exact power of two-prover interactive proof systems (MIP) introduced by M. Ben-Or et al. (Proc. 20th Symp. on Theory of Computing, 1988, p. 113-31) is determined. In this system, two all-powerful noncommunicating provers convince a randomizing polynomial-time verifier in polynomial time that the input x belongs to the language L. It was previously suspected (and proved in a relativized sense) that coNP-complete languages do not admit such proof systems. In sharp contrast, it is shown that the class of languages having two-prover interactive proof systems is computable in nondeterministic exponential time (NEXP). This represents a further step demonstrating the unexpectedly immense power for randomization and interaction in efficient provability. >
FOCS Conference 1990 Conference Paper
The diameter of a group G with respect to a set S of generators is the maximum over g in G of the length of the shortest word in S union S/sup -1/ representing g. This concept arises in the contexts of efficient communication networks and Rubik's-cube-type puzzles. 'Best' generators are pertinent to networks, whereas 'worst' and 'average' generators seem more adequate models for puzzles. A substantial body of recent work on these subjects by the authors is surveyed. Regarding the 'best' case, it is shown that, although the structure of the group is essentially irrelevant if mod S mod is allowed to exceed (log mod G mod )/sup 1+c/(c>0), it plays a strong role when mod S mod =O(1). >
FOCS Conference 1989 Conference Paper
The bit complexity of computing irreducible representations of finite groups is considered. Exact computations in algebraic number fields are performed symbolically. A polynomial-time algorithm for finding a complete set of inequivalent irreducible representations over the field of complex numbers of a finite group given by its multiplication table is presented. It follows that some representative of each equivalence class of irreducible representations admits a polynomial-size description. The problem of decomposing a given representation V of the finite group G over an algebraic number field F into absolutely irreducible constituents is considered. It is shown that this can be done in deterministic polynomial time if V is given by the list of matrices (V(g); g in G) and in randomized (Las Vegas) polynomial time under the more concise input (V(g); g in S), where S is a set of generators of G. >
STOC Conference 1989 Conference Paper
I&C Journal 1989 Journal Article
The problem of proving membership in languages accepted by interactive proof protocols is reduced to the problem of estimating the number of leaves in certain trees. Using this reduction, we present a direct proof that every language accepted by an interactive protocol whithin g(n) rounds is also accepted by an Arthur Merlin game within ⌈ g(n) 2 ⌉ rounds. This unifies the proofs of the two main positive results on the IP Hierarchy, namely: that private coin tossing can be replaced by public coin tossing, and that the numer of interactions can be reduced by a constant factor.
FOCS Conference 1988 Conference Paper
Novel algorithms for computation in permutation groups are presented. They provide an order-of-magnitude improvement in the worst-case analysis of the basic permutation-group problems, including membership testing and computing the order of the group. For deeper questions about the group, including finding composition factors, an improvement of up to four orders of magnitude is realized. These and other essential investigations are all accomplished in O(n/sup 4/log/sup c/n) time. The approach is distinguished by its recognition and use of the intrinsic structure of the group at hand. >
I&C Journal 1988 Journal Article
Up to now, few models of computation with the power of evaluating discontinuous functions have been analyzed and few of their lower bounds or results on the decidability of languages are known. In this paper, we present a model of an “analytic computation tree” (ACT). These trees operate on real numbers and are able to compare real numbers, to evaluate functions on real numbers, and to evaluate certain discontinuous functions like the “floor function. ” This model generalizes the model of “algebraic computation trees” introduced by Ben Or. We show by topological arguments that by ACTs one cannot decide certain classes of languages, examples of which are Q n and the set of tuples (x1, …, xn ) ∈ R n that have components which are Z -linearly or algebraically dependent.
STOC Conference 1987 Conference Paper
We show that the basic problems of permutation group manipulation admit efficient parallel solutions. Given a permutation group G by a list of generators, we find a set of NC-efficient strong generators in NC. Using this, we show, that the following problems are in NC: membership in G; determining the order of G; finding the center of G; finding a composition series of G along with permutation representations of each composition factor. Moreover, given G, we are able to find the pointwise stabilizer of a set in NC. One consequence is that isomorphism of graphs with bounded multiplicity of eigenvalues is in NC. The analysis of the algorithms depends, in several ways, on consequences of the classification of finite simple groups.
FOCS Conference 1986 Conference Paper
FOCS Conference 1986 Conference Paper
We take a complexity theoretic view of A. C. Yao's theory of communication complexity. A rich structure of natural complexity classes is introduced. Besides providing a more structured approach to the complexity of a variety of concrete problems of interest to VLSI, the main objective is to exploit the analogy between Turing machine (TM) and communication complexity (CC) classes. The latter provide a more amicable environment for the study of questions analogous to the most notorious problems in TM complexity. Implicitly, CC classes corresponding to P, NP, coNP, BPP and PP have previously been considered. Surprisingly, pcc = Npcc ∩ coNPcc is known [AUY]. We develop the definitions of PSPACEcc and of the polynomial time hierarchy in CC. Notions of reducibility are introduced and a natural complete member in each class is found. BPPcc ⊆ Σ2cc ∩ Π2cc [Si2] remains valid. We solve the question that BPPcc ⊉ NPcc by proving an Ω(√n) lower bound for the bounded-error complexity of the coNPcc- complete problem "disjointness". Similar lower bounds follow for essentially any nontrivial monotone graph property. Another consequence is that the deterministically exponentially hard "equality" relation is not NPcc-hard with respect to oracle-protocol reductions. We prove that the distributional complexity of the disjointness problem is O(√n log n) under any product measure on {0, 1}n × {0, 1}n. This points to the difficulty of improving the Ω(√n) lower bound for the B2PP complexity of "disjointness". The variety of counting and probabilistic classes appears to be greater than in the Turing machine versions. Many of the simplest graph problems (undirected reachability, planarity, bipartiteness, 2-CNF-satisfiability) turn out to be PSPACEcc-hard. The main open problem remains the separation of the hierarchy, more specifically, the conjecture that Σ2cc ≠ Π2cc. Another major problem is to show that PSPACEcc and the probabilistic class UPPcc are not comparable.
STOC Conference 1986 Conference Paper
STOC Conference 1985 Conference Paper
In a previous paper [BS] we proved, using the elements of the theory of nilpotent groups , that some of the fundamental computational problems in matriz groups belong to NP . These problems were also shown to belong to coNP , assuming an unproven hypothesis concerning finite simple groups . The aim of this paper is to replace most of the (proven and unproven) group theory of [BS] by elementary combinatorial arguments. The result we prove is that relative to a random oracle B , the mentioned matrix group problems belong to ( NP∩coNP ) B . The problems we consider are membership in and order of a matrix group given by a list of generators. These problems can be viewed as multidimensional versions of a close relative of the discrete logarithm problem. Hence NP∩coNP might be the lowest natural complexity class they may fit in. We remark that the results remain valid for black box groups where group operations are performed by an oracle. The tools we introduce seem interesting in their own right. We define a new hierarchy of complexity classes AM ( k ) “just above NP ”, introducing Arthur vs. Merlin games , the bounded-away version of Papdimitriou's Games against Nature . We prove that in spite of their analogy with the polynomial time hierarchy, the finite levels of this hierarchy collapse to AM=AM (2). Using a combinatorial lemma on finite groups [BE], we construct a game by which the nondeterministic player (Merlin) is able to convince the random player (Arthur) about the relation [ G ]= N provided Arthur trusts conclusions based on statistical evidence (such as a Slowly-Strassen type “proof” of primality). One can prove that AM consists precisely of those languages which belong to NP B for almost every oracle B . Our hierarchy has an interesting, still unclarified relation to another hierarchy, obtained by removing the central ingredient from the User vs. Expert games of Goldwasser, Micali and Rackoff.
FOCS Conference 1984 Conference Paper
We build a theory of black box groups, and apply it to matrix groups over finite fields. Elements of a black box group are encoded by strings of uniform length and group operations are performd by an oracle. Subgroups are given by a list of generators. We prove that for such subgroups, membership and divisor of the order are in NP B. (B is the group box oracle.) Under a plausible mathematical hypothesis on short presentations of finite simple groups, nom membership and exaact order will also be in NP B and thus in NP B ∩ NP B.
STOC Conference 1983 Conference Paper
We announce an algebraic approach to the problem of assigning canonical forms to graphs. We compute canonical forms and the associated canonical labelings (or renumberings) in polynomial time for graphs of bounded valence, in moderately exponential, exp(n ½ + ο(1) ),time for general graphs, in subexponential, n log n , time for tournaments and for 2-(ν,κ,λ) block designs with κ,λ bounded and n log log n time for λ-planes (symmetric designs) with λ bounded. We prove some related problems NP-hard and indicate some open problems.
FOCS Conference 1983 Conference Paper
We address the graph isomorphism problem and related fundamental complexity problems of computational group theory. The main results are these: A1. A polynomial time algorithm to test simplicity and find composition factors of a given permutation group (COMP). A2. A polynomial time algorithm to find elements of given prime order p in a permutation group of order divisible by p. A3. A polynomial time reduction of the problem of finding Sylow subgroups of permutation groups (SYLFIND) to finding the intersection of two cosets of permutation groups (INT). As a consequence, one can find Sylow subgroups of solvable groups and of groups with bounded nonabelian composition factors in polynomial time. A4. A polynomial time algorithm to solve SYLFIND for finite simple groups. A5. An ncd/log d algorithm for isomorphism (ISO) of graphs of valency less than d and a consequent improved moderately exponential general graph isomorphism test in exp(c√n log n) steps. A6. A moderately exponential, n, c√n algorithm for INT. Combined with A3, we obtain an nc√n algorithm for SYLFIND as well. All these problems have strong links to each other. ISO easily reduces to INT. A subcase of SYLFIND was solved in polynomial time and applied to bounded valence ISO in [Lul]. Now, SYLFIND is reduced to INT. Interesting special cases of SYLFIND belong to NP ∩ coNP and are not known to have subexponential solutions. All the results stated depend on the classification of finite simple groups. We note that no previous ISO test had no(d) worst case behavior for graphs of valency less than d. It appears that unless there is another radical breakthrough in ISO, independent of the previous one, the simple groups classification is an indispensable tool for further developments.
STOC Conference 1982 Conference Paper
We investigate the connection between the spectrum of a graph, i.e. the eigenvalues of the adjacency matrix, and the complexity of testing isomorphism. In particular we describe two polynomial time algorithms which test isomorphism of undirected graphs whose eigenvalues have bounded multiplicity. If X and Y are graphs of eigenvalue multiplicity m, then the isomorphism of X and Y can be tested by an O(n 4m+c ) deterministic and by an O(n 2m+c ) Las Vegas algorithm, where n is the number of vertices of X and Y.
FOCS Conference 1979 Conference Paper
Canonical labelling of graphs (CL, for short) can be used, e. g. , to test isomorphism. We prove that a simple vertex classification procedure results after only two refinement steps in a CL of random graphs with probability 1 - exp(-cn). With a slight modification we obtain a linear time CL algorithm with only exp(-cn log n/log log n) probability of failure. An additional depth-first search yields a CL of all graphs in linear average time.