Technical Program

Paper Detail

Paper Title Scalable Automated Proving of Information Theoretic Inequalities with Proximal Algorithms
Paper IdentifierTU4.R9.2
Authors Lin Ling, Chee Wei Tan, City University of Hong Kong, Hong Kong SAR of China; Siu-Wai Ho, University of Adelaide, Australia; Raymond W. Yeung, Chinese University of Hong Kong, Hong Kong SAR of China
Session Information Inequalities
Location Pontoise, Level 5
Session Time Tuesday, 09 July, 16:40 - 18:00
Presentation Time Tuesday, 09 July, 17:00 - 17:20
Manuscript  Click here to download the manuscript
Abstract Proving or disproving linear information theoretic inequalities is a fundamental task in information theory, and it has also been proved to be important in fields like cryptography and quantum communication theory. Manually proving information inequalities involving more than a few random variables can often be tedious or even intractable. In 1997, Yeung proposed a linear programming framework for verifying information inequalities, which was later extended to construct analytical proofs and disproofs. However, in practice this framework can be very slow for inequalities involving more than ten random variables, thus it is impossible to be applied to a wide range of practical problems. In this paper, we further extend this optimization-theoretic framework by reformulating the LPs and applying the Alternating Direction Method of Multipliers (ADMM) technique, where all the subproblems have closed-form solutions and thus can be solved efficiently. The proposed algorithm is also parallelizable so the performance can be further improved by running it on a GPU. An online web service is developed to allow users to prove or disprove their problem-specific inequalities without installing any software package or dependency.