A Lower Bound for Monotone Arithmetic Circuits Computing 0-1 Permanent.pdf

A Lower Bound for Monotone Arithmetic CircuitsComputing 0-1 Permanent Rimli SenguptaDept. of Computer ScienceRose-Hulman Institute of TechnologyTerre Haute, IN 47803-3999e-mail: rimli@cs.rose-hulman.edu H. VenkateswaranCollege of ComputingGeorgia Institute of TechnologyAtlanta, GA 30332-0280e-mail : venkat@cc.gatech.eduMarch 11, 1998Keywords permanent, size lower bound, arithmetic circuit.1 IntroductionThe permanent of an n n matrix X = [xij] is dened as follows:PERM[X] = X2Sn Yi=1;nxi;(i);where Sn is the set of all permutation functions on n elements. Despite its similarity withthe determinant polynomial, the permanent is believed to be much harder to compute than thedeterminant [7].In [1], Jerrum and Snir showed that algebraic circuits over certain semirings require exponentialsize to compute the permanent polynomial. In particular, their lower bound applies to the semiringof reals, with the usual multiplication and addition operators. Since there are no additive inverses,circuits over such an algebra can only compute \monotone polynomials, that is, polynomials withpositive coecients. To re ect this, we refer to circuits over the semiring of reals as monotonearithmetic circuits. Such circuits are distinct from monotone Boolean circuits studied by Razborovin [3].We consider the problem of computing the permanent of matrices with only 0-1 entries. Thisversion of the permanent problem has a natural interpretation for graphs: if the nn 0-1 matrix XThis work was supported in part by NSF grant CCR-9200878.1 represents a bipartite graph U [V with n vertices in each partition such that xij = 1 i there is anedge between vertex i 2 U and vertex j 2 V , then PERM[X] counts the number of perfect matchingsin the bipartite graph. Prior to the size lower bound in [1], Shamir and Snir [5] had shown a lineardepth lower bound for computing the permanent polynomial using monotone arithmetic circuits.Nisan [2] gives a alternative proof of this depth result by showing an expo