1998

Computer Science Newsletter

Jean-Claude Latombe

September 1998

Dear Alumni and Friends:

As this hot summer comes to an end, it is my pleasure to write to you. I hope these last few months have been both as restful and productive for you as they have been for me here at Stanford. During this past year many important things have happened in the Computer Science Department. I am happy to say that the Department can review its accomplishments from the 1997-98 year with pride. We now look forward to an exciting 1998-99 academic year with a new crop of brilliant students, and a number of impressive new faculty.

New Faculty

As I mentioned in my newsletter last year, Bill Dally and Dan Boneh joined us in Fall '97 as new faculty members. While Bill conducts research in the architecture and implementation of high-performance computer systems, Dan's main interest is cryptography and computer security. Dan is currently leading a project on Intrusion Tolerance that provides new solutions for coping with computer intruders and another project on electronic commerce using Digital Assistants such as the PalmPilot.

During the past academic year we conducted several faculty searches which have resulted in four appointments for 1998-99:

Christoph Bregler will join Stanford as an assistant professor in January 1999. Chris obtained his Ph.D. from U.C. Berkeley in 1998. He does research in machine perception of human movements (locomotion, lip motions, hand gestures), and its connections to vision, speech, graphics, and multimedia. Chris will play a major role in our Department to connect existing research groups in vision, graphics, HCI, robotics, and artificial intelligence.

Dawson Engler will join us as an assistant professor in January 1999. He will have a joint appointment with the Electrical Engineering Department. He will finish his Ph.D. at MIT in Fall '98. His research focuses on three areas: operation systems, dynamic code generation, and incorporation of application semantics and control into application.

Armando Fox will arrive in January 1999 as an assistant professor. He obtained his Ph.D. from U.C.Berkeley in 1998. His current projects provide system infrastructure for distributed Internet service applications. In particular, he is the developer of TACC, a framework and programming model for Internet applications that run on a heterogeneous range of client devices from smart phones and PDA to desktop workstations.

Balaji Prabhakar is joining us in September 1998 as an assistant professor in both the Electrical Engineering and Computer Science Departments. After receiving his Ph.D. from Stanford in 1994, he became a Postdoctoral Fellow at Hewlett-Packard Labs in Bristol (UK) and then a Research Scientist in the Laboratory for Information and Decision Systems at MIT. His research interests are in the field of computer networks, and he will reinforce Stanford's leadership in this field.

A New Director for the Computer Systems Laboratory

After three years of outstanding service to both the CS and EE Departments, Hector Garcia-Molina has passed the baton to Mark Horowitz, who is the new director of the Computer Systems Laboratory. Established in 1968, CSL is a research and teaching laboratory operating under the auspices of the CS and EE Departments. Research in CSL spans all areas of computer systems, including integrated circuit design, networking, graphics, databases, and computer architecture. Over 300 faculty, staff and students contribute to the teaching and research efforts of CSL.

Hector provided extraordinary leadership during a period of considerable change for both Departments. We are extremely pleased that Mark has agreed to succeed him as the CSL director.

Faculty Chair

David Filo and Jerry Yang, two former Ph.D. students in the Electrical Engineering Department, who are better known as the founders of Yahoo!, have made a gift to Stanford to endow a chair in the School of Engineering. Mark Horowitz is the first recipient of this chair, named the Yahoo! Founders chair.

Honors

Ed McCluskey was elected to the National Academy of Engineering, for logic design, computer engineering, and engineering education.

Jeff Ullman won the '97 ACM Karl V. Karlstrom Outstanding Educator Award. This award recognizes an outstanding educator for advancements in teaching methods and for effective new curriculum in Computer Science and Engineering. Jeff is honored for "his profound and lasting impact on Computer Science education through the books he has written, and the doctoral students he has supervised."

At the '97-98 Commencement ceremonies Eric Roberts received the Lloyd W. Dinkelspiel Award in recognition of distinctive contributions to undergraduate education.

Yoav Shoham was elected a Fellow of the American Association for Artificial Intelligence "in recognition of fundamental contributions concerning logics of time, knowledge and belief that have resulted in significant advances in reasoning about time and change."

Andrew Stuart was awarded the Dahlquist Prize by SIAM. This prize, named after the Swedish scientist Germund Dahlquist, recognizes outstanding work in the field of numerical analysis.

Russ Altman has been chosen to receive a Presidential Early Career Award for Scientists and Engineers. This is the highest honor bestowed by the United States government on outstanding scientists and engineers at the outset of their independent research careers.

