H. Venkateswaran

TCS Journal 2000 Journal Article

Non-cancellative Boolean circuits: A generalization of monotone boolean circuits

• Rimli Sengupta
• H. Venkateswaran

Cancellations are known to be helpful in efficient algebraic computation of polynomials over fields. We define a notion of cancellation in Boolean circuits and define Boolean circuits that do not use cancellation to be non-cancellative. Non-cancellative Boolean circuits are a natural generalization of monotone Boolean circuits. We show that in the absence of cancellation, Boolean circuits require super-polynomial size to compute the determinant interpreted over GF(2). This non-monotone Boolean function is known to be in P. In the spirit of monotone complexity classes, we define complexity classes based on non-cancellative Boolean circuits. We show that when the Boolean circuit model is restricted by withholding cancellation, P and popular classes within P are restricted as well, but NP and circuit definable classes above it remain unchanged.

TCS Journal 1998 Journal Article

A lower bound for monotone arithmetic circuits computing 0–1 permanent

• Rimli Sengupta
• H. Venkateswaran

I&C Journal 1993 Journal Article

A Circuit-Based Proof of Toda′s Theorem

• R. Kannan
• H. Venkateswaran
• V. Vinay
• A.C. Yao

We present a simple proof of Toda′s result (Toda (1989), in "Proceedings, 30th Annual IEEE Symposium on Foundations of Computer Science, " pp. 514-519), which states that ⊕ P is hard for the Polynomial Hierarchy under randomized reductions. Our approach is circuit-based in the sense that we start with uniform circuit definitions of the Polynomial Hierarchy and apply the Valiant-Vazirani lemma on these circuits (Valiant and Vazirani (1986), Thoeret. Comput. Sci. 47, 85-93).

I&C Journal 1991 Journal Article

Two dynamic programming algorithms for which interpreted pebbling helps

• H. Venkateswaran

We consider extensions of one-person and two-person pebble games that take into account the types of the gates of the circuits on which the games are played. A simple relationship is established between the extended games and the corresponding original games. This is useful in showing that the extended games allow more efficient pebbling than the original games on certain natural circuits for problems such as context-free language recognition and transitive closure of directed graphs.

STOC Conference 1987 Conference Paper

Properties that Characterize LOGCFL

• H. Venkateswaran

Two properties, called semi-unboundedness , and polynomial proof-size , are identified as key properties shared by the definitions of LOGCFL on several models of computations. The semi-unboundedness property leads to the definition of new models of computation based on unbounded fan-in circuits. These are circuits obtained from unbounded fan-in circuits by restricting the fan-in of gates of one type. A new characterization of LOGCFL is obtained on such a model in which the fan-in of the AND gates are bounded by a constant. This property also suggests new characterizations of LOGCFL on the following models: alternating Turing machines [CKS81], nondeterministic auxiliary pushdown automata [Co71], and bounded fan-in Boolean circuits [Co85].

FOCS Conference 1986 Conference Paper

A New Pebble Game that Characterizes Parallel Complexity Classes

• H. Venkateswaran
• Martin Tompa

A new two-person pebble game that models parallel computations is defined. This game extends the two-person pebble game defined in [DT85] and is used to characterize two natural parallel complexity classes, namely LOGCFL and AG1. The characterizations show a fundamental way in which the computations in these two classes differ. This game model also unifies the proofs of some well known results of complexity theory.