MARC

 008250123s2024        us                              c    eng  d
■001000017161263
■00520250211151331
■006m          o    d                
■007cr#unu||||||||
■020    ▼a9798382841045
■035    ▼a(MiAaPQ)AAI31241126
■040    ▼aMiAaPQ▼cMiAaPQ
■0820  ▼a004
■1001  ▼aLiao,  Jyun-Jie.▼0(orcid)0000-0003-3332-1460
■24510▼aExtractors  for  Additive  Structures  and  Space-bounded  Computation
■260    ▼a[Sl]▼bCornell  University▼c2024
■260  1▼aAnn  Arbor▼bProQuest  Dissertations  &  Theses▼c2024
■300    ▼a223  p
■500    ▼aSource:  Dissertations  Abstracts  International,  Volume:  85-12,  Section:  B.
■500    ▼aAdvisor:  Chattopadhyay,  Eshan.
■5021  ▼aThesis  (Ph.D.)--Cornell  University,  2024.
■520    ▼aRandomness  is  a  powerful  resource  in  computer  science,  with  rich  applications  in  algorithm  design,  cryptography,  distributed  computing,  etc.  Most  of  the  applications  assume  access  to  a  sequence  of  uniform  and  independent  random  bits.  However,  the  randomness  we  collect  from  nature  (e.g.,  activity  of  CPU,  atmospheric  noise,  radioactive  decay)  does  not  seem  as  perfect.  This  motivates  the  study  of  randomness  extractors,  which  are  deterministic  algorithms  that  can  convert  an  imperfect  random  source  (with  some  entropy)  into  a  uniform  random  string.  The  ultimate  goal  in  the  area  of  randomness  extraction  is  to  construct  an  extractor  that  can  work  for  any  source  that  we  would  ever  see  in  nature  and  applications.  Unfortunately,  a  folklore  result  shows  that  it  is  impossible  to  construct  an  extractor  that  can  work  for  every  source  that  has  entropy.  It  is  therefore  necessary  to  assume  that  the  given  source  has  certain  structure,  but  we  still  hope  that  the  structure  we  assume  is  as  general  as  possible.  In  this  thesis,  we  first  focus  on  the  construction  of  randomness  extractors  for  sources  with  additive  structure.  This  includes  affine  sources,  which  are  uniform  distributions  over  affine  subspaces;  and  more  generally  the  sum  of  two  independent  sources,  which  is  a  surprisingly  general  model  that  contains  many  other  natural  sources  such  as  independent  sources,  affine  sources  and  sources  samplable  by  space-bounded  computation.  For  both  models,  we  construct  extractors  that  improve  the  previous  state-of-the-art,  and  develop  many  useful  tools  along  the  way.  In  addition,  we  discover  new  connections  between  sources  with  additive  structure  and  space-bounded  computation,  and  as  a  result  we  obtain  extractors  for  small-space  sources  with  optimal  entropy  requirement,  and  a  new  lower  bound  for  linear  branching  programs.  Finally,  we  develop  more  results  regarding  randomness  and  space-bounded  computation,  including  new  weighted  pseudorandom  generators  and  derandomization  bounds  for  small-space  algorithms.
■590    ▼aSchool  code:  0058.
■650  4▼aComputer  science
■650  4▼aComputer  engineering
■650  4▼aApplied  mathematics
■653    ▼aDerandomization
■653    ▼aPseudorandom  generator
■653    ▼aRandomness  extractor
■653    ▼aSpace-bounded  computation
■653    ▼aSumset  extractors
■690    ▼a0984
■690    ▼a0464
■690    ▼a0364
■71020▼aCornell  University▼bComputer  Science.
■7730  ▼tDissertations  Abstracts  International▼g85-12B.
■790    ▼a0058
■791    ▼aPh.D.
■792    ▼a2024
■793    ▼aEnglish
■85640▼uhttp://www.riss.kr/pdu/ddodLink.do?id=T17161263▼nKERIS▼z이  자료의  원문은  한국교육학술정보원에서  제공합니다.

Preview

Export

ChatGPT Discussion

AI Recommended Related Books