Krishna Narayanan is the Eric D. Rubin professor in the Dept. of Electrical and Computer Engineering at Texas A&M University. He recently held visiting positions at Qualcomm research and at the Simons Institute for Computing. His research interests are broadly in coding theory, information theory, signal processing, and machine learning with applications to wireless communications. He recently received the 2022 joint Communications Society and Information Theory Society best paper award, the 2020 best paper award in data storage from the IEEE Communications Society and a university-level distinguished teaching award in 2018. He has served as a lecturer at the North American, Australian, and East Asian schools on information theory. He was elected a Fellow of the IEEE for contributions to coding for wireless communications and data storage.
Abstract: The emergence of generative AI systems and the resounding success of ChatGPT have generated unprecedented interest in the capabilities of large language models (LLMs). Researchers are exploring a myriad of applications for LLMs, reporting record-breaking performance in many areas. While a theoretical understanding of LLMs remains in its infancy, strong empirical evidence indicates that LLMs and large transformer-based architectures possess two remarkable properties - they excel at predicting the next token in a time series, and they possess in-context learning abilities. We study these properties in relation to two canonical tasks in information theory - compression and symbol estimation.
First, we design a lossless compression algorithm for English text using a large language model in conjunction with arithmetic coding, demonstrating state-of-the-art performance. We review results showing that transformers have sufficient expressive power to emulate popular compression algorithms such as prediction by partial matching and context-tree weighting. Next, we show that symbol estimation in wireless communications can be framed as an in-context estimation problem. We prove that, for a subclass of such problems, a single-layer softmax attention transformer computes the optimal solution in the limit of large prompt length. Furthermore, we empirically demonstrate the proficiency of multi-layer transformers in efficiently solving broader in-context estimation problems. This talk aims to provide an overview of recent results regarding the expressive power of transformers.
Maneesh Agrawala is the Forest Baskett Professor of Computer Science and Director of the Brown Institute for Media Innovation at Stanford University. He works on computer graphics, human computer interaction and visualization. His focus is on investigating how cognitive design principles can be used to improve the effectiveness of audio/visual media. The goals of this work are to discover the design principles and then instantiate them in both interactive and automated design tools. Honors include an Okawa Foundation Research Grant (2006), an Alfred P. Sloan Foundation Fellowship (2007), an NSF CAREER Award (2007), a SIGGRAPH Significant New Researcher Award (2008), a MacArthur Foundation Fellowship (2009), an Allen Distinguished Investigator Award (2014) and induction into the SIGCHI Academy (2021). He was named an ACM Fellow in 2022.
Abstract: Modern generative AI models are capable of producing surprisingly high-quality text, images, video and even program code. Yet, the models are black boxes, making it impossible for users to build a mental/conceptual model for how the AI works. Users have no way to predict how the black box transmutes input controls (e.g., natural language prompts) into the output text, images, video or code. Instead, users have to repeatedly create a prompt, apply the model to produce a result and then adjust the prompt and try again, until a suitable result is achieved. In this talk, I’ll assert that such unpredictable black boxes are terrible interfaces and that they always will be until we can identify ways to explain how they work. I’ll also argue that the ambiguity of natural language and a lack of shared semantics between AI models and human users are partly to blame. Finally, I’ll suggest some approaches for improving the interfaces to the AI models.
Piya Pal Piya Pal is an Associate Professor of Electrical and Computer Engineering at the University of California, San Diego, where she was also a founding faculty of the Haliciouglu Data Science Institute (HDSI). She obtained her B.Tech in Electronics and Electrical Communication Engineering from IIT Kharagpur, India in 2007, and her Ph.D in Electrical Engineering from Caltech in 2013 supervised by Prof. P. P. Vaidyanathan. Her Ph.D thesis was awarded the 2014 Charles and Ellen Wilts Prize for Outstanding Doctoral Thesis in Electrical Engineering at Caltech. Her research interests include signal representation and sampling techniques for high-dimensional signal/data processing, (sparse) sensor arrays and computational sensing, mathematical foundations of super-resolution imaging, and optimization and machine learning for inverse problems. Her contributions to sparse sensing have been recognized by several awards, including the 2020 IEEE Signal Processing Society Pierre-Simon Laplace Early Career Technical Achievement Award, and the 2019 US Presidential Early Career Award for Scientists and Engineers (PECASE). She is also a recipient of the 2019 Office of Naval Research Young Investigator Program (ONR YIP) award, the 2016 NSF CAREER and several best paper awards with her Ph.D students. She has served as an Associate Editor for IEEE Transactions on Signal Processing, IEEE Signal Processing Magazine and as Lead and Guest Editors for IEEE Journal on Selected Areas in Information Theory.
Abstract: Super-resolution is a prototypical ill-posed inverse problem that is encountered in many scientific and engineering tasks such radar target localization, super-resolution microscopy and modern autonomous sensing. The key objective is to retrieve “seemingly lost information” (typically high frequency components) from limited, low-frequency measurements, which are often distorted by a physical acquisition system and corrupted by noise. It is a classical but fertile topic where new innovations are continuously pushing the limits of what is achievable, and thereby giving rise to new scientific questions that can reshape our understanding of the fundamental limits of super-resolution.
We will study some of these innovations and fundamental questions that have been driven by sensing geometries (such as sparse arrays) and algorithmic advances (convex and non-convex methods). We will establish that resolution is a not a simple quantity that only depends on the aperture of the imaging system (as commonly believed), but is crucially shaped by factors noise level, sensing geometry, dynamic range and the trade-off between spatial and temporal measurements. Perspectives from coding theory have intriguing connections with sensing and super-resolution, which we will explore in the context of difference sets and subspace codes. Finally, we will take a critical look at the role of algorithm design for super-resolution and understand the trade-off between computational complexity and achievable resolution. In particular, we will argue that super-resolution is inherently a non-convex problem and one has to pay a hefty price in terms of achievable resolution by adopting a convex surrogate. We will demonstrate that it is possible to strike a balance between computational complexity and resolution without resorting to relaxation, and instead exploiting the rich structure that some of these super-resolution problems possess.
