2015 DISTINGUISHED LECTURE SERIES

Abstract:

Recent announcements by IBM, Google, and even Dwave reflect a growing interest in quantum computation. More than ever, computer scientists have the opportunity to help accelerate the evolution of quantum technologies towards practical, large-scale systems.  The key is to formulate the challenges that allows us to draw on decades of experience designing classical computer systems and software.

In this talk, I will present some lessons learned and future research directions in the design of architectures and software for scalable quantum computation.  First, I will discuss early work specializing architectures for application parallelism, reliability, and speed requirements.  Second, I will present a dynamic code generation approach for arbitrary quantum rotations. Third, I will discuss scalability challenges in the Scaffold infrastructure for compiling quantum programs.  Finally, I will outline future work in program verification, certified compilation, and the use of network routing algorithms to schedule large surface code computations.

Biography:

Fred Chong is the Seymour Goodman Professor of Computer Architecture in the Department of Computer Science at the University of Chicago. Chong received his Ph.D. from MIT in 1996 and was a faculty member and Chancellor's fellow at UC Davis from 1997-2005. He was also a Professor of Computer Science, Director of Computer Engineering, and Director of the Greenscale Center for Energy-Efficient Computing at UCSB from 2005-2015. He is a recipient of the NSF CAREER award, the DARPATech Most Significant Technical Achievement Award, and 5 best paper awards. His research interests include emerging technologies for computing, multicore and embedded architectures, computer security, and sustainable computing. Prof. Chong has been funded by NSF, Google, AFOSR, IARPA, DARPA, Mitsubishi, Altera and Xilinx. He has led or co-led $20M in awarded research, and been co-PI on an additional $10M.

Abstract:

The computational complexity of counting problems has been extensively studied since Valiant's foundational work in the 1970s. The complexity of computing exact solutions is by now well understood, in part through work done at Simon Fraser. Given the preponderance of negative results, it is natural to consider the complexity of computing approximate solutions with guaranteed error bounds. The situation here is less well understood. We can explore the topic conveniently through a study of spin systems of a kind seen in statistical physics. Such a system is defined by a graph, a number q of "spins", and a matrix of interaction strengths between pairs of spins. Each configuration,for example, assignment of spins to vertices, has a certain weight, obtained by taking a product over edges of the interaction strength between the spins at the endpoints of the edge. The problem is to approximate the partition function of the system, for example, the sum of weights over all configurations. In the context of spin systems, I'll discuss how complexity theory needs to be adapted to prove intractability results, and what algorithmic techniques exist to establish tractability results. The work on which this talk is based is due to too many authors to list here, so credits will be left to the talk itself.

Abstract:

Driven by the rapid increase in the quantities of data available, machine learning is undergoing a transition from large scale to very large scale modeling. Like the transition from LSI to VLSI in microelectronics circa 1980, this is not just a change in scale, but a paradigm shift. Where we used to model individual entities, we now can (and need to) model entire systems: we're going  from customers to social networks, from molecules to metabolic pathways, from neurons to brains, from services to cities, from species to ecosystems. Techniques that worked for the former break down for the latter. A set of principles for very large scale modeling is emerging, and I will describe three in this talk, illustrating them with examples from my research. The first principle is: Model the whole, not just the parts. I will show how we can do this with Markov logic networks. The second principle is: Tame complexity via hierarchical decomposition. The sum-product theorem provides a way to do this. The third principle is: Time and space should not depend on data size. Streaming bound algorithms make this possible. Building on principles like these, the impact of machine learning on society is set to increase manifold in the next decade.

Biography:

Pedro Domingos is Professor of Computer Science and Engineering at the University of Washington. His research interests are in machine learning, artificial intelligence and data science. He received a PhD in
Information and Computer Science from the University of California at Irvine, and is the author or co-author of over 200 technical publications. He is a winner of the SIGKDD Innovation Award, the highest honor in
data science. He is a AAAI Fellow, and has received a Sloan Fellowship, an NSF CAREER Award, a Fulbright Scholarship, an IBM Faculty Award, and best paper awards at several leading conferences. He is a member of
the editorial board of the Machine Learning journal, co-founder of the International Machine Learning Society, and past associate editor of JAIR. He was program co-chair of KDD-2003 and SRL-2009, and has served on
numerous program committees.

Abstract:

Computing has entered the era of approximation, in which hardware and software generate, compute, and reason about estimates. Sensors, machine leaning, unreliable systems, approximate computing, and big data generate estimates. However, applications that reason about these estimates are surprisingly ad-hoc because their programming models either require domain and statistics sophistication, which many developers lack, or worse, they obscure and ignore uncertainty.

We identify pervasive correctness, programmability, and optimization problems when computing with estimates. We propose Uncertain<T>, a first order type for estimates. Experts that generate estimates define Uncertain<T> sampling functions for distributions of type T.  Applications that consume estimates use familiar operations for T, a new conditional operator to control false positives and negatives, and a new Bayesian operator to combine estimates. The runtime implements hypothesis tests on conditionals with lazy and efficient sampling. We demonstrate correctness, programmability, and efficiency for GPS sensor applications, approximate computing, and Xbox.

Biography:

Kathryn S. McKinley is a Principal Researcher at Microsoft. She was previously an Endowed Professor of Computer Science at The University of Texas at Austin. She recieved her BA, MS, and PhD from Rice University. Her research interests span programming languages, compilers, runtime systems, architecture, performance, and energy with a recent focus on programming models for estimates.  She and her collaborators have produced several widely used tools: DaCapo Java Benchmarks, TRIPS Compiler, Hoard memory manager, MMTk memory management toolkit, and Immix garbage collector. She has graduated 21 PhD students. Her awards include the ACM SIGPLAN Programming Languages Software Award; ACM SIGPLAN Distinguished Service Award; and best & test of time awards from ASPLOS, OOPSLA, ICS, SIGMETRICS, IEEE Top Picks, and CACM Research Highlights.  She served as program chair for ASPLOS, PACT, PLDI, ISMM, and CGO. She is currently an ISAT, CRA, and CRA-W Board member.  Dr. McKinley was honored to testify to the House Science Committee (Feb. 14, 2013). She and her husband have three sons.  She is an IEEE and ACM Fellow.