| LDR | | 02615nmm uu200469 4500 |
| 001 | | 000000331505 |
| 005 | | 20240805164522 |
| 008 | | 181129s2018 |||||||||||||||||c||eng d |
| 020 | |
▼a 9780438345003 |
| 035 | |
▼a (MiAaPQ)AAI10928893 |
| 035 | |
▼a (MiAaPQ)cornellgrad:11095 |
| 040 | |
▼a MiAaPQ
▼c MiAaPQ
▼d 248032 |
| 082 | 0 |
▼a 004 |
| 100 | 1 |
▼a Hopkins, Samuel.
▼0 (orcid)0000-0001-6519-8079 |
| 245 | 10 |
▼a Statistical Inference and the Sum of Squares Method. |
| 260 | |
▼a [S.l.] :
▼b Cornell University.,
▼c 2018 |
| 260 | 1 |
▼a Ann Arbor :
▼b ProQuest Dissertations & Theses,
▼c 2018 |
| 300 | |
▼a 430 p. |
| 500 | |
▼a Source: Dissertation Abstracts International, Volume: 80-01(E), Section: B. |
| 500 | |
▼a Adviser: David Steurer. |
| 502 | 1 |
▼a Thesis (Ph.D.)--Cornell University, 2018. |
| 520 | |
▼a Statistical inference on high-dimensional and noisy data is a central concern of modern computer science. Often, the main challenges are inherently computational: the problems are well understood from a purely statistical perspective, but key st |
| 520 | |
▼a We develop a unified approach to algorithm design for statistical inference based on the Sum of Squares method, a powerful tool for convex programming with low-degree polynomials, which generalizes linear programming and spectral algorithms. We |
| 520 | |
▼a We also prove computational lower bounds for some statistical problems, including the long-studied planted clique problem. Our lower bounds provide new strong evidence for the existence of information-computation gaps -- that is, statistical pro |
| 520 | |
▼a We show that polynomial-size semidefinite programs from the Sum of Squares hierarchy cannot refute the existence of cliques of size much less than the square root of n in n-node random graphs. Additionally, we prove a lower bound for sparse prin |
| 520 | |
▼a Our approach to algorithms and lower bounds suggests a new method to chart the edge of algorithmic tractability for statistical inference. We propose a classification of Bayesian inference problems according to solvability by algorithms which co |
| 590 | |
▼a School code: 0058. |
| 650 | 4 |
▼a Computer science. |
| 650 | 4 |
▼a Mathematics. |
| 650 | 4 |
▼a Statistics. |
| 690 | |
▼a 0984 |
| 690 | |
▼a 0405 |
| 690 | |
▼a 0463 |
| 710 | 20 |
▼a Cornell University.
▼b Computer Science. |
| 773 | 0 |
▼t Dissertation Abstracts International
▼g 80-01B(E). |
| 773 | |
▼t Dissertation Abstract International |
| 790 | |
▼a 0058 |
| 791 | |
▼a Ph.D. |
| 792 | |
▼a 2018 |
| 793 | |
▼a English |
| 856 | 40 |
▼u http://www.riss.kr/pdu/ddodLink.do?id=T15000924
▼n KERIS |
| 980 | |
▼a 201812
▼f 2019 |
| 990 | |
▼a 관리자 |