상세정보
Export to Refworks부가기능
Connections Between Complexity Lower Bounds and Meta-computational Upper Bounds
상세 프로파일
| 자료유형 | 학위논문 |
|---|---|
| 서명/저자사항 | Connections Between Complexity Lower Bounds and Meta-computational Upper Bounds. |
| 개인저자 | Carmosino, Marco Leandro. |
| 단체저자명 | University of California, San Diego. Computer Science and Engineering. |
| 발행사항 | [S.l.]: University of California, San Diego., 2019. |
| 발행사항 | Ann Arbor: ProQuest Dissertations & Theses, 2019. |
| 형태사항 | 223 p. |
| 기본자료 저록 | Dissertations Abstracts International 81-05B. Dissertation Abstract International |
| ISBN | 9781687927972 |
| 학위논문주기 | Thesis (Ph.D.)--University of California, San Diego, 2019. |
| 일반주기 |
Source: Dissertations Abstracts International, Volume: 81-05, Section: B.
Advisor: Impagliazzo, Russell. |
| 이용제한사항 | This item must not be sold to any third party vendors.This item must not be added to any third party search indexes. |
| 요약 | This dissertation presents several results at the intersection of complexity theory and algorithm design. Complexity theory aims to lower-bound the amount of computational resources (such as time and space) required to solve interesting problems. Algorithm design aims to upper-bound the amount of computational resources required to solve interesting problems. These pursuits appear opposed. However, some algorithm design and complexity lower bound problems are inextricably connected.This dissertation explores several such connections. From "natural" proofs of circuit-size lower bounds, we create learning algorithms. From the exact hardness of problems in polynomial time, we create algorithms of estimating the acceptance probability of circuits. Finally, from algorithms for testing the identity of arithmetic circuits over finite fields, we create arithmetic circuit-complexity lower bounds. |
| 일반주제명 | Computer science. |
| 언어 | 영어 |
| 바로가기 | 
: 이 자료의 원문은 한국교육학술정보원에서 제공합니다. |
