BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1147
DTSTAMP:20230914T125952Z
SUMMARY:Exact Sampling & List-Decoding
DESCRIPTION:Speaker: Siddharth Bhandari\n\nAbstract: \nWe will discuss the
following results. 1. Exact sampling: We will present an efficient algorit
hm that\, given a graph of maximum degree $\\Delta$ and a list of at least
$3\\Delta+1$ colours\, produces a random colouring of the graph that is \
\emph{exactly} uniformly distributed on the set of all proper colourings.
Our algorithm can be generalized to the setting of list colourings\, where
each vertex is provided with a separate list of at least $3\\Delta+1$ col
ours. Before this work\, it was known that exact sampling was possible if
about $\\Delta^2$ colours were allowed. 2. List-decoding error-correcting
codes: In list-decoding\, the decoder\, based on the received word\, is re
quired to output a small list of messages\, one of which must be the origi
nal message. We will discuss the following results about list-decoding. (a
) Zero-error list decoding capacity of the $q/(q-1)$ channel: We will pres
ent a lower bound showing that the zero-error list decoding capacity of th
is channel is exponentially small in $q$ even 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 th
an $1.58q$. (b) Multiplicity codes: We consider a natural generalization o
f Reed-Muller codes where at each evaluation point\, one records not only
the evaluation of the message polynomial\, but also all its partial deriva
tives up to a certain order. We will present an efficient algorithm that (
under mild assumptions) list-decodes multivariate multiplicity codes on ar
bitrary grids up to their distance. Previously such results were known onl
y for univariate multiplicity codes. (c) Polynomial ideal codes: A polynom
ial ideal code is specified by a collection of relatively prime monic poly
nomials. The encoding is obtained by specifying the remainders of the mess
age polynomial modulo the various polynomials in the collection. We will d
escribe an efficient algorithm to list-decode some special polynomial idea
l codes\, which we \\emph{call affine folded Reed-Solomon codes\,} up to t
heir distance. Previous results allowed list-decoding up to the distance f
or folded Reed-Solomon codes\, univariate multiplicity codes and additive
folded Reed-Solomon codes\, which are all instances of affine folded Reed-
Solomon codes. (The above results were obtained in collaborations that inv
olved the following: Sayantan Chakraborty\, Prahladh Harsha\, Mrinal Kumar
\, Jaikumar Radhakrishnan\, Madhu Sudan.)\n
URL:https://www.tcs.tifr.res.in/web/events/1147
DTSTART;TZID=Asia/Kolkata:20210803T160000
DTEND;TZID=Asia/Kolkata:20210803T170000
END:VEVENT
END:VCALENDAR