서브메뉴
검색
A Complexity-Theoretic Perspective on Convex Geometry
A Complexity-Theoretic Perspective on Convex Geometry
상세정보
- 자료유형
- 학위논문 서양
- 최종처리일시
- 20250211151511
- ISBN
- 9798383591604
- DDC
- 004
- 서명/저자
- A Complexity-Theoretic Perspective on Convex Geometry
- 발행사항
- [Sl] : Columbia University, 2024
- 발행사항
- Ann Arbor : ProQuest Dissertations & Theses, 2024
- 형태사항
- 294 p
- 주기사항
- Source: Dissertations Abstracts International, Volume: 86-02, Section: B.
- 주기사항
- Advisor: Servedio, Rocco;Yannakakis, Mihalis.
- 학위논문주기
- Thesis (Ph.D.)--Columbia University, 2024.
- 초록/해제
- 요약This thesis considers algorithmic and structural aspects of high-dimensional convex sets with respect to the standard Gaussian measure.Among our contributions, (i) we introduce a notion of influence for convex sets that yields the first quantitative strengthening of Royen's celebrated Gaussian correlation inequality; (ii) we investigate the approximability of general convex sets by intersections of halfspaces, where the approximation quality is measured with respect to the standard Gaussian distribution; and (iii) we give the first lower bounds for testing convexity and estimating the distance to convexity of an unknown set in the black-box query model.Our results and techniques are inspired by a number of fundamental ingredients and results---such as the influence of variables, noise sensitivity, and various extremal constructions---from the analysis of Boolean functions in complexity theory.
- 일반주제명
- Computer science
- 일반주제명
- Mathematics
- 일반주제명
- Theoretical mathematics
- 키워드
- Convex geometry
- 키워드
- Gaussian measure
- 기타저자
- Columbia University Computer Science
- 기본자료저록
- Dissertations Abstracts International. 86-02B.
- 전자적 위치 및 접속
- 로그인 후 원문을 볼 수 있습니다.
MARC
008250123s2024 us c eng d■001000017161988
■00520250211151511
■006m o d
■007cr#unu||||||||
■020 ▼a9798383591604
■035 ▼a(MiAaPQ)AAI31299836
■040 ▼aMiAaPQ▼cMiAaPQ
■0820 ▼a004
■1001 ▼aNadimpalli, Shivam.
■24512▼aA Complexity-Theoretic Perspective on Convex Geometry
■260 ▼a[Sl]▼bColumbia University▼c2024
■260 1▼aAnn Arbor▼bProQuest Dissertations & Theses▼c2024
■300 ▼a294 p
■500 ▼aSource: Dissertations Abstracts International, Volume: 86-02, Section: B.
■500 ▼aAdvisor: Servedio, Rocco;Yannakakis, Mihalis.
■5021 ▼aThesis (Ph.D.)--Columbia University, 2024.
■520 ▼aThis thesis considers algorithmic and structural aspects of high-dimensional convex sets with respect to the standard Gaussian measure.Among our contributions, (i) we introduce a notion of influence for convex sets that yields the first quantitative strengthening of Royen's celebrated Gaussian correlation inequality; (ii) we investigate the approximability of general convex sets by intersections of halfspaces, where the approximation quality is measured with respect to the standard Gaussian distribution; and (iii) we give the first lower bounds for testing convexity and estimating the distance to convexity of an unknown set in the black-box query model.Our results and techniques are inspired by a number of fundamental ingredients and results---such as the influence of variables, noise sensitivity, and various extremal constructions---from the analysis of Boolean functions in complexity theory.
■590 ▼aSchool code: 0054.
■650 4▼aComputer science
■650 4▼aMathematics
■650 4▼aTheoretical mathematics
■653 ▼aBoolean functions
■653 ▼aComplexity theory
■653 ▼aConvex geometry
■653 ▼aGaussian measure
■690 ▼a0984
■690 ▼a0405
■690 ▼a0642
■71020▼aColumbia University▼bComputer Science.
■7730 ▼tDissertations Abstracts International▼g86-02B.
■790 ▼a0054
■791 ▼aPh.D.
■792 ▼a2024
■793 ▼aEnglish
■85640▼uhttp://www.riss.kr/pdu/ddodLink.do?id=T17161988▼nKERIS▼z이 자료의 원문은 한국교육학술정보원에서 제공합니다.
