BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1177
DTSTAMP:20230914T125953Z
SUMMARY:Exact Sampling and List-Decoding
DESCRIPTION:Speaker: Siddharth Bhandari\n\nAbstract: \nIn this thesis defen
 se\, we will discuss the following results.\n1.  Exact sampling:  We wil
 l present an efficient algorithm that\, given a graph of maximum degree $\
 \Delta$ and a list of at least $3\\Delta+1$ colours\, produces a random co
 louring of the graph that is \\emph{exactly} uniformly distributed on the 
 set of all proper colourings.  Before this work\, it was known that exact
  sampling was possible if about $\\Delta^2$ colours were allowed.\n2. List
 -decoding error-correcting codes:  In list-decoding\, the decoder\, based
  on the received word\, is required to output a small list of messages\, o
 ne of which must be the original message. We will discuss the following re
 sults about list-decoding.\n(a) Zero-error list decoding capacity of the $
 q/(q-1)$ channel:  We will present a lower bound showing that the zero-er
 ror list decoding capacity of this channel is exponentially small in $q$ e
 ven if the list size is allowed grow as $\\frac{1}{6} q \\ln q$. Previous 
 results showed that the capacity was exponentially small if the list size 
 was allowed to grow no larger than $1.58q$.\n(b) Multiplicity codes:  We 
 consider a  natural generalization of Reed-Muller codes where at each eva
 luation point\,  one records not only the evaluation of the message polyn
 omial\, but also all its partial derivatives up to a certain order. We wil
 l present an efficient algorithm that (under mild assumptions)  list-deco
 des multivariate multiplicity codes on arbitrary grids up to their distanc
 e.  Previously such results were known only for univariate multiplicity c
 odes.\n(c) Polynomial ideal codes:  A polynomial ideal code is specified 
 by a collection of relatively prime monic polynomials. The encoding is obt
 ained by specifying the remainders of the message polynomial modulo the va
 rious polynomials in the collection. We will describe an efficient algorit
 hm to list-decode some special polynomial ideal codes\, which we \\emph{ca
 ll affine folded Reed-Solomon codes\,} up to their distance. Previous resu
 lts allowed list-decoding up to the distance for folded Reed-Solomon codes
 \, univariate multiplicity codes and additive folded Reed-Solomon codes\, 
 which are all instances of affine folded Reed-Solomon codes.\n(The above r
 esults were obtained in collaborations that involved the\nfollowing: Sayan
 tan Chakraborty\, Prahladh Harsha\, Mrinal Kumar\, Jaikumar Radhakrishnan\
 , Madhu Sudan.)\n\nZoom link: https://zoom.us/j/95587295066?pwd=ZW5QQ1NrSV
 EwOG5iZzloVTlMV2ZBZz09\n
URL:https://www.tcs.tifr.res.in/web/events/1177
DTSTART;TZID=Asia/Kolkata:20211210T090000
DTEND;TZID=Asia/Kolkata:20211210T100000
LOCATION:Via Zoom
END:VEVENT
END:VCALENDAR