Complexity Theoretic aspects of Rank Rigidity and circuit evaluation[HBNI Th8]

Abstract

This thesis studies some combinatorial, topological and linear algebraic parameters associated with Boolean and arithmetic circuits. It is divided into two parts, the first describes a study of combinations of graph theoretic or circuit theoretic restrictions that could be imposed on Boolean circuits to obtain complexity-theoretic characterisations for the circuit Value problem. The question of evaluating monotone planar circuits (MPCVP) is addressed. The second part of the thesis studies the complexity of some linear algebraic parameters associated with the circuits. The circuit and computational complexity of matrix rank are explored, and in general it is known to characterise a complexity class inside P. Several restricted cases of the problem to obtain algebraic characterisations of the complexity classes are studied. The complexity of computing the rigidity of a matrix - the minimum number of entries of the matrix that need to be changed in order to bring down a rank below a given value are studied with the motivation from applications of optimisation problems associated with matrix rank. A problem is formulated to construct explicit matrices which have super linear rigidity, using the language of algebraic geometry. The continuity properties of matrix rigidity function are studied. Some known combinatorial techniques are applied in the lower bound settings, to show almost optimal lower and upper bounds that for a rigidity of a restricted triangular matrices.