BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1046
DTSTAMP:20230914T125948Z
SUMMARY:Weight Distribution and List-Decoding size of Reed-Muller codes
DESCRIPTION:Speaker: Tulasi mohan Molli\n\nAbstract: \nAbstract: The proble
m of list-decoding an error-correcting code is the following:\ngiven a rec
eived word and a distance parameter find all codewords of the code that ar
e within the given distance from the received word. It is a generalization
of the more common notion of unique decoding.\nThe weight distributio
n of an error-correcting code counts\, for every given weight parameter\,
the number of codewords whose hamming weight is less than the given weight
parameter.\nThe codewords of Reed-Muller code can be thought of as truth-
tables of low degree polynomials. Kaufman\, Lovett\, and Porat in their wo
rk from 2010 made a novel connection between computer science techniques u
sed for studying low-degree polynomials and these seemingly related coding
theory questions in the case of Reed-Muller codes.\nIn this talk\, we wil
l see\n1) The above-mentioned result of Kaufman\, Lovett\, and Porat[KLP10
] and subsequent improvement of it due to Abbe\, Sphilka\, and Wigderson[A
SW15] which give upper bounds on the weight distribution of Reed-Muller co
des.\n2) A lower bound on the weight-distribution of Reed-Muller codes by
exhibiting a collection of low-degree polynomials that satisfy the weight
requirement for any given weight parameter. This is joint work with Bhanda
ri\, Harsha\, and Saptarishi and independently discovered by Sberlo and Sh
pilka[SS20].\n
URL:https://www.tcs.tifr.res.in/web/events/1046
DTSTART;TZID=Asia/Kolkata:20200124T160000
DTEND;TZID=Asia/Kolkata:20200124T173000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR