# Wonders of the Digital Envelope Happy Birthday Les ! Valiants Permanent gift to TCS to TCS Avi Wigderson Institute for Advanced Valiants gift to me -my postdoc problems! [Valiant 82] Parallel computation, Proc. Of 7th IBM symposium on mathematical foundations of computer science. Are the following inherently sequential? -Finding maximal independent set?

[Karp-Wigderson] No! NC algorithm. -Finding a perfect matching? The Permanent X11,X12,, X1n X21,X22,, X2n X = X ,X ,, X Xi(i) n1 n2 nn to Pern(X) = Sn i[n] TCS

[Valiant 79] The complexity of computing the permanent [Valiant 79] The complexity of enumeration and reliability problems Valiant brought the Permanent, polynomials and Algebra into the focus of TCS research. Plan of the talk As many results and questions as I can squeeze in an hour about the Permanent and friends: Determinant, Perfect matching, counting Monotone formulae for Majority M Y

X17 Y2 1 X3 Y X37 1 0 V V V X1

F 0 Y Xm1 X2 V V [Valiant]: random! exp(-k) 1 Xk V

X2 V X1 m=k10 Pr[ F Majk ] < Counting classes: PP, #P, P#P, M [Gill] PP X1 X2 X3

C(000) C(001) Xk C(111) C = C(Z1,Z2,,Zn) is a small circuit/formula, k=2n, + [Valiant] #P X1 X2 X3 C(000) C(001) Xk C(111)

The richness of #P-complete problems V NP SAT CLIQUE C(000) C(001) #SAT #P #CLIQUE Permanent C(000) C(001) #2-SAT Network Reliability Monomer-Dimer Ising, Potts, Tutte

C(111) + C(111) Enumeration, Algebra, Probability, Stat. The power of counting: Todas Theorem PH P NP PSPACE P#P NP [Valiant-Vazirani]

PROBABILISTIC Poly-time reduction:C(000) C(001) CD OPEN: Deterministic Valiant-Vazirani? +P D(000) C(001) V C(111) + C(111) Nice properties of Permanent Per is downwards self-reducible

Pern(X) = Sn i[n] Xi(i) Pern(X) = i[n] Pern-1(X1i) Per is random self-reducible [Beaver-Feigenbaum, Lipton] C errs on 1/(8n) Interpolate Pern(X) from C(X+iY) with Y random, C errs x+2y x+3y x+y Fnxn

x Hardness amplification If the Permanent can be efficiently computed for most inputs, then it can for all inputs ! If the Permanent is hard in the worst-case, then it is also hard on average Worst-case Average case reduction Works for any low degree polynomial. Arithmetization: Boolean functionspolynomials Avalanche of consequences to probabilistic proof systems Using both RSR and DSR of Permanent! [Nisan] Per 2IP [Lund-Fortnow-Karloff-Nisan] Per IP

[Shamir] IP = PSPACE [Babai-Fortnow-Lund] 2IP = NEXP [Arora-Safra, Arora-Lund-Motwani-Sudan-Szegedy] PCP = NP Which classes have complete RSR problems? EXP PSPACE Low degree extensions #P Permenent PH NP No Black-Box reductions P [Fortnow-Feigenbaum,BogdanovTrevisan] NC2 Determinant

L NC1 [Barrington] ? OPEN: Non Black-Box reductions? On what fraction of inputs can we compute Permanent? Assume: a PPT algorithm A computer Pern for on fraction of all matrices in Mn(Fp). =1 #P = BPP =1-1/n #P = BPP [Lipton] =1/nc #P = BPP [CaiPavanSivakumar] =n3/p

#P = PH =AM [FeigeLund] =1/p possible! Hardness vs. Randomness [Babai-Fortnaow-Nisan-Wigderson] EXP P/poly BPP SUBEXP [Impagliazzo-Wigderson] EXP BPP BPP SUBEXP Proof: EXP P/poly Were done EXP P/poly

Per is EXP-complete [Karp-Lipton,Toda] workRSRDSR work [Kabanets-Impagliazzo] Permanent is easy iff Identity Testing can be derandomized Non-relativizing & Nonnatural circuit lower bounds [Vinodchandran]: PP SIZE(n10) [Aaronson]: This result doesnt relativize Vinodchandrans Proof: PP P/poly Were done [Santhanam]:

NonRelativizing PP P/poly P#P = MA [LFKN] Non-Natural P#P = PP 2P PP [Toda] PP SIZE(n10) [Kannan] MA/1 SIZE(n10) OPEN: Prove NP SIZE(n10) [Aaronson-Wigderson] requires non- The power of negation Arithmetic circuits PMP(G) Perfect Matching polynomial of G

[ShamirSnir,TiwariTompa]: msize(PMP(Kn,n)) > exp(n) [FisherKasteleynTemperly]:size(PMP(Gridn,n)) = poly(n) Boolean circuitsn,n)) > [Valiant]: msize(PMP(Grid PM Perfect Matching function exp(n) [Edmonds]: size(PM) = poly(n) [Razborov]: tight? msize(PM) > nlogn

OPEN: The power of Determinant (and linear algebra) XMk(F) Detk(X) = Sk sgn() i[k] Xi(i) [Kirchoff]: counting spanning trees in n-graphs Detn [FisherKasteleynTemperly]: counting perfect matchings in planar n-graphs Detn [Valiant, Cai-Lu] Holographic algorithms [Valiant]: evaluating size n formulae Detn [Hyafill, ValiantSkyumBerkowitzRackoff]: nlogd

Algebraic analog of PNP F field, char(F)2. XMk(F) YMn(F) Detk(X) = Sk sgn() i[k] Xi(i) Pern(Y) = Sn i[n] Yi(i) Affine map L: Mn(F) Mk(F) is good if Pern = Detk L k(n): the smallest k for which there is a good map? [Polya] k(2) =2 Per2 a b = Det2 cd

ab -c d [Valiant] F k(n) < exp(n) [Mignon-Ressayre] F k(n) > n2 [Valiant] k(n) poly(n) PNP [Mulmuley-Sohoni] Algebraic-geometric approach Detn vs. Pern [Nisan] Both require noncommutative arithmetic branching programs of size 2n [Raz] Both require multilinear arithmetic formulae of size nlogn [Pauli,Troyansky-Tishby] Both equally computable by nature- quantum state of n identical particles: bosons Pern, fermions Detn

[Ryser] Pern has depth-3 circuits of size n22n OPEN: Improve n! for Detn Approximating Pern A: nn 0/1 matrix. B: Bij Aij at random [Godsil-Gutman] Pern(A) = E[Detn(B)2] [KarmarkarKarpLiptonLovaszLuby] variance = 2n B: Bij AijRij with random Rij, E[R]=0, E[R2]=1 Use R={,2,3=1}. variance 2n/2 [Chien-Luby-Rassmusen] R non commutative! Use R={C1,C2,..Cn} elements of Clifford algebra. variance poly(n) Approx scheme? OPEN: Compute Det(B) Approx Pern deterministically

A: nn non-negative real matrix. [Linial-Samorodnitsky-Wigderson] Deterministic e-n -factor approximation. Two ingredients: (1) [Falikman,Egorichev] If B Doubly Stochastic then e-n n!/nn Per(B) 1 (the lower bound solved van der Vardens conj) (2) Strongly polynomial algorithm for the following reduction to DS matrices: Matrix scaling: Find diagonal X,Y s.t. XAY is DS OPEN: Find a deterministic subexp approx. Many happy returns, Les !!!