2012

Jennifer Widom
Summer 2012

Dear Computer Science Alumni and Friends,

No deep reflection is needed to come up with what's happened over the past year in the CS department; most everyone would agree the year’s distinguishing features were StanfordNYC and Online-Education. I’ll discuss both of these very interesting developments―one already in the past and the other going strong―later in the newsletter, although it’s not possible to give either of them the coverage they deserve without going on for pages! I’ll also highlight our exciting new faculty hires, record-breaking enrollments and majors, a special year on CS theory, our usual array of faculty, staff, and student awards, and a tiny glimpse into our plethora of research activities.

I doubt many of you are counting, but this marks my third newsletter. I had intended it to be my last―although my time as CS department chair falls a bit short of the departmental average, it's already been longer than the three-year rotation I signed up for. But given the turmoil of the past year (reminder: StanfordNYC and Online-Education), my arm was twisted to stick it out another year or two for continuity. So, for better or worse, you’ll be hearing from me again next summer.

Please enjoy the many departmental highlights of the 2011-12 academic year.

New Faculty

Once again we were able to snag two of the year's most talented CS PhDs to join our faculty:  In 2013, Michael Bernstein and Greg Valiant will become Stanford CS assistant professors.

Michael Bernstein received his Ph.D. from MIT, where he has already made prominent contributions to the new and exciting field of crowdsourcing, within the broader areas of social computing and human-computer interaction. Stanford is a bit of a homecoming for Michael, who graduated from Stanford with a symbolic systems major before heading to MIT for graduate school. (It's even more of a homecoming for Michael's wife, Adi Greif, who not only was a Stanford undergraduate, but grew up on the Stanford campus as a faculty child.) Michael is spending his first ½ year back in the Bay Area as a post-doc at Facebook, before moving into the Gates Building in January.

Gregory Valiant is finishing up his Ph.D. at UC Berkeley―our traditional cross-bay rival, but also the source of many of our faculty. (Hiring our own PhDs directly to the faculty is strongly frowned upon due to "inbreeding," so it's not surprising that most of our faculty come from other top departments like Berkeley and MIT.) Greg works in computer science theory, with a broad portfolio of results in algorithms, learning, applied probability, and statistics. Greg will spend a year as a post-doc at the Microsoft Cambridge research lab before joining us in the fall of 2013. Incidentally, lest you wonder if there's a relationship, Greg's father Leslie not long ago won ACM's Turing Award, widely considered the "Nobel Prize of Computer Science." And Greg's brother Paul will be joining the CS faculty at Brown University. Quite a family!

Faculty-Knowledge Quiz: Michael Bernstein is our third faculty member to have participated in the much-loved CS section leader program as an undergraduate. Do you know who the other two are? Email your answer to smorze@stanford.edu; if it’s correct we’ll include your name in next year’s newsletter.

CS Popularity among Undergraduates Reaches Record Levels

This was a record-breaking year for CS enrollments on many fronts. First, we set a new all-time high for the number of undergraduates choosing to major in CS, with 246 students declaring their CS major this past year alone. That’s more than 40% higher than the previous record of 171 CS declarations in 2000-01 (at the height of the dot-com bubble), and double the number of annual declarations from just a few years ago (e.g., 123 CS declarations 2008-09). As a result, CS has become—for the first time ever—the largest undergraduate major at Stanford.

In addition to record numbers of CS majors, we are also seeing large numbers of students from across the university choosing to take CS courses. More than 1,500 students took the introductory programming course CS106A this past academic year, an increase of more than a 25% from 2010-11 (which was the previous record). Also, the CS department taught a total of nearly 60,000 class units last year, the largest number of units taught by any department at Stanford. Currently over 90% of all Stanford undergraduates take at least one CS class before graduating, and we’re seeing increasing numbers of graduate students from other fields taking CS classes as well.

Needless to say, accommodating all of these students in our classes poses some logistical challenges, but the level of interest in CS across the student body is exciting and invigorating.

StanfordNYC

In July 2011, mayor Michael Bloomberg announced a university competition to open a world-class campus for engineering and applied sciences in New York City. Despite peer institutions having set up shop in locales ranging from Singapore to Qatar, Stanford long resisted overtures to create a satellite campus abroad. However, a NYC campus held more appeal: There's no language or cultural barrier (though some might argue there's a pretty big cultural divide between California and New York!), no insurmountable time difference, and NYC has the largest concentration of Stanford alums outside of the Bay Area.

