How does the Mulmuley-Sohoni geometric approach to producing lower bounds avoid producing natural proofs (in the Razborov-Rudich sense)?

Question

The exact phrasing of the title is due to Anand Kulkarni (who proposed this site be created). This question was asked as an example question, but I’m insanely curious. I know very little about algebraic geometry, and in fact also only have a cursory, undergraduate understanding of the obstacles at play in the P/poly versus NP question (non-relativizing, non-algebrazing, likely won’t be a natural proof).

What makes algebraic geometry seem like it can bypass these sorts of obstacles? Is it just field expert intuition or do we have a really good reason to believe the approach is fundamentally more powerful than previous approachs? What weaker results have this approach been able to achieve?

Answer 1

[I'll answer the question as stated in the title, leaving the litany of other questions about GCT for other threads.] Proving the conjectures arising in GCT seems like it will crucially use the fact that the functions under consideration (determinant and permanent, and other related polynomials for P/poly and NP) are characterized by their symmetries. This necessity is not a formal result, but an intuition expressed by several experts. (Basically that in the absence of characterization by symmetries, understanding the algebraic geometry and representation theory that arises is far harder.)

This should bypass Razborov-Rudich because very few functions are characterized by their symmetries (bypassing the largeness condition in the definition of natural proofs). Again, I have not seen a proof of this, but it is an intuition I have heard expressed by several experts.

Now, over the complex numbers, it's not clear to me that there's an analog of Razborov-Rudich. Although most of GCT currently focuses on the complex numbers, there are analogs in the finite characteristic (promised in the forthcoming paper GCT VIII). In finite characteristic, one might actually be able to prove a statement of the form "Very few functions are characterized by their symmetries."

---

[In response to Ross Snider's comment, here's an explanation of characterization by symmetries.]

First, an explanation-by-example. For the example, define an auxiliary function $q$. If $A$ is a permutation matrix, then $q(A)=1$ and if $A$ is diagonal, then $q(A)=det(A)$ (product of the diagonal entries). Now, suppose $p(X)$ is a homogeneous degree $n$ polynomial in $n^2$ variables (that we think of as the entires of an $n \times n$ matrix $X$). If $p$ has the following symmetries:

• $p(X) = p(X^t)$ (transpose)
• $p(AXB) = p(X)$ for all pairs of matrices $(A,B)$ such that $A$ and $B$ are each either permutation matrices or diagonal matrices and $q(A)q(B) = 1$

then $p(X)$ is a constant multiple of $perm(X)$ for all matrices $X$. Hence we say the permanent is characterized by its symmetries.

More generally, if we have a (homogeneous) polynomial $f(x_1, ..., x_m)$ in $m$ variables, then $GL_m$ (the group of all invertible $m \times m$ matrices) acts on $f$ by $(Af)(x_1,...,x_m) = f(A^{-1}(x_1),...,A^{-1}(x_{m}))$ for $A \in GL_m$ (where we are taking the variables $x_1,...,x_m$ as a basis for the $m$-dimensional vector space on which $GL_m$ naturally acts). The stabilizer of $f$ in $GL_m$ is the subgroup $\text{Stab}(f) = \{ A \in GL_m : Af = f\}$. We say $f$ is characterized by its symmetries if the following holds: for any homogeneous polynomial $f'$ in $m$ variables of the same degree as $f$, if $Af' = f'$ for all $A \in \text{Stab}(f)$, then $f'$ is a constant multiple of $f$.

Answer 2

Joshua Grochow's answer is a good one, but I think it's worth making a more general comment. The Razborov–Rudich result says that if you want to prove that some Boolean function is not in $P/poly$, then (assuming you believe their cryptographic hypothesis) you must use some property of that function that is either nontrivial to compute or that is shared by only a small number of other Boolean functions. In practice it is not easy to come up with suitable properties; however, the Razborov–Rudich observation does not actually rule out very many general plans of attack on circuit lower bounds, in the absence of concrete details about the intended proof. For example, suppose I were to naively say that my plan to prove $NP\not\subseteq P/poly$ involved showing that $SAT\notin P/poly$, and that I intended to use the fact that $SAT$ is $NP$-complete. This naive "plan of attack" is almost content-free, but Razborov–Rudich doesn't rule it out, because $NP$-completeness is not a large property.

To put it another way, Razborov–Rudich usually doesn't present much of an obstacle in the early stages of planning a line of attack on circuit lower bounds, as long as you leave some room in your plan for eventually employing "special properties" of your candidate Boolean functions. It's only when you roll up your sleeves and try to fill out the details of the argument that the naturalization barrier will start to rear its head in earnest. Given that GCT is still at an early stage of development, we shouldn't expect to have to worry much about naturalization yet (though of course it's worth checking that the GCT program isn't doomed for trivial reasons).

You may also want to check out Ken Regan's exposition of GCT, which includes some remarks about the naturalization barrier.