New Directions in Arithmetic and Boolean Circuit Complexity (Record no. 48851)
[ view plain ]
| 000 -LEADER | |
|---|---|
| fixed length control field | 01566nam a2200253Ia 4500 |
| 008 - FIXED-LENGTH DATA ELEMENTS--GENERAL INFORMATION | |
| fixed length control field | 160627s2011||||xx |||||||||||||| ||und|| |
| 080 ## - UNIVERSAL DECIMAL CLASSIFICATION NUMBER | |
| Universal Decimal Classification number | HBNI Th 28 |
| 100 ## - MAIN ENTRY--AUTHOR NAME | |
| Personal name | Srikanth Srinivasan |
| Relator term | author |
| 245 ## - TITLE STATEMENT | |
| Title | New Directions in Arithmetic and Boolean Circuit Complexity |
| 260 ## - PUBLICATION, DISTRIBUTION, ETC. (IMPRINT) | |
| Year of publication | 2011 |
| 300 ## - PHYSICAL DESCRIPTION | |
| Number of Pages | 103p. |
| 502 ## - DISSERTATION NOTE | |
| Dissertation note | 2011 |
| 502 ## - DISSERTATION NOTE | |
| Degree Type | Ph.D |
| 502 ## - DISSERTATION NOTE | |
| Name of granting institution | HBNI |
| 520 3# - SUMMARY, ETC. | |
| Summary, etc | Proving lower bounds has been a notoriously hard problem for Theoretical Computer Scientists. The purpose of this thesis is to supplement the efforts in many theorems regarding lower bounds in restricted models of computation: namely, to point out some interesting new directions for lower bounds, and take some steps towards resolving these questions. *This thesis studies the question of proving lower bounds for constant-depth Boolean circuits with help functions and noncommutative Algebraic Branching Programs with help polynomials; of proving lower bounds for monotone arithmetic circuits of bounded width; and of proving lower bounds on the size of noncommutative arithmetic circuits computing the noncommutative determinant. These problems are introduced in greater detail and the corresponding results are stated. |
| 650 14 - SUBJECT ADDED ENTRY--TOPICAL TERM | |
| Topical Term | Computer Science |
| 653 10 - INDEX TERM--UNCONTROLLED | |
| Uncontrolled term | Arithmetic Complexity |
| 653 10 - INDEX TERM--UNCONTROLLED | |
| Uncontrolled term | Boolean Circuit complexity |
| 653 10 - INDEX TERM--UNCONTROLLED | |
| Uncontrolled term | HBNI Th 28 |
| 720 1# - ADDED ENTRY--UNCONTROLLED NAME | |
| Thesis Advisor | Arvind, V. |
| Relator term | Thesis advisor [ths] |
| 856 ## - ELECTRONIC LOCATION AND ACCESS | |
| Uniform Resource Identifier | http://www.imsc.res.in/xmlui/handle/123456789/256 |
| 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 28 | 64968 | http://www.imsc.res.in/xmlui/handle/123456789/256 | THESIS & DISSERTATION |