• A Lower Bound for Boolean Permanent in Bijective Boolean Circuits and Its Consequences 

      Sengupta, Rimli; Venkateswaran, H. (Georgia Institute of Technology, 1994)
      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 ...
    • A Lower Bound for Noncommutative Monotone Arithmetic Circuits 

      Sengupta, Rimli (Georgia Institute of Technology, 1994)
      We consider arithmetic circuits over the semiring (∑*, min, concat) and show that such circuits require super-polynomial size to compute the lexicographically minimum perfect matching of a bipartite graph. By defining ...
    • Lower Bounds for Perfect Matching in Restricted Boolean Circuits 

      Sengupta, Rimli; Venkateswaran, H. (Georgia Institute of Technology, 1993)
      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 ...
    • Multilinearity Can Be Exponentially Restrictive (Preliminary Version) 

      Sengupta, Rimli; Venkateswaran, H. (Georgia Institute of Technology, 1994)
      We define a Boolean circuit to be multilinear if the formal polynomial associated with it is multilinear as well. We consider the problem of computing the connectivity function using circuits that are monotone and ...