Jayalal Sarma

This paper explores the power of catalytic computation when the catalytic space (c(n), the full memory whose content needs to be restored to the original by the end of computation) is much more than exponential in the pure space (s(n), the empty memory which does not have any access/restoration constraints). We study the following three regimes of the relation between s(n) and c(n) and explore the class CSPACE(s(n),c(n)) in each of them. • High-end regime - s(n)=O(c(n)ϵ): We show an implementation of incremental dynamic program using catalytic machines, thus showing that Knapsack problem (with n items, sum of their costs as C and the capacity of the bag as K) can be solved in O(nlog⁡nlog⁡C+log⁡(nKC)) pure space and O(n2KC3log2⁡Klog⁡n) catalytic space. Hence, catalytic algorithms can lead to a non-trivial saving in the pure space required for computation when K is Ω(n2). • Low-end regime - s(n)=O(1): We define the classes CR and CNR (nondeterministic variant of CR) where s(n)=O(1) and c(n)=poly(n). Exploring the connection between computational power of one counter machines (OC) and constant pure space catalytic Turing machines, we observe that OC⊆CR and show that CR⊆OC⇒CR≠CNR. We prove that L⊈CSPACE(O(1),o(n)). We also study the effect of adding additional read-only tapes to the model and show that: For any k∈N, (k+1)-CSPACE(O(1),O(nc))⊆CSPACE(klog⁡n,nc)⊆(4k+1)-CSPACE(O(1),O(nc)). • Low-end non-constant regime - s(n)=o(log⁡log⁡n): Let M be an oblivious catalytic Turing machine using s(n) pure space and c(n) catalytic space such that s(n)+log⁡c(n)=o(log⁡log⁡n) then L(M) is regular. This strengthens the classical theorem on s(n)=o(log⁡log⁡n) to the case of catalytic Turing machines. Our techniques include interesting generalizations of crossing sequence arguments and implementations of incremental dynamic programs using catalytic algorithms. These may be of independent interest.

We study projective dimension, a graph parameter (denoted by pd(G) for a graph G), introduced by Pudlák and Rödl (1992). For a Boolean function f(on n bits), Pudlák and Rödl associated a bipartite graph Gf and showed that size of the optimal branching program computing f (denoted by bpsize(f)) is at least pd(Gf) (also denoted by pd(f)). Hence, proving lower bounds for pd(f) imply lower bounds for bpsize(f). Despite several attempts (Pudlák and Rödl (1992), Rónyai et.al, (2000)), proving super-linear lower bounds for projective dimension of explicit families of graphs has remained elusive. We observe that there exist a Boolean function f for which the gap between the pd(f) and bpsize(f)) is 2Ω(n). Motivated by the argument in Pudlák and Rödl (1992), we define two variants of projective dimension - projective dimension with intersection dimension 1 (denoted by upd(f)) and bitwise decomposable projective dimension (denoted by bpdim(f)). We show the following results: (a) We observe that there exist a Boolean function f for which the gap between upd(f) and bpsize(f) is 2Ω(n). In contrast, we also show that the bitwise decomposable projective dimension characterizes size of the branching program up to a polynomial factor. That is, there exists a large constant c > 0 and for any function f, bpdim(f)/6 ≤ bpsize(f) ≤ (bpdim(f))c. (b) We introduce a new candidate function family f for showing super-polynomial lower bounds for bpdim(f). As our main result, we demonstrate gaps between pd(f) and the above two new measures for f: pd(f) = O(√n) upd(f) = Ω(n) bpdim(f) = Ω(n1.5/log n). (c) Although not related to branching program lower bounds, we derive exponential lower bounds for two restricted variants of pd(f) and upd(f) respectively by observing that they are exactly equal to well-studied graph parameters - bipartite clique cover number and bipartite partition number respectively.

We study projective dimension, a graph parameter, denoted by pd(G) for a bipartite graph G, introduced by Pudlák and Rödl (1992). For a Boolean function f (on n bits), Pudlák and Rödl associated a bipartite graph G f and showed that size of the optimal branching program computing f , denoted by bpsize(f ), is at least pd(G f ) (also denoted by pd(f )). Hence, proving lower bounds for pd(f ) implies lower bounds for bpsize(f ). Despite several attempts (Pudlák and Rödl (1992), Rónyai et al. (2000)), proving super-linear lower bounds for projective dimension of explicit families of graphs has remained elusive. We observe that there exist a Boolean function f for which the gap between the pd(f ) and bpsize(f )) is 2 Ω( n ) . Motivated by the argument in Pudlák and Rödl (1992), we define two variants of projective dimension: projective dimension with intersection dimension 1, denoted by upd(f ), and bitwise decomposable projective dimension, denoted by bitpdim(f ). We show the following results: (a) We observe that there exist a Boolean function f for which the gap between upd(f ) and bpsize(f ) is 2 Ω( n ) . In contrast, we also show that the bitwise decomposable projective dimension characterizes size of the branching program up to a polynomial factor. That is, there exists a constant c > 0 and for any function f , bitpdim(f )/6 ≤ bpsize(f ) ≤ (bitpdim(f )) c . (b) We introduce a new candidate family of functions f for showing super-polynomial lower bounds for bitpdim(f ). As our main result, for this family of functions, we demonstrate gaps between pd(f ) and the above two new measures for f : . We adapt Nechiporuk's techniques for our linear algebraic setting to prove the best-known bpsize lower bounds for bitpdim. Motivated by this linear algebraic setting of our main result, we derive exponential lower bounds for two restricted variants of pd(f ) and upd(f ) by observing that they are exactly equal to well-studied graph parameters-bipartite clique cover number and bipartite partition number, respectively.

We contribute to the program of proving lower bounds on the size of branching programs solving the Tree Evaluation Problem introduced by Cook et al. [2012]. Proving a superpolynomial lower bound for the size of nondeterministic thrifty branching programs would be an important step toward separating NL from P using the tree evaluation problem. First, we show that Read-Once Nondeterministic Thrifty BPs are equivalent to whole black-white pebbling algorithms, thus showing a tight lower bound (ignoring polynomial factors) for this model. We then introduce a weaker restriction of nondeterministic thrifty branching programs called Bitwise Independence. The best known [Cook et al. 2012] nondeterministic thrifty branching programs (of size O(kh/2+)) for the tree evaluation problem are Bitwise Independent. As our main result, we show that any Bitwise Independent Nondeterministic Thrifty Branching Program solving BT2(h, k) must have at least (k/2)h/2 states. Prior to this work, lower bounds were known for nondeterministic thrifty branching programs only for fixed heights h = 2, 3, 4 [Cook et al. 2012]. We prove our results by associating a fractional blackwhite pebbling strategy with any bitwise independent nondeterministic thrifty branching program solving the Tree Evaluation Problem. Such a connection was not known previously, even for fixed heights. Our main technique is the entropy method introduced by Jukna and Zák [2001] originally in the context of proving lower bounds for read-once branching programs. We also show that the previous lower bounds known [Cook et al. 2012] for deterministic branching programs for the Tree Evaluation Problem can be obtained using this approach. Using this method, we also show tight lower bounds for any k-way deterministic branching program solving the Tree Evaluation Problem when the instances are restricted to have the same group operation in all internal nodes.