Paul Beame, Michael Saks, Jayram S. Thathachar
We obtain the first non-trivial time-space tradeo # lower bound for functions f: {0,
Paul Beame, Michael Saks, Jayram S. Thathachar
We obtain the first non-trivial time-space tradeo # lower bound for functions f: {0,
Time-space tradeoffs for branching programs (1998)
Paul Beame, Michael Saks, Jayram S. Thathachar
We obtain the first non-trivial time-space tradeoff lower bound for functions f: f0; 1g
On Separating the Read-k-Times Branching Program Hierarchy (1998)
We obtain an exponential separation between consecutive levels in the hierarchy of classes of functions computable by polynomial-size syntactic read-k-times branching programs, for all k ? 0, as...
On the Limitations of Ordered Representations of Functions (1998)
We demonstrate the limitations of the various ordered representations that have been considered in the literature for symbolic model checking including BDDs [3], *-BMDs [6], HDDs [13], MTBDDs [11]...
On the Limitations of Ordered Representations of Functions (1997)
Jayram S. Thathachar, Jayram S. Thathachar
We introduce a lower bound technique that applies to a broad spectrum of functional representations including Binary Decision Diagrams (BDDs), Binary Moment Diagrams (*-BMDs), Hybrid Decision...
Random Striping for News on Demand Servers (1997)
Juan Alemany, Juan Alemany, Jayram S. Thathachar, Jayram S. Thathachar
We address the problem of assigning blocks of video streams to disks in News on Demand video servers. Specifically, given the common assumption that video streams are striped across the disks, we...
On the Limitations of Ordered Representations of Functions (1996)
Jayram S. Thathachar, Jayram S. Thathachar
We demonstrate the limitations of the various ordered representations that have been considered in the literature for symbolic model checking including OBDDs [Bry86], MTBDDs [CMZ + 93], EVBDDs...
Efficient Oblivious Branching Programs for Threshold and Mod Functions (1994)
Rakesh Kumar, Sinha Jayram, S. Thathachar, Jayram S. Thathachar
In his survey paper on branching programs, Razborov [Raz91] asked the following question: Does every rectifier-switching network computing the majority of n bits have size n1+\Omega\Gamma10 ? We...