Fri, 16-Feb-2024 / 2:00pm / Packard 202
https://stanford.zoom.us/j/95879122526?pwd=dzhIcm1uZ0JlMER5azdPNFBhSVhEZz09
In information theory, there are problems that we know how to solve (e.g., the capacity of point-to-point discrete memoryless channels), problems that we do not know how to solve yet (e.g., the capacity region of broadcast channels), and problems that we know for sure are impossible to solve. Undecidable problems cannot be solved by any algorithm, regardless of whether it is polynomial or exponential time. We will discuss several undecidable problems in information theory, namely the general network coding problem (deciding whether a given network has a valid coding scheme), the conditional independence implication problem (deciding whether a list of conditional independence statements imply another such statement), and the conditional information inequalities problem. While these results might sound “pessimistic”, they help us locate the boundary between coding settings that can be solved, and coding settings that are too complex to be solved.
Cheuk Ting Li received the B.Sc. degree in mathematics and B.Eng. degree in information engineering from The Chinese University of Hong Kong in 2012, and the M.S. and Ph.D. degree in electrical engineering from Stanford University in 2014 and 2018 respectively. He was a postdoctoral scholar at the Department of Electrical Engineering and Computer Sciences, University of California, Berkeley. He joined the Department of Information Engineering, the Chinese University of Hong Kong in January 2020. He was awarded the 2016 IEEE Jack Keil Wolf ISIT Student Paper Award, and the 2023 Information Theory Society Paper Award.
Cheuk Ting Li is interested in developing information-theoretic techniques to address problems in multi-user communications, delay-constrained communications, automated theorem proving and machine learning.
Packard Building
Electrical Engineering Department
350 Jane Stanford Way
Stanford, CA 94305-9515
