Title：Communication Complexity as an Interface to Theoretical Computer Science and Applications
Date：2025/11/21 14:20-15:30
Location：R103, CSIE
Speakers：張峻銘研究員
Host：黃上恩教授
Abstract:
In the basic communication complexity model, two or more players collaborate to determine the value of a joint function, where each player privately holds a portion of the input. The central goal of communication complexity theory is to quantify the minimal amount of information that must be exchanged to compute different functions, under the assumption that each player has unbounded computational power. Though a seemingly unrealistic model, communication complexity has proven highly useful for establishing impossibility results across many areas of computer science, both theoretical and applied.
In this talk, I will survey several results from my past research in communication complexity, highlighting applications in other areas like algorithm design and query complexity theory. I will illustrate how communication complexity techniques yield provable hardness results, providing insights into the fundamental limits of computational tasks and guiding the design of efficient algorithms.
Biography:
Tsun-Ming Cheung is a postdoctoral fellow at the Institute of Information Science, Academia Sinica. His research interests span theoretical computer science and discrete mathematics, encompassing areas such as complexity theory, streaming algorithms, and quantum computation theory. Previously, he received his PhD degree from McGill University, Canada, and his M.Phil. degree from the Chinese University of Hong Kong.