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:20240101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20250722T163000
DTEND;TZID=Asia/Seoul:20250722T173000
DTSTAMP:20260416T183559
CREATED:20250610T134044Z
LAST-MODIFIED:20250611T222217Z
UID:10983-1753201800-1753205400@dimag.ibs.re.kr
SUMMARY:Linda Cook\, A tight algorithmic meta-theorem for distributed certification within bounded treewidth graphs
DESCRIPTION:A local certification of a graph property is a protocol in which nodes are given  “certificates of a graph property” that allow the nodes to check whether their network has this property while only communicating with their local network. The key property of a local certification is that if certificates are corrupted\, some node in the network will be able to recognize this. Inspired by practical concerns\, the aim in LOCAL certification is to minimize the maximum size of a certificate. \nIn this talk we introduce local certification and open problems in the area and  present some recent joint work with Eunjung Kim and Tomáš Masařík\, A Tight Meta-theorem for LOCAL Certification of MSO2 Properties within Bounded Treewidth Graphs. \nIn this work\, instead of considering a specific graph property and developing a local certification protocol tailor-made for this property\, we aim for generic protocols that can certify any property expressible in a certain logical framework. We consider Monadic Second Order Logic (MSO$_2$)\, a powerful framework that can express properties such as non-$k$-colorability\, Hamiltonicity\, and $H$-minor-freeness. Unfortunately\, in general\, there are MSO$_2$-expressible properties that cannot be certified without huge certificates. For instance\, non-3-colorability requires certificates of size $\Omega(n^2/\log n)$ on general $n$-vertex graphs (Göös\, Suomela 2016). Hence\, we impose additional structural restrictions on the graph. Inspired by their importance in centralized computing and Robertson-Seymour Graph Minor theory\, we consider graphs of bounded treewidth. We provide a local certification protocol for certifying any MSO$_2$-expressible property on graphs of bounded treewidth and\, consequently\, a local certification protocol for certifying bounded treewidth. That is\, for each integer $k$ and each MSO$_2$-expressible property $\Pi$\, we give a local certification protocol to certify that a graph satisfies $\Pi$ and has treewidth at most $k$ using certificates of size $\mathcal{O}(\log n)$ (which is asymptotically optimal). Our result improves upon the works of Fraigniaud\, Montealegre\, Rapaport\, and Todinca (Algorithmica 2024)\,  Bousquet\, Feuilloley\, Pierron (PODC 2022)\, and the very recent work of Baterisna and Chang (PODC 2025).
URL:https://dimag.ibs.re.kr/event/2025-07-22/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR