Tata Institute of Fundamental Research
Exact Sampling and List-Decoding
PhD Thesis Seminar
Speaker:
Siddharth Bhandari
Organiser:
Prahladh Harsha
Date:
Friday, 10 Dec 2021, 09:00 to 10:00
Venue:
Via Zoom
(Scan to add to calendar)
Abstract:
In this thesis defense, we will discuss the following results.
1. Exact sampling: We will 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 colouring 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.
2. List-decoding error-correcting codes: In list-decoding, the decoder, based on the received word, is required to output a small list of messages, one of which must be the original message. We will discuss the following results about list-decoding.
(a) Zero-error list decoding capacity of the $q/(q-1)$ channel: We will present a lower bound showing that the zero-error list decoding capacity of this 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 than $1.58q$.
(b) Multiplicity codes: We consider a natural generalization of Reed-Muller codes where at each evaluation point, one records not only the evaluation of the message polynomial, but also all its partial derivatives up to a certain order. We will present an efficient algorithm that (under mild assumptions) list-decodes multivariate multiplicity codes on arbitrary grids up to their distance. Previously such results were known only for univariate multiplicity codes.
(c) Polynomial ideal codes: A polynomial ideal code is specified by a collection of relatively prime monic polynomials. The encoding is obtained by specifying the remainders of the message polynomial modulo the various polynomials in the collection. We will describe an efficient algorithm to list-decode some special polynomial ideal codes, which we \emph{call affine folded Reed-Solomon codes,} up to their distance. Previous results 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.
(The above results were obtained in collaborations that involved the
following: Sayantan Chakraborty, Prahladh Harsha, Mrinal Kumar, Jaikumar Radhakrishnan, Madhu Sudan.)
Zoom link: https://zoom.us/j/95587295066?pwd=ZW5QQ1NrSVEwOG5iZzloVTlMV2ZBZz09
| Speaker: | Siddharth Bhandari |
| Organiser: | Prahladh Harsha |
| Date: | Friday, 10 Dec 2021, 09:00 to 10:00 |
| Venue: | Via Zoom |
(Scan to add to calendar)
Abstract:
In this thesis defense, we will discuss the following results.
1. Exact sampling: We will 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 colouring 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.
2. List-decoding error-correcting codes: In list-decoding, the decoder, based on the received word, is required to output a small list of messages, one of which must be the original message. We will discuss the following results about list-decoding.
(a) Zero-error list decoding capacity of the $q/(q-1)$ channel: We will present a lower bound showing that the zero-error list decoding capacity of this 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 than $1.58q$.
(b) Multiplicity codes: We consider a natural generalization of Reed-Muller codes where at each evaluation point, one records not only the evaluation of the message polynomial, but also all its partial derivatives up to a certain order. We will present an efficient algorithm that (under mild assumptions) list-decodes multivariate multiplicity codes on arbitrary grids up to their distance. Previously such results were known only for univariate multiplicity codes.
(c) Polynomial ideal codes: A polynomial ideal code is specified by a collection of relatively prime monic polynomials. The encoding is obtained by specifying the remainders of the message polynomial modulo the various polynomials in the collection. We will describe an efficient algorithm to list-decode some special polynomial ideal codes, which we \emph{call affine folded Reed-Solomon codes,} up to their distance. Previous results 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.
(The above results were obtained in collaborations that involved the
following: Sayantan Chakraborty, Prahladh Harsha, Mrinal Kumar, Jaikumar Radhakrishnan, Madhu Sudan.)
Zoom link: https://zoom.us/j/95587295066?pwd=ZW5QQ1NrSVEwOG5iZzloVTlMV2ZBZz09
1. Exact sampling: We will 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 colouring 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.
2. List-decoding error-correcting codes: In list-decoding, the decoder, based on the received word, is required to output a small list of messages, one of which must be the original message. We will discuss the following results about list-decoding.
(a) Zero-error list decoding capacity of the $q/(q-1)$ channel: We will present a lower bound showing that the zero-error list decoding capacity of this 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 than $1.58q$.
(b) Multiplicity codes: We consider a natural generalization of Reed-Muller codes where at each evaluation point, one records not only the evaluation of the message polynomial, but also all its partial derivatives up to a certain order. We will present an efficient algorithm that (under mild assumptions) list-decodes multivariate multiplicity codes on arbitrary grids up to their distance. Previously such results were known only for univariate multiplicity codes.
(c) Polynomial ideal codes: A polynomial ideal code is specified by a collection of relatively prime monic polynomials. The encoding is obtained by specifying the remainders of the message polynomial modulo the various polynomials in the collection. We will describe an efficient algorithm to list-decode some special polynomial ideal codes, which we \emph{call affine folded Reed-Solomon codes,} up to their distance. Previous results 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.
(The above results were obtained in collaborations that involved the
following: Sayantan Chakraborty, Prahladh Harsha, Mrinal Kumar, Jaikumar Radhakrishnan, Madhu Sudan.)
Zoom link: https://zoom.us/j/95587295066?pwd=ZW5QQ1NrSVEwOG5iZzloVTlMV2ZBZz09