Dan Boneh, Daphne Koller, Dawson Engler, and Balaji Prabhakar have been named Terman Fellows by the Dean of the School of Engineering.

Wireless Network Extension

The CSD Computer Facilities Group, led by Tom Dienstbier, has been active over the summer installing an experimental wireless network manufactured by Lucent Technologies. This new network consists of 14 access points located throughout the Gates Building. It provides coverage on all floors including the basement. These access points are bridge style devices that attach to a special Gates Building Ethernet subnet on one side and 2.4GHz wireless on the other. Bandwidth through each bridge is 2MB shared. In connection with the new network, the Department will provide 20 Dell laptops with wireless modems to the first-year CS Ph.D. students coming in September 1998.

Installing this wireless network is aimed at developing an infrastructure that will facilitate interaction and cooperation among the residents of the Gates Building. We plan to expand this effort during the coming years by increasing the speed of the wireless network and by equipping some conference rooms with mural graphic panels being developed in the Graphics Laboratory by Pat Hanrahan and Terry Winograd.

This wireless network also provides a testbed for Mary Baker's research group. This group is deploying SPINACH (the Secure Public INternet ACcess Handler) on both the wireless and wired networks in Gates (GatesNet). SPINACH provides access control for public network ports and for GatesNet to faculty, staff, students and authorized guests. It is easy to use, requires no special software and it takes only about 30 seconds to get online. For more details, see http://spinach.stanford.edu. Mary and her students will be looking at performance and access patterns over time to tune SPINACH and determine its effectiveness as an access control architecture. They also plan to examine packet traces on GatesNet to explore mobility patterns and compare these patterns with those gathered over a metropolitan-area wireless network.

The Digital Michelangelo Project

Recent improvements in laser rangefinder technology, together with algorithms developed at Stanford for combining multiple range and color images, make it possible to reliably and accurately digitize the external shape and surface characteristics of many physical objects. As an application of this technology, Marc Levoy and his group have embarked on a project to create an authoritative 3D computer archive of the sculptures of Michelangelo. Working with Italian museums and institutions, they will begin by constructing models of his major statues in Florence and Rome. The goals of this project are primarily scholarly and educational. The project's sponsors are Interval Research Corporation and the Paul W. Allen Foundation.

