{"id":"palomar/PALOMAR-2026-10-17-000017","url":"https://github.com/lennrt/palomar-formalizations/tree/9a61a84e3a2e1494bc08b8eaf714c42f3f918325/zenodo-23346565/palomar","json":"https://data.palomar-registry.org/entries/PALOMAR-2026-10-17-000017-v1.json","repo":"https://github.com/lennrt/palomar-formalizations","tags":["cs.DC","math.CO","msc:68W15","msc:05C85","local-computation","graph-orientation","distributed-computing"],"score":0,"title":"Optimal Local Decompression: Uniform Finite-View Reduction","trust":"high","domain":"cs.DC","source":"palomar","authors":["Lennart Rudolph"],"reviews":0,"subject":"cs.DC","summary":"A uniform finite-view reduction at the paper's counting-optimal k-bit vertex budget for odd maximum degree 2k-1. Given one total finite-view orientation rule with a sufficient one-bit advice guarantee, one decoder family is chosen before graph order, topology, markers, advice and payload. Every connected graph on Fin n with n>16(k+1) and degree at most 2k-1 admits an encoder recovering every edge bit at either endpoint from a 2^k-symbol vertex alphabet. The same total decoder is local across different connected graphs and arbitrary labelings, with no marker validity or encoded-input premise.…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"verified":true,"discussed":0,"published":"2026-10-17","reactions":{},"formalized":true,"formalizes":[{"title":"Optimal Local Decompression on Graphs of Odd Maximum Degree","identifier":"doi:10.5281/zenodo.23346565","relationship":"formalizes"}]}