Determinant and Permanent

by Avi Wigderson

Oded's comments

Avi started with a review of basic definitions and results regarding arithmetic circuit complexity. These included the definitions of the classes VP and VNP as classes of "polynomials" that are arithmetically reduced (i.e., vai a linear projection) to arithmetic versions of CVAL and CSAT. He recalled that DET has polylog depth and is quasi-complete for VP, whereas PERM is complete for VNP. He highlighted the fact that (for low degree polynomuials) arithmetic depth is polylogarithmic in arithmetic circuit size, whereas in the Boolean world such a result is known only for formulae.

The next definition was of $dc(n)$, the minimum dimention $m$ such that $PERM_n$ can be reduced to $DET_m$. By the above, $dc()$ is polynomial iff VP=NVP. On the other hand, $dc(n)\leq n!$ (since PERM has a formula of size $n!$ and any $s$-sized formula reduces to $DET_s$). Also, $dc(2)=2$ but $dc(n) \geq n^2/4$ (and a proof was presented in the talk).

The rest of the presentation was devoted to lower bounds in restricted models (i.e., depth three, multilinear circuits, and non-commutative ones), and to the partial derivative tecnique(s). In particular, non-commutative circuits are not allowed to utilize the commutativity law (i.e., their result is understood as a formal polynomial in a non-commutative ring such as the one of 2-by-2 matrices). A resect result (of Hrubes, Avi, and Yehudayoff) asserts that an exponential lower bound on the size of non-commutative circuits for the determiniant, provided the "sum of squares" conjecture holds (which refers to arbitrary commutative rings). Avi surveyed this conjecture, which refers to the growth rate of $k=k_R(n)$ such that $(\sum_{i\in[n]}x_i)(\sum_{i\in[n]}y_i) =(\sum_{i\in[k]}L_i)$ for $L_i$ that are bilinear forms (over $R$). He also mentioned a recent result by which the non-commutative size complexity of the permanent is polynomially related to the non-commutative size complexity of the determinant.

Turning to depth three circuits, Avi recalled Ben-Or's proof that such quadratic size circuits can compute any symmetric function (whereas depth two circuits are analogous to CNFs in the Boolean world). He cited a result with Nisan that indicates the essential use of cancelations (of non-homegeneous intermediate results) in Ben-Or's contruction.

Regarding the partial derivative techinques, Avi presented a few examples and mentioned a forthcoming survey on applications of partial derivative in TCS (by Chen, Kayal, and himself [to appear in FnT in TCS]).

The original abstract

I'll survey a few of many old and new results about these two similar, yet so different polynomials. The main purpose is to ask a few of many, old and new open problems about them, focusing on arithmetic complexity. No particular knowledge is required. After 1 hour we'll take a break, and for those who stay I'll give a few proofs.

Back to list of Oded's choices.