Marc Levoy and his group (including graduate and undergraduate students) will spend the 1998-99 academic year in Italy. To house them, two temporary computer graphics laboratories will be built, one in Florence, adjacent to the Stanford Overseas Studies Center, and the second in the Vatican Museum in Rome. If time permits, Marc will also apply 3D scanning techniques to problems in archeology and art preservation. One prospective application is the Forma Urbis Romae, a giant map of ancient Rome carved onto marble slabs in circa 200 A.D. The map lies in fragments (over 1,000 of them. Piecing this map together has been one of the great unsolved problems of archeology. Suppose one scanned these fragments; could a computer program be written that could "solve the jigsaw puzzle?" Marc hopes to do just that.

Visiting Committee

The Department was visited in November by a distinguished external committee charged by our Dean, John Hennessy, to review the quality of our graduate programs. This year, the committee was chaired by David Liddle (Interval). Other members were Ruzena Bajcsy (University of Pennsylvania), Forest Baskett (Silicon Graphics), Bill Coughran (Lucent), Bob Kahn (Corporation for National Research Initiatives), Randy Katz (U.C. Berkeley), Tom Mitchell (CMU), and Moshe Vardi (Rice University). This visit resulted in very constructive discussions about future research directions for the Department and its educational programs. The committee issued a very positive report, with numerous helpful comments, especially on our teaching activities.

Student News

For the second time in the past three years, a CS undergrad won the Ford Scholar Award, the highest award given to undergrads by the School of Engineering. Brian Babcock was the 1997-98 recipient.

Eight CS students, Brian Babcock, Benjamin Taskar, Beverly Yang, David Y.W. Park,
Sean Jeffrey Treichler, James Pei-Ping Yao, Yi-Ling Su, and Salim Shabbir Yusufali, were selected as this year's recipients of the Frederick E. Terman Award for Scholastic Achievement in Engineering. The Terman Awards are the most selective academic awards for undergraduate students in the School of Engineering. They are presented to the top 5% of each year's seniors. The large number of awards to CS students (eight out of the 16 Terman awards given out) tells a lot about the excellence of our students.

Brian Curless and Saman Amarasinghe received the Samuel Thesis Awards for the Ph.D. theses they completed in 1997-98. This departmental award is presented annually to two graduating Ph.D. students. A committee selects from among the theses nominated by the CS faculty. In 1997-98, the committee consisted of Ed McCluskey, Victor Pereyra, Prabhakar Raghavan (chair), and Stan Rosenschein.

Freshman Seminars

Last academic year was the first year for the Stanford Freshman Seminars project initiated by President Casper and aimed at increasing faculty participation in undergraduate education. CS faculty members gave five Freshman Seminars:

� Downside of Computing Systems (Baker)

� Paradox: Bug or Feature? (Pratt)

� Programming and Problem Solving (Ullman)

� Science of Art (Levoy)

� Traveling the Information Highways (Wiederhold)

These courses, which present advanced topics in computer science to freshman students, have been extremely well received by the students, and the faculty members who taught them also enjoyed their time interacting with enthusiastic students. This is what Vaughn Pratt said:

"With 76 applicants for my freshman seminar "Paradox: Bug or Feature" and a university-mandated enrollment limit of 16, it was painful to decide whom to admit. The students were considerably more enthusiastic than I am accustomed to, which I attribute to the interactive format of the course facilitated by the small class size, its elective status, and the initial strong enthusiasm of the students for the topic expressed in the statement of purpose in their application.

Nominally the subject matter for the course was logic, which tends to be as technical as calculus or linear algebra, but the emphasis on the relatively accessible topic of paradoxes permitted a more interactive style of teaching, consistent with the general goal of the freshman seminars. The students placed great value on being able to participate actively in the lectures, contributing a steady barrage of questions and suggested solutions to problems raised in class, which kept almost all of them wide awake and alert.

My biggest regret was that I could not accommodate twice as many students in this format, which of course would have defeated the purpose of the freshman seminars."

The following Stanford Introductory Seminars will be given in 1998-99:

� Computers: Fact and Fiction (Koller)

� Great Ideas in Computer Science (Motwani, Raghavan)

� The Two Cultures: Bridging the Gap (Roberts, Saldivar)

� Downside of Computing Systems (Baker)

� Programming and Problem Solving (Ullman)

� Computer Security and Privacy in the Electronic Age (Mitchell)

� Digital Actors (Latombe)

The CS Major and Masters� Programs

Student enrollments in CS continue to climb at Stanford. In 1997-98, both enrollments and units increased by a little over 10%. Some courses have seen remarkable increases in the number of students, suggesting that the size of the major is likely to increase dramatically in the next few years. We currently have 325 declared majors, an increase of 17% over last year's 278.

A committee led by John Mitchell has reviewed the curriculum of the CS major to take into account the rapid growth of the field and the critical changes that this growth has brought. Requiring students to take courses in every topic area that we identify as important is no longer feasible, and will become less so as future developments expand computer science into more areas. The committee has designed a more flexible curriculum that we will start implementing this year.

To encourage more of our students to go for Ph.D. studies (at Stanford or elsewhere), we have set up an Honors program in our CS major; in particular, each student accepted into this program will have to complete at least nine units of research under the direction of a faculty member. We are also starting an MS program with "distinction in research."

Staff News

Andy Kacsmar, Kathy Sumner, and Eddie Wallace received our Staff Outstanding Achievement Awards.

Andy Kacsmar manages computer facilities for the Stanford Database Group, which includes over 100 computers. He has a habit of working all night just to make sure demos run smoothly, and his group can't live without him.

Kathy Sumner is responsible for the day-to-day building management of the 150,000 square foot Gates Building. She is notorious for her good humor and cheerful disposition. She works out every day at lunch so she can do the work of three strong men.

Eddie Wallace joined the Educational Affairs division in late 1996 supporting Eric Roberts, Claire Stager, and the CSD lecture staff. In addition to running the office efficiently, he has the quickest wit in the Department. In his spare time, Eddie is an accomplished actor whose favorite roles include the Stage Manager in "Our Town," the Gentleman Caller in "Glass Menagerie," and Frank Sweeney in "Molly Sweeney."

Computer Forum

The Computer Forum has completed a prosperous and exciting year under the expert direction of Oussama Khatib. Membership now stands at 79 companies, a near-record high.

In March, the Computer Forum celebrated its 30th anniversary with an annual meeting program which included participants from both academia and industry in a new one-track format. Edwin Catmull of PIXAR capped the successful new format with a keynote lecture on the history of computers and animation, and the presentation of his company's Academy Award winning short film, Geri's Game.

In June, the first Forum World Symposium took place at the Tepia Conference Center in Tokyo, Japan. More than a dozen Stanford faculty and researchers, as well as over 120 guests, collaborated in the lively and informative sessions. John McCarthy delivered the keynote address "Computer Science (Past and Future," and a live videoconference between Tepia and the Stanford Robotics Lab highlighted the program. The Forum will extend the success of the first Symposium into a series: a second World Symposium, probably to be held in Europe, is in the works for 1999; and regional symposia are planned for the United States as well.

Computer Museum

On November 5th we opened the Computer History Exhibits in the Gates Building. Displays are on each floor, each covering a specific topic. On the first floor are items specific to the history of the Department. Penny Nii and Voy Wiederhold retrieved, enlarged, and mounted photographs of the original Department members, some in interesting settings, such as John Herriott in front of the original Card-Programmed-Calculator, then in Encina Hall, and John McCarthy playing computer chess with Russian colleagues on the IBM 7090 in Pine Hall. Calculators used by George Forsythe and Bob Floyd are shown as well. One case is devoted to the AI lab in the D.C. Powers building, and a 4' diameter platter (4 Mbytes per side) from its Librascope disk drive is the centerpiece.

On floors 2, 3, and 4 are cases displaying items from the 1950s, 60s, and 70s, many on loan from The Computer Museum in Boston. A Williams-tube memory (256 bits) from SWAC (Standard Western Automatic Computer) is on display, the first (unless disproven) and hence the fastest computer in the West in 1951. The oldest device is a Swiss mechanical integrator (1916) donated by Dr. Harry S. Newcomer many years ago. We know nothing about the donor, and would appreciate any hints. On the 5th floor is the first commercial computer game, the Galaxy, enjoyed in Tresidder in 1971 and 1972, and now lovingly restored by Bill Pitts and Ted Panofsky. Driving two displays for four players in 16k bytes would be a sadistic assignment for our students today. The basement floor contains an Apollo computing module, and is slated to be expanded to show development timelines.

We will continue to update the displays. We have, for instance, copies of the first qualifying exams given to our students. We are placing some images of the items on our Web pages, accessible from the Department page (or http://www-db.stanford.edu/pub/voy/museum.html). There is also a listing of all faculty, and, gradually, their student trees, so that visitors will be able to track all descendants of the Stanford CSD department.

We would appreciate additional information and items of historical value, especially those related to Stanford and its effects on Silicon Valley. A CROMEMCO machine (named after Crothers Memorial Hall), for instance, would fill a hole in the displays. Do come and look at the displays when you are at Stanford, and if you have suggestions, send a note to gio@cs.stanford.edu.

Special Note to Users of Xenon

The Department maintains accounts for our alumni on the computer system called Xenon. However, we have had numerous break-ins on this system. To help prevent re-occurring break-ins, some security precautions are now in effect. As of September 1, 1998, connections to Xenon can be made only using these secured access methods: SSH, SRP, and Kerberos. These methods are explained in more detail on Xenon's Web page under the heading of Security Alert. Xenon's Web page is http://xenon.stanford.edu. In addition, we encourage all alumni to read Xenon's usage policy at http://xenon.stanford.edu/policy.html

.  

And a few words on my recent mountaineering trip

In July '98, I went on a climbing trip to Kirgizstan, in the Tien-Shan range. Kirgizstan, a relatively small but very friendly country, is located south of Kazakstan and west of China. The Tien Shan (Celestial Mountains) is one of the great mountain ranges of the world, 2000km long and 400km wide, with 7300km glaciated area. After acclimating on smaller peaks, our team of three spent 14 days trying to climb Khan Tengri (6995m, previously measured at 7010m), a stunning and almost perfect pyramid of white marble that dominates the 65km-long Engilchek Glacier (see http://www.sft.fact400.ru/kopylov/khan.htm and http://www.premier1.net/jdockery/USSR.III.html). Unfortunately, we had good weather during only two of the 14 days on the mountain. We spent four days and four nights at a saddle at 6000m waiting for sufficiently good weather to make it safely to the summit, but we did not have this chance. Defeated by the bad weather, we climbed down on July 22 early in the morning when the snow that had accumulated during the previous days was the most stable. A few hours later, an avalanche swept out our route; by then, we had safely reached base camp.

Nevertheless, I am very glad to be back.

Sincerely,

Jean-Claude Latombe