Lower Bounds for Perfect Matching in Restricted Boolean Circuits

Abstract

We consider three restrictions on Boolean circuits: bijectivity, consistency and multilinearity. Our main result is that Boolean circuits require exponential size to compute the bipartite perfect matching function when restricted to be (i) bijective or (ii) consistent and multilinear. As a consequence of the lower bound on bijective circuits, we prove an exponential size lower bound for monotone arithmetic circuits that compute the 0-1 permanent function. We also define a notion of homogeneity for Boolean circuits and show that consistent homogeneous circuits require exponential size to compute the bipartite perfect matching function. Motivated by consistent multilinear circuits, we consider certain restricted (⊕, ⋀) circuits and obtain an exponential lower bound for computing bipartite perfect matching using such circuits. Finally, we show that the lower bound arguments for the bipartite perfect matching function on all these restricted models can be adapted to prove exponential lower bounds for the Hamiltonian circuit problem in all these models.