| LDR | | 00000nam u2200205 4500 |
| 001 | | 000000431497 |
| 005 | | 20200224101846 |
| 008 | | 200131s2019 ||||||||||||||||| ||eng d |
| 020 | |
▼a 9781392766347 |
| 035 | |
▼a (MiAaPQ)AAI13904638 |
| 040 | |
▼a MiAaPQ
▼c MiAaPQ
▼d 247004 |
| 082 | 0 |
▼a 004 |
| 100 | 1 |
▼a Thiruvenkatachari, Devanathan. |
| 245 | 10 |
▼a Approximation Algorithms, Hardness, and PCPs. |
| 260 | |
▼a [S.l.]:
▼b New York University.,
▼c 2019. |
| 260 | 1 |
▼a Ann Arbor:
▼b ProQuest Dissertations & Theses,
▼c 2019. |
| 300 | |
▼a 144 p. |
| 500 | |
▼a Source: Dissertations Abstracts International, Volume: 81-06, Section: B. |
| 500 | |
▼a Advisor: Khot, Subhash. |
| 502 | 1 |
▼a Thesis (Ph.D.)--New York University, 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 thesis is a collection of theoretical results on the topic of approximationalgorithms and hardness of approximation. The results presented here use acombination of classical and modern techniques to achieve better approximationalgorithms and hardness results for some pivotal NP-hard problems and theirvariants. We study CSPs from a multi-objective point of view, with the goal ofsimultaneous optimization of multiple instances over the same set of variables,withMAX-CUT as the central focus. We provide an approximation algorithm thatis near optimal assuming the unique games conjecture. We also study PCPs andtheir role in hardness of approximation, and present a hardness result for 3-LINin the sub-constant soundness regime. Lastly, dictatorship testing is a propertytesting problem with significant applications in proving hardness results, andwe present an improvement on the soundness of the k-bit dictatorship test withperfect completeness. |
| 590 | |
▼a School code: 0146. |
| 650 | 4 |
▼a Computer science. |
| 690 | |
▼a 0984 |
| 710 | 20 |
▼a New York University.
▼b Computer Science. |
| 773 | 0 |
▼t Dissertations Abstracts International
▼g 81-06B. |
| 773 | |
▼t Dissertation Abstract International |
| 790 | |
▼a 0146 |
| 791 | |
▼a Ph.D. |
| 792 | |
▼a 2019 |
| 793 | |
▼a English |
| 856 | 40 |
▼u http://www.riss.kr/pdu/ddodLink.do?id=T15492553
▼n KERIS
▼z 이 자료의 원문은 한국교육학술정보원에서 제공합니다. |
| 980 | |
▼a 202002
▼f 2020 |
| 990 | |
▼a ***1008102 |
| 991 | |
▼a E-BOOK |