The rigidity of a matrix A for target rank r is the minimum number of entries of A that need to be changed in order to obtain a matrix of rank at most r (Valiant, 1977). We study the dependence of rigidity on the target field. We consider especially two natural regimes: when one is allowed to make changes only from the field of definition of the matrix ("strict rigidity"), and when the changes are allowed to be in an arbitrary extension field ("absolute rigidity"). We demonstrate, apparently for the first time, a separation between these two concepts. We establish a gap of a factor of 3/2-o(1) between strict and absolute rigidities. The question seems especially timely because of recent results by Dvir and Liu (Theory of Computing, 2020) where important families of matrices, previously expected to be rigid, are shown not to be absolutely rigid, while their strict rigidity remains open. Our lower-bound method combines elementary arguments from algebraic geometry with "untouched minors" arguments. Finally, we point out that more families of long-time rigidity candidates fall as a consequence of the results of Dvir and Liu. These include the incidence matrices of projective planes over finite fields, proposed by Valiant as candidates for rigidity over 𝔽₂.

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.

The codewords of the homomorphism code $\operatorname{aHom}(G,H)$ are the affine homomorphisms between two finite groups, $G$ and $H$, generalizing Hadamard codes. Following the work of Goldreich--Levin (1989), Grigorescu et al. (2006), Dinur et al. (2008), and Guo and Sudan (2014), we further expand the range of groups for which local list-decoding is possible up to $\textsf{mindist}$, the minimum distance of the code. In particular, for the first time, we do not require either $G$ or $H$ to be solvable. Specifically, we demonstrate a $\operatorname{poly}(1/\varepsilon)$ bound on the list size, i.e., on the number of codewords within distance $(\textsf{mindist}-\varepsilon)$ from any received word, when $G$ is either abelian or an alternating group, and $H$ is an arbitrary (finite or infinite) group. We conjecture that a similar bound holds for all finite simple groups as domains; the alternating groups serve as the first test case. The abelian vs. arbitrary result then permits us to adapt previous techniques to obtain efficient local list-decoding for this case. We also obtain efficient local list-decoding for the permutation representations of alternating groups (i.e., when the codomain is a symmetric group $S_m$) under the restriction that the domain $G=A_n$ is paired with codomain $H=S_m$ satisfying $m < 2^{n-1}/\sqrt{n}$. The limitations on the codomain in the latter case arise from severe technical difficulties stemming from the need to solve the homomorphism extension (HomExt) problem in certain cases; these are addressed in a separate paper (Wuu 2018). However, we also introduce an intermediate "semi-algorithmic" model we call Certificate List-Decoding that bypasses the HomExt bottleneck and works in the alternating vs. arbitrary setting. A certificate list-decoder produces partial homomorphisms that uniquely extend to the homomorphisms in the list.

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.