After a long series of discussions at all levels of the university, and a lot of hard work, in October 2011 Stanford submitted a 100+ page proposal for "StanfordNYC"―a $2.5 billion, 1.9-million-square-foot campus to be developed on Roosevelt Island over 30 years. The campus would have an eventual faculty of more than 200, and an eventual graduate student body of more than 2,000. The initial focus of the campus would be on information technology and entrepreneurship, something we at Stanford, especially in the CS department, are certainly experts in! Needless to say, the new campus would have a tremendous impact on the CS department, demanding rapid growth as well as exciting innovations in distance learning and new opportunities for collaborative research.

It was widely acknowledged that Stanford was one of leading contenders to be awarded the campus. Extensive discussions between Stanford and NYC took place during November and early December 2011. During the discussions Stanford was taken by surprise by a number of logistics and restrictions that were not part of the original announcement. Eventually Stanford came to realize the project would not be the partnership with the city that was originally envisioned, and we withdrew our proposal. There was, of course, a significant amount of disappointment after so much work had been done, and so much excitement generated. But admittedly there was some relief as well―the campus would have changed the course of the CS department considerably, and we think we're already doing pretty well as we are! Shortly after Stanford's withdrawal, the NYC campus was awarded to a collaborative proposal between Cornell University and Israel's Technion.

Please visit the StanfordNYC page if you're interested in learning more.

Online Education Initiatives

Over the past few years a number of CS faculty started thinking about shaking up the way we teach. You might remember from our 2010 newsletter (see Using Technology to Enable Human-Human Interaction in the Classroom) that Prof. Daphne Koller was promoting the idea of a “flipped classroom,” where students watch prerecorded video lectures on their own time to learn the core material. The videos are delivered in short, topic-specific chunks, with embedded quizzes to check basic understanding. Classroom time is devoted to interactive exercises and other engaging activities that reinforce and expand the core material. In the summer of 2011, Prof. Sebastian Thrun surprised everyone by deciding that not only would he use the flipped classroom approach for his fall offering of CS221-Introduction to Artificial Intelligence, but he would make the lecture videos available for free to the public, and augment them with automatically-checked exercises and a public discussion forum. Prof. Andrew Ng and yours truly had also been planning to try the flipped classroom in our fall courses (CS229-Machine Learning and CS145-Introduction to Databases), so we joined Sebastian in making our courses available to the world. The reception was unprecedented. Within just a few weeks, literally hundreds of thousands of students had signed up for the three courses!

Fast-forwarding to the end of fall quarter, tens of thousands of students from around the world had completed one or more of the courses, with a huge outpouring of gratitude and excitement. Profs. Thrun, Ng, and I had thrown ourselves into our projects, creating and perfecting course materials and exercises, while watching with wonder as the discussion forums hummed with activity. It turns out there’s no need for teaching assistants when you have social networking among thousands of eager students! On the Stanford front, although there were some mixed reactions to the new format, the key to success was improved self-learning together with good use of the new-found classroom time. In my database course there was nearly unanimous agreement that the purpose-made lecture videos with quizzes, and the extensive automated exercises, were enjoyable and provided an effective way to learn the basic material. Add on the interactive classroom activities, hand-graded challenge problems, a programming project, and conventional exams, and the complete package sat very well with the Stanford students. As concrete evidence, my course-evaluation scores saw a measurable uptick; it’s hard to argue with that.

