CS Department Colloquium Series

We provide an overview of the introductory computer science curriculum at Carnegie Mellon University and then provide some detail about its perhaps most unusual component: a first-semester freshman-level course on imperative programming, algorithms, data structures, and computational thinking.  A key aspect of this course is its use of C0, a small safe subset of C augmented with a language for expressing contracts that capture pre- and post-conditions as well as loop and data structure invariants.  We provide some sample lecture material and report on our experience with this course over the last six years.

 Frank Pfenning studied Mathematics and Computer Science at the Technical University Darmstadt and then left for Carnegie Mellon University on a Fulbright scholarship where he obtained his Ph.D. in Mathematics in 1987 under the supervision of Professor Peter Andrews.

He subsequently joined the Department of Computer Science at Carnegie Mellon University as research faculty where he became Professor in 2002 and served as Director of Graduate Programs from 2004 to 2008 and Associate Dean for Graduate Education from 2009 to 2010. He was appointed Head of the Computer Science Department in January 2013 and the Joseph F. Traub Professor of Computer Science in October 2015.

He has spent time as visiting scientist at the Max-Planck-Institute for Computer Science in Saarbrücken, as Alexander-von-Humboldt fellow at the Technical University Darmstadt, and as visiting professor at École Polytechnique and INRIA-Futurs. He has advised 24 completed Ph.D. theses and won the Herbert A. Simon Award for Teaching Excellence in the School of Computer Science in 2002.

He served as trustee, vice president, and president of CADE, Inc., the governing body of the International Conference on Automated Deduction, and on advisory boards for INRIA, the Max-Planck-Institute for Computer Science, and Seoul National University. He has chaired several conferences and program committees, including CADE and LICS, and has been a member of the editorial boards for Theoretical Computer Science, Journal of Automated Reasoning, and the Journal of Symbolic Computation. He was named Fellow of the ACM in 2015.

His research interests include programming languages, logic and type theory, logical frameworks, automated deduction, and computer security. In his spare time he enjoys playing squash, running, hiking, cooking, and reading. 

The talk will survey a number of open problems in computer security, and discuss recent progress on communication systems that hide the metadata.  We will present a recent system, called Riposte, that uses cryptographic techniques to provide anonymous Tweets for very large anonymity sets.  This is joint work with Henry Corrigan-Gibbs and David Mazieres.

Dr. Boneh is a Professor of Computer Science at Stanford University where he heads the applied cryptography group and co-directs the computer security lab.  Dr. Boneh's research focuses on applications of cryptography to computer security.  His work includes cryptosystems with novel properties, security for mobile devices, web security, and cryptanalysis.  He is the author of over a 150 publications in the field and is a recipient of the 2014 ACM Infosys award, the 2013 Godel prize, and the Ishii award for education.

An Infovore is an information-based entity that explores the world, learns, and applies these learnings effectively.  In essence: a form of weak AI.  We have been working on a general-purpose infovore for making decisions using elements of contextual bandits, systems, and experts-style learning that has now been successfully deployed at large scale.  I will discuss the architecture of the infovore, the key results upon which it relies, and how everything works together to enable true open-loop learning in the real world.

 

Improving security requires both empirically-grounded insights into existing systems and threats, as well as theoretically-grounded solutions that anticipate how future users and attackers will adapt. I will present examples of both. I’ll begin by introducing empirical methods that I created to bring quantitative rigor to the question of how users choose authentication secrets (PINs, passwords, and security questions), a topic that has long been misunderstood due to a lack of data. I'll then present two theoretically-grounded approaches that apply cryptography to providing transparency that trusted authorities are behaving correctly. The first addresses servers for distributing public keys for secure communication, ensuring that the authority cannot lie without being detected.  The second ensures that banks that store bitcoins are solvent: that they actually are holding as many bitcoins as they have promised to their clients.

Intelligent agents require the ability to perceive their environments, understand their high-level semantics, and communicate with humans. While computer vision has recently made great strides on visual recognition tasks, the predominant paradigm is to predict one or more fixed visual categories for each image. I will describe a line of work that significantly expands the vocabulary of our computer vision systems and allows them to express visual concepts in natural language, such as “a picture of a girl playing with a stack of legos”, or “a couple holding hands and walking on a beach”. In particular, the final model can take an image and both detect and describe in natural language all of its salient regions. My modeling techniques draw on recent advances in Deep Learning that allow us to construct and train neural networks with hundreds of millions of neurons that take raw images and map them directly to natural language sentences. I will show that the model generates qualitatively compelling results and quantitative evaluation and control experiments demonstrate the strength of this approach with respect to simpler baselines and previous methods.

Andrej Karpathy is a Computer Science Ph.D. candidate at Stanford University working with Prof. Fei-Fei Li. He received his M.S. from University of British Columbia in Computer Science and his B.S from University of Toronto in Computer Science and Physics. He is interested in the intersection of computer vision, natural language processing and reinforcement learning with the aim of developing agents who can intelligently interact with humans in dynamic environments. His work was featured in the New York Times and MIT Technology Review. He helped develop and instruct a new Computer Science class at Stanford on Convolutional Neural Networks for Visual Recognition. In his spare time he develops Deep Learning libraries in Javascript and maintains websites that support more efficient meta-research.

When real people interact with algorithms (e.g. in auctions, crowdsourcing, Bitcoin, etc.), they impose additional objectives beyond simply that the algorithm is correct, fast, and uses little storage. People strategize during these interactions, so algorithms deployed in these settings must be robust against potential manipulation. Additionally, people prefer transparent interactions, so these algorithms must also be as simple as possible. My research addresses these, and other novel challenges that arise when algorithms interact with strategic agents.

