MARC

 008250123s2024        us                              c    eng  d
■001000017162213
■00520250211151946
■006m          o    d                
■007cr#unu||||||||
■020    ▼a9798383243923
■035    ▼a(MiAaPQ)AAI31327738
■040    ▼aMiAaPQ▼cMiAaPQ
■0820  ▼a004
■1001  ▼aHopkins,  Nathaniel  Max  Klevit.
■24510▼aHigh  Dimensional  Expanders  in  Analysis  and  Computation
■260    ▼a[Sl]▼bUniversity  of  California,  San  Diego▼c2024
■260  1▼aAnn  Arbor▼bProQuest  Dissertations  &  Theses▼c2024
■300    ▼a820  p
■500    ▼aSource:  Dissertations  Abstracts  International,  Volume:  86-01,  Section:  B.
■500    ▼aAdvisor:  Kane,  Daniel;Lovett,  Shachar.
■5021  ▼aThesis  (Ph.D.)--University  of  California,  San  Diego,  2024.
■520    ▼aHigh  dimensional  expanders  (HDX)  are  a  nascent  generalization  of  expander  graphs  (sparse  yet  robustly  connected  networks  that  play  a  core  role  in  the  theory  of  computation)  to  high  dimensional  domains.  Despite  recent  breakthrough  use  in  sampling  and  local  testability,  relatively  little  is  known  about  HDX,  their  properties,  and  their  broader  position  in  theoretical  computer  science.  In  this  dissertation,  we  develop  the  role  of  high  dimensional  expanders  in  computation  through  the  interplay  of  Boolean  analysis,  concentration  of  measure,  approximation  algorithms,  and  hardness  of  approximation.In  the  first  half  of  this  dissertation,  we  develop  a  robust  theory  of  Fourier  and  probabilistic  analysis  on  HDX.  This  includes  generalizations  of  standard  tools  of  theoretical  computer  science  such  as  the  Fourier  decomposition,  hypercontractivity,  and  Chernoff  bounds,  as  well  as  more  application-focused  techniques  such  as  symmetrization,  reverse  hypercontractivity,  and  concentration  of  high  degree  functions.  In  many  cases,  our  results  give  the  first  sparse  domains  satisfying  such  notions,  a  critical  consideration  in  application  where  density  or  'degree'  controls  the  cost  associated  with  their  use.In  the  second  half  of  this  dissertation,  we  give  applications  of  these  ideas  to  algorithms,  complexity,  and  mathematics.  Algorithmically,  we  show  the  local  structure  of  high  dimensional  expanders  can  be  exploited  to  build  fast  approximation  algorithms  for  unique  games,  and  explore  implications  of  fast  approximate  sampling  algorithms  on  HDX  to  massive  multiplayer  matrix  games.  In  mathematics,  we  show  high  dimensional  expanders  have  optimal  geometric  overlap,  extend  a  variant  of  the  Frankl-Rodl  theorem  to  HDX,  and  prove  new  degree  lower  bounds  for  certain  HDX.  Finally  in  complexity  we  leverage  new  topological  HDX  to  construct  optimally  hard  explicit  constraint  satisfaction  problems  for  Sum-of-Squares  (a  powerful  optimization  paradigm),  and  prove  spectral  HDX  satisfy  an  optimal  (local)  agreement  testing  theorem  and  an  optimal  global  tester  under  stronger  ℓ∞-type  assumptions,  a  stepping  stone  towards  improved  low-soundness  probabilistically  checkable  proofs  and  hardness  of  approximation.
■590    ▼aSchool  code:  0033.
■650  4▼aComputer  science
■650  4▼aMathematics
■653    ▼aHigh  dimensional  expanders
■653    ▼aBoolean  analysis
■653    ▼aApproximation  algorithms
■653    ▼aGraphs
■690    ▼a0984
■690    ▼a0405
■71020▼aUniversity  of  California,  San  Diego▼bComputer  Science  and  Engineering.
■7730  ▼tDissertations  Abstracts  International▼g86-01B.
■790    ▼a0033
■791    ▼aPh.D.
■792    ▼a2024
■793    ▼aEnglish
■85640▼uhttp://www.riss.kr/pdu/ddodLink.do?id=T17162213▼nKERIS▼z이  자료의  원문은  한국교육학술정보원에서  제공합니다.

미리보기

내보내기

chatGPT토론

Ai 추천 관련 도서