A Lower Bound for Boolean Permanent in Bijective Boolean Circuits and Its Consequences
MetadataShow full item record
We identify a new and non-trivial restriction called bijectivity on Boolean circuits and prove an exponential size lower bound for computing the Boolean permanent matching function in this model. As consequences of this lower bound, we show exponential size lower bounds for: (a) computing the Boolean permanent using monotone multilinear circuits; (b) computing the 0-1 permanent function using monotone arithmetic circuits; and (c) computing the lexicographically first bipartite perfect matching function using circuits over (min, concat). The lower bound arguments for the Boolean permanent function are adapted to prove an exponential lower bound for computing the Hamiltonian cycle function using bijective circuits. We identify a class of monotone functions such that if their counting version is #P-hard, then there are no polynomial size bijective circuits for such functions unless PH collapses.