IIIT Hyderabad Publications 


Extending Branching Programs with MemoryAuthor: Nithish Raja 2021201079 Date: 20240625 Report no: IIIT/TH/2024/134 Advisor:Suryajith Chillara AbstractIn this study, we continue the line of research that was initiated by Mengel [Men13] wherein he showed that by augmenting algebraic branching programs with a single stack as memory and randomaccess memory we obtain characterizations for the classes VP and VNP respectively. In this thesis, we introduce kstack branching programs, a generalization of Mengel’s singlestack branching program, and show that when k ⩾ 2, the computational model characterizes the class VNP. Due to this, we get a clean characterization of the classes VBP, VP, and VNP using algebraic branching programs with 0, 1, and 2 stacks as memory. Similar to what happens with pushdown automata, we show that a branching program with 2 stacks as memory is equivalent to a branching program with a queue as memory. Next, we impose restrictions such as bounded stack height and bounded branching program width upon stack branching programs and show that any polynomial family in VP can be computed by a polynomialsized stack branching program with the stack height bounded by O(log(n) 2 ). Finally, we detail a technique using which we can construct a (k + 1)stack branching program that computes P ¯(e)∈{0,1}m−n qm(x1, · · · , xn, e¯) when given a kstack branching program that computes qm(x1, · · · , xn, e¯). Using this we give an alternate proof for the fact that exponential summation of a polynomial family in VP gives a polynomial family in VNP which was originally shown in [Val82]. This technique combined with one of the previous result of adding more stacks to a 2stack branching program does not increase the computational power gives us alternate proofs for • exponential summation of a polynomial family in VBP gives a polynomial family in VNP and • exponential summation of a polynomial family in VNP gives a polynomial family in VNP. Full thesis: pdf Centre for Security, Theory and Algorithms 

Copyright © 2009  IIIT Hyderabad. All Rights Reserved. 