MARC

 008250123s2024        us                              c    eng  d
■001000017161717
■00520250211151435
■006m          o    d                
■007cr#unu||||||||
■020    ▼a9798382810294
■035    ▼a(MiAaPQ)AAI31295557
■040    ▼aMiAaPQ▼cMiAaPQ
■0820  ▼a004
■1001  ▼aParamonov,  Dmitry.▼0(orcid)0009-0005-5592-060X
■24510▼aHandling  Data  Too  Large  to  Handle:  On  Multi-Pass  Streaming  and  Interactive  Coding
■260    ▼a[Sl]▼bPrinceton  University▼c2024
■260  1▼aAnn  Arbor▼bProQuest  Dissertations  &  Theses▼c2024
■300    ▼a476  p
■500    ▼aSource:  Dissertations  Abstracts  International,  Volume:  85-12,  Section:  B.
■500    ▼aAdvisor:  Kol,  Gillat.
■5021  ▼aThesis  (Ph.D.)--Princeton  University,  2024.
■520    ▼aOver  the  last  decades,  the  world  has  become  increasingly  more  information-centric  and  massive  amounts  of  data,  potentially  distributed  between  many  different  sources,  are  being  processed  all  the  time.  In  this  thesis,  I  consider  two  mechanisms  for  coping  with  big  data  and  the  distributed  nature  of  timely  tasks.In  Part  I,  I  showcase  my  work  on  the  streaming  setting,  where  the  input  to  the  algorithm  is  given  as  a  stream  of  elements.  The  algorithm's  goal  is  to  compute  a  value  that  depends  on  the  stream  while  only  utilizing  memory  that  is  much  smaller  than  the  entire  stream.  My  work  in  this  field  focuses  on  proving  that  various  fundamental  graph  problems  essentially  require  the  streaming  algorithm  to  store  the  entire  graph,  even  if  it  is  allowed  to  make  several  passes  through  the  given  stream  of  edges.In  Part  II,  I  consider  error-correcting  codes  for  distributed,  interactive  settings.  Classical  error-correcting  codes  assume  that  a  sender  who  has  all  the  information  wishes  to  send  it  to  a  receiver  over  a  noisy  channel.  However,  in  many  modern,  big  data  applications,  the  information  is  distributed  amongst  many  parties  that  communicate  back-and-forth  to  compute  a  value  that  depends  on  all  their  inputs.  My  work  examines  the  noise  resilience  of  various  such  settings.  For  some  models,  we  can  design  error-correcting  protocols  that  allow  the  encoding  of  every  noiseless  protocol  by  a  noise-resilient  protocol  with  low  overhead,  whereas  for  other  models,  it  can  be  shown  that  this  task  is  impossible.While  these  two  topics  appear  greatly  unrelated,  and  almost  orthogonal  to  one  another,  the  tools  used  to  prove  results  in  both  turn  out  to  be  remarkably  similar,  with  many  standard  problems  and  information  theory  lemmas  being  a  critical  part  of  both. 
■590    ▼aSchool  code:  0181.
■650  4▼aComputer  science
■650  4▼aComputer  engineering
■653    ▼aDistributed  computing
■653    ▼aInteractive  coding
■653    ▼aStreaming  complexity
■653    ▼aInformation  theory
■690    ▼a0984
■690    ▼a0464
■71020▼aPrinceton  University▼bComputer  Science.
■7730  ▼tDissertations  Abstracts  International▼g85-12B.
■790    ▼a0181
■791    ▼aPh.D.
■792    ▼a2024
■793    ▼aEnglish
■85640▼uhttp://www.riss.kr/pdu/ddodLink.do?id=T17161717▼nKERIS▼z이  자료의  원문은  한국교육학술정보원에서  제공합니다.

Preview

Export

ChatGPT Discussion

AI Recommended Related Books