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