A Correspondence between Coding Problems and Logic via Confusion Hypergraphs (Part II).

Abstract: Information is often represented as random variables or partitions of the sample space, where we can take the "conjunction" of two pieces of information as the joint random variable, but cannot perform other logical operations. By generalizing partitions to confusion hypergraphs (which form a Heyting algebra), we can take conjunction, disjunction and implication between information. In this talk, we will discuss connections between confusion hypergraphs and logic (generalized inquisitive logic and intuitionistic logic), and show how we can directly compute an almost-optimal coding scheme for various coding settings (e.g., network coding and index coding) by translating the settings into logical formulae, and evaluating the formulae over hypergraphs. The optimal communication cost is given approximately by the hypergraph entropy. We will also discuss several identities and inequalities on hypergraph entropy, and their interpretations in coding settings. (Part II of the talk).

Computer scienceMathematics

Audience: researchers in the discipline

( paper | slides )

Comments: This is the 2nd part of the talk started on Sep 23. The recorded video and slides of the first part of the talk are available on the page of the seminar, www.lirmm.fr/~romashchen/seminar-aait.html .

---

Seminar on Algorithmic Aspects of Information Theory

Series comments: This online seminar is a follow up of the Dagstuhl Seminar 22301, www.dagstuhl.de/en/program/calendar/semhp/?semnr=22301.

---