2010


Jennifer Widom

Summer 2010

 

Dear Computer Science Alumni and Friends,

Upon completing my first full academic year as department chair, the job so far has been primarily a pleasure and just occasionally a challenge. Our faculty, staff, and students continue to demonstrate their top-notch caliber, while remaining dedicated to the well-being and advancement of our department. For me, interacting with the large number and wide variety of people who make us world's leading Computer Science Department has turned out to be one of the most interesting and enjoyable aspects of the job. (Okay okay, we're sometimes tied with MIT in those academic polls, but there's no question we've got them on weather.)

What about the challenges? We're dealing with dramatic two-year increases in CS majors, with no end in sight---more on that below. But once we're settled into absorbing the new numbers, that can hardly be considered a bad thing. The budget has been tight, but like all units on campus, we've correspondingly tightened our belts, and the worst appears to be behind us. There are the random day-to-day departmental surprises, like the French coffee press gone missing, or reprimands from the fire marshal when our research poster sessions attract an overflow of interested people, but overall it's hard to come up with too much to complain about!

One of my goals as department chair---a goal shared by many chairs across the School of Engineering and the entire university---is to see an increase in departmental activities that have a positive impact on society. Of course just about all of our research eventually has societal impact, but I'm talking about direct near-term influence on key areas like health, environment, energy, and K-12 education. CS has much to contribute, but it's no secret that telling our faculty what they ought to be doing is next to impossible---our philosophy since the inception of the department has been to hire the very best people and let them do what they want. We do have some small incentives, like a seed funding program for faculty who want to try out speculative research ideas that are difficult to fund in traditional ways; this year we've focused that funding on research that also has societal impact. But in general faculty set their own course. I'm delighted that a substantial number of faculty and students have been involved in research and other projects with direct benefits to society. I've chosen to feature those types of activities throughout this newsletter.

Please enjoy the many departmental highlights of the 2009-10 academic year.

New and Retired Faculty

We are very pleased to welcome Stephen Cooper to our faculty as an Associate Professor in the Teaching line. Steve joins our two current teaching faculty, Eric Roberts and Mehran Sahami; this very strong trio positions us to be the leading institution in CS education. Steve has been on the faculty at St. Joseph's University and Purdue University, and recently served as a Program Director in the Division of Undergraduate Education at the National Science Foundation. Steve has been very active in the Alice programming language project, having authored two popular Alice textbooks. Through this work he has drawn students of all ages and backgrounds into computer science, especially those who might otherwise not consider the field. At Stanford, Steve will be teaching CS courses for both majors and non-majors, and will also be active in our K-12 outreach efforts. Anyone who has met Steve knows that he's an absolute dynamo---we're very excited about the breadth and new ideas he brings to our educational team.

Zohar Manna retired this year after a truly distinguished 42 years on the faculty. Zohar contributed profoundly to the logical foundations of computation, starting with a series of seminal papers in the 1960's and 1970's developing the formal basis for reasoning about programs. Later he made equally important contributions in automated deduction, temporal logics and concurrency, and reactive systems. Zohar collaborated with numerous preeminent computer scientists worldwide, and he has been universally acclaimed and appreciated as a consummate educator and advisor. He wrote eight books on aspects of logic in computer science that have been described as "models of clarity and comprehensiveness," and he leaves a tremendous legacy in his graduate students, many of whom are now in the very top ranks of computer scientists themselves. In aggregate, Zohar's students and co-authors read like a computer science hall of fame. On the occasion of his 64th birthday, Zohar's students wrote: "We received much more than just superb academic guidance from Zohar. Each one of us has volumes of tales to tell of the sound advice, sage counsel, joie de vivre, and the vibrant example of both hard work and great play set by Zohar.Zohar and his wife, Nitza, raised four children and traveled regularly with them from continent to continent. The youngest of the four recently graduated from Stanford with a Bachelors degree in computer science. Good choice!

New Endowed Professorship in Computer Science

In last year's newsletter I reported that the university granted approval for the CS Department to increase in size by up to ten regular faculty members, but that we need to raise funds to support the growth. Each additional faculty position requires an endowment of $2.5 million, to be augmented by School of Engineering funds.

