Complexity Theoretic aspects of Rank Rigidity and circuit evaluation (Record no. 48811)
[ view plain ]
| 000 -LEADER | |
|---|---|
| fixed length control field | 02255nam a2200265Ia 4500 |
| 008 - FIXED-LENGTH DATA ELEMENTS--GENERAL INFORMATION | |
| fixed length control field | 160627s2009||||xx |||||||||||||| ||und|| |
| 080 ## - UNIVERSAL DECIMAL CLASSIFICATION NUMBER | |
| Universal Decimal Classification number | HBNI Th-8 |
| 100 ## - MAIN ENTRY--AUTHOR NAME | |
| Personal name | Jayalal Sarma, M. N. |
| Relator term | author |
| 245 ## - TITLE STATEMENT | |
| Title | Complexity Theoretic aspects of Rank Rigidity and circuit evaluation |
| 260 ## - PUBLICATION, DISTRIBUTION, ETC. (IMPRINT) | |
| Year of publication | 2009 |
| 300 ## - PHYSICAL DESCRIPTION | |
| Number of Pages | viii; 153p. |
| 502 ## - DISSERTATION NOTE | |
| Dissertation note | 2009 |
| 502 ## - DISSERTATION NOTE | |
| Degree Type | Ph.D |
| 502 ## - DISSERTATION NOTE | |
| Name of granting institution | HBNI |
| 520 3# - SUMMARY, ETC. | |
| Summary, etc | 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. |
| 650 14 - SUBJECT ADDED ENTRY--TOPICAL TERM | |
| Topical Term | Computer Science |
| 653 10 - INDEX TERM--UNCONTROLLED | |
| Uncontrolled term | Circuit Evaluation |
| 653 10 - INDEX TERM--UNCONTROLLED | |
| Uncontrolled term | Combinatorics |
| 653 10 - INDEX TERM--UNCONTROLLED | |
| Uncontrolled term | Matrix Rank |
| 653 10 - INDEX TERM--UNCONTROLLED | |
| Uncontrolled term | Optimisation Problems |
| 720 1# - ADDED ENTRY--UNCONTROLLED NAME | |
| Thesis Advisor | Meena Mahajan |
| Relator term | Thesis advisor [ths] |
| 856 ## - ELECTRONIC LOCATION AND ACCESS | |
| Uniform Resource Identifier | http://www.imsc.res.in/xmlui/handle/123456789/121 |
| 942 ## - ADDED ENTRY ELEMENTS (KOHA) | |
| Koha item type | THESIS & DISSERTATION |
| Withdrawn status | Lost status | Damaged status | Not for loan | Current library | Full call number | Accession Number | Uniform Resource Identifier | Koha item type |
|---|---|---|---|---|---|---|---|---|
| IMSc Library | HBNI Th-8 | 61481 | http://www.imsc.res.in/xmlui/handle/123456789/121 | THESIS & DISSERTATION |