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

DSpace/Manakin Repository

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

Show simple item record Jayalal Sarma, M. N. 2009-09-18T10:33:41Z 2009-09-18T10:33:41Z 2009-09-18T10:33:41Z 2009
dc.description.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. en_US
dc.subject Circuit Evaluation en_US
dc.subject Combinatorics en_US
dc.subject Optimisation Problems en_US
dc.subject Matrix Rank en_US
dc.title Complexity Theoretic aspects of Rank Rigidity and circuit evaluation[HBNI Th 8] en_US Ph.D en_US
dc.type.institution HBNI en_US
dc.description.advisor Meena Mahajan
dc.description.pages viii; 153p. en_US
dc.type.mainsub Computer Science en_US

Files in this item

Files Size Format View
jayalal-sharma-phd.pdf 1.338Mb PDF View/Open

This item appears in the following Collection(s)

Show simple item record

Search DSpace

Advanced Search


My Account