We are extremely grateful to Google for donating the first of the ten endowed chairs, although under very sad circumstances. We will soon be naming a faculty member to the Google-funded Rajeev Motwani Professorship in Computer Science: In the spirit of Rajeev, the professorship will honor a distinguished senior faculty member whose work is like his: deeply rooted in computer science fundamentals and the underlying theory, but also applicable to important practical problems within and beyond traditional boundaries of the discipline.

 We are confident that happier occasions will mark the naming of additional endowed chairs in the years to come.

Distinguished Visitors and Lecturers

Even though our department generally steers a successful course on its own, there's no such thing as perfection, so I have felt compelled to introduce a few new initiatives in my term as department chair. In last year's newsletter I mentioned our quarterly department wine-tasting receptions, to socialize more, and to recognize the constant stream of awards bestowed upon our faculty and staff. (More on this year's awards below.)

Another initiative has been to introduce a formal program that brings in leading computer scientists, either asDistinguished Lecturers for a day of meetings capped by a broad talk, or as Distinguished Visitors in residence for a few months or longer. Truthfully, most other CS departments already have such programs. We've been lax in part because we tend to attract many terrific visitors and speakers in the regular course of events. Nevertheless, under the leadership of Prof. David Dill, we gave a more formal program a try. In its first year it's already been deemed a great success.

For the 2009-10 academic year we hosted Stuart Card as a Distinguished Visitor. Stuart was on sabbatical from the Xerox Palo Alto Research Center where he is a Senior Research Fellow. Considered one of the pioneers in the field of Human-Computer Interaction, Stuart has garnered just about every possible honor. His visit was a tremendous boon to our already strong HCI Group, and we look forward to continued interactions with Stuart in years to come.

We hosted two Distinguished Lecturers this year: David Salesin from Adobe Systems, and Marc Raibert from Boston Dynamics. David and Marc are world leaders in computer graphics and robotics, respectively. Each of them gave very engaging talks to overflow audiences, and they spent a day visiting with faculty and students in the department. We hope to attract equally exciting speakers next year.

Skyrocketing CS Majors

No, I don't mean that our CS majors are literally taking off in rockets, although I wouldn't be surprised---the variety of things these students are up to never ceases to amaze me. (In fact some of them have been involved in a course in the Aeronautics and Astronautics department in spacecraft design.) I'm referring to the skyrocketing number of CS majors. In 2009-10 we saw an increase of about 30% in the number of students declaring CS as their major, compounding a 41% growth the preceding year. If you do the arithmetic, that's an 83% increase over a two-year period. At this time, roughly 9% of Stanford undergraduates are declaring computer science as their major! Stanford has a policy of not limiting the number of students in any major, so who knows what next year will bring. Stay tuned.

New Courses

I figured it might be interesting to mention the new courses we introduced in the department this year. I was dumbfounded to discover that in 2009-10 we offered no fewer than 22 brand-new courses and five brand-new seminars. WOW! Here are just a few examples of the new offerings; our entire course list is, of course, available online.

          Programming Massively Parallel Processors
          Canons of Computer Science
          Network Analysis
          Understanding Images and Videos
          Data Visualization
          Math and Computer Science Behind Special Effects
          Seminar on Computing and Design Thinking
          Surgical Robotics Seminar


Using Technology to Enable Human-Human Interaction in the Classroom

 We all remember sitting in a large classroom trying to pay attention while the professor drones on. Even the best professors face a challenge keeping students focused in large lecture courses, and indeed, educational research overwhelmingly shows that students learn much better when they have the opportunity to engage in active learning, to participate in small group interactions, or to discuss the relevance of course material to topics of relevance to them. However, there is rarely time for such activities in a standard lecture course. To address this shortcoming, Prof. Daphne Koller recently piloted a new teaching model, with the support of President Hennessy and Vice-Provost John Bravman. In the new model, all of the traditional frontal instruction has been moved to an online format, whereas classroom time is devoted to small group activities and interactive problem solving in which students and faculty truly interact with each other. Importantly, the online material is not simply the standard recording of traditional lectures. Rather, the material is divided into 8-15 minute "chunks," each of which is a conceptual unit. The chunks are organized into a flow diagram that encodes the dependencies between them. Moreover, the video chunks are interspersed with multiple-choice quizzes, forcing the students to actively test their knowledge and get immediate feedback about their understanding. Chunks are also accompanied by an online discussion forum, in which students can communicate with each other and with the course staff regarding the material. The new format was tried out this year in Daphne's Probabilistic Graphical Models, a core course in the department's AI sequence. The experiment went over very well with the students, and the new features---the interactive sessions, the chunking of the material and the online quizzes---got particularly positive reviews.

The university is now exploring the use of this technology in a range of other courses, at both the undergraduate and graduate level. Its modular and flexible format has the potential to allow students to navigate course material in different ways, supporting diverse interests and backgrounds. It can also help reduce duplication between courses and reduce long prerequisite chains. And, of course, this format can be disseminated easily outside of Stanford, providing a much broader community access to some of Stanford's finest teachers.

Research Activities

As always, a tremendous amount of exciting research is going on in the department. For this newsletter I selected four research projects with direct impact on key areas of societal need. Please visit the CS Department website to learn about ongoing research across the entire field.

 Can Machine Learning Help Save ICU Patients?

Many of us hope that our work will improve people's lives, but the path from academic research to real-world impact is often a long one. Prof. Daphne Koller and her student Suchi Saria are working together with neonatologist Prof. Anna Penn to try and make a direct impact on medical care and treatment. Their NICU project uses the power of machine learning to help understand disease processes and predict outcome in infants in the neonatal intensive care unit of Packard Children's Hospital. Born weighing less than 2000 grams, these infants are at risk for a range of major complications, many of which are life-threatening or can lead to poor long-term developmental outcomes. Identifying which infants are at risk of developing major complications can help guide treatment and resource allocation. In their project, they have exploited the recent introduction of electronic medical records to effectively collect physiological data from bedside monitors and lab results. They have built machine learning methods to discover knowledge in these complex data streams and to systematically integrate diverse information sources. Their approach can currently identify these high-risk infants with very high accuracy using only non-invasive markers from the monitor data from the first three hours of life. They are currently extending this work to other prediction tasks such as identifying specific complications before a doctor would normally be able to recognize them. Ultimately, they hope to extend these methods to other clinical settings where early warnings could save lives but recognizing the relevant complex patterns from the available measurements is difficult. Daphne and Suchi believe that easier access to more detailed electronic health records and machine learning algorithms targeted towards decoding this data can add a whole new dimension to patient care by helping tailor treatments to the patient. Perhaps not too far in the future, ICU patients and their families will rest more comfortably knowing that computer science will have given their doctor another set of eyes capable of diligently watching out for their health.

Where Do All the Kilowatts Go?

It started with the electricity bill. Surveying the $35,000 tab for one month's use of electricity in the Gates Computer Science Building, Ph.D. student Maria Kazandjieva decided that she needed to know where kilowatts are spent. In collaboration with Ph.D. student Brandon Heller, she built and deployed a 140 node wireless sensor network, PowerNet. PowerNet measures the power used by electronic devices, from servers in the basement to network switches to kitchen microwave ovens. Using PowerNet, the students were able to determine that over 55% of the building's energy bill---$20,000 per month---goes to computing systems. By adding software and hardware sensors that measure the activity of computing devices, Maria was then able to determine how much of this energy is spent doing useful work, and how much is wasted. Based on these findings, Maria identified three ways to make the Gates building more green: Working with Prof. Scott Klemmer, she is researching human intervention strategies to change user behavior, such as a large display in the building lobby. Working with staff members Peche Turner and Miles Davis, she is researching how policy changes, such as when backups occur, could allow devices to be turned off when not in use. Finally, working with Profs. Christos Kozyrakis and Philip Levis, she is designing a new, energy-efficient computing infrastructure that is being deployed in one wing of the building. In the long run, the infrastructure will yield a toolkit for helping IT and systems administrators design and manage the enterprise networks of the future. To learn more about the project, please visit the Powernetwebsite.

Healthcare Privacy and Security

Over the last decade, many hospitals and clinics have moved from paper to electronic medical records. An increasing number now also allow patients to book appointments, ask questions, and view test results over the Web. While the move to more accessible healthcare information is helpful to many patients, it also raises privacy and security concerns. Along with fears of embarrassment and potential job discrimination, many patients are concerned that access to their medical records might lead insurers to raise their rates or deny coverage. What is our department doing to help? A project led by Prof. John Mitchell began by developing a logic for expressing privacy policies and regulations, such as the Health Insurance Portability and Accountability Act (HIPAA), in executable form. John's group then built a prototype Web-based messaging system based on an existing hospital system and incorporating their logic. The system provides judgments on proposed or requested information transfers between doctors, nurses, patients, family members, hospital administrators, police, and others. For example, if a doctor plans to give an insurance company information about psychological treatment of a patient, the system may remind the doctor that this kind of message is not allowed. The system can also be used as a training tool to help hospital workers understand their hospital policies, so they don't overreact and unnecessarily withhold useful information. John's work is just beginning, as he was recently designated "Chief Computer Scientist" for a new $15 million multi-university project developing healthcare information security and privacy technology in collaboration with medical doctors and other computer security researchers. Overall, by developing ways for computer systems to reason about privacy issues, laws, and conventions, the work in John's group is making it possible to build systems that both respect privacy and improve healthcare.

Incentives Mechanisms for Societal Networks

Frustrating traffic jams are well-known to commuters. Less well-known is how expensive congestion is: a study by the Texas Transportation Institute estimates that more than $80 billion is wasted in time and fuel costs annually in the U.S., and transportation systems contribute more than 20% to carbon emissions. This staggering cost and the increasing green-consciousness in the population begs the question "Why don't commuters take public transportation, carpool, or travel during uncongested times?"  The answer lies in the insidious nature of the inefficiency: when measured at the individual level, it's only about $1 dollar a day.  The effort required to reduce the inefficiency seems excessive compared to the benefit.  Similar costs and reasons exist in other "societal networks" such as energy, healthcare, and recycling systems: We don't turn off lights, reduce our energy consumption, take care of our health, or ensure that bottles and cans don't end up in landfills. "There are two major reasons for this state of affairs," says Prof. Balaji Prabhakar, who has launched a research program on societal networks.  "First, we lacked an ability to monitor and measure inefficiency and waste at an individual level. Second, we could not communicate with and coordinate the many different users.  But with technologies like the Internet, mobile telephony, GPS systems, and low-cost environmental sensors becoming ubiquitous and extremely affordable, the ability to monitor individual behavior and incentivize change has been altered dramatically." Prabhakar and his collaborators have reacted to this opportunity with gusto! Over a six-month period in 2008-2009, they incentivized 14,000 commuters at Infosys Technologies, Bangalore, India, to commute during off-peak hours. Since small amounts of money do not induce large behavioral changes, they rewarded consistent off-peak hour commuters through a lottery mechanism. Similarly, in an experiment conducted in a Freshman Seminar in Spring 2010, recyclers were paid up to $100 (with 1/2000 chance) for a recyclable worth 5 cents.  Next up for Prabhakar and his collaborators: incentivizing off-peak commuting at Stanford; decongesting Singapore's public rail system; working with insurance companies to reduce risky driving behavior; and working with the Bonneville Power Administration to reduce household energy consumption in the Pacific Northwest.

Student Projects

All CS majors engage in a Senior Project, either independently or as part of a group. Projects are demonstrated during a high-energy Software Project Faire put on each spring, typically attracting a large number of industry folks. Browsing through the projects at the Faire and talking with the sleep-deprived but proud students is an amazing experience. (Contact Bob Plummer if you're interested in receiving an invitation in future years.) Here are three projects that give a flavor of the level of innovation and sophistication among our seniors, while demonstrating fairly immediate societal impact.

         Brain-Computer Interface - an application by which severely disabled persons can perform typing and environmental control. The application is built using MindSet, a headset that senses and interprets EEG brainwaves to detect eye blinks and to determine the wearer's level of attention and meditation. The application was developed in consultation with David Jaffe, who teaches an Assistive Technology course in the Mechanical Engineering Department, and a quadriplegic patient at the VA Hospital in Palo Alto.

         Audi Fuse - a complete battery and vehicle management system for electric vehicles that can schedule charging, preheat the battery and cabin, calculate driving range, plan routes, and much more using a mobile web browser. The driving range calculator provides an innovative map showing locations that can be reached given the current charge level and driving conditions, eliminating the electric car owner's biggest worry.

         RoboMathsters - a novel form of online math education for elementary school students. Students exercise their problem-solving skills using a multiplayer online game-driven platform centered on virtual manipulatives (virtual learning environments that help students visualize relationships and applications) and math drills. In conjunction with game-play, parents and teachers can monitor student progression and comprehension through online reports.

Liberation Technologies

Prof. Terry Winograd has joined with Political Science Profs. Josh Cohen and Larry Diamond from the Center on Democracy, Development, and the Rule of Law (CDDRL) to create the Stanford Project on Liberation Technologies. Their focus is on the ways that emerging information and communication technologies affect the political, economic, and social development of countries around the world. The project comprises a variety of research and teaching activities, including a speaker series with topics this past year ranging from the effect of blogging on the political situation in repressive countries to the use of mobile phones for economic development through improving market information. In a course offered this Spring in conjunction with the Hasso Plattner Institute of Design (affectionately, the d.school), interdisciplinary student teams developed applications of mobile technology to improve access to health care in Nairobi, Kenya. The course was in conjunction with the Nokia Research Center Nairobi, and with faculty and students in the Computer Science Department at the University of Nairobi, with whom Prof. Winograd looks forward to an ongoing collaboration.

Ph.D. Student Wins ACM Dissertation Award

Each year ACM, the professional society for computer scientists, chooses one Ph.D. dissertation from those nominated worldwide to receive the ACM Dissertation Award. I'm thrilled to report that this year's winner isCraig Gentry, a Ph.D. student in Prof. Dan Boneh's group. Craig's thesis is titled A Fully Homomorphic Encryption Scheme. It solves a central open problem in cryptography that was first posed over 30 years ago. No wonder he won the award! The results obtained in Craig's thesis enable arbitrary computations on encrypted data, for example allowing spam filters to operate on encrypted email, and enabling private queries to a search engine or database where the encrypted queries and answers are never seen in the clear. Congratulations to Dan and Craig!

Faculty Awards

Once again our faculty have garnered a wealth of major awards. Without further ado:

         Bill Dally ― ACM/IEEE Eckert-Mauchly Award

         Oussama Khatib ― IEEE Pioneer in Robotics and Automation Award

         Don Knuth ― Katayanagi Prize for Research Excellence

         Chris Manning ― AAAI Fellow

         Tim Roughgarden ― ACM Grace Murray Hopper Award

         Mendel Rosenblum ― ACM Software System Award for VMWare (with current Ph.D. student Jeremy Sugerman and others)

         Jeffrey Ullman ― IEEE John von Neumann Medal

         Terry Winograd ― ACM Fellow

In addition, Leo Guibas was named to the School of Engineering Pigott Professorship, Jeff Heer was listed as one of Technology Review's "TR35" (Young Innovators Under 35), and Jean-Claude Latombe was ordained as a Knight in the Ordre National du Merite (France).

Student News

As usual, our students at all levels have been doing truly remarkable things.

University-Level Honors for Teaching ― Andrew Adams, a Ph.D. student advised by Marc Levoy, received a 2010 Gores Award, the university's highest teaching honor, for his work in designing and teaching the all-new course Image Processing for Photography and Vision, as well as tremendous work as a teaching assistant in other courses. (You might check out some of the applets Andrew developed for teaching photography; they're viewed thousands of times a day from all over the world.) Andrew was honored with the award at the university-wide commencement ceremony held in the Stanford Stadium. What a moment for Andrew and the CS Department!

School-Wide Academic Honors ― Each year the School of Engineering names as Ford Scholar the undergraduate student with the highest GPA across the entire school. We're pleased that this year's Ford Scholar is CS student Keith Schwarz.

Undergraduate Research ― Justin Solomon won the Wegbreit Prize for Best CS Undergraduate Honors Thesis. His thesis, advised by Prof. Leo Guibas, is titled Discrete Killing Fields for Pattern Synthesis and Symmetry Detection. This novel work was also recognized by a university-wide Firestone Medal for Excellence in Undergraduate Research.

Master's Research ― Gustav Rystedt won the Christofer Stephenson Memorial Award for Best CS Master's Research Report. Gustav was advised by Profs. Dan Boneh and John Mitchell; his thesis is Busting Frame Busting: a Study of Clickjacking Vulnerabilities on Popular Sites.

Ph.D. Research ― In addition to the ACM Dissertation Award winning thesis by Craig Gentry described above, the department's other Arthur Samuel Award for outstanding Ph.D. thesis went to Chuong (Tom) Do. Tom's thesis, titled Discriminative Probabilistic Models for Biological Sequence Analysis, was co-advised by Profs. Serafim Batzoglou and Andrew Ng.

Centennial TA Award ― Ben Packer, a Ph.D. student advised by Prof. Daphne Koller, was selected as a winner of this year's Centennial TA Award. Ben was recognized for his outstanding work in helping migrate Daphne's course to the new educational model described earlier in this newsletter, including producing all of the online quizzes.  Ben also offered extra sections and office hours to provide the students with exceptional support and guidance as the new format was rolled out.

ACM Programming Contest ― The annual ACM Regional Programming Contest took place once again this past fall, with 77 teams from schools throughout Pacific Northwest Region participating. Stanford did well, with the three teams we fielded coming in 2nd, 3rd, and 17th place. Stanford's 2nd place team comprised of Philipp Krahenbuhl, Jae Hyun Park, and Jeffrey Wang, and coached by CS Lecturer Jerry Cain, advanced to compete at the World Finals in Harbin, China. They did quite well, placing 1st in the North America region and 14thworldwide.

ACM Student Chapter ― Our local ACM chapter won the 2009-10 ACM Student Chapter Excellence Award for Outstanding Community Service, for organizing the Dance Marathon Hack-A-Thon. The event was organized by CS students David Gobaud (then ACM chapter president) and Karina Qian.

More Winners ― A team comprised of CS students Xuwen Cao, Joseph Lau, George Tang, and Jason Wei, together with Economics & East Asian Studies student Mark Bocanegra, won the 2010 "Juicy Ideas Collegiate Competition" by developing an application to help users discover leisure ideas and activities. Evidently, there are still some people in the world with leisure time―who knew? The prize may not be quite as attractive for our students as it would be for others: the winning team receives an all-expenses paid trip to the Google headquarters in Mountain View.

Computer Forum News

The Computer Forum is our long-standing industrial affiliates program, facilitating connections between Stanford's CS and EE departments and 60 companies worldwide. Computer Forum activities span the range from research collaborations to recruiting events. The Computer Forum's Annual Meeting is always very popular, with hundreds of participants from Stanford and member companies. This year's meeting, chaired by Prof. Scott Klemmer, included talks by faculty and industry leaders on current research in data webs, design thinking, and social creativity, and a well-attended evening reception featuring 58 student posters. As usual, focused all-day workshops were held before and after the main event.

We are pleased that Prof. Mendel Rosenblum will be stepping in as the new Forum Faculty Director, succeeding Profs. Hector Garcia-Molina and John Mitchell. Suzanne Bigas, Associate Director of the Computer Forum, retired in 2009 after 18 years at Stanford. We welcome Connie Chan as our new Associate Director. Connie has been with the Forum for over 10 years and brings a wealth of expertise to the program. We look forward to the Forum's continued excellence and industry relevance under Mendel and Connie's leadership.

 Until the next newsletter, have a terrific year.

Jennifer Widom

Fletcher Jones Professor

Chair, Department of Computer Science