What’s happened since last fall can only be described as scary and wonderful chaos. Two start-up companies were born from the Stanford efforts: Coursera, founded by Profs. Koller and Ng, is building a platform that can deliver a wide variety of courses developed by multiple universities, while Udacity, founded by Prof. Thrun, is developing its own curriculum to educate budding software engineers. MIT and Harvard jointly announced edX; reportedly many other universities are thinking very seriously about how or whether they should join the fray. Press coverage has been widespread. Practically every gathering of faculty, formal or informal, within Stanford or beyond, ends up with a long discussion of online education—what it means for us now, and what it means in the long run.

President Hennessy took a sabbatical for a few months this spring; guess what he reports spending his time thinking about? He describes a tsunami coming to education, one that we can either surf or be drowned by. This is Stanford―we created the initial wave, and we'll be riding the tsunami. Meanwhile back in the CS department, about a dozen more courses have been converted to a flipped classroom, a public offering, or both. It’s a lot of work for the faculty, but every instructor is simply jazzed by the ability to make substantial improvements in his or her Stanford course, while at the same reaching thousands of students around the world.

At some point the chaos will settle and we’ll see where these developments are headed for the long term. Our own Prof. John Mitchellhas been named Vice Provost for Online Learning, a post that includes chairing a high-powered university-level committee to think seriously about the many issues involved and where Stanford should head. Meanwhile, in true Stanford style, the plan is to encourage experimentation across platforms, disciplines, and audiences. You can follow Stanford’s wide variety of online-education activities—some new and many long-standing—on the website Online Learning at Stanford. One thing you can count on: CS faculty will be at the heart of Stanford's fast-moving efforts to use new technology to improve on-campus and off-campus education.

Special Year on Theoretical Computer Science

The theory group celebrated a number of recent faculty hires (Prof. Luca Trevisan, Prof. Ryan Williams, and now Greg Valiant) with a “Special Year on Theoretical Computer Science," which featured important visitors as well as seminars, workshops, and a new colloquium series. Princeton professor Bob Tarjan, the CS department’s Distinguished Visitor for the year, ran a seminar on data structures and collaborated with Prof. Ashish Goel (from Stanford’s MS&E department) on new results for the classical Union-Find data structure. Harvard professor Salil Vadhan and his Ph.D. students also visited the department, working with Prof. Trevisan and his group on problems in computational complexity and cryptography. Prof. Tim Roughgarden organized an algorithms workshop with the theme Beyond Worst-Case Analysis. Profs. Roughgarden and Trevisan initiated the Rajeev Motwani Distinguished Lecture Series, an ongoing quarterly series of colloquia in theoretical computer science aimed at a broad audience. All workshop and colloquium talks are archived on YouTube.

While the Special Year has come to a close, the theory group continues to be a hotbed of activity. This coming year Stanford will host two of the premier annual conferences in theoretical computer science: the ACM Symposium on Theory of Computing and the IEEE Conference on Computational Complexity. Prof. Trevisan will run a workshop on graph partitioning algorithms, random walks, and expander graphs, three topics that have significant mathematical connections but are studied by largely distinct communities. Prof. Goel and Prof. Amin Saberi (also from the MS&E department) will organize a workshop on issues at the intersection of social networks and theoretical computer science, an area that is also well represented in the long-standing RAIN (Research on Algorithms and Incentives in Networks) seminar, run jointly by CS and MS&E.

Research Activities

As always, a tremendous amount of exciting research is going on in the department. Please enjoy these four samples, representing a diverse cross-section of topics and research styles, and visit the CS Department website to learn about our ongoing research across the entire field.

The MobiSocial Project
Spring 2011 saw the creation of the new MobiSocial Computing Laboratory, directed by Prof. Monica Lam. A primary goal of the MobiSocial project is to create open technologies for social networking and data ownership that free users from being locked into proprietary solutions. In just over a year the lab has already developed a new social network called Musubi, which allows groups of phone users to share text, pictures, games, and most importantly apps, in real time, all without intermediation. Data is shared over phones with the help of identity-based encryption and backed up to users' choice of storage. Musubi has recently been released on the Android Play Store, and the iPhone version is forthcoming. With the help of a few freshmen and local high school students, Musubi is also emerging as a promising research platform to attract pre-college students, especially girls, into computer science. The MobiSocial Lab operates in part as an industry affiliates program, currently consisting of five partners: AVG, Google, ING Direct (part of Capital One), Nokia, and Sony/Ericsson. Given what's come out of the new lab in just one short year, stay tuned for exciting further developments.

