PUBLIC VIVAVOCE NOTIFICATION 11.30 am, Seminar Hall Succinct Numbers, Skew Circuits and Bounded Treewidth Graphs: Algorithms and Complexity Nikhil Balaji 210716 Abstract In this thesis, we concern ourselves with three broad themes that are loosely tied together by the aim to improve our understanding of the complexity of counting problems: 1) Inferring properties of succinctly represented numbers and matrices: We study the complexity of computing some simple properties of numbers represented via arithmetic circuits. We give improved algorithms (all of which lie in the Counting Hierarchy) for the problems of obtaining an arbitrary bit of a) A number represented by an arithmetic circuit. b) A constantsized matrix with nbit entries raised to nbit powers. c) An nbit number raised to nbit powers. We also show a weak reduction (in the Counting Hierarchy) of the classic Sum of Square Roots problem to the problem of powering (2x2) matrices to nbit powers. 2) Skew circuits of small width: We study width5 branching programs and Barringtonâs Theorem via a special class of structurally restricted circuits, namely \emph{skew} circuits. We prove that skew circuits of width7 captureNC^1. We then study the complexity hierarchy within width7, and show some separations and inclusions between these classes. 3) Counting problems on bounded treewidth graphs: We first study the complexity of computing linear algebraic invariants like the Determinant, rank, characteristic polynomial, etc. for matrices whose underying graph is bounded treewidth. We show tight Logspace upper and lower bounds for all these invariants. We also study the problem of counting Euler tours on bounded treewidth graphs. Our Logspace Determinant algorithm gives an efficient way to count Euler tours on directed graphs. In the case of undirected graphs, this problem is known to be #Pcomplete on general graphs. We give an NC^2algorithm for this problem on bounded treewidth graphs.
