FH and, hence, GOH. Further evidence is provided by a recent article, 7 which constructs explicit geometric obstructions in the analogous setting for the lower bound problem for matrix multiplication, albeit for a problem of very modest size. Explicit computation for any larger example is difficult at present due to the difficulty of the problems that arise.

The strong flip theorem for the per-
manent vs. determinant conjecture
and analogous results in Mulmuley21
for other fundamental hardness con-
jectures in complexity theory, such
as the arithmetic P vs. NP conjec-
tures, show a fundamental difference
between such hardness conjectures
that are at least as hard as the deran-
domization conjectures and the known
lower bound results in the restricted
models of computation such as con-
stant depth5 or monotone27 circuits.
The lower bounds in these restricted
models are statements about the weak-
ness of these models. In contrast, by the
strong flip theorem, the permanent vs.
determinant problem is a statement
about the strength of the complex-
ity class NC (or rather its arithmetic
analogue29 VP) for which the determi-
nant is essentially complete. It does
not say that NC (or rather VP) is small
and weak, but rather that it is big and
strong—strong enough to assert that
“I am different from P” (or rather its
arithmetic analogue VNP29), for the per-
manent is complete. Similarly, by an
analogous flip theorem for the (arith-
metic) P vs. NP problem, this problem
is a statement about the strength of the
complexity class P. It does not say that
P is weak and small but rather that it
is big and strong—strong enough to
assert that “I am different from NP.”
It should also be remarked that FH
will almost never hold for functions
not characterized by their symmetries
(in place of the determinant and the
permanent), since the characteriza-
tion by symmetries plays a crucial role
in the proof of the strong flip theorem
that forms the crux of the justification
of FH. This is why the characterization
by symmetries is so crucial for the flip
strategy. It is indeed a fortunate coin-
cidence that the fundamental com-
plexity classes such as P and NC have
complete functions characterized by
their symmetries.

frequently Asked Questions
Can GCT be used to prove some
modest lower bounds first?
Given the difficulty of the fundamen-
tal hardness conjectures, one may
ask if GCT can be used to prove some
modest lower bounds first. That is
indeed so. Currently, the best known
lower bounds in the context of the
P vs. NC and strong permanent vs.
determinant problems are both based
on GCT. The first lower bound is a
special case of the P ≠ NC conjecture
proved in Mulmuley. 18 It says that the
P-complete max-flow problem can-
not be solved in polylogarithmic time
using polynomially many processors
in the PRAM model without bit opera-
tions. This model is quite realistic and
natural in contrast to the constant
depth5 or monotone27 circuit models
used for proving lower bounds earlier.
This lower bound is currently the only
known super-polynomial lower bound
that is a nontrivial implication of a
fundamental separation conjecture
like the P ≠ NC conjecture and holds
unconditionally in a natural and real-
istic model of computation. Its proof
is geometric and quasi-explicit. No
combinatorial or elementary proof
is known so far. This result was the
beginning of the GCT approach to the
fundamental hardness conjectures.
The second lower bound based on GCT
constructions, specifically the variet-
ies Δ[det, m] and D[perm, n, m], is the
quadratic lower bound14 stated earlier
in the context of the strong perma-
nent vs. determinant conjecture. It is a
stronger form of the earlier quadratic
lower bound16 for the usual permanent
vs. determinant problem. The proof in
Mignon and Ressayre16 is elementary
and does not need GCT. The differ-
ence between the strong and usual
versions of the permanent vs. deter-
minant problem in Landsberg et al. 14
and Mignon and Ressayre16 is akin to
the difference between the tensor rank
and usual versions of the lower bound
problem for matrix multiplication. 6

 

Are explicit proofs necessary? By the strong flip theorem, we know that any proof of the strong permanent vs. determinant conjecture leads to an explicit proof modulo derandomization. This does not say that explicit proofs are necessary. There may be nonexplicit proofs that avoid derandomization altogether. But this does suggest that if derandomization is indeed easier than the fundamental hardness conjectures12 as the complexity theory suggests, then even such nonexplicit proofs would essentially have the necessary mathematical ingredients to construct proof-certif-icates of hardness efficiently a posteriori. If so, it makes sense to go toward

figure 3. Division in the world of lower bounds by the circle of self-reference.

Hard lower bounds
(e.g., perm. vs. det, or
The circle of
self-referential
difficulty around
the lower bound
problems at least
as hard as
derandomization
GCT:
Understand Geometry and Algorithms (P)

Modest
Lower bounds