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 full item record

Title: Complexity Theoretic aspects of Rank Rigidity and circuit evaluation[HBNI Th 8]
Author: Jayalal Sarma, M. N.
Advisor: Meena Mahajan
Degree: Ph.D
Main Subjects: Computer Science
Institution: HBNI
Year: 2009
Pages: viii; 153p.
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.
URI: http://hdl.handle.net/123456789/121

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 full item record

Search DSpace


Advanced Search

Browse

My Account