Authors Stephan Mertens, Cristopher Moore,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 9 (6), 2013, pp. 273–282
www.theoryofcomputing.org
NOTE
The Complexity of the Fermionant and
Immanants of Constant Width
Stephan Mertens Cristopher Moore
Received November 11, 2011; Revised January 20, 2013; Published February 26, 2013
Abstract: In the context of statistical physics, Chandrasekharan and Wiese recently intro-
duced the fermionant Fermk , a determinant-like function of a matrix where each permutation
π is weighted by −k raised to the number of cycles in π. We show that computing Fermk is
#P-hard under polynomial-time Turing reductions for any constant k > 2, and is ⊕P-hard
for k = 2, where both results hold even for the adjacency matrices of planar graphs. As a
consequence, unless the polynomial-time hierarchy collapses, it is impossible to compute
the immanant Immλ A as a function of the Young diagram λ in polynomial time, even if the
width of λ is restricted to be at most 2. In particular, unless NP ⊆ RP, Ferm2 is not in P, and
there are Young diagrams λ of width 2 such that Immλ is not in P.
ACM Classification: F.2.1
AMS Classification: 68Q17
Key words and phrases: fermionant, immanant, partition function, statistical physics, determinant,
permanent, computational complexity, graph theory, representation theory
1 Introduction
The permanent and determinant of a matrix have deep and well-known connections with statistical physics.
Physicists are generally concerned with a type of generating function called the partition function,
Z = ∑ e−β E(s) .
s
© 2013 Stephan Mertens and Cristopher Moore
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2013.v009a006
S TEPHAN M ERTENS AND C RISTOPHER M OORE
If the system consists of n sites each of which has a spin that can point up or down, say, this sum ranges
over all 2n states s of the system. The summand is the Boltzmann factor, where E(s) is the energy and β
is the inverse temperature. Virtually any physical quantity can then be written as a derivative of Z with
respect to an appropriate variable, representing the physical interactions in the system.
In a number of systems of physical interest, such as the Ising model of magnetism, Z can be rewritten
as a sum over all perfect matchings of a weighted graph, where the weight of each matching is the product
of the (possibly complex-valued) weights of its edges. In the bipartite case, this sum is the permanent of
the weighted adjacency matrix. But in the planar case, the weights can be modified in such a way that
this permanent (or in the non-bipartite case, a Pfaffian) becomes a determinant. Computing the partition
function is then a simple matter of finding the eigenvalues of this matrix, and indeed this is one way to
derive the celebrated exact solution of the Ising model in two dimensions [20, Ch. 13].
Inspired by these connections, Chandrasekharan and Wiese [10] recently showed that the partition
functions of certain models in quantum statistical physics can be written in terms of a quantity they call
the fermionant. Let A be an n × n matrix. The fermionant of A, with parameter k, is defined as
n
Fermk A = (−1)n ∑ (−k)c(π) ∏ Ai,π(i) .
π∈Sn i=1
Here Sn denotes the symmetric group, i. e., the group of permutations of n objects, and c(π) denotes the
number of cycles in π. This raises the interesting question of whether the fermionant can be computed in
polynomial time, especially in the case k = 2, which corresponds to fermionic systems.
Since (−1)n+c(π) is also the parity of π, the fermionant for k = 1 is simply the determinant, which
can of course be computed in polynomial time. But this appears to be the only value of k for which this is
possible. We prove the following:
Theorem 1.1. For any constant k > 2, computing Fermk for the adjacency matrix of a planar graph is
#P-hard under polynomial-time Turing reductions. Moreover, unless NP ⊂ RP, for k > 2 there can be no
fully polynomial randomized approximation scheme (FPRAS) that computes Fermk within a multiplicative
error 1 + ε in time polynomial in n and 1/ε with probability at least 3/4.
Our proof consists of a reduction to the fermionant from certain values of the Tutte polynomial for
planar graphs. Theorem 1.1 then follows from Vertigan’s results [24] on the #P-hardness of planar Tutte
polynomials, and the recent results of Goldberg and Jerrum [14] on their inapproximability.
For the most physically relevant case k = 2, we have a slightly weaker result. Recall that ⊕P is
the class of problems of the form “is |S| odd,” where S is a set such that we can tell whether x ∈ S in
polynomial time.
Theorem 1.2. Computing Ferm2 for the adjacency matrix of a planar graph is ⊕P-hard.
By Toda’s theorem [21], the polynomial-time hierarchy PH reduces to ⊕P under randomized polynomial-
time reductions. Therefore, unless PH collapses, and indeed unless NP ⊂ RP, Ferm2 is not in P.
Theorems 1.1 and 1.2 also imply new hardness results for the immanant. Recall that a Young diagram
λ is an nonincreasing integer partition of n, λ1 ≥ λ2 ≥ · · · ≥ λt such that ∑i λi = n. They are often drawn
as diagrams with λ1 boxes on the first row, λ2 boxes on the second row, and so on. The width of a Young
T HEORY OF C OMPUTING, Volume 9 (6), 2013, pp. 273–282 274
T HE C OMPLEXITY OF THE F ERMIONANT AND I MMANANTS OF C ONSTANT W IDTH
diagram is λ1 , and its depth is the largest t such that λt > 0. Each Young diagram is associated with an
irreducible character χλ of Sn , and the immanant Immλ of a matrix A is
n
Immλ A = ∑ χλ (π) ∏ Ai,π(i) .
π∈Sn i=1
If χλ is the parity (−1)π or the trivial character 1, the immanant is the determinant or the permanent
respectively. Thus we can think of the immanant as interpolating, in some sense, from det A to perm A.
Since the determinant is in P but the permanent is #P-hard [22, 20], it makes sense to ask how
the complexity of the immanant varies as λ ’s Young diagram ranges from a single row of length n (the
trivial representation) to a single column (the parity). Strengthening earlier results of Hartmann [15],
Bürgisser [8] showed that the immanant is #P-hard if λ is a hook or rectangle of polynomial width,
λ1 = w , λ2 = · · · = λn−w+1 = 1 or λ1 = · · · = λn/w = w ,
where w = Ω(nδ ) for some δ > 0. Recently Brylinski and Brylinski [7] improved these results by
showing that the immanant is #P-hard whenever two successive rows have a polynomial “overhang,”
i. e., if there is an i such that λi − λi+1 = Ω(nδ ) for some δ > 0. The case where λ has large width but
small overhang, such as a “ziggurat” where λi = w − i + 1 and n = w(w + 1)/2, remains open.
At the other extreme, Barvinok [3] and Bürgisser [9] showed that the immanant is in P if λ is
extremely close to the parity, in the sense that the leftmost column contains all but O(1) of the n boxes.
Specifically, [9] gives an algorithm that computes Immλ A in time O(sλ dλ n2 log n), where sλ and dλ
are the number of standard and semistandard tableaux of shape λ respectively. Recall that a standard
tableau is a labeling of the boxes of a Young tableau with the numbers 1, 2, . . . , n such that each row and
column is strictly increasing. In a semistandard tableau, the columns are strictly increasing and the rows
are√ nondecreasing. If the height of λ is n − c where c = O(1), then sλ and dλ are bounded above by
n c n n+c−1 2c
c c! = O(n ) and c c = O(n ) respectively, giving a polynomial-time algorithm for Immλ .
Any function of the cycle structure of a permutation is a class function, i. e., it is invariant under
conjugation. Since any class function is a linear combination of irreducible characters, the fermionant is a
linear combination of immanants. If k is a positive integer, it has nonzero contributions from immanants
whose Young diagrams have width k or less:
(k)
Fermk A = ∑ dλ Immλ T A . (1)
λ
(k)
Here λ ranges over all Young diagrams with depth at most k, dλ denotes the number of semistandard
tableaux of shape λ and content in {1, . . . , k}, and λ T denotes the transpose of a Young diagram, i. e., its
reflection around the diagonal:
λiT = max{ j : λ j ≥ i} .
To derive (1), first note that the class function kc(π) is the trace of π’s action on (Ck )⊗n by permuting the
coordinates of the tensor product,
π(v1 ⊗ v2 ⊗ · · · ⊗ vn ) = vπ(1) ⊗ vπ(2) ⊗ · · · ⊗ vπ(n) .
T HEORY OF C OMPUTING, Volume 9 (6), 2013, pp. 273–282 275
S TEPHAN M ERTENS AND C RISTOPHER M OORE
(k)
By Schur duality (see,e. g., [13]) the multiplicity of λ in (Ck )⊗n is dλ , so
(k)
kc(π) = ∑ dλ χλ (π) .
λ
We then transform kc(π) to (−1)n (−k)c(π) by tensoring each λ with the sign representation, flipping it to
its transpose λ T , which has width at most k.
If k = O(1), there are O(nk−1 ) = poly(n) Young diagrams of width k or less. Thus for any constant
k there is a polynomial-time Turing reduction from the fermionant Fermk to the problem of computing
the immanant Immλ where λ is given as part of the input, and where λ has width at most k. Therefore,
Theorems 1.1 and 1.2 give us the following corollary.
Corollary 1.3. For any constant integer k, the problem of computing the immanant Immλ A as a function
of A and λ is #P-hard under polynomial-time Turing reductions if k ≥ 3, and ⊕P-hard if k = 2, even if
λ is restricted to Young diagrams with width k or less.
In particular, unless the polynomial-time hierarchy collapses, there exist diagrams λ of width 2 such that
Immλ is not in P. This is somewhat surprising, since these immanants are “close to the determinant” in
some sense.
This partly answers a question of Bürgisser [8], who asked whether immanants of width k = 2 are
VNP-complete in the arithmetic model. Indeed, we conjecture that the fermionant is #P-hard, as opposed
to just ⊕P-hard, when k = 2. Moreover, we conjecture that the immanant is #P-hard for any family of
Young diagrams of depth n − Ω(nδ ), or equivalently, any family with a polynomial number of boxes to
the right of the first column:
Conjecture 1.4. Let λ (n) be any family of Young diagrams of depth n − Ω(nδ ) for some constant δ > 0.
Then Immλ (n) is #P-hard.
Roughly speaking, this would imply that the results of [3, 9] showing that Immλ is in P if λ has depth
n − O(1) are tight.
2 #P-hardness from circuit partitions and the Tutte polynomial
Proof of Theorem 1.1. Our proof consists of reduction from the Tutte polynomial to the fermionant,
through the circuit partition polynomial. Let G be a directed graph. A circuit partition of G is a partition
of G’s edges into circuits, i. e., sets of directed edges {(v1 , v2 ), (v2 , v3 ), . . . , (vs , v1 )}. Let rt denote the
number of circuit partitions containing t circuits; for instance, r1 is the number of Eulerian circuits. The
circuit partition polynomial j(G; z) is the generating function
∞
j(G; z) = ∑ rt zt . (2)
t=1
This polynomial was first studied by Martin [19], with a slightly different parametrization; see also [1, 4,
5, 11, 16, 17, 18].
T HEORY OF C OMPUTING, Volume 9 (6), 2013, pp. 273–282 276
T HE C OMPLEXITY OF THE F ERMIONANT AND I MMANANTS OF C ONSTANT W IDTH
Figure 1: Left, a planar graph G (white vertices and black edges) and its medial graph Gm (gray vertices
and directed edges). Right, a subset of the edges of G, and the corresponding circuit partition of Gm .
For planar graphs, j(G; z) has a known relationship with the Tutte polynomial [12, 19] which we
review here. Recall that the Tutte polynomial of an undirected graph G = (V, E) can be written as a sum
over all spanning subgraphs of G, i. e., all subsets S of E,
T (G; x, y) = ∑ (x − 1)c(S)−c(G) (y − 1)c(S)+|S|−|V | . (3)
S⊆E
Here c(G) denotes the number of connected components in G. Similarly, c(S) denotes the number of
connected components in the spanning subgraph (V, S), including isolated vertices. When x = y,
T (G; x, x) = ∑ (x − 1)c(S)+`(S)−c(G) , (4)
S⊆E
where `(S) = c(S) + |S| − |V | is the total excess of the components of S, i. e., the number of edges that
would have to be removed to make S a forest.
If G is planar, then we can define its directed medial graph Gm . Each vertex of Gm corresponds to an
edge of G, edges of Gm correspond to shared vertices in G, and we orient the edges of Gm so that they go
counterclockwise around the interior faces of G, and clockwise around the outside of G (alternatively, we
think of G and Gm as drawn on a sphere, in which case these edges go counterclockwise around the face
consisting of the rest of the plane). Each vertex of Gm has in-degree and out-degree 2, so Gm is Eulerian.
The following identity is due to Martin [19]; see also [17], or [2] for a review.
j(Gm ; z) = zc(G) T (G; z + 1, z + 1) . (5)
We illustrate this in Figure 1. There is a one-to-one correspondence between subsets S ⊆ E and circuit
partitions of Gm . Let v be a vertex of Gm corresponding to an edge e of G. If e ∈ S, the circuit partition
T HEORY OF C OMPUTING, Volume 9 (6), 2013, pp. 273–282 277
S TEPHAN M ERTENS AND C RISTOPHER M OORE
“bounces off e,” connecting each of v’s incoming edges to the outgoing edge on the same side of e. If
e∈/ S, the partition crosses over e in each direction. The number of circuits is then c(S) + `(S), in which
case (4) yields (5).
To reduce the circuit partition polynomial to the fermionant, we simply have to turn Eulerian-style
circuit partitions, which cover each edge once, into Hamiltonian-style ones, which cover each vertex once.
Given a directed graph G, let Ge be its line graph. Each vertex of Ge corresponds to an edge (u, v) of G,
and there is an edge between (u, v) and (u0 , v0 ) if v = u0 so that (u, v) and (u0 , v0 ) could form a directed
path of length two. Then each circuit partition of G corresponds to a permutation π of the vertices of Ge ,
and
Fermk Ae = j(G; −k) ,
where Ae is the adjacency matrix of Ge . In particular, if G is planar, Gm is its medial graph, Gm,e is the
line graph of Gm (which is also planar) and Am,e is its adjacency matrix, then
Fermk Am,e = (−k)c(G) T (G; 1 − k, 1 − k) . (6)
Having derived a reduction from the Tutte polynomial to the fermionant, we complete the proof
by referring to known hardness results on the Tutte polynomial. Vertigan [24] proved that computing
T (G; x, y) for planar graphs is #P-hard under polynomial-time Turing reductions, except on the set
{x, y : (x − 1)(y − 1) ∈ {1, 2}} ∪ {(1, 1), (−1, −1), (ω, ω ∗ ), (ω ∗ , ω)} ,
where ω = e2πi/3 is the cube root of unity. Moreover, Goldberg and Jerrum [14] showed that T (G; x, y)
is inapproximable for planar graphs at many values of x and y, and in particular in the region x, y < −1.
Then (6) implies that Fermk is #P-hard, and inapproximable, for any k > 2.
3 ⊕P-hardness from Hamiltonian circuits
Proof of Theorem 1.2. We will prove Theorem 1.2 by showing that the fermionant Ferm2 can be used to
compute the parity of the number of Hamiltonian circuits in an undirected graph of size n > 4.
Let A be the adjacency matrix of an undirected graph G with n vertices and no self-loops or multiple
edges. Each permutation π ∈ Sn that gives a non-zero contribution to Ferm2 (A) corresponds to a
Hamiltonian-style circuit partition of G; that is, a vertex-disjoint union of undirected cycles that includes
every vertex. A 2-cycle in π corresponds to a circuit that travels back and forth along a single edge. Any
circuit of length greater than 2 can be oriented in two ways, so a circuit partition with c2 2-cycles and c0
0
longer cycles corresponds to 2c permutations.
0
Taken together, these permutations contribute (−1)n (−2)c2 (−4)c to Ferm2 A. This is a multiple of 8
unless c0 = 0 and c2 ≤ 2, which implies n ≤ 4, or if c2 = 0 and c0 = 1, which corresponds to a Hamiltonian
cycle. In the latter case Ferm2 A is a multiple of 4 but not of 8. Thus if n > 4 we have
1
Ferm2 A ≡2 #H , (7)
4
where #H denotes the number of Hamiltonian cycles of G. Valiant [23] showed, using a parsimonious
reduction from 3-SAT to H AMILTONIAN C YCLE, that the problem ⊕H AMILTONIAN C IRCUITS of
T HEORY OF C OMPUTING, Volume 9 (6), 2013, pp. 273–282 278
T HE C OMPLEXITY OF THE F ERMIONANT AND I MMANANTS OF C ONSTANT W IDTH
computing #H mod 2 is ⊕P-complete. Indeed, he showed this even in the case where G is planar and
every vertex has degree 2 or 3. Since (7) gives a reduction from ⊕H AMILTONIAN C IRCUITS to Ferm2 ,
this shows that Ferm2 is ⊕P-hard as well.
More generally, Fermk is at least as hard as computing the number of Hamiltonian circuits mod k.
But for k ≥ 3, our #P-hardness result from Theorem 1.1 is stronger.
4 Conclusion
Is the fermionant #P-hard for k = 2? And are immanants #P-hard even for some Young diagrams of
width 2, as in Conjecture 1.4? For instance, is Immλ hard for the Young diagram λ of width 2 and height
n/2?
The reduction of Theorem 1.1 fails in this case k = 2, since for x = y = −1 the Tutte polynomial is
easy to compute [24]. In particular, if G = (V, E) then
Ferm2 Am,e = (−2)c(G) T (G; −1, −1) = (−2)c(G) (−1)|E| (−2)dim B .
Here dim B is the dimension of G’s bicycle space—the set of functions from E to Z2 that can be written
both as linear combinations of cycles and as linear combinations of stars—which we can determine in
polynomial time using linear algebra.
However, there is no reason to think that we might not be able to prove #P-hardness for Ferm2 using
another reduction. After all, the number of Eulerian circuits of the medial graph Gm is the number of
spanning trees of G, which is also in P—but Brightwell and Winkler showed that counting Eulerian
circuits is #P-hard in general [6].
Finally, it is interesting that our proof of #P-hardness is an indirect reduction from, say, the chromatic
polynomial, passing through the Tutte polynomial and its ability to perform polynomial interpolation
(under polynomial-time Turing reductions) by decorating the graph. Thus another open question is
whether there is a more direct reduction to the fermionant from the permanent or, say, #H AMILTONIAN
C IRCUITS.
Acknowledgments. This work was supported by the National Science Foundation grant CCF-1117426,
and by the ARO under contract W911NF-09-1-0483. We are grateful to Uwe-Jens Wiese for telling
us about the fermionant, and to Alex Russell, Leonard J. Schulman, Leslie Ann Goldberg, and David
Gamarnik for helpful discussions.
References
[1] R ICHARD A RRATIA , B ÉLA B OLLOBÁS , AND G REGORY B. S ORKIN: The interlace polynomial
of a graph. J. Combin. Theory Ser. B, 92(2):199–233, 2004. Preliminary version in SODA’00.
[doi:10.1016/j.jctb.2004.03.003] 276
T HEORY OF C OMPUTING, Volume 9 (6), 2013, pp. 273–282 279
S TEPHAN M ERTENS AND C RISTOPHER M OORE
[2] A NDREA AUSTIN: The circuit partition polynomial with applications and relation to the Tutte
and interlace polynomials. Rose-Hulman Undergraduate Mathematics Journal, 8(2):1:1–19, 2007.
http://www.rose-hulman.edu/mathjournal/v8n2.php. 277
[3] A LEXANDER I. BARVINOK: Computational complexity of immanents and representations
of the full linear group. Functional Analysis and its Applications, 24(2):144–145, 1990.
[doi:10.1007/BF01077707] 275, 276
[4] B ÉLA B OLLOBÁS: Evaluations of the circuit partition polynomial. J. Combin. Theory Ser. B,
85(2):261–268, 2002. [doi:10.1006/jctb.2001.2102] 276
[5] A NDRÉ B OUCHET: Tutte-Martin polynomials and orienting vectors of isotropic systems. Graphs
and Combinatorics, 7(3):235–252, 1991. [doi:10.1007/BF01787630] 276
[6] G RAHAM B RIGHTWELL AND P ETER W INKLER: Counting Eulerian circuits is #P-complete. In
Proc. 7th Workshop on Algorithm Engineering and Experiments and 2nd Workshop on Analytic Al-
gorithmics and Combinatorics (ALENEX/ANALCO’05), pp. 259–262. SIAM Press, 2005. Available
from SIAM. 279
[7] J EAN -L UC B RYLINSKI AND R ANEE B RYLINSKI: Complexity and completeness of immanants.
Technical report, 2003. [arXiv:cs/0301024] 275
[8] P ETER B ÜRGISSER: The computational complexity of immanants. SIAM J. Comput., 30(3):1023–
1040, 2000. Preliminary version in FPSAC’98. [doi:10.1137/S0097539798367880] 275, 276
[9] P ETER B ÜRGISSER: The computational complexity to evaluate representations of general lin-
ear groups. SIAM J. Comput., 30(3):1010–1022, 2000. Preliminary version in FPSAC’98.
[doi:10.1137/S0097539798367892] 275, 276
[10] S HAILESH C HANDRASEKHARAN AND U WE -J ENS W IESE: Partition functions of strongly corre-
lated electron systems as “fermionants”. Technical report, 2011. [arXiv:1108.2461] 274
[11] J OANNA A. E LLIS -M ONAGHAN: New results for the Martin polynomial. J. Combin. Theory Ser. B,
74(2):326–352, 1998. [doi:10.1006/jctb.1998.1853] 276
[12] J OANNA A. E LLIS -M ONAGHAN AND I RASEMA S ARMIENTO: Distance hereditary graphs and
the interlace polynomial. Combinatorics, Probability & Computing, 16(6):947–973, 2007.
[doi:10.1017/S0963548307008723] 277
[13] W ILLIAM F ULTON AND J OE H ARRIS: Representation Theory: A First Course. Springer, 2004.
Available from Springer. 276
[14] L ESLIE A NN G OLDBERG AND M ARK J ERRUM: Inapproximability of the Tutte polynomial of a
planar graph. Comput. Complexity, 21(4):605–642, 2012. [doi:10.1007/s00037-012-0046-4] 274,
278
[15] W ERNER H ARTMANN: On the complexity of immanants. Linear and Multilinear Algebra,
18(2):127–140, 1985. [doi:10.1080/03081088508817680] 275
T HEORY OF C OMPUTING, Volume 9 (6), 2013, pp. 273–282 280
T HE C OMPLEXITY OF THE F ERMIONANT AND I MMANANTS OF C ONSTANT W IDTH
[16] F RANÇOIS JAEGER: On Tutte polynomials and cycles of plane graphs. J. Combin. Theory Ser. B,
44(2):127–146, 1988. [doi:10.1016/0095-8956(88)90083-4] 276
[17] M ICHEL L AS V ERGNAS: On Eulerian partitions of graphs. Research Notes in Mathematics,
34:62–75, 1979. 276, 277
[18] M ICHEL L AS V ERGNAS: On the evaluation at (3, 3) of the Tutte polynomial of a graph. J. Combin.
Theory Ser. B, 45(3):367–372, 1988. [doi:10.1016/0095-8956(88)90079-2] 276
[19] P IERRE M ARTIN: Enumérations eulériennes dans les multigraphes et invariants de Tutte-
Grothendieck. Thesis, Université Scientifique et Médicale de Grenoble, 1977. Available in Archives
Ouvertes. 276, 277
[20] C RISTOPHER M OORE AND S TEPHAN M ERTENS: The Nature of Computation. Oxford University
Press, 2011. [ACM:2086753] 274, 275
[21] S EINOSUKE T ODA: PP is as hard as the polynomial-time hierarchy. SIAM J. Comput., 20(5):865–
877, 1991. Preliminary version in FOCS’89. [doi:10.1137/0220053] 274
[22] L ESLIE G. VALIANT: The complexity of computing the permanent. Theoret. Comput. Sci., 8(2):189–
201, 1979. [doi:10.1016/0304-3975(79)90044-6] 275
[23] L ESLIE G. VALIANT: Completeness for parity problems. In Proc. 11th Ann. Internat. Computing
and Combinatorics Conf. (COCOON’05), pp. 1–8. Springer, 2005. [doi:10.1007/11533719_1] 278
[24] D IRK L. V ERTIGAN: The computational complexity of Tutte invariants for planar graphs. SIAM J.
Comput., 35(3):690–712, 2005. [doi:10.1137/S0097539704446797] 274, 278, 279
AUTHORS
Stephan Mertens
Professor
Institute for Theoretical Physics
Otto-von-Guericke University Magdeburg, Germany
External Professor
Santa Fe Institute
mertens ovgu de
http://www.ovgu.de/mertens
Cristopher Moore
Professor
Santa Fe Institute
moore santafe edu
http://www.santafe.edu/~moore
T HEORY OF C OMPUTING, Volume 9 (6), 2013, pp. 273–282 281
S TEPHAN M ERTENS AND C RISTOPHER M OORE
ABOUT THE AUTHORS
S TEPHAN M ERTENS received his Ph. D. in Physics from Georg-August-University Göttingen,
Germany in 1991. His Ph. D. advisor was Annette Zippelius, and his thesis was on the
theory of neural networks, which back then was very fashionable. His current research
focuses on phase transitions in computational problems, algorithms for hard problems in
statistical physics, and parallel computing. With Cristopher Moore he is the author of
The Nature of Computation.
C RISTOPHER M OORE received his Ph. D. in Physics from Cornell University in 1991.
His Ph. D. advisor was Philip Holmes, and his thesis was on undecidable problems in
dynamical systems. Two out of three members of his thesis committee agreed that it
warranted a degree in Physics. He now works at the boundary of computer science and
physics, on topics including quantum computation, phase transitions, and social networks.
With Stephan Mertens he is the author of The Nature of Computation.
T HEORY OF C OMPUTING, Volume 9 (6), 2013, pp. 273–282 282