Picture of Joshua A. Grochow Joshua A. Grochow
Assistant Professor
Departments of Computer Science and Mathematics
University of Colorado at Boulder
[first initial][last name]@colorado.edu
ECES 118E   (303) 735-7438
CS Theory @ CU Boulder

Me @ Twitter csthoery.SE mathoverflow ORCID
My pubs @ arXiv ECCC (ECCC too) DBLP MathSciNet Google Scholar SciRate

Papers

Designing Strassen's algorithm.
J. A. Grochow and C. Moore
arXiv:1708.09398 [cs.DS, cs.CC, cs.SC, math.RT], 2017. (arXiv) and ECCC Technical Report TR17-131, August 2017 (ECCC)
 Abstract    BibTeX
@misc{GrochowMooreStrassen,
       AUTHOR = {Joshua A. Grochow and Cristopher Moore},
        TITLE = {Designing {Strassen's} algorithm},
         YEAR = {2017},
 HOWPUBLISHED = {arXiv:1708.09398 [cs.DS]},
}   
In 1969, Strassen shocked the world by showing that two n x n matrices could be multiplied in time asymptotically less than O(n3). While the recursive construction in his algorithm is very clear, the key gain was made by showing that 2 x 2 matrix multiplication could be performed with only 7 multiplications instead of 8. The latter construction was arrived at by a process of elimination and appears to come out of thin air. Here, we give the simplest and most transparent proof of Strassen's algorithm that we are aware of, using only a simple unitary 2-design and a few easy lines of calculation. Moreover, using basic facts from the representation theory of finite groups, we use 2-designs coming from group orbits to generalize our construction to all n (although the resulting algorithms aren't optimal for n at least 3).
Comparing information-theoretic measures of complexity in Boltzmann machines.
M. S. Kanwal, J. A. Grochow, and N. Ay
Entropy 19(7):310, 2017. (doi)
arXiv:1706.09667 [cs.IT, cs.NE, q-bio.NC], 2017. (arXiv)
 Abstract    BibTeX
@article{KanwalGrochowAyMeasures,
       AUTHOR = {Maxinder S. Kanwal and Joshua A. Grochow and Nihat Ay},
        TITLE = {Comparing Information-Theoretic Measures of Complexity in {Boltzmann} Machines},
         YEAR = {2017},
      JOURNAL = {Entropy},
       VOLUME = {19},
        ISSUE = {7},
        PAGES = {310},
         NOTE = {Open access. Special issue ``{Information} {Geometry} {II}.'' Also available as arXiv:1706.09667 [cs.IT]},
}   
In the past three decades, many theoretical measures of complexity have been proposed to help understand complex systems. In this work, for the first time, we place these measures on a level playing field, to explore the qualitative similarities and difference between them, and their shortcomings. Specifically, using the Boltzmann machine architecture (a fully connected recurrent neural network) with uniformly distributed weights as our model of study, we numerically measure how complexity changes as a function of network dynamics and network parameters. We apply an extension of one such information-theoretic measure of complexity to understand incremental Hebbian learning in Hopfield networks, a fully recurrent architecture model of autoassociative memory. In the course of Hebbian learning, the total information flow reflects a natural upward trend in complexity as the network attempts to learn more and more patterns.
On the records.
A. Berdahl, U. Bhat, V. Ferdinand, J. Garland, K. Ghazi-Zahedi, J. Grana, J. A. Grochow, E. A. Hobson, Y. Kallus, C. P. Kempes, A. Kolchinsky, D. B. Larremore, E. Libby, E. A. Power, B. D. Tracey (Santa Fe Institute Postdocs)
arXiv:1705.04353 [physics.soc-ph, q-bio.PE, nlin.AO, cs.SI, cs.MA], May 2017. (arXiv)
 Abstract    BibTeX
@misc{72hS,
       AUTHOR = {Berdahl, Andrew and Bhat, Uttam and Ferdinand, Vanessa and
                 Garland, Joshua and Ghazi-Zahedi, Keyan and Grana, Justin and
                 Grochow, Joshua A. and Hobson, Elizabeth A. and Kallus, Yoav and
                 Kempes, Christopher P. and Kolchinsky, Artemy and Larremore, 
                 Daniel B. and Libby, Eric and Power, Eleanor A. and Tracey, 
                 Brendan D. (Santa Fe Institute Postdocs)},
        TITLE = {On the records},
         YEAR = {2017},
 HOWPUBLISHED = {arXiv:1705.04353 [physics.soc-ph]},
         NOTE = {This paper was produced, from conception of idea, to execution, to writing,
                 by a team in just 72 hours (see Appendix)},
}
World record setting has long attracted public interest and scientific investigation. Extremal records summarize the limits of the space explored by a process, and the historical progression of a record sheds light on the underlying dynamics of the process. Existing analyses of prediction, statistical properties, and ultimate limits of record progressions have focused on particular domains. However, a broad perspective on how record progressions vary across different spheres of activity needs further development. Here we employ cross-cutting metrics to compare records across a variety of domains, including sports, games, biological evolution, and technological development. We find that these domains exhibit characteristic statistical signatures in terms of rates of improvement, "burstiness" of record-breaking time series, and the acceleration of the record breaking process. Specifically, sports and games exhibit the slowest rate of improvement and a wide range of rates of "burstiness." Technology improves at a much faster rate and, unlike other domains, tends to show acceleration in records. Many biological and technological processes are characterized by constant rates of improvement, showing less burstiness than sports and games. It is important to understand how these statistical properties of record progression emerge from the underlying dynamics. Towards this end, we conduct a detailed analysis of a particular record-setting event: elite marathon running. In this domain, we find that studying record-setting data alone can obscure many of the structural properties of the underlying process. The marathon study also illustrates how some of the standard statistical assumptions underlying record progression models may be inappropriate or commonly violated in real-world datasets.
Towards an algebraic natural proofs barrier via polynomial identity testing.
J. A. Grochow, M. Kumar, M. Saks, and S. Saraf
arXiv:1701.01717 [cs.CC, math.AG], January 2017 (arXiv) and ECCC Technical Report TR17-009, January 2017 (ECCC)
 Abstract    BibTeX
@misc{GKSSAlgebraicNaturalProofs,
       AUTHOR = {Grochow, Joshua A. and Kumar, Mrinal and Saks, Michael and Saraf, Shubhangi},
        TITLE = {Towards an algebraic natural proofs barrier via polynomial identity testing},
         YEAR = {2017},
 HOWPUBLISHED = {ECCC Tech. Report TR17-009 and arXiv:1701.01717 [cs.CC]},
}

We observe that a certain kind of algebraic proof—which covers essentially all known algebraic circuit lower bounds to date—cannot be used to prove lower bounds against VP if and only if what we call succinct hitting sets exist for VP. This is analogous to the Razborov-Rudich natural proofs barrier in Boolean circuit complexity, in that we rule out a large class of lower bound techniques under a derandomization assumption. We also discuss connections between this algebraic natural proofs barrier, geometric complexity theory, and (algebraic) proof complexity.

Matrix multiplication algorithms from group orbits.
J. A. Grochow and C. Moore
arXiv:1612.01527 [cs.CC, cs.DS, math.AG, math.RT], December 2016 (arXiv)
 Abstract    BibTeX
@misc{GrochowMooreMM,
       AUTHOR = {Grochow, Joshua A. and Moore, Cristopher},
        TITLE = {Matrix multiplication algorithms from group orbits},
         YEAR = {2016},
 HOWPUBLISHED = {arXiv:1612.01527 [cs.CC]},
}

We show how to construct highly symmetric algorithms for matrix multiplication. In particular, we consider algorithms which decompose the matrix multiplication tensor into a sum of rank-1 tensors, where the decomposition itself consists of orbits under some finite group action. We show how to use the representation theory of the corresponding group to derive simple constraints on the decomposition, which we solve by hand for n=2,3,4,5, recovering Strassen's algorithm (in a particularly symmetric form) and new algorithms for larger n. While these new algorithms do not improve the known upper bounds on tensor rank or the matrix multiplication exponent, they are beautiful in their own right, and we point out modifications of this idea that could plausibly lead to further improvements. Our constructions also suggest further patterns that could be mined for new algorithms, including a tantalizing connection with lattices. In particular, using lattices we give the most transparent proof to date of Strassen's algorithm; the same proof works for all n, to yield a decomposition with n3 - n + 1 terms.

A quantitative definition of organismality and its application to lichen.
E. Libby, J. A. Grochow, S. DeDeo, and D. H. Wolpert
arXiv:1612.00036 [q-bio.OT], December 2016 (arXiv)
 Abstract    BibTeX
@misc{LibbyGrochowDeDeoWolpertOrganismalitySSCLichen,
       AUTHOR = {Libby, Eric and Wolpert, David H. and Grochow, Joshua A. and DeDeo, Simon},
        TITLE = {A quantitative definition of organismality and its application to lichen},
         YEAR = {2016},
 HOWPUBLISHED = {arXiv:1612.00036 [q-bio.OT]},
}

The organism is a fundamental concept in biology. However there is no universally accepted, formal, and yet broadly applicable definition of what an organism is. Here we introduce a candidate definition. We adopt the view that the "organism" is a functional concept, used by scientists to address particular questions concerning the future state of a biological system, rather than something wholly defined by that system. In this approach organisms are a coarse-graining of a fine-grained dynamical model of a biological system. Crucially, the coarse-graining of the system into organisms is chosen so that their dynamics can be used by scientists to make accurate predictions of those features of the biological system that interests them, and do so with minimal computational burden. To illustrate our framework we apply it to a dynamic model of lichen symbiosis—a system where either the lichen or its constituent fungi and algae could reasonably be considered "organisms." We find that the best choice for what organisms are in this scenario are complex mixtures of many entities that do not resemble standard notions of organisms. When we restrict our allowed coarse-grainings to more traditional types of organisms, we find that ecological conditions, such as niche competition and predation pressure, play a significant role in determining the best choice for organisms.

NP-hard sets are not sparse unless P=NP: An exposition of a simple proof of Mahaney's Theorem, with applications.
J. A. Grochow
arXiv:1610.05825 [cs.CC, math.CO, math.RT] (arXiv) and ECCC Technical Report TR15-162, October 2016. (ECCC)
 Abstract    BibTeX
@misc{GrochowAgrawalMahaney,
       AUTHOR = {Grochow, Joshua A.},
        TITLE = {NP-hard sets are not sparse unless P=NP: {An} exposition
                 of a simple proof of {Mahaney's} {Theorem}, with applications},
         YEAR = {2016},
 HOWPUBLISHED = {arXiv:1610.05825 [cs.CC]},
}

Mahaney's Theorem states that, assuming P ≠ NP, no NP-hard set can have a polynomially bounded number of yes-instances at each input length. We give an exposition of a very simple unpublished proof of Manindra Agrawal whose ideas appear in Agrawal-Arvind (Theoret. Comp. Sci., 1996). This proof is so simple that it can easily be taught to undergraduates or a general graduate CS audience - not just theorists! - in about 10 minutes, which the author has done successfully several times. We also include applications of Mahaney's Theorem to fundamental questions that bright undergraduates would ask which could be used to fill the remaining hour of a lecture, as well as an application (due to Ikenmeyer, Mulmuley, and Walter, arXiv:1507.02955) to the representation theory of the symmetric group and the Geometric Complexity Theory Program. To this author, the fact that sparsity results on NP-complete sets have an application to classical questions in representation theory says that they are not only a gem of classical theoretical computer science, but indeed a gem of mathematics.

On cap sets and the group-theoretic approach to matrix multiplication.
J. Blasiak, T. Church, H. Cohn, J. A. Grochow, E. Naslund, W. Sawin, C. Umans
Discrete Analysis 2017:3 (doi)
arXiv:1605.06702 [math.CO, cs.DS, math.GR], May 2016 (arXiv)
 Abstract    BibTeX
@article{BCCGNSUCapSetMM,
       AUTHOR = {Blasiak, Jonah and Church, Thomas and Cohn, Henry and Grochow, Joshua A. and 
                 Naslund, Eric and Sawin, William F. and Umans, Chris},
        TITLE = {On cap sets and the group-theoretic approach to matrix multiplication},
         YEAR = {2017},
      JOURNAL = {Disc. Analysis},
     FJOURNAL = {Discrete Analysis},
       NUMBER = {3},
         NOTE = {Available as arXiv:1605.06702 [math.CO]},
          DOI = {10.19086/da.1245},
}

In 2003, Cohn and Umans described a framework for proving upper bounds on the exponent ω of matrix multiplication by reducing matrix multiplication to group algebra multiplication, and in 2005 Cohn, Kleinberg, Szegedy, and Umans proposed specific conjectures for how to obtain ω=2 in this framework. In this paper we rule out obtaining ω=2 in this framework from the abelian groups of bounded exponent. To do this, we bound the size of tricolored sum-free sets in such groups, extending the breakthrough results of Croot, Lev, Pach, Ellenberg, and Gijswijt on cap sets. As a byproduct of our proof, we show that a variant of tensor rank due to Tao gives a quantitative understanding of the notion of unstable tensor from geometric invariant theory.

Boundaries of VP and VNP.
J. A. Grochow, K. D. Mulmuley, and Y. Qiao
International Colloquium on Automata, Languages, and Programming (ICALP), 2016. (doi)
arXiv:1605.02815 [cs.CC, math.AG, math.CO, math.RT], May 2016 (arXiv)
 Abstract    BibTeX
@inproceedings{GrochowMulmuleyQiaoBoundaries,
       AUTHOR = {Grochow, Joshua A. and Mulmuley, Ketan D. and Qiao, Youming},
        TITLE = {Boundaries of {$\mathsf{VP}$} and {$\mathsf{VNP}$}},
         YEAR = {2016},
        PAGES =	{34:1--34:14},
       SERIES =	{Leibniz International Proceedings in Informatics (LIPIcs)},
    BOOKTITLE = {43rd International Colloquium on Automata,
                 Languages, and Programming (ICALP16)},
       VOLUME = {55},
          DOI = {10.4230/LIPIcs.ICALP.2016.34},
         NOTE = {Preprint of the full version available as arXiv:1605.02815 [cs.CC]},
}

One fundamental question in the context of the geometric complexity theory approach to the VP versus VNP conjecture is whether VP = VP, where VP is the class of families of polynomials that can be computed by arithmetic circuits of polynomial degree and size, and VP is the class of families of polynomials that can be approximated infinitesimally closely by arithmetic circuits of polynomial degree and size. The goal of this article is to study the conjecture in (Mulmuley, arXiv:1209.5993 [cs.CC] and FOCS 2012) that VP is not contained in VP.

Towards that end, we introduce three degenerations of VP (i.e., sets of points in VP), namely the stable degeneration Stable-VP, the Newton degeneration Newton-VP, and the p-definable one-parameter degeneration VP*. We also introduce analogous degenerations of VNP. We show that Stable-VPNewton-VPVP*VNP, and Stable-VNP = Newton-VNP = VNP* = VNP. The three notions of degenerations and the proof of this result shed light on the problem of separating VP from VP.

Although we do not yet construct explicit candidates for the polynomial families in VP \ VP, we prove results which tell us where not to look for such families. Specifically, we demonstrate that the families in Newton-VP \ VP based on semi-invariants of quivers would have to be non-generic by showing that, for many finite quivers (including some wild ones), Newton degeneration of any generic semi-invariant can be computed by a circuit of polynomial size. We also show that the Newton degenerations of perfect matching Pfaffians, monotone arithmetic circuits over the reals, and Schur polynomials have polynomial-size circuits.

Dynamics of beneficial epidemics.
A. Berdahl, C. Brelsford, C. De Bacco, M. Dumas, V. Ferdinand, J. A. Grochow, L. Hébert-Dufresne, Y. Kallus, C. P. Kempes, A. Kolchinsky, D. B. Larremore, E. Libby, E. A. Power, C. A. Stern, and B. D. Tracey (Santa Fe Institute Postdocs)
arXiv:1604.02096 [physics.soc-ph, q-bio.PE, nlin.AO, cs.SI, cs.MA], April 2016. (arXiv)
 Abstract    BibTeX
@misc{72hS,
       AUTHOR = {Berdahl, Andrew and Brelsford, Christa and De Bacco, Caterina and Dumas, Marion
                 and Ferdinand, Vanessa and Grochow, Joshua A. and H\'{e}bert-Dufresne, Laurent
                 and Kallus, Yoav and Kempes, Christopher P. and Kolchinsky, Artemy
                 and Larremore, Daniel B. and Libby, Eric and Power, Eleanor A.
                 and Stern, Caitlin A. and Tracey, Brendan D. (Santa Fe Institute Postdocs)},
        TITLE = {Dynamics of beneficial epidemics},
         YEAR = {2016},
 HOWPUBLISHED = {arXiv:1604.02096 [physics.soc-ph]},
         NOTE = {This paper was produced, from conception of idea, to execution, to writing,
                 by a team in just 72 hours (see Appendix)},
}
Pathogens can spread epidemically through populations. Beneficial contagions, such as viruses that enhance host survival or technological innovations that improve quality of life, also have the potential to spread epidemically. How do the dynamics of beneficial biological and social epidemics differ from those of detrimental epidemics? We investigate this question using three theoretical approaches as well as an empirical analysis of concept propagation. First, in evolutionary models, we show that a beneficial horizontally-transmissible element, such as viral DNA, spreads super-exponentially through a population, substantially more quickly than a beneficial mutation. Second, in an epidemiological social network approach, we show that infections that cause increased connectivity lead to faster-than-exponential fixation in the population. Third, in a sociological model with strategic rewiring, we find that preferences for increased global infection accelerate spread and produce super-exponential fixation rates, while preferences for local assortativity halt epidemics by disconnecting the infected from the susceptible. Finally, in an investigation of the Google Ngram corpus, we find that new words and phrases spread super-exponentially, as anticipated by our models. We conclude that the dynamics of beneficial biological and social epidemics are characterized by the remarkably rapid spread of beneficial elements, which can be facilitated in biological systems by horizontal transmission and in social systems by active spreading strategies of infected individuals.
Multi-scale structure and topological anomaly detection via a new network statistic: The onion decomposition.
L. Hébert-Dufresne, J. A. Grochow, and A. Allard
Scientific Reports, 6, Article no. 31708, 2016. (doi)
Preprint available as arXiv:1510.08542 [physics.soc-ph, cond-math.dis-nn, cs.DM, math.CO, cs.SI], October 2015. (arXiv)
 Abstract    BibTeX
@article{HebertDufresneGrochowAllardOnion,
       AUTHOR = {H\'{e}bert-Dufresne, Laurent and Grochow, Joshua A. and Allard, Antoine},
        TITLE = {Multi-scale structure and topological anomaly detection via a new network statistic:
The onion decomposition},
         YEAR = {2016},
      JOURNAL = {Sci. Rep.},
     FJOURNAL = {Scientific Reports},
       VOLUME = {6},
        PAGES = {31708},
         NOTE = {Preprint available as arXiv:1510.08542 [physics.soc-ph]},
          DOI = {10.1038/srep31708},
} 
We introduce a network statistic that measures structural properties at the micro-, meso-, and macroscopic scales, while still being easy to compute and interpretable at a glance. Our statistic, the onion spectrum, is based on the onion decomposition, which refines the k-core decomposition, a standard network fingerprinting method. The onion spectrum is exactly as easy to compute as the k-cores: It is based on the stages at which each vertex gets removed from a graph in the standard algorithm for computing the k-cores. Yet, the onion spectrum reveals much more information about a network, and at multiple scales; for example, it can be used to quantify node heterogeneity, degree correlations, centrality, and tree- or lattice-likeness. Furthermore, unlike the k-core decomposition, the combined degree-onion spectrum immediately gives a clear local picture of the network around each node which allows the detection of interesting subgraphs whose topological structure differs from the global network organization. This local description can also be leveraged to easily generate samples from the ensemble of networks with a given joint degree-onion distribution. We demonstrate the utility of the onion spectrum for understanding both static and dynamic properties on several standard graph models and on many real-world networks.
Monotone projection lower bounds from extended formulation lower bounds.
J. A. Grochow
Theory of Computing, to appear, 2017.
ECCC Technical Report TR15-171 (ECCC) and arXiv:1510.08417 [cs.CC] (arXiv), October 2015.
 Abstract    BibTeX
@article{GrochowMonotone,
       AUTHOR = {Grochow, Joshua A.},
        TITLE = {Monotone projection lower bounds from extended formulation lower bounds},
         YEAR = {2017},
      JOURNAL = {Theory of Computing},
         NOTE = {To appear. Preprint available as ECCC Tech. Report TR15-171 and
                 arXiv:1510.08417 [cs.CC]},
}
In this short note, we show that the Hamiltonian Cycle polynomial is not a monotone sub-exponential-size projection of the permanent; this both rules out a natural attempt at a monotone lower bound on the Boolean permanent, and shows that the permanent is not complete for non-negative polynomials in VNPR under monotone p-projections. We also show that the cut polynomials, ΣA ⊆ [n] Πi ∈ A, j ∉ A xijq-1, and the perfect matching polynomial (or "unsigned Pfaffian") 12nn!Σπ ∈ S2nΠi ∈ [n] xπ(2i-1),π(2i) are not monotone p-projections of the permanent. The latter can be interpreted as saying that there is no monotone projection reduction from counting perfect matchings in general graphs to counting perfect matchings in bipartite graphs, putting at least one theorem behind the well-established intuition. As the permanent is universal for monotone formulas, these results also imply exponential lower bounds on the monotone formula size and monotone circuit size of these polynomials. To prove these results we introduce a new connection between monotone projections of polynomials and extended formulations of linear programs that may have further applications.
Graph isomorphism and circuit size.
E. Allender, J. A. Grochow, and C. Moore
arXiv:1511.08189 [cs.CC] (arXiv) and ECCC Technical Report TR15-162, October 2015. (ECCC)
Watch Eric's talk about it!
 Abstract    BibTeX
@misc{AllenderGrochowMooreGI,
       AUTHOR = {Allender, Eric and Grochow, Joshua A. and Moore, Cristopher},
        TITLE = {Graph isomorphism and circuit size},
         YEAR = {2015},
 HOWPUBLISHED = {arXiv:1511.08189 [cs.CC] and ECCC Tech. Report TR15-162},
}
We show that the Graph Automorphism problem is ZPP-reducible to MKTP, the problem of minimizing time-bounded Kolmogorov complexity. MKTP has previously been studied in connection with the Minimum Circuit Size Problem (MCSP) and is often viewed as essentially a different encoding of MCSP. All prior reductions to MCSP have applied equally well to MKTP, and vice-versa, and all such reductions have relied on the fact that functions computable in polynomial time can be inverted with high probability relative to MCSP and MKTP. Our reduction uses a different approach, and consequently yields the first example of a problem in ZPPMKTP that is not known to lie in NP∩coNP. We also show that this approach can be used to provide a reduction of the Graph Isomorphism problem to MKTP.
Polynomial-time isomorphism test of groups that are tame extensions.
J. A. Grochow and Y. Qiao
26th International Symposium on Algorithms and Computation (ISAAC), 2015. (doi)
arXiv:1507.01917 [cs.DS, cs.CC, math.GR, math.RT] (arXiv)
 Abstract    BibTeX
@inproceedings{GrochowQiaoTame,
    AUTHOR = {Grochow, Joshua A. and Qiao, Youming},
     TITLE = {Polynomial-time isomorphism test of groups that are tame extensions},
      YEAR = {2015},
 BOOKTITLE = {26th International Symposium on Algorithms and Computation (ISAAC)
              (Springer Lecture Notes in Computer Science 9472)},
     PAGES = {578--589},
       DOI = {10.1007/978-3-662-48971-0_49},
      NOTE = {Full version available as arXiv:1507.01917 [cs.DS]},
}

We give new polynomial-time algorithms for testing isomorphism of a class of groups given by multiplication tables (GpI). Two results (Cannon & Holt, J. Symb. Comput. 2003; Babai, Codenotti & Qiao, ICALP 2012) imply that GpI reduces to the following: given groups G, H with characteristic subgroups of the same type and isomorphic to Zpd, and given the coset of isomorphisms Iso(G/Zpd, H/Zpd), compute Iso(G, H) in time poly(|G|). Babai & Qiao (STACS 2012) solved this problem when a Sylow p-subgroup of G/Zpd is trivial. In this paper, we solve the preceding problem in the so-called "tame" case, i.e., when a Sylow p-subgroup of G/Zpd is cyclic, dihedral, semi-dihedral, or generalized quaternion. These cases correspond exactly to the group algebra Fp[G/Zpd] being of tame type, as in the celebrated tame-wild dichotomy in representation theory. We then solve new cases of GpI in polynomial time.

Our result relies crucially on the divide-and-conquer strategy proposed earlier by the authors (CCC 2014), which splits GpI into two problems, one on group actions (representations), and one on group cohomology. Based on this strategy, we combine permutation group and representation algorithms with new mathematical results, including bounds on the number of indecomposable representations of groups in the tame case, and on the size of their cohomology groups.

Finally, we note that when a group extension is not tame, the preceding bounds do not hold. This suggests a precise sense in which the tame-wild dichotomy from representation theory may also be a dividing line between the (currently) easy and hard instances of GpI.

A framework for optimal high-level descriptions in science and engineering—preliminary report.
D. H. Wolpert, J. A. Grochow, E. Libby, and S. DeDeo
Chapter in From matter to life: information and causality, S. Walker and P. Davies (eds.), Cambridge University Press, in press, 2015.
Preliminary version available as arXiv:1409.7403 [cs.IT, cond-mat.stat-mech, cs.AI, cs.CE, q-bio.PE] (arXiv) and SFI Working Paper 2015-06-017 (SFI)
 Abstract    BibTeX
@incollection{WolpertGrochowLibbyDeDeoSSC,
       AUTHOR = {Wolpert, David H. and Grochow, Joshua A. and Libby, Eric and DeDeo, Simon},
        TITLE = {Optimal high-level descriptions of dynamical systems},
         YEAR = {2015},
       EDITOR = {S. I. Walker and P. Davies},
    BOOKTITLE = {From Matter to Life: Information and Causality},
    PUBLISHER = {Cambridge University Press},
         NOTE = {In press. Preliminary version available as arXiv:1409.7403 [cs.IT] and SFI Working Paper 2015-06-017},
}

Both science and engineering rely on the use of high-level descriptions. These go under various names, including "macrostates," "coarse-grainings," and "effective theories". The ideal gas is a high-level description of a large collection of point particles, just as a a set of interacting firms is a high-level description of individuals participating in an economy and just as a cell a high-level description of a set of biochemical interactions. Typically, these descriptions are constructed in an ad hoc manner, without an explicit understanding of their purpose. Here, we formalize and quantify that purpose as a combination of the need to accurately predict observables of interest, and to do so efficiently and with bounded computational resources. This State Space Compression framework makes it possible to solve for the optimal high-level description of a given dynamical system, rather than relying on human intuition alone.

In this preliminary report, we present our framework, show its application to a diverse set of examples in Computer Science, Biology, Physics and Networks, and develop some technical machinery for evaluating accuracy and computation costs in a variety of systems.

Circuit complexity, proof complexity, and polynomial identity testing.
J. A. Grochow and T. Pitassi
IEEE Symposium on Foundations of Computer Science (FOCS), October 2014. (doi) (watch the video of Toni's FOCS talk!)
Submitted for journal publication.
Also available as ECCC Technical Report TR14-052, April 2014 (ECCC) and arXiv:1404.3820 [cs.CC, cs.LO, math.LO] (arXiv)
 Abstract    BibTeX
@inproceedings{GrochowPitassiPIT,
    AUTHOR = {Grochow, Joshua A. and Pitassi, Toniann},
     TITLE = {Circuit complexity, proof complexity, and polynomial identity testing},
      YEAR = {2014},
 BOOKTITLE = {55th Annual IEEE Symposium on Foundations of Computer Science (FOCS)},
      NOTE = {Also available as arXiv:1404.3820 [cs.CC] and ECCC Technical Report TR14-052. Submitted for journal publication.},
       DOI = {10.1109/FOCS.2014.20},
}

We introduce a new and very natural algebraic proof system, which has tight connections to (algebraic) circuit complexity. In particular, we show that any super-polynomial lower bound on any Boolean tautology in our proof system implies that the permanent does not have polynomial-size algebraic circuits (VNP is not equal to VP). As a corollary to the proof, we also show that super-polynomial lower bounds on the number of lines in Polynomial Calculus proofs (as opposed to the usual measure of number of monomials) imply the Permanent versus Determinant Conjecture. Note that, prior to our work, there was no proof system for which lower bounds on an arbitrary tautology implied any computational lower bound.

Our proof system helps clarify the relationships between previous algebraic proof systems, and begins to shed light on why proof complexity lower bounds for various proof systems have been so much harder than lower bounds on the corresponding circuit classes. In doing so, we highlight the importance of polynomial identity testing (PIT) for understanding proof complexity.

More specifically, we introduce certain propositional axioms satisfied by any Boolean circuit computing PIT. (The existence of efficient proofs for our PIT axioms appears to be somewhere in between the major conjecture that PIT is in P and the known result that PIT is in P/poly.) We use these PIT axioms to shed light on AC0[p]-Frege lower bounds, which have been open for nearly 30 years, with no satisfactory explanation as to their apparent difficulty. We show that either:

  1. Proving super-polynomial lower bounds on AC0[p]-Frege implies VNPGF(p) does not have polynomial-size circuits of depth d—a notoriously open question for any d≥4—thus explaining the difficulty of lower bounds on AC0[p]-Frege, or
  2. AC0[p]-Frege cannot efficiently prove the depth d PIT axioms, and hence we have a lower bound on AC0[p]-Frege.
We also prove many variants on this statement for other proof systems and other computational lower bounds.

Finally, using the algebraic structure of our proof system, we propose a novel way to extend techniques from algebraic circuit complexity to prove lower bounds in proof complexity. Although we have not yet succeeded in proving such lower bounds, this proposal should be contrasted with the difficulty of extending AC0[p] circuit lower bounds to AC0[p]-Frege lower bounds.

Algorithms for group isomorphism via group extensions and cohomology.
J. A. Grochow and Y. Qiao
SIAM J. Comput. 46(4):1153-1216, 2017. (doi)
Preliminary version appeared as IEEE Conference on Computational Complexity (CCC), June 2014. (doi)
Also available as arXiv:1309.1776 [cs.DS] (arXiv) and ECCC Technical Report TR13-123, September 2013. (ECCC)
 Abstract    BibTeX
@article{GrochowQiaoGpIso,
     TITLE = {Algorithms for group isomorphism via group extensions and cohomology},
    AUTHOR = {Grochow, Joshua A. and Qiao, Youming},
   JOURNAL = {SIAM J. Comput.},
  FJOURNAL = {SIAM Journal on Computing},
      YEAR = {2017},
    VOLUME = {46},
    NUMBER = {4},
     PAGES = {1153--1216},
      NOTE = {Preliminary version in IEEE Conference on Computational Complexity (CCC) 2014 
              (DOI:10.1109/CCC.2014.19). Also available as arXiv:1309.1776 [cs.DS] and 
              ECCC Technical Report TR13-123.},
       DOI = {10.1137/15M1009767},
}

The isomorphism problem for groups given by their multiplication tables (GpI) has long been known to be solvable in nO(log n) time, but only recently has there been significant progress towards polynomial time. For example, Babai, Codenotti & Qiao (ICALP 2012) gave a polynomial-time algorithm for groups with no abelian normal subgroups. Thus, at present it is crucial to understand groups with abelian normal subgroups to develop no(log n)-time algorithms.

Towards this goal we advocate a strategy via the extension theory of groups, which describes how a normal subgroup N is related to the quotient group G/N via G. This strategy "splits" GpI into two subproblems: one regarding group actions on other groups, and one regarding group cohomology. The solution of these problems is essentially necessary and sufficient to solve GpI. Most previous works on GpI naturally align with this strategy, and it thus helps explain in a unified way the recent polynomial-time algorithms for other group classes. In particular, most results in the Cayley table model have focused on the group action aspect, despite the general necessity of cohomology, for example for p-groups of class 2—believed to be the hardest case of GpI.

To make progress on the group cohomology aspect of GpI, we consider central-radical groups, proposed in Babai et al. (SODA 2011): the class of groups such that G mod its center has no abelian normal subgroups. Recall that Babai et al. (ICALP 2012) consider the class of groups G such that G itself has no abelian normal subgroups. Following the above strategy, we solve GpI in nO(log log n) time for central-radical groups, and in polynomial time for several prominent sub-classes of central-radical groups. We also achieve an nO(log log n)-time bound for groups whose solvable normal subgroups are elementary abelian but not necessarily central. As far as we are aware, this is the first time that a nontrivial algorithm with worst-case guarantees has tackled both aspects of GpI—actions and cohomology—simultaneously.

Prior to our work, nothing better than the trivial nO(log n)-time algorithm was known, even for groups with a central radical of constant size, such as Z(G)=Z2. To develop these algorithms we utilize several mathematical results on the detailed structure of cohomology classes, as well as algorithmic results for code equivalence, coset intersection and cyclicity testing of modules over finite-dimensional associative algebras. We also suggest several promising directions for future work.

Rotor-routing and spanning trees on planar graphs.
M. Chan, T. Church, and J. A. Grochow
International Mathematics Research Notices 11:3225-3244, 2015. (doi) (first published online 2014)
Also available as arXiv:1308.2677 [math.CO] August 2013. (arXiv)
 Abstract    BibTeX
@article{ChanChurchGrochowRotor,
    AUTHOR = {Chan, Melody and Church, Thomas and Grochow, Joshua A.},
     TITLE = {Rotor-routing and spanning trees on planar graphs},
   JOURNAL = {Int. Math Res. Not.},
  FJOURNAL = {International Mathematics Research Notices},
      YEAR = {2015},
    VOLUME = {11},
     PAGES = {3225--3244},
      NOTE = {Also available as arXiv:1308.2677 [math.CO]},
       DOI = {10.1093/imrn/rnu025},
}
The sandpile group Pic0(G) of a finite graph G is a discrete analogue of the Jacobian of a Riemann surface which was rediscovered several times in the contexts of arithmetic geometry, self-organized criticality, random walks, and algorithms. Given a ribbon graph G, Holroyd et al. used the "rotor-routing" model to define a free and transitive action of Pic0(G) on the set of spanning trees of G. However, their construction depends a priori on a choice of basepoint vertex. Ellenberg asked whether this action does in fact depend on the choice of basepoint. We answer this question by proving that the action of Pic0(G) is independent of the basepoint if and only if G is a planar ribbon graph.
Unifying known lower bounds via geometric complexity theory.
J. A. Grochow
Computational Complexity, Special Issue, 24(2):393-475, 2015. (doi)
Extended abstract appeared in IEEE Conference on Computational Complexity (CCC), June 2014. (doi)
Preliminary version available as arXiv:1304.6333 [cs.CC] April 2013, but the final official version is Open Access!
 Abstract    BibTeX
@article{GrochowGCTUnity,
     TITLE = {Unifying known lower bounds via geometric complexity theory},
    AUTHOR = {Grochow, Joshua A.},
   JOURNAL = {computational complexity},
      YEAR = {2015},
    VOLUME = {24},
     ISSUE = {2},
     PAGES = {393--475},
      NOTE = {Special issue from IEEE CCC 2014. Open access.},
       DOI = {10.1007/s00037-015-0103-x},
}
We show that most arithmetic circuit lower bounds and relations between lower bounds naturally fit into the representation-theoretic framework suggested by geometric complexity theory (GCT), including: the partial derivatives technique (Nisan–Wigderson), the results of Razborov and Smolensky on AC0[p], multilinear formula and circuit size lower bounds (Raz et al.), the degree bound (Strassen, Baur–Strassen), the connected components technique (Ben-Or), depth 3 arithmetic circuit lower bounds over finite fields (Grigoriev–Karpinski), lower bounds on permanent versus determinant (Mignon–Ressayre, Landsberg–Manivel–Ressayre), lower bounds on matrix multiplication (Bürgisser–Ikenmeyer) (these last two were already known to fit into GCT), the chasms at depth 3 and 4 (Gupta–Kayal–Kamath–Saptharishi; Agrawal–Vinay; Koiran), matrix rigidity (Valiant) and others. That is, the original proofs, with what is often just a little extra work, already provide representation-theoretic obstructions in the sense of GCT for their respective lower bounds. This enables us to expose a new viewpoint on GCT, whereby it is a natural unification of known results and broad generalization of known techniques. It also shows that the framework of GCT is at least as powerful as known methods, and gives many new proofs-of-concept that GCT can indeed provide significant asymptotic lower bounds. This new viewpoint also opens up the possibility of fruitful two-way interactions between previous results and the new methods of GCT; we provide several concrete suggestions of such interactions. For example, the representation-theoretic viewpoint of GCT naturally provides new properties to consider in the search for new lower bounds.
Matrix Lie algebra isomorphism. (Previously: Lie algebra conjugacy. More accurately: Matrix isomorphism of matrix Lie algebras.)
J. A. Grochow
IEEE Conference on Computational Complexity (CCC), June 2012. (doi)
Also available as arXiv:1112.2012 [cs.CC, cs.DS, cs.SC, math.RT] (arXiv) and ECCC Technical Report TR11-168 (ECCC)
See my Ph.D. thesis for a more complete version.
 Short Abstract    Detailed Abstract    BibTeX
@inproceedings{GrochowLieAlgebraIso,
    AUTHOR = {Grochow, Joshua A.},
     TITLE = {Matrix {Lie} algebra isomorphism},
 BOOKTITLE = {IEEE Conference on Computational Complexity (CCC12)},
      YEAR = {2012},
     PAGES = {203--213},
      NOTE = {Also available as arXiv:1112.2012 [cs.CC] and ECCC Technical Report TR11-168.},
       DOI = {10.1109/CCC.2012.34},
}
We study the problem of matrix isomorphism of matrix Lie algebras (MatIsoLie). Lie algebras arise centrally in areas as diverse as differential equations, particle physics, group theory, and the Geometric Complexity Theory Program (cf. Mulmuley, Comm. ACM, 2012, and references therein). A matrix Lie algebra is a set L of matrices that is closed under linear combinations and the operation [A,B] = AB - BA. Two matrix Lie algebras L, L' are matrix isomorphic if there is an invertible matrix M such that conjugating every matrix in L by M yields the set L'. We show that certain cases of MatIsoLie—for the wide and widely studied classes of semisimple and abelian Lie algebras—are equivalent to graph isomorphism and linear code equivalence, respectively. On the other hand, we give polynomial-time algorithms for other cases of MatIsoLie, which allow us to mostly derandomize a recent result of Kayal on affine equivalence of polynomials.
We study the problem of matrix Lie algebra conjugacy. Lie algebras arise centrally in areas as diverse as differential equations, particle physics, group theory, and the Geometric Complexity Theory Program (cf. Mulmuley, Comm. ACM, 2012, and references therein). A matrix Lie algebra is a set L of matrices such that A,B ∈ L implies AB - BA ∈ L. Two matrix Lie algebras are conjugate if there is an invertible matrix M such that L1 = ML2M-1. We show that certain cases of Lie algebra conjugacy are equivalent to graph isomorphism. On the other hand, we give polynomial-time algorithms for other cases of Lie algebra conjugacy, which allow us to mostly derandomize a recent result of Kayal on affine equivalence of polynomials. Affine equivalence is related to many complexity problems such as factoring integers, graph isomorphism, matrix multiplication, and permanent versus determinant. Specifically, we show:
  • Abelian Lie algebra conjugacy is as hard as graph isomorphism. A Lie algebra is abelian if all of its matrices commute pairwise.
  • Abelian diagonalizable Lie algebra conjugacy of n × n matrices can be solved in poly(n) time when the Lie algebras have dimension O(1). The dimension of a Lie algebra is the maximum number of linearly independent matrices it contains. A Lie algebra L is diagonalizable if there is a single matrix M such that for every A in L, MAM-1 is diagonal.
  • Semisimple Lie algebra conjugacy is equivalent to graph isomorphism. A Lie algebra is semisimple if it is a direct sum of simple Lie algebras.
  • Semisimple Lie algebra conjugacy of n × n matrices can be solved in polynomial time when the Lie algebras consist of only O(log n) simple direct summands.
  • Conjugacy of completely reducible Lie algebras—that is, a direct sum of an abelian diagonalizable and a semisimple Lie algebra—can be solved in polynomial time when the abelian part has dimension O(1) and the semisimple part has O(log n) simple direct summands.
Report on "Mathematical Aspects of P vs. NP and its Variants".
J. A. Grochow and K. Rusek
arXiv:1203.2888 [cs.CC, math.AG, math.NT, math.RT] (arxiv)
 Abstract    BibTeX
@misc{GrochowRusekReport,
       AUTHOR = {Grochow, Joshua A. and Rusek, Korben},
        TITLE = {Report on ``{Mathematical} {Aspects} of {P} vs. {NP} and its {Variants}''},
         YEAR = {2012},
 HOWPUBLISHED = {arXiv:1203.2888 [cs.CC]},
         NOTE = {Workshop held at {Brown--ICERM} in August, 2011, organizers: 
                 {Saugata} {Basu}, {J.} {M.} {Landsberg,} and {J.} {Maurice} {Rojas}},
}
This is a report on a workshop held August 1 to August 5, 2011 at the Institute for Computational and Experimental Research in Mathematics (ICERM) at Brown University, Providence, Rhode Island, organized by Saugata Basu, Joseph M. Landsberg, and J. Maurice Rojas. We provide overviews of the more recent results presented at the workshop, including some works-in-progress as well as tentative and intriguing ideas for new directions. The main themes we discuss are representation theory and geometry in the Geometric Complexity Theory Program (cf. Mulmuley, Comm. ACM, 2012, and references therein), and number theory and other ideas in the Blum-Shub-Smale model.
Complexity classes of equivalence problems revisited.
L. Fortnow and J. A. Grochow
Information and Computation 209(4):748-763, 2011. (doi)
Also available as arXiv:0907.4775v2 [cs.CC], 2009. (arXiv)
Originally my master's thesis. See my my Ph.D. thesis for the latest updates.
 Abstract    BibTeX
@article{FortnowGrochowPEq,
    AUTHOR = {Fortnow, Lance and Grochow, Joshua A.},
     TITLE = {Complexity classes of equivalence problems revisited},
   JOURNAL = {Inform. and Comput.},
  FJOURNAL = {Information and Computation},
    VOLUME = {209},
      YEAR = {2011},
    NUMBER = {4},
     PAGES = {748--763},
      ISSN = {0890-5401},
      NOTE = {Also available as arXiv:0907.4775 [cs.CC]},
       DOI = {10.1016/j.ic.2011.01.006},
}
To determine if two lists of numbers are the same set, we sort both lists and see if we get the same result. The sorted list is a canonical form for the equivalence relation of set equality. Other canonical forms arise in graph isomorphism algorithms. To determine if two graphs are cospectral (have the same eigenvalues), we compute their characteristic polynomials and see if they are equal; the characteristic polynomial is a complete invariant for cospectrality. Finally, an equivalence relation may be decidable in P without either a complete invariant or canonical form. Blass and Gurevich (SIAM J. Comput., 1984) ask whether these conditions on equivalence relations—having an FP canonical form, having an FP complete invariant, and being in P—are distinct. They showed that this question requires non-relativizing techniques to resolve. We extend their results, and give new connections to probabilistic and quantum computation.
Code equivalence and group isomorphism.
L. Babai, P. Codenotti, J. A. Grochow, Y. Qiao
ACM-SIAM Symposium on Discrete Algorithms (SODA), 2011. (pdf) (doi)
 Abstract    BibTeX
@inproceedings {BabaiCodenottiGrochowQiaoSODA11,
    AUTHOR = {Babai, L{\'a}szl{\'o} and Codenotti, Paolo and Grochow, Joshua A. and Qiao, Youming},
     TITLE = {Code equivalence and group isomorphism},
 BOOKTITLE = {Proceedings of the {Twenty-Second} {Annual} {ACM--SIAM} {Symposium} on {Discrete} 
              {Algorithms} ({SODA11})},
     PAGES = {1395--1408},
 PUBLISHER = {SIAM},
   ADDRESS = {Philadelphia, PA},
      YEAR = {2011},
       DOI = {10.1137/1.9781611973082.107},
}

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 (STOC 1999).

We comment on the complexity of the closely related problem of permutational isomorphism of permutation groups.

Genomic analysis reveals a tight link between transcription factor dynamics and regulatory network architecture.
R. Jothi, S. Balaji, A. Wuster, J. A. Grochow, J. Gsponer, T. M. Przytycka, L. Aravind, and M. Madan Babu
Molecular Systems Biology 5:294, 2009. (pdf) (doi)
 Abstract    BibTeX
@article{jothiBalajiEtAlMSB2009,
    AUTHOR = {Jothi, Raja and Balaji, S. and Wuster, Arthur and Grochow, Joshua A. and 
              Gsponer, J\"{o}rg and Przytycka, Teresa M. and Aravind, L. and Babu, M. Madan},
     TITLE = {Genomic analysis reveals a tight link between transcription factor dynamics and 
              regulatory network architecture},
   JOURNAL = {Mol. Syst. Biol.},
  FJOURNAL = {Molecular Systems Biology},
    VOLUME = {5},
    NUMBER = {294},
      YEAR = {2009},
 PUBLISHER = {EMBO and Nature Publishing Group},
       DOI = {10.1038/msb.2009.52},
}
Although several studies have provided important insights into the general principles of biological networks, the link between network organization and the genome-scale dynamics of the underlying entities (genes, mRNAs, and proteins) and its role in systems behavior remain unclear. Here we show that transcription factor (TF) dynamics and regulatory network organization are tightly linked. By classifying TFs in the yeast regulatory network into three hierarchical layers (top, core, and bottom) and integrating diverse genome-scale datasets, we find that the TFs have static and dynamic properties that are similar within a layer and different across layers. At the protein level, the top-layer TFs are relatively abundant, long-lived, and noisy compared with the core- and bottom-layer TFs. Although variability in expression of top-layer TFs might confer a selective advantage, as this permits at least some members in a clonal cell population to initiate a response to changing conditions, tight regulation of the core- and bottom-layer TFs may minimize noise propagation and ensure fidelity in regulation. We propose that the interplay between network organization and TF dynamics could permit differential utilization of the same underlying network by distinct members of a clonal cell population.
Network motif discovery using subgraph enumeration and symmetry-breaking.
J. A. Grochow and M. Kellis
In RECOMB 2007, Lecture Notes in Computer Science 4453, pp. 92-106. Springer-Verlag, 2007. (pdf) (doi)
See my master's thesis for a more complete version.
 Abstract    BibTeX
@inproceedings{GrochowKellisRECOMB2007,
    AUTHOR = {Grochow, Joshua A. and Kellis, Manolis},
     TITLE = {Network motif discovery using subgraph enumeration and symmetry-breaking},
 BOOKTITLE = {Research in Computational Molecular Biology (RECOMB07)},
    SERIES = {Lecture Notes in Computer Science},
    VOLUME = {4453},
      YEAR = {2007},
     PAGES = {92--106},
 PUBLISHER = {Springer-Verlag},
      ISBN = {978-3-540-71680-8},
      ISSN = {0302-9743},
       DOI = {10.1007/978-3-540-71681-5_7},
}

The study of biological networks and network motifs can yield significant new insights into systems biology. Previous methods of discovering network motifs—network-centric subgraph enumeration and sampling—have been limited to motifs of 6 to 8 nodes, revealing only the smallest network components. New methods are necessary to identify larger network sub-structures and functional motifs.

Here we present a novel algorithm for discovering large network motifs that achieves these goals, based on a novel symmetry-breaking technique, which eliminates repeated isomorphism testing, leading to an exponential speed-up over previous methods. This technique is made possible by reversing the traditional network-based search at the heart of the algorithm to a motif-based search, which also eliminates the need to store all motifs of a given size and enables parallelization and scaling. Additionally, our method enables us to study the clustering properties of discovered motifs, revealing even larger network elements.

We apply this algorithm to the protein-protein interaction network and transcription regulatory network of S. cerevisiae, and discover several large network motifs, which were previously inaccessible to existing methods, including a 29-node cluster of 15-node motifs corresponding to the key transcription machinery of S. cerevisiae.

Theses

Symmetry and equivalence relations in classical and geometric complexity theory.
J. A. Grochow
Doctoral dissertation, U. Chicago, 2012. Advisors: Prof. Ketan Mulmuley and Prof. Lance Fortnow (pdf)
 Informal Summary    Abstract    BibTeX
@phdthesis{grochowPhD,
   AUTHOR = {Grochow, Joshua A.},
    TITLE = {Symmetry and equivalence relations in classical and geometric complexity theory},
     YEAR = {2012},
   SCHOOL = {University of Chicago},
  ADDRESS = {Chicago, IL},
}
The main results of this thesis (sometimes with fewer details) were published in my papers Complexity classes of equivalence relations revisited and Matrix Lie algebra isomorphism. However, this thesis is more than merely two papers stapled together: it also includes a tutorial/introductory survey of the Geometric Complexity Theory Program, and a broader discussion of the role of symmetry in complexity theory.

This thesis studies some of the ways in which symmetries and equivalence relations arise in classical and geometric complexity theory. The Geometric Complexity Theory Program is aimed at resolving central questions in complexity such as P versus NP using techniques from algebraic geometry and representation theory. The equivalence relations we study are mostly algebraic in nature and we heavily use algebraic techniques to reason about the computational properties of these problems. We first provide a tutorial and survey on Geometric Complexity Theory to provide perspective and motivate the other problems we study.

One equivalence relation we study is matrix isomorphism of matrix Lie algebras, which is a problem that arises naturally in Geometric Complexity Theory. For certain cases of matrix isomorphism of Lie algebras we provide polynomial-time algorithms, and for other cases we show that the problem is as hard as graph isomorphism. To our knowledge, this is the first time graph isomorphism has appeared in connection with any lower bounds program.

Finally, we study algorithms for equivalence relations more generally (joint work with Lance Fortnow). Two techniques are often employed for algorithmically deciding equivalence relations: 1) finding a complete set of easily computable invariants, or 2) finding an algorithm which will compute a canonical form for each equivalence class. Some equivalence relations in the literature have been solved efficiently by other means as well. We ask whether these three conditions—having an efficient solution, having an efficiently computable complete invariant, and having an efficiently computable canonical form—are equivalent. We show that this question requires non-relativizing techniques to resolve, and provide new connections between this question and factoring integers, probabilistic algorithms, and quantum computation.

The complexity of equivalence relations.
J. A. Grochow.
Master's thesis, U. Chicago, 2008. Advisor: Prof. László Babai (pdf)
Journal version above.
 Abstract    BibTeX
@mastersthesis{GrochowEquivalence2008,
 AUTHOR = {Grochow, Joshua A.},
  TITLE = {The complexity of equivalence relations},
 SCHOOL = {University of Chicago},
   YEAR = {2008},
  MONTH = {December},
}

To determine if two given lists of numbers are the same set, we would sort both lists and see if we get the same result. The sorted list is a canonical form for the equivalence relation of set equality. Other canonical forms for equivalences arise in graph isomorphism and its variants, and the equality of permutation groups given by generators. To determine if two given graphs are cospectral, however, we compute their characteristic polynomials and see if they are the same; the characteristic polynomial is a complete invariant for the equivalence relation of cospectrality. This is weaker than a canonical form, and it is not known whether a canonical form for cospectrality exists. Note that it is a priori possible for an equivalence relation to be decidable in polynomial time without either a complete invariant or canonical form.

Blass and Gurevich (SIAM J. Comput., 1984) ask whether these conditions on equivalence relations—having an FP canonical form, having an FP complete invariant, and simply being in P—are in fact different. They showed that this question requires non-relativizing techniques to resolve. Here we extend their results using generic oracles, and give new connections to probabilistic and quantum computation.

We denote the class of equivalence problems in P by PEq, the class of problems with complete FP invariants Ker, and the class with FP canonical forms CF; CFKerPEq, and we ask whether these inclusions are proper. If x ~ y implies |y| ≤ poly(|x|), we say that ~ is polynomially bounded; we denote the corresponding classes of equivalence relation CFp, Kerp, and PEqp. Our main results are:

  • If CF=PEq then NP=UP=RP and thus PH = BPP;
  • If CF = Ker then NP = UP, PH = ZPPNP, integers can be factored in probabilistic polynomial time, and deterministic collision-free hash functions do not exist;
  • If Ker=PEq then UPBQP;
  • There is an oracle relative to which CFKerPEq; and
  • There is an oracle relative to which CFp = Kerp and KerPEq.
On the structure and evolution of protein interaction networks.
J. A. Grochow.
Master's thesis, M. I. T., 2006. Advisor: Prof. Manolis Kellis (pdf)
One chapter was published in RECOMB 2007
(This thesis won the Charles and Jennifer Johnson Thesis Award.)
 Abstract    BibTeX
@mastersthesis{GrochowNetworks2006,
 AUTHOR = {Grochow, Joshua A.},
  TITLE = {On the structure and evolution of protein interaction networks},
 SCHOOL = {Massachusetts Institute of Technology},
   YEAR = {2006},
  MONTH = {August},
}

The study of protein interactions from the networks point of view has yielded new insights into systems biology. In particular, "network motifs" become apparent as a useful and systematic tool for describing and exploring networks. Finding motifs has involved either exact counting (e.g. Milo et al., Science, 2002) or subgraph sampling (e.g. Kashtan et al., Bioinf. 2004 and Middendorf et al., PNAS 2005). In this thesis we develop an algorithm to count all instances of a particular subgraph, which can be used to query whether a given subgraph is a significant motif. This method can be used to perform exact counting of network motifs faster and with less memory than previous methods, and can also be combined with subgraph sampling to find larger motifs than ever before—we have found motifs with up to 15 nodes and explored subgraphs up to 20 nodes. Unlike previous methods, this method can also be used to explore motif clustering and can be combined with network alignment techniques (e.g. Graemlin or pathBLAST).

We also present new methods of estimating parameters for models of biological network growth, and present a new model based on these parameters and underlying binding domains.

Finally, we propose an experiment to explore the effect of the whole genome duplication on the protein-protein interaction network of S. cerevisiae, allowing us to distinguish between cases of subfunctionalization and neofunctionalization.