All reports by Author Jayram S. Thathachar:

__
TR98-053
| 30th August 1998
__

Paul Beame, Michael Saks, Jayram S. Thathachar#### Time-Space Tradeoffs for Branching Programs

Comments: 1

__
TR98-002
| 8th January 1998
__

Jayram S. Thathachar#### On Separating the Read-k-Times Branching Program Hierarchy

Paul Beame, Michael Saks, Jayram S. Thathachar

We obtain the first non-trivial time-space tradeoff lower bound for

functions f:{0,1}^n ->{0,1} on general branching programs by exhibiting a

Boolean function f that requires exponential size to be computed by any

branching program of length cn, for some constant c>1. We also give the first

separation result between the ...
more >>>

Jayram S. Thathachar

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

{\em all\/} $k>0$, as conjectured by various

authors~\cite{weg87,ss93,pon95b}. For every $k$, we exhibit two

explicit functions that can be computed by linear-sized

read-$(\kpluso)$-times branching programs but ...
more >>>