BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1494
DTSTAMP:20241125T044841Z
SUMMARY:Improved PIR Schemes using Matching Vectors and Derivatives
DESCRIPTION:Speaker: Madhu Sudan (Harvard John A. Paulson School of Enginee
 ring and Applied Sciences)\n\nAbstract: \nPrivate Information Retrieval (P
 IR) schemes are communication protocols with low comnunication that allow 
 a user to recover a single bit of information from a large database stored
  at multiple non-interacting servers without revealing any information abo
 ut their query to any of the servers. PIRs have long been the subject of s
 tudy with close relationships to locally decodable codes (LDCs). In this t
 alk we describe new t-server PIR schemes with communication complexity sub
 polynomial in the previously best known\, for all but finitely many t. Our
  results are based on combining the use of derivatives with "matching vect
 ors". Both ingredients are well-used in the literature on PIRs and LDCs an
 d in particular were used together in an ingenious way by Dvir and Gopi\, 
 using polynomials and derivatives over certain exotic rings\, en route to 
 their fundamental result giving the first 2-server PIR with subpolynomial 
 communication. Our result gives a matching bound for 2-server PIRs with an
  arguably simple proof\; and also leads to improvements for most other val
 ues of t\, the number of servers. (Knowledge of previous works on PIRs or
  LDCs will not be assumed in the talk.) Joint work with Fatemeh Ghasemi a
 nd  Swastik Kopparty (U. Toronto).\nShort Bio: Madhu Sudan is a Gordon Mc
 Kay Professor in the John A. Paulson School of Engineering and Applied Sci
 ences at Harvard University\, where he has been since 2015. Madhu Sudan go
 t his Bachelors degree from IIT Delhi in 1987 and his Ph.D. from U.C. Berk
 eley in 1992. Between 1992 and 2015\, Madhu Sudan worked at IBM Research (
 Research Staff Member 1992-1997)\, at MIT (Associate Professor 1997-2000\,
  Professor 2000-2011\, Fujitsu Chair Professor 2003-2011\, CSAIL Associate
  Director 2007-2009\, Adjunct Professor 2011-2015)\, and at Microsoft Rese
 arch (Principal Researcher\, 2009-2015). Madhu Sudan is a recipient of the
  Nevanlinna Prize awarded by the International Mathematical Union for outs
 tanding contributions to mathematics of computer and information science\,
  and the Infosys Foundation Prize in Mathematical Sciences\, and the IEEE 
 Hamming Medal. Madhu Sudan is a fellow of the Association for Computing Ma
 chinery\,  the Institute of Electrical and Electronics Engineers and the 
 American Mathematical Society.  He is a member of the American Academy of
  Arts and Sciences and the National Academy of Sciences. \nMadhu Sudan's r
 esearch interests revolve around mathematical studies of communication and
  computation. Specifically his research focusses on concepts of reliabilit
 y and mechanisms that are\, or can be\, used by computers to interact reli
 ably with each other. His research draws on tools from computational compl
 exity\, which studies efficiency of computation\, and many areas of mathem
 atics including algebra and probability theory.  He is best known for his
  works on probabilistic checking of proofs\, and on the design of list-dec
 oding algorithms for error-correcting codes.  His current research intere
 sts include property testing which is the study of sublinear time algorith
 ms to estimate properties of massive data\, and communication amid uncerta
 inty\, a mathematical study of the role of context in communication. \n
URL:https://www.tcs.tifr.res.in/web/events/1494
DTSTART;TZID=Asia/Kolkata:20241209T110000
DTEND;TZID=Asia/Kolkata:20241209T120000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR