Seminars

View all Seminars  |  Download ICal for this event

Fractional Subadditivity of Submodular Functions: Equality Conditions and Their Applications

Series: Bangalore Theory Seminars

Speaker: Suryajith Chillara, Assistant Professor, Center for Security, Theory and Algorithmic Research (CSTAR), International Institute of Information Technology, Hyderabad

Date/Time: Aug 26 11:00:00

Location: CSA Auditorium, (Room No. 104, Ground Floor)

Abstract:
Submodular functions are known to satisfy various forms of fractional subadditivity. In this work, we investigate the conditions for equality to hold exactly or approximately in fractional subadditivity. We establish that a small inequality gap implies that the function is close to being modular, and that the gap is zero if and only if the function is modular. We also present the natural implications of these results for special cases of submodular functions, such as entropy, relative entropy, and matroid rank. As a consequence, we characterize the necessary and sufficient conditions for equality in Shearers lemma, recovering a result of Ellis et al. (2016) as a special case. We leverage our results to propose a new multivariate mutual information, which generalizes Watanabes total correlation (1960) and Hans dual total correlation (1975), and analyze its properties. Among these properties, we extend Watanabes characterization of total correlation as the maximum correlation over partitions to fractional partitions. When applied to matrix determinantal inequalities for positive definite matrices, our results recover the equality conditions of the classical determinantal inequalities of Hadamard, Szasz, and Fischer as special cases.

This is a joint work with Gunank Jakhar, Gowtham R. Kurri, and Vinod Prabhakaran. Appeared in proceedings of ISIT 2025.


Microsoft teams link:

Link

We are grateful to the Kirani family (Link and the Walmart Center for Tech Excellence (Link for generously supporting this seminar series


Hosts: Rameesh Paul, Nirjhar Das, KVN Sreenivas, Rahul Madhavan, Debajyoti Kar