Nithish Raja G supervised by Dr. Suryajith Chillara received his Master of Science in Computer Science and Engineering (CSE). Here’s a summary of his research work on Extending Branching Programs with Memory:
In this study, we introduce new computational models, k-stack branching programs and queue branching programs, for computing polynomials and study their computational power. We show that the class VNP is exactly characterized by 2-stack branching programs and queue branching programs. We also show that increasing the number of stacks beyond 2 does not provide any gain in computational power. Next we study the computational power of k-stack branching programs by imposing restrictions such as stack height, branching program width and stack alphabet size. We give characterizations of the classes VF and VBP based on restricted k-stack branching programs. By definition, an exponential sum over a polynomial family in VP is always a polynomial family in VNP. We demonstrate a technique to construct a 2-stack branching program from exponential sum of a stack branching program. Using this technique, we give a proof for the fact that the exponential sum of a polynomial family in VBP is always a polynomial family in VNP.
June 2024