2004

September 2004

Dear Computer Science Alumni and Friends:

It is time once again to report on all the exciting goings-on in the Computer Science department. After you read this newsletter, you'll agree that it has been another vintage year!

Let me start by letting you know that this will be my last newsletter. I will be retiring as department chair. It has been an exciting three and a half years (four years by the time I am done), but now it is time to hand over the "glory and power" of this job to one of my colleagues, Professor Bill Dally. Bill has agreed, after a bit of arm-twisting, to take over as department chair starting January 1, 2005. I would like to take this opportunity to thank all our faculty, staff, students, and friends who have given me their support and advice during these years. I wish Bill all the best in his upcoming chairmanship.

And now, here is my report on last year's activities. I have added web links, so if you do not want to type in all the URLs, you may want to visit the electronic version of this newsletter at CS News (cs.stanford.edu/News/).

Research Activities

Have you ever worked on a group project and found yourself crowding around a single computer, trying to work on a common paper, program, or presentation? Or perhaps you have worked with your colleagues on separate computers, but then faced the frustration of dealing with conflicting updates to the shared documents?

Well, worry no more! The solution, thanks to Professors Armando Fox and Terry Winograd, is TeamSpace, which consists of two or more large flat-panel displays and a server acting as a "group desktop." Thus, you reap the physical benefit of using multiple machines while retaining a single shared system view. Group members working on projects can download and install the TeamSpace software onto their laptops for immediate connectivity to the other laptops and to the workspace. The plan is to deploy TeamSpace across campus in various computer clusters so that our students can start enjoying this new technology. For more information, go to the article in the Stanford Daily.

Professor Dan Boneh is leading a new project on information privacy called PORTIA (Privacy, Obligations, and Rights in Technologies of Information Assessment). As we all know, increasing use of computers in all aspects of daily life has led to a proliferation of sensitive digital data. Concern about the ownership, control, privacy, and accuracy of this data has become a top priority. The PORTIA project aims to study and develop a broad set of tools for managing sensitive digital data. One major technical issue of the project is the ability to mine data while preserving privacy. More generally, the project attempts to resolve the potentially conflicting goals of respecting individual rights while allowing law enforcement and other legitimate organizations to collect and mine massive data sets. Other technical problems include managing sensitive data in P2P networks (e.g., maintaining reputation and privacy in a P2P network); database policy enforcement tools (e.g., distributed access control and controlling derived data); and identity theft and identity privacy (e.g., mechanisms for preventing online identity theft).

This multi-institutional project involves five universities, a number of nonacademic partners, user communities, and D.C.-based policy organizations. The academic partners are Stanford, Yale, Stevens Institute, New York University, and the University of New Mexico. Industry partners include IBM, HP, and Microsoft. User communities include Citigroup, NIH, Yale Center for Medical Informatics, the Census Bureau, and the U.S. Secret Service. The D.C.-based policy organizations are the Center for Democracy and Technology (CDT) and the Electronic Privacy Information Center (EPIC). At Stanford, Professors John Mitchell, Rajeev Motwani, Mendel Rosenblum, and yours truly are involved in the project.

As part of the PORTIA project, some of us have been meeting regularly to discuss data management issues in the context of privacy. We zeroed in on something called the W3C Platform for Privacy Preferences Project (P3P), which has set standards for organizations to declare their privacy policies on their websites. We think this approach to privacy is broken. From an individual's perspective, relying on these policies involves accepting that (a) the organization has clearly stated its policies, (b) the organization will adhere to the policies, and (c) the organization has the means to implement the policies. Recent history chronicles several episodes where trust was willingly - or accidentally - violated by corporations facing bankruptcy, subpoenas, or mergers.

Those of us with a paranoid streak would much rather see a different approach to privacy - one that lets individuals retain control over their information. The claim is that one can design information models and mechanisms that enable individuals to control the use and update of personal information, even after it has been released to an organization. If you think this is all too good to be true, check out the "vision paper" written by Professors Rajeev Motwani, Jennifer Widom, myself, and some of our students. We call this crazy idea P4P: Paranoid Platform for Privacy Preferences.

As you know, Professor Alex Aiken joined our department last year. In the years prior to coming to Stanford, Alex's work focused on alias analysis. An alias analysis answers this question: Can two program expressions refer to the same memory location (i.e., can they alias each other)? It isn't hard to believe that for most applications of sound analysis of software source code that aliasing is an important piece of the picture.�The algorithms and implementation of alias analysis developed in Alex's group will be incorporated into the next release of gcc, the standard C compiler for most Unix and Linux operating systems - a real research milestone!