In order to create truly autonomous physical robots, understand the underlying principles behind human movement, or tell narratives in animated films and interactive games, it is necessary to synthesize movement behaviours with the same wide variety, richness and complexity observed in humans and other animals. Moreover, these behaviours should be discovered automatically from only a few core principles, and not be a result of extensive manual engineering or a mimicking of demonstrations. In this talk at the intersection of robotics, computer graphics and biomechanics, I will show work on novel trajectory and policy optimization methods that give rise to a range of behaviours such getting up, climbing, moving objects, hand manipulation, acrobatics, and various cooperative actions involving multiple characters all in a single system. The resulting movements can be used to successfully control a physical bipedal robot and coupled with detailed models of human physiology, motions that match real human motion can be produced de novo, giving the predictive power to conduct virtual biomechanics experiments. The approach is fully automatic, based on general neural network policy representations and does not require domain knowledge specific to each behaviour, pre-existing examples or motion capture data. Although discovery and learning are computationally-expensive and rely on cloud and GPU computing, the interactive animation can run in real-time on any hardware once the controllers are learned.

Humans as well as information are organized in networks. Interacting with these networks is part of our daily lives: we talk to friends in our social network; we find information by navigating the Web; and we form opinions by listening to others and to the media. Thus, understanding, predicting, and enhancing human behavior in networks poses important research problems for computer and data science with practical applications of high impact. In this talk I will present some of my work in this area, focusing on (1) human navigation of information networks and (2) person-to-person opinions in social networks.

 Network navigation constitutes a fundamental human behavior: in order to make use of the information and resources around us, we constantly explore, disentangle, and navigate networks such as the Web. Studying navigation patterns lets us understand better how humans reason about complex networks and lets us build more human-friendly information systems. As an example, I will present an algorithm for improving website hyperlink structure by mining raw web server logs. The resulting system is being deployed on Wikipedia's full server logs at terabyte scale, producing links that are clicked 10 times as frequently as the average link added by human Wikipedia editors.

 Communication and coordination through natural language is another prominent human network behavior. Studying the interplay of social network structure and language has the potential to benefit both sociolinguistics and natural language processing. Intriguing opportunities and challenges have arisen recently with the advent of online social media, which produce large amounts of both network and natural language data. As an example, I will discuss my work on person-to-person sentiment analysis in social networks, which combines the sociological theory of structural balance with techniques from natural language processing, resulting in a machine learning model for sentiment prediction that clearly outperforms both text-only and network-only versions.

I will conclude the talk by sketching interesting future directions for computational approaches to studying and enhancing human behavior in networks.

Robert West is a sixth-year Ph.D. candidate in Computer Science in the Infolab at Stanford University, advised by Jure Leskovec. His research aims to understand, predict, and enhance human behavior in social and information networks by developing techniques in data science, data mining, network analysis, machine learning, and natural language processing. Previously, he obtained a Master's degree from McGill University in 2010 and a Diplom degree from Technische Universität München in 2007.

A fundamental issue with any new sensing technology is the deployment burden. The new technology often comes with a rigid and perhaps expensive list of pre-requisites; and it affects the overall cost-effectiveness, deployability, and accessibility of the solution. For example, a user might find it hard to buy and carry a medical device with them everyday. The primary theme of my Ph.D. research has been to reduce the adoption and deployment barriers of new sensing technologies by using the sensors that are already around us. In this talk, I will present my research on extending the capabilities of the on-board sensors on consumer devices for various applications. First, I will discuss how we can leverage the on-device sensors to enable novel human-computer interactions and make the mobile devices more usable. Next, I will discuss my work on using the on-device sensors for building  health technologies that work as well as their clinically-approved counterparts and they continue to evolve through deployments in various parts of the world. Finally, I will discuss how my recent work in extending the on-device sensors is shaping my future interests and how I plan to continue to lower the adoption barriers for new sensing technologies.

Mayank Goel is a Ph.D. candidate in Computer Science and Engineering in the Ubiquitous Computing (UbiComp) Lab at the University of Washington, advised by Shwetak Patel and Gaetano Borriello. His research focuses on building sensing systems to solve hard problems in diverse application areas, ranging from health sensing, technologies for the developing world to novel user interaction; with an eye toward reducing deployment barriers. His research in the area of health technologies is currently used by hundreds of patients every week, around the world. He was awarded the Microsoft Research Ph.D. Fellowship in 2014, a University of Washington CSE Fellowship, and 7 Best Paper Nominations. He received an M.S. in Computer Science from Georgia Institute of Technology in 2009, where he was advised by Gregory Abowd and specialized in mobile and ubiquitous computing.

The field of computer vision is arguably seeing one of its most transformative changes in recent history. Convolutional neural networks (CNNs) have revolutionized the field, reaching super-human performance on some long-standing computer vision tasks, such as image classification. The success of these networks is fueled by massive amounts of human-labeled data. However this paradigm does not scale to a deeper and more detailed understanding of images, as it is simply too hard to collect enough human-labeled data. The issue is not that we humans don't understand the image, but we often struggle to convey enough information to successfully supervise a vision system.

In this talk I show how computer vision can go beyond massive human supervision. This involves designing better models that deal with fewer labels, exploiting easier and more intuitive annotations, or coming up with novel optimizations to train deep architectures with far fewer human annotations, or even without any at all. I'll focus on three long standing computer vision problems: semantic segmentation, intrinsic image decomposition and dense semantic correspondences. 

Philipp Krähenbühl is a postdoctoral researcher at UC Berkeley. He received a B.S. in Computer Science from ETH Zurich in 2009, and a PhD in Computer Science from Stanford University in 2014. Philipp's research interests lie in Computer vision, Machine learning and Computer Graphics. He is particularly interested in deep learning, efficient optimization techniques, and structured output prediction.