Exploring Size Complexity and Randomness in the Query Model (Record no. 60500)
[ view plain ]
| 000 -LEADER | |
|---|---|
| fixed length control field | 01627nam a22002057a 4500 |
| 008 - FIXED-LENGTH DATA ELEMENTS--GENERAL INFORMATION | |
| fixed length control field | 240628b |||||||| |||| 00| 0 eng d |
| 041 ## - LANGUAGE CODE | |
| Language code of text/sound track or separate title | eng |
| 080 ## - UNIVERSAL DECIMAL CLASSIFICATION NUMBER | |
| Universal Decimal Classification number | HBNI |
| Item number | Th245 |
| 100 ## - MAIN ENTRY--AUTHOR NAME | |
| Personal name | Dahiya, Yogesh |
| Relator term | author |
| 245 ## - TITLE STATEMENT | |
| Title | Exploring Size Complexity and Randomness in the Query Model |
| 260 ## - PUBLICATION, DISTRIBUTION, ETC. (IMPRINT) | |
| Place of publication | Chennai |
| Name of publisher | The Institute of Mathematical Sciences |
| Year of publication | 2024 |
| 300 ## - PHYSICAL DESCRIPTION | |
| Number of Pages | xxii, 205p. |
| 502 ## - DISSERTATION NOTE | |
| Degree Type | Ph.D |
| Name of granting institution | HBNI |
| Year degree granted | 2024 |
| 520 ## - SUMMARY, ETC. | |
| Summary, etc | Decision trees, also known as query models, are one of the simplest and most<br/>basic models of computation, where a computational task is performed by adaptively<br/>querying the input with the goal of minimizing the number of queries. Despite its<br/>simplicity, it still remains a puzzle with many unresolved questions and have been<br/>central to significant breakthroughs in recent years. These advancements include new<br/>connections between proof complexity and query complexity, and the development<br/>of query-to-communication lifting theorems, which have yielded new insights in<br/>proof complexity, Boolean circuit complexity, and communication complexity. In<br/>the decision tree model, there are two natural complexity measures of importance:<br/>the depth complexity (the worst-case number of queries asked by a query algorithm)<br/>and the size complexity (the space required to store the query algorithm). While<br/>significant attention has been devoted to the former, the latter remains relatively<br/>under-explored. |
| 650 ## - SUBJECT ADDED ENTRY--TOPICAL TERM | |
| Topical Term | Mathematics |
| 690 ## - LOCAL SUBJECT ADDED ENTRY--TOPICAL TERM (OCLC, RLIN) | |
| Topical term or geographic name as entry element | Mathematics |
| 720 ## - ADDED ENTRY--UNCONTROLLED NAME | |
| Thesis Advisor | Meena Mahajan |
| Relator term | Thesis Advisor [ths] |
| 856 ## - ELECTRONIC LOCATION AND ACCESS | |
| Uniform Resource Identifier | https://dspace.imsc.res.in/xmlui/handle/123456789/881 |
| 942 ## - ADDED ENTRY ELEMENTS (KOHA) | |
| Koha item type | THESIS & DISSERTATION |
| Withdrawn status | Lost status | Damaged status | Not for loan | Collection code | Current library | Shelving location | Full call number | Accession Number | Uniform Resource Identifier | Koha item type |
|---|---|---|---|---|---|---|---|---|---|---|
| 1 | IMSc Thesis | IMSc Library | IN PROCESS | HBNI Th245 | 78044 | https://dspace.imsc.res.in/xmlui/handle/123456789/881 | THESIS & DISSERTATION |