Data-Driven 3D Modeling
The ability to easily create detailed synthetic models of three-dimensional objects and environments would have significant applications in entertainment, education, and telecommunication. Unfortunately, creating three-dimensional models of complex objects is notoriously difficult and time-consuming. Making the creation of three-dimensional content more accessible is one of the biggest challenges in computer graphics research. Over the past few years, Prof. Vladlen Koltun and his group have developed a new generation of 3D modeling tools that allow even novices to create detailed models of complex objects. The key idea is to use machine learning to construct representations of geometric and structural properties of objects from different families, such as buildings, airplanes, or chairs. These representations are used to assist the modeling process. They are capable of generating complete objects from these categories in response to high-level specifications, and can fill in geometric details that previously required painstaking sculpting. Prof. Koltun's group has demonstrated that data-driven tools support rapid modeling of custom buildings, furniture, vehicles, aircraft, ships, animals, and other types of complex objects. See the project page for more information.

Web Privacy and Third-Party Tracking
Prof. John Mitchell has been studying third-party tracking on the web, together with his Ph.D. student Jonathan Mayer who has the unusual distinction of pursuing jointly a CS Ph.D. and Law degree. When you visit a web site that contains an advertisement, the advertisement is requested by your browser based on commands provided by the site you visited. These commands may trigger a series of requests to third-party sites, possibly passing any information known to the first-party site. Since third-party advertisers learn your network address and other information about you each time they serve an ad, they can correlate data associated with different requests originating from different first-party sites you visit. As a result, an advertiser can learn for example that you visited several different shopping sites, a health site, and a social network site, possibly correlating information about what you looked at or bought at each one. Prof. Mitchell and his student designed a method for opting out of third-party tracking called “Do Not Track,” which is now supported in all major browsers. Over this past year, the group also developed a tool called “Fourth Party,” which can be used to track third-party tracking. Fourth Party is an instrumented browser that records events that occur when a web site is visited and stores them in a database. Using Fourth Party, a number of sites have been found to violate their apparent privacy promises to users, or to use unusually invasive tracking techniques such as "history stealing." Data collected using Fourth Party has led to a number of actions against tracking companies by the Federal Trade Commission, and a number of prominent articles in major news outlets.

Architectural Support for Snapshot Isolation and Atomic Update
The long-running quest for abstractions and mechanisms that facilitate the development of highly concurrent and highly available systems has gained importance with the growing use of multi-core systems and the expectation of 24x7 system availability. The atomic transaction is being used extensively to this end in both database and distributed systems. The snapshot isolation model of transactions is being favored because it avoids the need to detect read-write conflicts. With the memory system being the performance bottleneck for many applications, an important research question being addressed by Prof. David Cheriton and his group is whether there is a compelling case for architectural support in the memory system for snapshot isolation-based transactions. Recent innovations provide a memory controller with an extra level of indirection to physical memory, allowing deduplication of memory at cache-line granularity for virtual machine environments, saving on DRAM. Prof. Cheriton's group uses this technology to make creating a snapshot of state far less expensive; it can also be used to atomically update on transaction commit.  The direction shows promise in supporting highly concurrent multi-core applications without locking, as well as providing hardware support for in-memory databases using "consistent read" semantics. Because the shared memory lines are immutable, this approach also reduces the coherency memory traffic between processor cores, a key issue with scaling performance. The same deduplicating memory architecture is being tried on sparse matrix computation where, again, memory access overhead dominates as the performance bottleneck. With benefits across several application domains, Prof. Cheriton believes this approach makes a compelling case for a major redesign of the 70-year old Von Neumann memory model.

Faculty and Staff Awards

It's been an especially good year for major faculty awards:

• Leo Guibas ― IEEE Fellow
• Jeff Heer ― Sloan Fellowship
• John Hennessy ― IEEE Medal of Honor (Yes, John is the university president, but he remains a member of the CS faculty and we're proud of it)
• Scott Klemmer ―  Katayanagi Prize for Emerging Leadership
• Don Knuth ― IET Faraday Medal
• Don Knuth again ― Elected to American Philosophical Society
• Jean-Claude Latombe ― IEEE Pioneer in Robotics and Automation Award
• Jure Leskovec ― Sloan Fellowship
• Chris Manning ― Fellow of Association for Computational Linguistics
• Ed McCluskey ― IEEE John von Neumann Medal
• Eric Roberts ― IEEE Computer Society Taylor L. Booth Education Award
• Mendel Rosenblum ― IEEE Computer Entrepreneur Award
• Tim Roughgarden ― Goedel Prize
• Jeff Ullman ― Elected to American Academy of Arts and Sciences

In addition, Mehran Sahami was named one of Princeton Review's Best 300 Professors (that's across all universities and all fields!), Ed Feigenbaum was named a Computer History Museum Fellow, Mehran Sahami (again) became the Robert and Ruth Halperin University Fellow in Undergraduate Education, and Dan Boneh received the Dean's Ishii Award for Industry Education Innovation.

When we hired Keith Schwarz as a lecturer a year ago, we knew he was an amazing teacher: as a Stanford CS undergraduate and coterminal student he created and taught courses that quickly became among the most highly-rated in the department. It didn’t take long for his talents to be recognized on an even broader scale. Keith is the 2012 recipient of the Tau Beta Pi Excellence in Teaching Award, given to just one individual across the entire school of engineering. It’s unusual for this award to go to a lecturer, and nearly unheard of for someone to receive it after just one year of full-time teaching. Keith is an educator of the very highest caliber; we’re extremely fortunate to have him.

On the staff side, we were thrilled that our beloved and extraordinarily competent student services specialist Meredith Hutchin won the School of Engineering's Kay Bradley Award for Outstanding Service to Students. Meredith indeed does an outstanding job with a wide variety of student-related tasks, but even more importantly she brings true compassion and a "can-do" attitude to student issues, be they large or small. Even with double the number of students from just a few years ago―and therefore double the number of student issues―Meredith solves them and does it with a smile. It's staff like Meredith that make the CS department such a happy home for so many.

Student News

Our students continue to do amazing things, and garner wide recognition for it.

School-Wide Academic Honors ― Frank Li was named the Ford Scholar in the School of Engineering, an award given annually to the undergraduate student with the highest GPA across the entire engineering school. Well done, Frank! Frank is the third Ford Scholar in a row to hail from the CS Department. Previous winners were David Tobin in 2011 and Keith Schwarz (now a CS Lecturer) in 2010.

Undergraduate Research ― Pang Wei Koh won not one, but three awards with his undergraduate honors thesis “Indentifying Genetic Drivers of Cancer Morphology,” advised by Prof. Daphne Koller. Departmentally, Pang Wei won the Wegbreit Prize for Best CS Undergraduate Honors Thesis. He also won one of 28 university-wide Firestone Medals for Excellence in Undergraduate Research. His crown jewel was receiving the Kennedy Thesis Prize for the best honors thesis across all of the applied sciences and engineering. Congratulations, Pang Wei!

Graduate Research ― The Arthur Samuel Award for outstanding CS Ph.D. thesis was given to Shaddin Dughmi for his thesis "Randomization and Computation in Strategic Settings," advised by Prof. Tim Roughgarden. MS student David Held won the Christofer Stephenson Memorial Award for Graduate Research, given to the best CS Masters research report. David’s report, “Autonomous Driving: Car Detection, Tracking, and Street Sign Detection,” was co-advised by Profs. Vaughan Pratt and Sebastian Thrun.

Teaching Awards ― Our students did such an impressive job in support of teaching this year that two of them, Katherine Breeden and David Cummings, received the department's George Forsythe Memorial Award for Excellence in Student Teaching. Katherine was recognized for her work as an outstanding Teaching Assistant for CS148: Introduction to Computer Graphics and Imaging, with many students gushing about her unusual talent at promoting learning and enthusiasm for the material. David was commended for helping to develop the public version of CS145: Introduction to Databases (see Online Education Initiatives above), in which over 60,000 students enrolled. David did an equally stellar job supporting the 140 Stanford students in the course..

ACM International Collegiate Programming Contest ― Stanford once again did quite well in the ACM ICPC, with the team of John Pardon, Nick Wu, and Chenguang Zhu winning first place in the Pacific Northwest Regional Contest, besting strong teams from the University of British Columbia, University of Washington, and, of course, our cross-bay rival UC Berkeley. John, Nick, and Chenguang then advanced to the World Finals in Warsaw, Poland, where they placed a respectable 13th (ahead of both Carnegie Mellon and MIT).

Recognition from Bill Clinton ― We’re excited to report that Code the Change, a student organization spearheaded by CS student Sam King to help computer scientists use their skills for social change, was recognized by former President Bill Clinton at the 2012 Clinton Global Initiative University. Keep up the great work, Sam!

Distinguished Visitors and Lecturers

Our distinguished visitor and lecture program, finishing up a third year since its revival, continues to thrive thanks to excellent oversight by Prof. David Dill.

For the 2011-12 academic year we hosted Bob Tarjan as a Distinguished Visitor. A Stanford Ph.D. alum, Tarjan is bicoastally distinguished: his permanent position is as Distinguished University Professor of Computer Science at Princeton. As a preeminent theorist, Tarjan’s visit was timed to coincide with the Special Year on Theory described earlier in the newsletter.

We hosted three Distinguished Lecturers this year: Shree Nayar from Columbia, Stefan Savage from UC San Diego, and Christos Papadimitriou from UC Berkeley. The three talks represented three very different areas ― computational photography, internet security, and theory of computation ― with engaging presentations on timely and fun topics within each one.

Computer Forum News

Times have never been busier at the Computer Forum, which for 40 years has been the prime facilitator of connections between industry and Stanford’s CS and EE Departments. Companies join the Computer Forum to get involved with research, recruiting, or both. This past year has seen membership reach a record high of 108 companies. At the peak of the dot-com boom around the year 2000 we had 82 members; between then and now we dipped as low as 59. Our hunch is that recruiting is the biggest allure for companies these days, given the sizzling hiring climate for Stanford CS graduates (see The Job Market in Computer Science is Hot in last year’s newsletter). We had a record-breaking 70 companies participating in our two major career fairs, and we hosted 180 information sessions (where companies give presentations to students, often accompanied by free pizza and corporate swag). We hosted over 250 interviews, and organized several field trips for students to visit local companies. Unfortunately none of our foreign companies (currently hailing from Brazil, China, Hong Kong, Japan, Korea, and Saudi Arabia) have yet offered to sponsor field trips.

On the research side, the spring Annual Meeting, together with focused workshops surrounding the main meeting, always draws hundreds of participants. This year's featured topics were on-line education, machine learning, computer security, and mobile & social applications. We‘re hosting 18 visiting scholars—member-company employees who spend a year in a Stanford research group.

Computer Forum membership fees are used in a variety of ways to support the CS and EE departments: they support incoming graduate students, research seminars, and student groups like our ACM student chapter, WICS (Women in Computer Science), and WEE (Women in Electrical Engineering). With increased membership, the Forum has also been able to support our annual undergraduate student project fair (popular with company representatives, not to mention venture capitalists), and provide funds for students to attend the always inspiring Grace Hopper Conference. The Computer Forum is a win-win enterprise for companies and Stanford alike. If your company is not yet a member, please consider joining!

Until the next newsletter, have a terrific year.

Jennifer Widom
Fletcher Jones Professor
Chair, Department of Computer Science