Saturday, February 14, 2009

A Quadratic Lower Bound for the Determinant and Permanent Problem

Join me, fellow students, in a quest to discover Complexity-Theory's version of the 'Holy Grail': lower bounds on the size of circuits. This quest began at the 1970s, when the question of P vs. NP first arose. At those early ages, when people were naive, optimistic, and still new to the question P=?NP, they sought to separate NP from P. One direction, that initially seemed promising, was though circuit size. Clearly, PP/poly. Furthermore, Karp showed that many functions belong to NP, and we know many functions with super-polynomial circuit-complexity do exist. So the hope was one would be able to show that some function in NP must have large circuit-size, thus proving PNP. In fact, one can show super-polynomial lower bound for some function in any level of the PH, and that will prove such a separation. And since Toda's theorem gives, PHP#P, the hope was that the Permanent, a #P-complete function, will have super-polynomial large circuits.

Recall that the Permanent is a function of numbers: Perm=σSnΠiMi,σ(i), whereas circuits were defined over boolean values. So we introduce arithmetics circuits. Arithmetic circuits have , gates (with fan-in 2), and gates (with fan-in 1), representing the arithmetic +,×,- operations over some field F, and additionally uses constants in F. Clearly, every polynomial (and in particular the Permanent and the Determinant) can be represented as an arithmetic circuit, and furthermore, one can reduce any boolean circuit to an arithmetic circuit (representing NOT as 1x and AND as xy). Using arithmetic circuits, Valiant defined in 1979 the arithmetics analogs of P and NP:

Definition 1: A polynomial p(x) of degree nO(1) is in VP if there exists a arithmetic circuit family of size nO(1) that computes it.
Definition 2: A polynomial p(x) of degree nO(1) is in VNP if for some m (polynomially bounded in n) there exists a family of polynomials qn+mVP s.t. p(x)=y{0,1}mq(x,y). For such p and q, we say that p is a projection of q.

Valiant showed that any polynomial in VNP is a projection of the Permanent. He also showed a nice characterization of the functions of VP, which will take us back to linear algebra. Recall that an affine transformation of vector spaces is a combination of a linear transformation and a translation. We look at affine functions from the vector space F[x1,x2,,xd] of polynomials in d variables over F, to the vector space Mn(F) of all n×n matrices.

Definition 3: We say that a polynomial pF[x1,,xd] has determinant complexity n if any affine mapping f:F[x1,,xd]Mn(F) s.t. pdetf, must map F[x1,,xd] to matrices of size n×n (or larger).

Valiant showed that if p has circuit complexity c, then its determinant complexity is 2c, so all functions in VP have polynomially bounded determinant complexity. Hence, in order to separate VNP from VP, one aspires to show that the determinant complexity of the Permanent is super-polynomial. Alas, until 2004, the best determinant-complexity lower bounds were linear in n. In 2004, Mignon and Ressayre showed a quadratic lower bound:

Theorem: If the characteristic of F is 0, then the determinant-complexity of the Permanent is at least n2/2.

The proof of this theorem naturally involves some linear algebra, and requires the definition of a special linear operator. If f:VF is a differentiable function, then we can define the tangent map Tf:VV*, by: Tf(v)=fxi(v),. I.e., we map every vV to a linear functional Tvf, where Tvf(w) is the scalar product of f(v) and w. Using the tangent and the fact that the space of linear functionals is a vector space, we can now define a tangent to the tangent. Let T2f:VHom(V,V*) be defined by T2f(v)=()THf(v)(), where Hf(v)=(2fxixj(v))i,j=1. I.e., we map every vV to a bilinear function Av(,) where Av is constructed by the 2nd order partial derivatives of f at v. Alternatively, one can think of f(v) as a map Tv2f:VV*, where (Tv2f)(w) is the linear functional Avw,. Recall that any bilinear function (and in particular Av) has a rank, which is the rank of the matrix.

Here is the proof of Mignon and Ressayre's theorem in a nutshell. Let f:Mn(F)Mm(F) be an affine function s.t. Permn=detmf. Then the following 3 claims hold:
Claim 1. Permn is isomorphic to restricting detm to the image of f, i.e. Permng where g=detmIm(f). Since g is a restriction of detm, we get rank(TA2g)rank(TA2detm).
Claim 2. There exists some non-invertible AMn(F), s.t. TA2Permn has rank =n2. (This is the most non-trivial part.)
Claim 3. For any non-invertible matrix A it must hold that rank(TA2detm)2m.

Combining the 3 steps together, we deduce the inequalities n2=rank(TA2Permn)=rank(TA2g)rank(TA2det\m)2m

None of the proofs of 1,2 or 3 is hard, and they all boil down to looking at the matrix generated by the T2 operator. If is our variable matrix, then we denote P=Permn(X). For the minor Xi,j (removing the ith row and the jth column of X), we denote Pi,j=Permn-1(Xi,j). For any iiʹ,jjʹ, we denote X{i,iʹ},{j,jʹ} to be the minor of X we get by removing both i and iʹ rows, and j and jʹ columns, and denote P{i,iʹ},{j,jʹ}=Permn-2(X{i,iʹ},{j,jʹ}). Then observe the following: T2Permn is the n2×n2 matrix where for every iiʹ, we have

Proving Claim 2 is the result of looking at . By sheer computation, they show that TA2Permn is of the form , for two particular, invertible, B and C, and show that this gives a n2×n2-matrix of full rank. We comment that the elements of B and C are multiplications of large factorials, so B and C are invertible because of the zero characteristic of F.

Proving Claim 3 uses a similar observation, based on the structure of T2. If X is a non-invertible matrix, then by changing basis, X can be turned into Xʹ, which is a diagonal matrix with some 0 entries on the main diagonal. TX2det and TXʹ2det will have the same rank. If we replace Perm in det, we get that TXʹ2det has the exact same structure as it had for the Permanent (replacing P{i,iʹ},{j,jʹ} with D{i,iʹ},{j,jʹ}, the determinant of the same minor). However, since Xʹ is diagonal and non-invertible, then the determinant is 0 for almost everywhere.

Proving Claim 1 boils down to showing the f is injective, thus isomorphic over its image. If f isn't injective, then exists a non-zero vKer(f). Hence, x,λF it holds that Permn(x+λv)=detm(f(x)+λf(v))=Permn(x), so the gradient of Permn at v must be 0. Alternatively, every TxPermn maps v into the 0-functional. So for every y it holds that Ty2Permn is a bilinear mapping, that maps every x into a functional φx which is 0 over v. Thus for every y it holds that Ty2Permn is not of full rank. In particular, TA2Permn has of rank strictly smaller than n2, which contradicts Claim 2. The proof of the theorem is done.

SPOILER ALERT: The quest for lower bounds on circuits is (thus far) unsuccessful. Obviously, we still don't know how to show super-polynomial lower bounds on the determinant complexity of the Permanent. To this day, lower bounds are known only to a very restricted class of circuits (such as AC0 or monotone circuits). In fact, Razborov and Rudich showed in 1995 that proving lower bounds using the currently known techniques is intrinsically difficult. However, there is some positive sign: in 2004, Kabanets and Impagliazzo showed that under the assumption coRP=P, either the Permanent or some function in NEXP doesn't have polynomial-size circuits.

No comments:

Post a Comment

Note: Only a member of this blog may post a comment.