Show simple item record

dc.contributor.authorSengupta, Rimlien_US
dc.contributor.authorVenkateswaran, H.
dc.date.accessioned2005-06-17T18:05:14Z
dc.date.available2005-06-17T18:05:14Z
dc.date.issued1993en_US
dc.identifier.urihttp://hdl.handle.net/1853/6787
dc.description.abstractWe 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.en_US
dc.format.extent255769 bytes
dc.format.mimetypeapplication/pdf
dc.language.isoen_US
dc.publisherGeorgia Institute of Technologyen_US
dc.relation.ispartofseriesCC Technical Report; GIT-CC-93-66en_US
dc.subjectBoolean circuits
dc.subjectBijectivity
dc.subjectMultilinearity
dc.subjectExponential size lower bounds
dc.subjectBipartite perfect matching functions
dc.subjectRestricted circuits
dc.subjectHamiltonian circuit problem
dc.titleLower Bounds for Perfect Matching in Restricted Boolean Circuitsen_US
dc.typeTechnical Reporteng_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record