BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1734
DTSTAMP:20260612T055104Z
SUMMARY:PIR schemes using Matching Vectors and Derivatives
DESCRIPTION:Speaker: Sayan Kar (ISI Kolkata)\n\nAbstract: \nPrivate Informa
 tion Retrieval (PIR) schemes are communication protocols that allow a user
  to recover a single bit from a large database stored across multiple non-
 interacting servers\, without revealing any information about which bit wa
 s queried. PIR schemes have deep connections to algebraic coding theory\, 
 and in particular to Locally Decodable Codes (LDCs).\nIn this talk\, new t
 -server PIR schemes are presented with communication complexity sub-polyno
 mial in the previously best known bounds\, for all but finitely many t. Th
 e key ingredients are matching vectors and polynomial derivatives\, both w
 ell-established tools in the PIR and LDC literature. A landmark result of 
 Dvir and Gopi previously combined these two ideas using polynomials and de
 rivatives over exotic algebraic rings\, giving the first 2-server PIR with
  sub-polynomial communication. The new approach achieves improved bounds v
 ia a simpler method that works natively over finite fields\, using only el
 ementary properties of polynomials. In particular\, this yields a 3-server
  PIR scheme with communication complexity 2^{O~((log n)^{1/3})}\, improvin
 g upon Efremenko's bound of 2^{O~(sqrt(log n))}.\n
URL:https://www.tcs.tifr.res.in/web/events/1734
DTSTART;TZID=Asia/Kolkata:20260617T160000
DTEND;TZID=Asia/Kolkata:20260617T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR