| LDR | | 00000nam u2200205 4500 |
| 001 | | 000000433468 |
| 005 | | 20200225142346 |
| 008 | | 200131s2019 ||||||||||||||||| ||eng d |
| 020 | |
▼a 9781687927972 |
| 035 | |
▼a (MiAaPQ)AAI22618052 |
| 040 | |
▼a MiAaPQ
▼c MiAaPQ
▼d 247004 |
| 082 | 0 |
▼a 004 |
| 100 | 1 |
▼a Carmosino, Marco Leandro. |
| 245 | 10 |
▼a Connections Between Complexity Lower Bounds and Meta-computational Upper Bounds. |
| 260 | |
▼a [S.l.]:
▼b University of California, San Diego.,
▼c 2019. |
| 260 | 1 |
▼a Ann Arbor:
▼b ProQuest Dissertations & Theses,
▼c 2019. |
| 300 | |
▼a 223 p. |
| 500 | |
▼a Source: Dissertations Abstracts International, Volume: 81-05, Section: B. |
| 500 | |
▼a Advisor: Impagliazzo, Russell. |
| 502 | 1 |
▼a Thesis (Ph.D.)--University of California, San Diego, 2019. |
| 506 | |
▼a This item must not be sold to any third party vendors. |
| 506 | |
▼a This item must not be added to any third party search indexes. |
| 520 | |
▼a 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. |
| 590 | |
▼a School code: 0033. |
| 650 | 4 |
▼a Computer science. |
| 690 | |
▼a 0984 |
| 710 | 20 |
▼a University of California, San Diego.
▼b Computer Science and Engineering. |
| 773 | 0 |
▼t Dissertations Abstracts International
▼g 81-05B. |
| 773 | |
▼t Dissertation Abstract International |
| 790 | |
▼a 0033 |
| 791 | |
▼a Ph.D. |
| 792 | |
▼a 2019 |
| 793 | |
▼a English |
| 856 | 40 |
▼u http://www.riss.kr/pdu/ddodLink.do?id=T15493509
▼n KERIS
▼z 이 자료의 원문은 한국교육학술정보원에서 제공합니다. |
| 980 | |
▼a 202002
▼f 2020 |
| 990 | |
▼a ***1008102 |
| 991 | |
▼a E-BOOK |