Alex's most recent projects are in the area of software reliability. The newest effort explores the possible applications when a small amount of randomly sampled information is collected from each execution of a deployed program. This project applies the idea to successful as well as failing runs - for example, it could be used for the dialog box that asks you to send a crash report after your desktop application dies. Instead of examining crash reports by hand, Alex's group is collaborating with machine learning researchers to develop algorithms that exploit the differences between successful and failing runs to automatically isolate the root cause of software errors.

And now, let us return to the continuing saga of Professor Marc Levoy and his Indiana Jones adventures trying to assemble that ancient map of Rome (see last year's newsletter). In March, Marc, his Ph.D. student David Koller, and Professor Jennifer Trimble (Marc's collaborator in the Classics department) traveled to Rome to present a sequence of talks at a conference devoted specifically to "New Discoveries Related to the Forma Urbis Romae." The conference was attended by every leading Italian-speaking Roman archaeologist in the world.

According to all reports, David's talk on "solving the puzzle" was the runaway hit of the day. Earlier talks had focused on one or another fragment of the map; for example, proposing a new placement for the fragment, re-interpreting the meaning of its incised architecture, etc. By contrast, David started his talk by throwing up a slide listing 50 proposed new matches. This drew audible gasps from the audience. He then marched through the list, spending less than a minute on each match. Such things are simply not done in that research community. The murmuring of the audience grew with each match. When he finished, there was loud and sustained applause, so much that David began blushing. Andrew Wallace-Hadrill, director of the British School in Rome was heard exclaiming, "Today changes everything; the study of this map will never be the same!"

Unfortunately, there is no news from David or Marc about the location of that hidden Roman treasure - the one that will solve our department's budget woes! We'll have to wait another year?

Changing subjects: Professors Jennifer Widom and Rajeev Motwani and their students have developed a system called STREAM: The Stanford Stream Data Manager. STREAM resembles a general-purpose database management system (DBMS), except it is built specifically to handle rapid, unbounded, unpredictable streams of incoming data along with traditional stored data sets. STREAM users register continuous queries via a declarative language that extends SQL, and they receive query results in real-time as data streams into the system. Research challenges include resource sharing for large numbers of streams and queries, adaptive processing when data and system conditions change over time, and graceful approximation during transient overloads. Possible applications of STREAM include network monitoring, financial tickers, telecommunications, manufacturing, sensor networks, RFID tags, and others.

For more information about the STREAM project, visit www-db.stanford.edu/stream/. From the project home page you can launch a cool demo over the Internet: A server is started at Stanford and a client also is started on your machine. Give it a try - and please send feedback to Jennifer and Rajeev! Source code for the system should be released to the public by the time you read this.

New Faculty

As I announced last year, Professor Tim Roughgarden will be joining our department this fall. Tim, a Stanford and Cornell graduate, spent last year at Berkeley. In addition to Tim, Scott Klemmer will be joining us this fall as assistant professor. Scott conducts research in Human-Computer Interaction, or HCI. He focuses on the design, implementation, and evaluation of software tools and interaction techniques to seamlessly integrate physical and digital worlds. Scott just received his Ph.D. from Berkeley, where he worked on several interesting projects, including:

The Designer's Outpost, a tool that combines the affordances of paper, large workspaces, and electronic media to support information design for the web; Books with Voices, a tangible user interface that combines paper and electronic feedback; and Papier-M�ch�, a toolkit for tangible user interfaces with technology-independent abstractions.

Promotions and Retirements

Yoav Shoham was promoted to full Professor. Yoav's interests include artificial intelligence, game theory, logic, and electronic commerce.

Jennifer Widom also was promoted to full Professor. Jennifer's area of research is database management systems, and, as noted earlier, one of her current interests is data streams.

Ed McCluskey will be retiring this summer. Ed has had a long and distinguished career that started at Bell Labs and Princeton University. He joined Stanford in 1966 and founded the Computer Systems Lab (originally called the Digital Systems Lab) and our Computer Forum. Ed and his students at the Center for Reliable Computing worked out many key ideas for fault equivalence, probabilistic modeling of logic networks, pseudo-exhaustive testing, and watchdog processors.

Kunle Olukotun will be taking over as director of the Computer Systems Lab (CSL) while Mark Horowitz is on sabbatical this year. As you may know, CSL is a joint CS and EE lab, and the director plays a critical role in ensuring a continued close relationship between EE and CS.

