BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.15.20//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-ORIGINAL-URL:https://dimag.ibs.re.kr
X-WR-CALDESC:Events for Discrete Mathematics Group
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:Asia/Seoul
BEGIN:STANDARD
TZOFFSETFROM:+0900
TZOFFSETTO:+0900
TZNAME:KST
DTSTART:20200101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20211214T163000
DTEND;TZID=Asia/Seoul:20211214T173000
DTSTAMP:20260423T004958
CREATED:20211214T073000Z
LAST-MODIFIED:20240705T180035Z
UID:4913-1639499400-1639503000@dimag.ibs.re.kr
SUMMARY:Tuan Tran\, Exponential decay of intersection volume with applications on list-decodability and sphere-covering bounds
DESCRIPTION:We give some natural sufficient conditions for balls in a metric space to have small intersection. Roughly speaking\, this happens when the metric space is (i) expanding and (ii) well-spread\, and (iii) certain random variable on the boundary of a ball has a small tail. As applications\, we show that the volume of intersection of balls in Hamming space and symmetric groups decays exponentially as their centers drift apart. To verify condition (iii)\, we prove some deviation inequalities `on the slice’ for functions with Lipschitz conditions. \nWe then use these estimates on intersection volumes to \n\nobtain a sharp lower bound on list-decodability of random q-ary codes\, confirming a conjecture of Li and Wootters [IEEE Trans. Inf. Theory 2021]; and\nimprove sphere-covering bound from the 70s on constant weight codes by a factor linear in dimension\, resolving a problem raised by Jiang and Vardy [IEEE Trans. Inf. Theory 2004].\n\nOur probabilistic point of view also offers a unified framework to obtain improvements on other sphere-covering bounds\, giving conceptually simple and calculation-free proofs for q-ary codes\, permutation codes\, and spherical codes. \nThis is joint work with Jaehoon Kim and Hong Liu.
URL:https://dimag.ibs.re.kr/event/2021-12-14/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR