דלג לתוכן (מקש קיצור 's')
אירועים

אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

event speaker icon
נגה רון-צבי (אונ' חיפה)
event date icon
יום רביעי, 15.05.2019, 12:30
event location icon
חדר 337, בניין טאוב למדעי המחשב
We show that Folded Reed-Solomon codes achieve list decoding capacity with constant list sizes, independent of the block length. Prior work yielded list sizes that are polynomial in the block length, and relied on elaborate subspace evasive machinery to reduce the list sizes to constant.

We further show that multiplicity codes exhibit similar behavior, and use this to obtain capacity achieving locally list decodable codes with query complexity significantly lower than was known before.

Based on joint work with Swastik Kopparty, Shubhangi Saraf, and Mary Wootters.