Faculty Awards

MIT's Technology Review has named our very own Professor Serafim Batzoglou as one of the top 100 young researchers in the world. We already knew this, but it is good to see independent confirmation. As if that were not enough, Serafim was selected as a 2004 Alfred P. Sloan Fellow. Sloan awards are intended to enhance the careers of the very best young faculty members across the sciences. A total 116 fellowships are awarded annually.

Another one of those 116 Sloan Fellowships went to Professor Ashish Goel, a faculty member in the Management Science and Engineering department and, by courtesy, in our CS department. Some of you may remember Ashish as a graduate student in CS not that long ago - how time flies!

Professor Terry Winograd has been elected to the CHI Academy. Members of this honorary group are the principal leaders who have led the research in human-computer interaction and shaped the discipline. Terry was inducted at the plenary opening meeting of the CHI conference in Vienna in April.

Professor Daphne Koller has been elected an AAAI Fellow. The six new Fellows were honored at a dinner in July at AAAI-04 in San Jose, California.

Professor John Mitchell received a "Director's Award" from the director of the U.S. Secret Service for his participation in the San Francisco Electronic Crimes Task Force.

The Electronic Frontier Foundation (EFF), an organization that works to protect fundamental rights regardless of technology, has given Professor David Dill its Pioneer Award. The online civil liberties group chose to honor David Dill, Kim Alexander, and Aviel Rubin for spearheading and nurturing the popular movement for integrity and transparency in modern elections. David founded VerifiedVoting.org, an organization and website that educates the public about the problems with relying upon electronic voting machines to record and count our votes without the backup of a voter-verifiable audit trail. It also provides actions voters can take to ensure that their votes are counted in future elections. David served on the California Secretary of State's Ad Hoc Touch Screen Task Force and joined Kim Alexander in successfully advocating for voter-verified paper audit trails.

Professor Alex Aiken received a Phi Beta Kappa Northern California Association 2003 Teaching Excellence Award.

Professor Mark Horowitz was elected as a Fellow of the ACM.

At the XVIII Mathematical Programming Symposium in Copenhagen, the Tucker Prize for an outstanding paper authored by a student was awarded to Tim Roughgarden for his Ph.D. thesis, "Selfish Routing," written at Cornell.

Pat Hanrahan won his SECOND technical Academy Award (given by the Academy of Motion Picture Arts and Sciences). The official citation says:

To Henrik Wann Jensen, Stephen R. Marschner, and Pat Hanrahan for their pioneering research in simulating subsurface scattering of light in translucent materials as presented in their paper "A Practical Model for Subsurface Light Transport."

This mathematical model contributed substantially to the development and implementation of practical techniques for simulating subsurface scattering of light in translucent materials for computer-generated images in motion pictures.

The Stanford section of the Society of Women Engineers selected Professor Armando Fox as its 2004 Teacher of the Year. In addition, Scientific American included Armando's work (jointly with Dave Patterson) on recovery-oriented computing in the "Scientific American 50" list for 2003. You may recall from last year's newsletter that Armando's work on recovery-oriented computing (ROC) was the cover article in the June 2003 issue of Scientific American.

Finally, I am pleased to announce some new endowed chairs/faculty scholars in our department:

Professor Dan Boneh has been named the Cisco Systems Faculty Scholar.

Professor Bill Dally has been named the Willard R. and Inez Kerr Bell Professor.

Professor John Mitchell has been named the Mary and Gordon Cray Family Professor.

Computer Forum News

The Computer Forum is 36 years old and still going strong, providing unparalleled benefits and services to both our academic and industrial colleagues alike.

The Forum is feeling flush with a rash of new members this year. We welcomed nVIDIA, NexTag, U.S. Bancorp, AAA, Citadel Commerce, Siemens TTB, WIS Technologies, and Sumisho Computer Systems to the more established ranks.

The recruiting program appears to be placing our students into industry as fast as we can recycle them back as affiliates. Numerous Stanford alumni in industry returned to speak at JobLunch and participated in the Winter Job Fair last year.

The Visiting Scholar Program currently hosts 15 researchers in the Gates Building from eight affiliate companies. Last year, aside from the usual luncheons and festive gatherings, the visitors "experienced" an Easter party, complete with Egg Hunt and Three Legged Egg & Spoon Races!

