|
PUBLIC VIVA-VOCE NOTIFICATION 11.30 am, Seminar Hall Succinct Numbers, Skew Circuits and Bounded Treewidth Graphs: Algorithms and Complexity Nikhil Balaji 21-07-16 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 constant-sized matrix with n-bit entries raised to n-bit powers. c) An n-bit number raised to n-bit 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 n-bit powers. 2) Skew circuits of small width: We study width-5 branching programs and Barringtonâs Theorem via a special class of structurally restricted circuits, namely \emph{skew} circuits. We prove that skew circuits of width-7 captureNC^1. We then study the complexity hierarchy within width-7, 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 #P-complete on general graphs. We give an NC^2-algorithm for this problem on bounded treewidth graphs.
|
