For problems that allow statistical interpretation, such as parameter estimation or information transmission, whenever different strategies are possible, it is natural to compare them on the basis of their statistical performance with respect to the problem at hand. The theory of statistical comparison provides a rigorous formalization of this scenario. In this lecture, I will introduce the basic ideas of the classical theory, including the theory of majorization and the Blackwell-Sherman-Stein theorem, present their extensions to the quantum setting, and discuss applications in information theory (e.g., channel ordering) and quantum foundations (e.g., quantum measurement theory).
Francesco Buscemi received his Ph.D. in Theoretical Physics from the University of Pavia, Italy, in 2006. After postdoctoral positions at the ERATO-SORST Quantum Computation and Information Project (Tokyo, Japan) and the Statistical Laboratory of the University of Cambridge (UK), he joined Nagoya University in 2009, where he is a full professor in the Department of Mathematical Informatics. In 2018, he was awarded the Birkhoff-von Neumann Prize by the International Quantum Structures Association for “solving some long-standing open problems in the foundations of quantum physics, using ideas from mathematical statistics and information theory”.
The lectures focus on techniques for proving "infeasibility results" for achievable rate regions. In particular, I will present the novel auxiliary receiver approach as a mathematical tool for writing outer bounds in network information theory. The technique's basic idea is to consider one or multiple “auxiliary” receivers and use their past and/or future when identifying the auxiliary random variables. I discuss the application of the technique to some fundamental open problems in network information theory: finding the capacity regions of the broadcast channel, the interference channel, and the relay channel, as well as secret key generation from correlated sources. This technique yields new outer bounds for the relay, interference, and broadcast channel settings. These bounds strictly outperform classical outer bounds at least in some regimes. For instance, we strictly improve on the cutset outer bound for the scalar Gaussian relay channel, the outer bounds for the Gaussian Z-interference channel, and the outer bounds for the two receiver broadcast channels.
Amin Gohari received the B.Sc. degree from the Sharif University of Technology, Tehran, Iran, in 2004, and the Ph.D. degree in electrical engineering from the University of California at Berkeley in 2010. From 2010 to 2011, he held a post-doctoral position with the Institute of Network Coding, The Chinese University of Hong Kong. From 2011 to 2022, he was with the Department of Electrical Engineering, Sharif University of Technology and with the Tehran Institute for Advanced Studies, Khatam University. He joined the Department of Information Engineering, The Chinese University of Hong Kong in 2022. His research interests include classical and quantum information theory, game theory, and molecular communication.
He received the 2010 Eli Jury Award from the Department of Electrical Engineering and Computer Sciences, UC Berkeley, for outstanding achievement in the area of communication networks, and the 2009–2010 Bernard Friedman Memorial Prize in Applied Mathematics from the Department of Mathematics, UC Berkeley, for demonstrated ability to do research in applied mathematics. He also received the Gold Medal from the 41st International Mathematical Olympiad (IMO 2000) and the First Prize from the 9th International Mathematical Competition for University Students (IMC 2002). He was a finalist for the Best Student Paper Award at the IEEE International Symposium on Information Theory (ISIT) in three consecutive years 2008, 2009, and 2010. He was also the co-author of a paper that won the ISIT 2013 Jack Wolf Student Paper Award and two that were finalists in 2012 and 2014 (as a supervisor). He was selected as an Exemplary Reviewer for the IEEE TRANSACTIONS ON COMMUNICATIONS in 2015 and 2016. He served as an Associate Editor for the IEEE TRANSACTIONS ON INFORMATION THEORY from 2018 to 2021. He also received the IEEE Iran Section’s Young Researcher Award in 2021.
Computational analogs of entropy, such as pseudorandomness and inaccessible entropy, play a crucial role in foundational constructions within cryptography. This includes the construction of pseudorandom generators, commitment schemes, to name a few. In this presentation, we delve into the intricacies of these concepts, establish their interrelations, and demonstrate their utilization in constructing fundamental cryptographic primitives.
Iftach is faculty member of the School of Computer Science at Tel Aviv University, currently on leave working at Coinbase as Principal cryptographer.
He received his PhD. from the Weizmann Institute of Science, under the supervision of Omer Reingold, and his Master’s degree under the supervision of Oded Goldreich. He is the recipient of the the Kadar Family Award for Outstanding Research and the the John F. Kennedy Prize for outstanding doctoral thesis.
Meta-complexity refers to the complexity of problems that ask about complexity. Examples of meta-computational problems include the Minimum Circuit Size Problem and the time-bounded Kolmogorov complexity problem. Recently, there has been an emerging paradigm suggesting that understanding meta-complexity might lead us to the resolution of long-standing open problems in average-case complexity and cryptography. In this lecture, I will explain the relationship among meta-complexity, average-case complexity, and (complexity-based) cryptography, focusing on why meta-complexity is a useful tool for analyzing average-case complexity.
Shuichi Hirahara is an associate professor at National Institute of Informatics (NII), Japan. He received a PhD in computer science from the University of Tokyo in 2019, joined NII as an assistant professor, and promoted to the current position in 2022. He was awarded the Complexity Result of the Year in 2022.
In cryptography, “information-theoretic security” typically means the adversary is computationally unbounded, as distinct from “computational security” which relies on computational complexity assumptions. This domain is full of open problems with a communication-complexity flavor. In this talk, we will mention several such problems that have a huge gap between the best known upper and lower bounds, including secret sharing, private information retrieval (PIR), private simultaneous messages (PSM) and conditional disclosure of secrets (CDS). We will also discuss their connections and present our works that close narrow the gaps.
Tianren Liu is an assistant professor in CFCS, Peking University. Previously, he was a postdoc researcher at University of Washington. He received master and Phd degrees from MIT, and bachelor degree from IIIS, Tsinghua University. He works in theoretical computer science, especially on the theoretical foundations of cryptography. His PhD dissertation solves a long-open problem in information-theoretic cryptography. He also works on secure multi-party computation, garbled circuits, and block ciphers.
Secure Multi-party Computation (MPC) is the standard-bearer and holy-grail problem in Cryptography that permits a collection of data-owners to compute a collaborative result, without any of them gaining any knowledge about the data provided by the other, except what is derivable from the result of the computation. Communication complexity is one of the most prominent complexity measures of MPC with information-theoretic security. In this talk, I will draw a high-level picture of how the communication complexity study progressed over the years and my contributions to this area.
Arpita Patra is presently an Associate Professor at Indian Institute of Science and a visiting faculty researcher at Google Research. Her area of interest is Cryptography, focusing on theoretical and practical aspects of secure multiparty computation protocols. She received her PhD from Indian Institute of Technology (IIT), Madras and held post-doctoral positions at University of Bristol, UK, ETH Zurich, Switzerland, and Aarhus University, Denmark. Her research has been recognized with Google Privacy Research Faculty Award 2023, J P Morgan Chase Faculty Award 2022, SONY Faculty Innovation Award 2021, Google Research Award 2020, NASI Young Scientist Platinum Jubilee Award 2018, SERB Women Excellence award 2016, INAE Young Engineer award 2016 and associateships with various scientific bodies such as Indian Academy of Sciences (IAS), National Academy of Engineering (INAE ), The World Academy of Sciences (TWAS). She is a council member of Indian Association for Research in Computing Science (IARCS). She has coauthored a textbook on Multi-party Computation titled “Secure Multiparty Computation against Passive Adversaries”.
The goal of an error-correcting code is to allow a receiver to reliably recover a message, even in the presence of noise. In list-decoding, and the related notion of list-recovery, the goal is relaxed so that the receiver is allowed to return a short list of possible messages, but in a regime where there is so much noise that unique decoding is impossible. While they were originally motivated by coding theory and communication, list-decoding and list-recovery have found many applications, including in cryptography. In this tutorial, we’ll give a quick overview of the area, as well as several example applications and open questions.
Mary Wootters is an associate professor of Computer Science and Electrical Engineering at Stanford University. She received a PhD in mathematics from the University of Michigan in 2014, and a BA in math and computer science from Swarthmore College in 2008; she was an NSF postdoctoral fellow at Carnegie Mellon University from 2014 to 2016. She works in theoretical computer science, applied math, and information theory; her research interests include error correcting codes and randomized algorithms for dealing with high dimensional data. Her Ph.D. thesis received the Sumner B. Myers Memorial Prize from the UMich Math Department and and the EATCS Distinguished Dissertation award. She is the recipient of an NSF CAREER award, was named a Sloan Research Fellow in 2019 and a Google Research Scholar in 2021; she was awarded the IEEE Information Theory Society James L. Massey award in 2022, and named the IEEE Information Theory Society Goldsmith Lecturer for 2024.