As part of our Computer Forum Annual Meeting, we scheduled three days of events, including our Security and Database workshops. Rick Rashid, head of Microsoft Research Worldwide, was our after-dinner speaker. Unfortunately, our official photographer brought his camera to only two of the events, the DB Workshop and one of the Poster Sessions.

The Forum website continues to develop with the Events and Seminar Calendar, Faculty Profiles, and CS/CSL Research Pages. Stay tuned for more updates!

Student Awards and Honors

We honored Penka Markova with the M.S. Student Service Award for the 2002-2003 academic year.�Penka completed her masters in the summer of 2003 and is currently pursuing a graduate degree in Electrical Engineering. Penka volunteered as a freshman and sophomore academic advisor during her two years in the CS department.�If that were not hectic enough, she also took on the yearlong commitment of being the student representative on the M.S. Admissions Committee.�Undaunted by the sheer number of applications that had to be screened, Penka always came to meetings with copious notes after giving each application a cover-to-cover reading.�Penka asked many questions in her sincere effort to understand and fairly review all applications.�Student representatives bring a unique perspective to the admissions process, and Penka's thoroughness and enthusiasm made the admissions process dynamic indeed!�We are grateful to her for participating in department activities and wish her the very best in her new career!

Neil Daswani was our unanimous choice for the Ph.D. Student Service Award. He embraced his student volunteer role with tremendous efficiency; managing the Ph.D. Bible and being a bureaucrat were only two of his many responsibilities.�Immediately after taking on his volunteer assignments, he initiated meetings with department staff to gather input on the expectations of his new role. He put together a much appreciated and useful student panel for the New Student Orientation. In his spare time, Neil was actively engaged in the creation of a new student lounge.� Neil was always a willing and enthusiastic volunteer.�He offered viable suggestions and solicited information from faculty, students, and staff with sincerity and diplomacy.�He gave feedback after completing a task and was a valuable liaison for students.�Neil was an organizer par excellence!�We deeply appreciate his enthusiasm and commitment.� Thank you, Neil!

Uri Lerner received the Arthur Samuel Thesis Award for 2003 for his paper on Hybrid Bayesian Networks for Reasoning about Complex Systems.

I am happy to report that a paper written by our Ph.D. students/recent graduates has been selected as a "Grand Finalist" in the ACM Student Research Competition. For this competition, each ACM Special Interest Group selects the best student paper. Among those winners, three are selected as "Grand Finalists" and invited to the Turing Award banquet. We won't know which of the three is selected as the top winner until the awards are given out. But being among the three finalists is already a great honor!

The paper was written by former students T. J. Giuli, Petros Maniatis, Mema Roussopoulos, and Yanto Muliadi (Statistics) with a bit of help :-) from co-authors Professors Mary Baker and David Rosenthal. The paper describes the LOCKSS system for document preservation. (It originally appeared in the SIGOPS conference.)

Other News

Our students competed in the World Finals of the ACM Programming Contest. Let me quote from an email I received from the team coach, Jerry Cain:

I'm here in Prague, Czech Republic, after an exhilarating three days of fun and competition. Last November, Tom Do, Andy Lutomirski, and Gary Huang competed in the regional ACM contest and placed high enough to advance to the World Finals. Those World Finals were held this morning here in Prague.

I'm delighted to report that the Stanford boys did us proud. Each of the 73 teams had five hours to solve 10 problems. Stanford submitted working solutions to five of them and ended up in 13th place. The guys were a little disappointed, because medals were given to the top 12 teams. But I should point out that Stanford solved as many problems as the team who placed sixth! (Fourteen teams submitted correct solutions to five or more problems, but Stanford used more time per problem than most of them. That's why they were 13th instead of sixth.)

In any event, we should be very proud to have such talented and motivated students. On any other day, Stanford could have placed in the top five; in fact, they ranked well above the one team that beat them at the regional competition this past November. And they were within minutes of submitting a solution to a sixth problem - had they done that they could very well have placed second.

I am impressed with the quality of our undergraduates, and it's at times like this that I'm reminded how very proud and honored I am to be teaching at a place like Stanford.

Speaking of programming, over the past year, Nick Parlante took on the job of transforming our introductory programming course (CS106A - Programming Methodology) from a procedural approach (in C) to an object-oriented one (in Java). This was a big job that included restructuring the course to teach problem solving and decomposition using objects. We offered the first version of the course during winter quarter 2003-04, and it was an unqualified success with the students.