We derive structural constraints on the automorphism groups of strongly regular (s.r.) graphs, giving a surprisingly strong answer to a decades-old problem, with tantalizing implications to testing isomorphism of s.r. graphs, and raising new combinatorial challenges.

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]."

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 nO(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 nO(log n) (a fact of interest to finite geometry and group theory.)

We consider the problem of testing isomorphism of groups of order n given by Cayley tables. The trivial n^{log n} bound on the time complexity for the general case has not been improved over the past four decades. Recently, Babai et al. (following Babai et al. in SODA 2011) presented a polynomial-time algorithm for groups without abelian normal subgroups, which suggests solvable groups as the hard case for group isomorphism problem. Extending recent work by Le Gall (STACS 2009) and Qiao et al. (STACS 2011), in this paper we design a polynomial-time algorithm to test isomorphism for the largest class of solvable groups yet, namely groups with abelian Sylow towers, defined as follows. A group G is said to possess a Sylow tower, if there exists a normal series where each quotient is isomorphic to Sylow subgroup of G. A group has an abelian Sylow tower if it has a Sylow tower and all its Sylow subgroups are abelian. In fact, we are able to compute the coset of isomorphisms of groups formed as coprime extensions of an abelian group, by a group whose automorphism group is known. The mathematical tools required include representation theory, Wedderburn's theorem on semisimple algebras, and M.E. Harris's 1980 work on p'-automorphisms of abelian p-groups. We use tools from the theory of permutation group algorithms, and develop an algorithm for a parameterized versin of the graph-isomorphism-hard setwise stabilizer problem, which may be of independent interest.

The isomorphism problem for groups given by their multiplication tables has long been known to be solvable in time nlog 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 nO(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.

A Boolean function on $N$ variables is called \emph{evasive} if its decision-tree complexity is $N$. A sequence $B_n$ of Boolean functions is \emph{eventually evasive} if $B_n$ is evasive for all sufficiently large $n$. We confirm the eventual evasiveness of several classes of monotone graph properties under widely accepted number theoretic hypotheses. In particular we show that Chowla's conjecture on Dirichlet primes implies that (a) for any graph $H$, ``forbidden subgraph $H$'' is eventually evasive and (b) all nontrivial monotone properties of graphs with $\le n^{3/2-\epsilon}$ edges are eventually evasive. ($n$ is the number of vertices.) While Chowla's conjecture is not known to follow from the Extended Riemann Hypothesis (ERH, the Riemann Hypothesis for Dirichlet's $L$ functions), we show (b) with the bound $O(n^{5/4-\epsilon})$ under ERH. We also prove unconditional results: (a$'$) for any graph $H$, the query complexity of ``forbidden subgraph $H$'' is $\binom{n}{2} - O(1)$; (b$'$) for some constant $c>0$, all nontrivial monotone properties of graphs with $\le cn\log n+O(1)$ edges are eventually evasive. Even these weaker, unconditional results rely on deep results from number theory such as Vinogradov's theorem on the Goldbach conjecture. Our technical contribution consists in connecting the topological framework of Kahn, Saks, and Sturtevant (1984), as further developed by Chakrabarti, Khot, and Shi (2002), with a deeper analysis of the orbital structure of permutation groups and their connection to the distribution of prime numbers. Our unconditional results include stronger versions and generalizations of some result of Chakrabarti et al.

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 prob-lems (factoring and discrete log); in fact, constructive mem-bership 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 sub-groups. For matrix groups over finite fields, we show that the order of the largest semisimple quotient can be deter-mined 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 recog-nition of simple groups, with the corollary that for a large class of matrix groups, our algorithms become Las Vegas.

Rank-convolutions have important applications in a variety of areas such as signal processing and computer vision. We define a mask as a function taking only values zero and infinity. Rank-convolutions with masks are of special interest to image processing. We show how to compute the rank- k convolution of a function over an interval of length n with an arbitrary mask of length m in O ( n √ m log m ) time. The result generalizes to the d -dimensional case. Previously no algorithm performing significantly better than the brute-force O ( nm ) bound was known. Our algorithm seems to perform well in practice. We describe an implementation, illustrating its application to a problem in image processing. Already on relatively small images, our experiments show a signficant speedup compared to brute force.

We give an algorithm to decide isomorphism of hypergraphs of rank k in time exp (Otilde(k2radicn)), 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 Cn(Luks 1999).

This volume comprises the polished and fully refereed versions of a selection of papers presented at the Thirty-Sixth Annual ACM Symposium on Theory of Computing (STOC 2004), held in Chicago, Illinois, June 13-15, 2004. Unrefereed preliminary versions of the papers presented at the symposium appeared in the proceedings of the meeting, published by ACM. The symposium was sponsored by the ACM Special Interest Group on Algorithms and Computation Theory (SIGACT). The STOC 2004 Program Committee consisted of Andris Ambainis, Laszlo Babai (chair), Boaz Barak, Moses Charikar, Irit Dinur, Herbert Edelsbrunner, Sandy Irani, Adam Klivans, Vladlen Koltun, Robert Krauthgamer, Satya Lokam, Tal Malkin, Oded Regev, Alexander Russell, Eva Tardos, Mikkel Thorup, D. Sivakumar, Chris Umans, and Eric Vigoda. Out of 271 "Extended Abstracts" submitted to the STOC 2004 Program Committee, 70 were selected for presentation at the symposium. Sixteen out of those 70 papers were invited to this volume. The authors of 5 of the invited papers declined, and the remaining 11 accepted the invitation. One of the 11 papers was not completed by the deadline; one other paper was found to fall short of SICOMP standards. The present volume includes the remaining 9 papers. This collection of papers encompasses a wide variety of questions and methods in theoretical computer science, often shedding new light on entire areas with a fresh approach. The topics include fundamental questions of complexity theory and algorithms as well as foundational mathematical problems. Several papers use methods of "continuous mathematics" to attack discrete optimization problems. Of the areas represented in this volume that have relatively recently gained prominence in the theory of computing, I should mention quantum computing and the theory of metric embeddings. This issue includes the journal versions of the two papers that shared the 2004 Danny Lewin Best Student Paper award. One of them, by Scott Aaronson, shows how quantum arguments inspire new results in a classical model; the other, by Jonathan Kelner, demonstrates the relevance of conformal geometry to the algorithmic question of partitioning graphs into clusters. All papers were refereed in accordance with SICOMP's stringent standards, and most of them were substantially updated in the process. We take this opportunity to thank all the referees whose anonymous work has significantly contributed to the value of this volume. Special issues dedicated to STOC have a distinguished history; a brief review of this history seems to be in order. SIGACT, the premier U.S.-based organization of theoretical computer science, has sponsored the publication of special issues to its annual STOC conferences since the second STOC held in 1970; the Journal of Computer and System Sciences (JCSS) was designated the venue of the publication. JCSS published 34 STOC special issues, starting with the 2nd STOC (JCSS 5:3, June 1971) and ending with the 35th STOC (JCSS 69:3, November 2004). The volumes from 1978 onward are accessible to subscribers on the Elsevier website at: http://www.sciencedirect.com/ It was an honor to edit the present special issue for the SIAM Journal on Computing. My personal remarks on the change of venue can be found on my home page.

Cyclic linear codes of block length n over a finite field F/sub q/ are 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. A code C is r-testable if there exists a randomized algorithm which, given a word x/spl isin//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 1) 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/PCP's. Recently it was asked whether there exist good, locally testable families of codes. In this paper the intersection of the two questions stated is addressed. Theorem. There are no good, locally testable families of cyclic codes over any (fixed) finite field. In fact the result is stronger in that it replaces condition ii) of local testability by the condition ii') if dist (x,C) /spl ges/ /spl epsi/n then x has a positive chance of being rejected. The proof involves methods from Galois theory, cyclotomy, and diophantine approximation.

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.

In the multiparty communication game (CFL game) of Chandra, Furst, and Lipton [Proceedings of the 15th Annual ACM Symposium on Theory of Computing, Boston, MA, 1983, pp. 94--99] k players collaboratively evaluate a function f(x 0 , . . . , x k -1) in which player i knows all inputs except xi. The players have unlimited computational power. The objective is to minimize communication. In this paper, we study the SIMULTANEOUS MESSAGES (SM) model of multiparty communication complexity. The SM model is a restricted version of the CFL game in which the players are not allowed to communicate with each other. Instead, each of the k players simultaneously sends a message to a referee, who sees none of the inputs. The referee then announces the function value. We prove lower and upper bounds on the SM complexity of several classes of explicit functions. Our lower bounds extend to randomized SM complexity via an entropy argument. A lemma establishing a tradeoff between average Hamming distance and range size for transformations of the Boolean cube might be of independent interest. Our lower bounds on SM complexity imply an exponential gap between the SM model and the CFL model for up to $(\log n)^{1-\epsilon}$ players for any $\epsilon > 0$. This separation is obtained by comparing the respective complexities of the Generalized Addressing Function, GAF G,k , where G is a group of order n. We also combine our lower bounds on SM complexity with the ideas of Håstad and Goldmann [Comput. Complexity, 1 (1991), pp. 113--129] to derive superpolynomial lower bounds for certain depth-2 circuits computing a function related to the GAF function. We prove some counterintuitive upper bounds on SM complexity. We show that {\sf GAF}$_{\mathbb{Z}_2^t,3}$ has SM complexity $O(n^{0.92})$. When the number of players is at least $c\log n$, for some constant c > 0, our SM protocol for {\sf GAF}$_{\mathbb{Z}_2^t,k}$ has polylog(n) complexity. We also examine a class of functions defined by certain depth-2 circuits. This class includes the Generalized Inner Product function and Majority of Majorities. When the number of players is at least 2+log n, we obtain polylog(n) upper bounds for this class of functions.

A function f is self-reducible if it can be computed given an oracle for f. In a random-self-reduction the queries must be made in such a way that the distribution of the ith query is independent of the input that gave rise to it. Random-self-reductions have many applications, including countless cryptographic protocols, probabilistically checkable proofs, average-case complexity, and program checking. A simpler model of randomized self-reducibility is coherence, in which the only condition on the queries is that the input itself may not be among the queries. We show that there is a function which is random-self-reducible with 2 rounds of queries, but which is not even coherent, even if polynomial advice is allowed, when the queries must be made in a single round.

We generalize the multiparty communication model of Chandra, Furot, nnd Lipton (1983) to functions with b-bit output (6 = 1 in (he CFL model), We allow the parties to receive up to b -1 bits of information from an all-powerful benevolent Helper who can see all lhc Input.WC construct families of explicit functions for which fl(n/c") bits of communication are required to find the "missing bit," where n ia the length of each player's input and H is the number of players, This extends the results of Babal, Nisan, Szegedy (1992), As a consequence we settle the old problem of separatlng the one-wny vs. multiround communication complexities (in the CFL sense) for h 5 (1 -6) log 9~ players, extending a result of Nionn and Wigdcrson (1991) who demonstrated this separation for 12 z 3 players.As a by-product we obtain S2(n/ck) lower bounds for the multiparty complexity (in the CFL sense) of new families of explicit boolean functions (not derivable from BNS).The proofs exploit the interplay between two new theories of multicolor discrepancy; discrete Fourier analysis is the basic tool.We nlao include a previously unpublished lower bound by A. Wigdernon regarding the one-way complexity of the 3-party pointer jumping function,

We solve a 17 year old problem of A.C.C. Yao (1979). In the two-player communication model introduced by Yao in 1979, Alice and Bob wish to collaboratively evaluate a function f(x,y) in which Alice knows only input x and Bob knows only input y. Both players have unlimited computational power. The objective is to minimize the amount of communication. Yao (1979) also introduced an oblivious version of this communication game which we call the simultaneous messages (SM) model. The difference is that in the SM model, Alice and Bob don't communicate with each other. Instead, they simultaneously send messages to a referee, who sees none of the input. The referee then announces the function value. The deterministic two-player SM complexity of any function is straight forward to determine. Yao suggested the randomized version of this model, where each player has access to private coin flips. Our main result is that the order of magnitude of the randomized SM complexity of any function f is at least the square root of the deterministic SM complexity of f. We found this result in February 1996, independently but subsequently to I. Newman and M. Szegedy (1996) who obtained this lower bound for the special case of the function. Our proof is entirely different from and considerably simpler than the Newman-Szegedy solution. A proof similar in spirit to ours, was found by J. Bourgain and A. Wigderson simultaneously to us (unpublished); we include an outline of their proof. The quadratic reduction actually does occur for the function. We give a new proof of this fact. This result, combined with our main result, settles Yao's question, asking the exact randomized SM complexity of the equality function. The lower bound proof uses the probabilistic method; the upper bound uses linear algebra. We also give a constructive proof that O(log n) public coins reduce the complexity of to constant.

Paul Erd6s's oeuw-e encompasses a multitude of areas of mathematics, including combinatorics, set theory, number theory, classical analysis, discrete geometry, probability theory, and more.The theory of computing is conspicuously missing from this list.It is a field in which Erd6s never took any inter- est.How, then, did Erd6s become a household name in the theoretical computer science community?We address this question in this memorial.I wish to thank all those who provided photographs.My special thanks are due to Peter Kimmel for temporarily suspending his work on communication complexity and instead struggling with the complexities of electronic photo technology to get these pictures into the article.His help has been invaluable.Short preliminary versions of this article appeared in SIGACT News 27/2(1996) pp.62-65, and SIAM News 30/1 ( 1997) p, 3. 1 am grateful to SIAM editor Gail Corbette for her perceptive suggestions from which the present article has also benefited,

We present new algorithms for permutation group manipulation. Our methods result in an improvement of nearly an order of magnitude in the worst-case analysis for the fundamental problems of finding strong generating sets and testing membership. The normal structure of the group is brought into play even for such elementary issues. An essential element is the recognition of large alternating composition factors of the given group and subsequent extension of the permutation domain to display the natural action of these alternating groups. Further new features include a novel fast handling of alternating groups and the sifting of defining relations in order to link these and other analyzed factors with the rest of the group. The analysis of the algorithm depends on the classification of finite simple groups. In a sequel to this paper, using an enhancement of the present method, we shall achieve a further order of magnitude improvement.

This paper contains two main results. The first is an explicit construction of bipartite graphs which do not contain certain complete bipartite subgraphs and have maximal density, up to a constant factor, under this constraint. This construction represents the first significant progress in three decades on this old problem in extremal graph theory. The construction beats the previously known probabilistic lower bound on density. The proof uses the elements of commutative algebra and algebraic geometry (theory of ideals, integral extensions, valuation rings). The second result concerns monotone span programs. We obtain the first superpolynomial lower bounds for explicit functions in this model. The best previous lower bound was $\Omega(n^{5/2})$ by Beimel, Gal, Paterson (FOCS’95); our analysis exploits a general combinatorial lower bound criterion from that paper. We give two proofs of superpolynomial lower bounds; one based on an analysis of Paley-type bipartitie graphs via Weil’s character sum estimates. A third result demonstrates the power of monotone span programs by exhibiting a function computable in this model in linear size while requiring superpolynomial size monotone circuits and exponential size monotone formulae.

The authors present a construction of binary self-dual codes from Eulerian graphs and establish that the code will be indecomposable if and only if the vertices of degree 2 are not a cutset of the graph. The construction is used to establish that every finite group is isomorphic to the automorphism group of some self dual code. It is further shown that deciding isomorphism of self-dual codes is at least as difficult as graph isomorphism.

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.>

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.>

Let G be a group of matrices with entries over an alge-

Let A be a matrix algebra over C, closed under Hermitian adjoints, and given by a basis.

We examine the effect of symmetry on the complexity of Boolean functions and find a remarkably tight hierarchy.Generalizing the fact that all symmetric Boolean functions belong to (nonuniform) Z'CO, we find that the complexity of the class of Boolean functions admitting a given group of symmetries is essentially determined by a single parameter of that group.

This paper considers “black box groups,” i.e., finite groups whose elements are uniquely encoded by strings of uniform length, with group operations being performed by a group oracleB. Let G, H be such groups, each given by a list of generators. It is known that the problem of membership in G belongs to ${\text{NP}}^B $ [L. Babai and E. Szemerédi, Proceedings of the 25th IEEE Symposium on the Foundation of Computer Science, 1984, pp. 229–240]. The following problems are shown to belong to the complexity class ${\text{AM}}^B $; i.e., they possess bounded-round randomized interactive proofs (Arthur–Merlin protocols): nonmembership in G, the verification of the order of G, isomorphism of G and H, and checking the list of composition factors of G. A group oracle B is constructed, under which none of these problems belongs to ${\text{NP}}^B $, even for abelian groups. All the results extend to “black box factor groups,” i.e., groups defined as factor groups $G/N$, where G is a black box group, $N \triangleleft G$ is a normal subgroup, and both G and N are given by lists of generators. A list of consequences puts verification of a large number of basic group theoretic constructions in $( {{\text{AM}} \cap co{\text{AM}}} )^B $. These include homomorphisms, kernels, intersection of subgroups and cosets, membership in double cosets, centralizers, the center, cores, minimal normal subgroups, and the maximal solvable normal subgroup. A notable extension of the applicability of the results is obtained by observing that subgroups of the automorphism group of a black box group G (given by a list of generators in their action on the generators of G) can be viewed (in a nondeterministic setting) as black box groups themselves. The results are applicable to matrix groups over finite fields and to factor groups thereof. (Matrix operations replace the group oracle.) In this case, most problems listed are conjectured to belong to NP, but a proposed approach to the proof of this statement requires detailed knowledge of the classification of finite simple groups. In contrast, the material presented here relies on the elements of group theory only (with the exception of the composition factors result). These applications provided the original motivation for introducing the Arthur–Merlin protocols in [L. Babai, Proceedings of the 17th Annual ACM Symposium on the Theory of Computing, 1985, pp. 421–429], where some of the results of this paper were announced. The key to the basic results is a “local expansion lemma” for groups, which has since found applications in designing polynomial time algorithms.

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.>

Article Free Access Share on Nearly linear time algorithms for permutation groups with a small base Authors: László Babai Dept. of Comp. Science, University of Chicago, Chicago, Illinois and Dept. of Algebra, Eötvös University, Budapest, Hungary H-1088 Dept. of Comp. Science, University of Chicago, Chicago, Illinois and Dept. of Algebra, Eötvös University, Budapest, Hungary H-1088View Profile , Gene Cooperman College of Comp. Science, Northeastern University, Boston, Mass. College of Comp. Science, Northeastern University, Boston, Mass.View Profile , Larry Finkelstein College of Comp. Science, Northeastern University, Boston, Mass. College of Comp. Science, Northeastern University, Boston, Mass.View Profile , Ákos Seress Dept. of Mathematics, Ohio State University, Columbus, Ohio Dept. of Mathematics, Ohio State University, Columbus, OhioView Profile Authors Info & Claims ISSAC '91: Proceedings of the 1991 international symposium on Symbolic and algebraic computationJune 1991 Pages 200–209https://doi.org/10.1145/120694.120724Online:01 June 1991Publication History 19citation320DownloadsMetricsTotal Citations19Total Downloads320Last 12 Months9Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Heuristicalgorithms manipulating finite groups often work under the assumption that certain operations lead

Article Free Access Share on Fast Monte Carlo algorithms for permutation groups Authors: László Babai Univ. of Chicago, Chicago, IL Univ. of Chicago, Chicago, ILView Profile , Gene Cooperman Northeastern Univ., Boston, MA Northeastern Univ., Boston, MAView Profile , Larry Finkelstein Northeastern Univ., Boston, MA Northeastern Univ., Boston, MAView Profile , Eugene Luks Univ. of Oregon, Eugene Univ. of Oregon, EugeneView Profile , Ákos Seress Ohio State Univ., Columbus Ohio State Univ., ColumbusView Profile Authors Info & Claims STOC '91: Proceedings of the twenty-third annual ACM symposium on Theory of ComputingJanuary 1991 Pages 90–100https://doi.org/10.1145/103418.103435Published:03 January 1991Publication History 14citation519DownloadsMetricsTotal Citations14Total Downloads519Last 12 Months55Last 6 weeks5 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

. Motivated by Manuel Blum's concept of instance checking, we consider new, very fast and generic mechanisms of checking computations. Our results exploit recent advances in interactive proof protocols [LFKN92], [Sha92], and especially the MIP = NEXP protocol from [BFL91]. We show that every nondeterministic computational task S(x; y), defined as a polynomial time relation between the instance x, representing the input and output combined, and the witness y can be modified to a task S 0 such that: (i) the same instances remain accepted; (ii) each instance/witness pair becomes checkable in polylogarithmic Monte Carlo time; and (iii) a witness satisfying S 0 can be computed in polynomial time from a witness satisfying S. Here the instance and the description of S have to be provided in error-correcting code (since the checker will not notice slight changes). A modification of the MIP proof was required to achieve polynomial time in (iii); the earlier technique yields N O(log log N)...

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.>

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.>

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).>

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.>

Let ƒ(x1, ···· xk) be a Boolean function that k parties wish to collaboratively evaluate. The i'th party knows each input argument except xi; and each party has unlimited computational power. They share a blackboard, viewed by all parties, where they can exchange messages. The objective is to minimize the number of bits written on the board.

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.>

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.

Available from Bibliothek des Instituts fuer Weltwirtschaft, ZBW, Duesternbrook Weg 120, D-24105 Kiel C 140759 / FIZ - Fachinformationszzentrum Karlsruhe / TIB - Technische Informationsbibliothek

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.

The first result concerns branching programs having width (log n) °{*).We give an fl(n log n~ log log n) lower bound for the size of such branching programs computing almost any symmetric Boolean fnnction and in particular the following explicit fnnction: "the sum of the input variables is a quadratic residue mod p" where p is any given prime between n 1/4 and n 1/3.This is a strengthening of previous nonlinear lower bounds obtained by Chandra, Furst, Lipton and by Pudlgk.We mention that by iterating our method the result can be further strengthened to lfl(nlog n).The second result is a C" lower bound for read-onceonly branching programs computing an explicit Boolean function.For n = (~), the function computes the parity of the number of triangles in a graph on v vertices.This improves previous exp(cx/n ) lower bounds for other graph functions by Wegener and Z£k.The result implies a linear lower bound for the space complexity of this Boolean function on "eraser machines", i.e. machines that erase each input bit immediately after having read it.

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.

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 NPB. (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 NPBand thus in NPB∩ NPB.

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.

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, nlog n, time for tournaments and for 2-(ν,κ,λ) block designs with κ,λ bounded and nlog log n time for λ-planes (symmetric designs) with λ bounded. We prove some related problems NP-hard and indicate some open problems.

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(n4m+c) deterministic and by an O(n2m+c) Las Vegas algorithm, where n is the number of vertices of X and Y.

We prove that a canonical labeling can be assigned to the n vertices of a strongly regular graph by an algorithm of $o(\exp (2n^{1/2} \log ^2 n))$ running time (in the worst case). This complexity, though still not properly subexponential, is much better than $O(2^n )$.

A straightforward linear time canonical labeling algorithm is shown to apply to almost all graphs (i.e. all but $o(2^{( \begin{subarray}{l} n \\ 2 \end{subarray} )} )$) of the $2^{( \begin{subarray}{l} n \\ 2 \end{subarray} )} $ graphs on n vertices). Hence, for almost all graphs X, any graph Y can be easily tested for isomorphism to X by an extremely naive linear time algorithm. This result is based on the following: In almost all graphs on n vertices, the largest $n^{0.15} $ degrees are distinct. In fact, they are pairwise at least $n^{0.03} $ apart.

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.