CS106B (Programming Abstractions), the class after CS106A, is also in a transition period. Julie Zelenski's task is to take the first group of "CS106A-in-Java" students into C++ in this "new" course. CS107 (Programming Paradigms) and other downstream courses also will require changes this year given the new approach in the CS106 sequence. The improvements in the lower division programming courses are part of a comprehensive plan to review and update the curriculum.

It is interesting to note that the number of undergraduates in our classes has decreased a bit after the tech bubble burst. The number of students declaring CS as a major has decreased to 366 this past year, down from 421 in FY03 and 472 in FY02. The number of students graduating also decreased to 130, down from 158 in FY03 and 168 in FY02. However, I think things have stabilized, and we are roughly back to our historical numbers. For example, in FY01, we had 116 graduates, which is still less than the number who graduated this past year.

As you know, Professor Sebastian Thrun joined Stanford in the summer of 2003 after being on the faculty of Carnegie Mellon University for a number of years. While at CMU, he masterminded Minerva, a robot that is now installed in a Smithsonian museum as a robotic tour-guide (1998), and Groundhog, a robot that autonomously maps abandoned mines (2002). Sebastian is probably best known for his pioneering work in the field of probabilistic robotics. (Probabilistic robotics applies techniques from statistics and operation research, such as Bayesian estimation and decision theory, to the field of robotics.)

Here at Stanford, Sebastian will be starting a team for the DARPA (Defense Advanced Research Projects Agency) Grand Challenge. This event is organized by the research arm of the Department of Defense. It involves driving a ground vehicle autonomously from L.A. to Las Vegas. The event took place for the first time in 2004 (sadly enough, without a Stanford team entered); the winning team's vehicle drove 7.4 miles out of 150 before the vehicle became high-centered and a tire burst into flames. The next event will occur in the fall of 2005, and I am sure the Stanford team will do great! Sebastian is busy raising funds and equipment for the event - so if you have a spare SUV, please contact Sebastian. (He promises not to put too many dents in it.)

From my previous newsletters, you may gather that some of our faculty like to travel quite a bit. Alex Aiken and Jennifer Widom, in particular, have recently become particularly fond of renting sailboats for extended periods of time in remote parts of the world. And I do mean remote - take a look at the Aiken/Widom Travel Page. Despite their novice efforts, they have yet to sink any of their boats. Or so they claim.

Once again, I went bowling with some of our undergrads (see photos here). Don't ask how poorly I did.

SAIL is back!! Those old-timers among you certainly remember the old SAIL: The Stanford Artificial Intelligence Laboratory. Well, this year our Robotics Lab expanded its scope to include all of AI, becoming SAIL once again. Sebastian Thrun is the director of the new lab, which is now home to everyone in the department pursuing research in AI. I took photos at the grand re-opening (www-db.stanford.edu/~hector/photos/2004/AILab/album.htm). The lab has a new home page that you are invited to visit.

In November we held the First IBM-Stanford Day. We hosted 80 participants from IBM and Stanford, including Alfred Spector, Vice President of Services and Software at IBM Research, and Robert Morris, Director of the Almaden Research Center and Vice President, Personal Systems and Storage. You can see some photos here.

The first annual CS T-shirt became a reality this year, starting with a design contest in the winter. Five designs were submitted, and 285 students voted to choose a winner. Over 250 shirts have been sold, and a limited number of extras are going fast! See http://www.stanford.edu/~zozo/tshirt for more details.

Every December, we hold a decorations contest; every floor in Gates Hall decorates its main lobby area. You can see the 2003 decorations here. Be sure to admire the "cool dude" in the "Neo" sunglasses in this photo (part of the Christmas tree decorations on the second floor). The third floor won this year, thanks to an interactive video display that used a video camera to capture one's face in real-time and automatically add a Santa hat.

Our official photographer made three other important events this year:

The CS/CSL New Academic Year Party. The Summer 2003 CURIS Poster Session. As you may know, CURIS is a summer research internship program for our undergraduates, and at the end of it they present posters with their research results. I am always impressed by how much the students are able to accomplish in one short summer. The Faculty Retreat. The faculty retreat was held at a local hotel (to save time and money!). Take a look at the photos and see how many of your old professors you recognize. Of course, not all of us are getting old, and those of us who are, it is only physically; we still feel young as ever!

That's it for last year. Have a wonderful 2004-05!

Regards,

Hector Garcia-Molina
Leonard Bosack and Sandra K. Lerner Professor
Chair, Department of Computer Science

P.S. Please send alumni news to alumninews@cs.stanford.edu so Bill can include the information in next year's newsletter.