2002

September 2002

Dear Alumni and Friends:

I have survived for a second year as department chair, with no revolts or mutinies, so it is time for my second newsletter.

Overall, I think it has been a good year for the department! In this post-bubble world, everybody seems more focused on learning, teaching and research. The number of undergraduates taking our courses has dropped a bit, which is a good thing since we were overloaded. However, we have not seen a change in the number of CS majors. This seems to suggest that the undergrads that have abandoned us are from other departments, and perhaps they were not interested in computer science but rather in becoming quick millionaires. And now that that fantasy is gone, well, they have gone elsewhere...

At the graduate level, we have seen a huge increase in the number of applicants. For the PhD program, we saw a 48% increase in applicants, while for the MS program, the increase was 24%. Clearly, people out there are seeing the value of a graduate education! We did not increase the number of accepted students, so this means that our graduate program became much more competitive. For example, we received 876 applications for the PhD program, and only admitted 63, which means that only 1 in 14 applicants was admitted. Of the 63 admitted, 42 accepted our offer, for a yield of 67%. (The ones who turned us down were obviously not as smart as we thought :-)

 

Research Activities

This past year, our engineering school conducted an alumni survey (thanks to those of you who participated). One of the findings was that our alums did like receiving this newsletter (maybe they had not seen my first newsletter, with its questionable humor). Our alums also said they would like to see seeing more research material in the newsletter. Thus, due to popular demand, I have added this section to the newsletter, reporting on some of our research activities. What follows is just a small sample. For more information about our department's research activities, be sure to visit http://cs.stanford.edu/Research/, which lists our various research groups and provides many interesting links to research projects. Many of our faculty work at the boundary between computing and the humanities. One of the more unusual projects along these lines is Professor Marc Levoy's Digital Michelangelo Project, a 5-year project to create a three-dimensional digital archive of the statues of Michelangelo. Creating a 2-billion polygon model from laser range data acquired under field conditions is hard. Making that model accurate enough for art historians to use in their own research is much harder. Completing the archive will require advances in scanner calibration, scan alignment, surface reconstruction, hole filling, and inverse rendering. Another project at the juncture of technology and the humanities is Levoy's recent digitization of the 1,186 fragments of the Forma Urbis Romae, a giant marble map of ancient Rome. With guidance from Prof.essor Jennifer Trimble in the Classics department, Marc and his students are creating a geometric, photographic, and textual database of the map, and with help from Professor. Leo Guibas in our department and his students, they're trying to solve the jigsaw puzzle. Yet aAnother project with an archaeological flavor is the Cuneiform Tablet Visualization Project in which Marc and his students are scanning, unwrapping, and non-photorealistically shading the tablets' curved inscribed surfaces. Additional information on these three projects can be found at:

http://graphics.stanford.edu/projects/mich
http://graphics.stanford.edu/projects/forma-urbis
http://graphics.stanford.edu/projects/cuneiform

Another area where there is a lot of activity in the department is peer-to-peer (P2P) systems. The goal of P2P systems is to exploit the resources (files, cycles, bandwidth) at the "edge" of the network, e.g., in people's offices and homes. Examples of P2P systems include Gnutella, Morpheus, and SETIeti-at-Home. The challenges include locating resources in a decentralized fashion (e.g., searching for a file containing a particular song), resource allocation (e.g., what files or file-fragments do you keep on your machine), payment mechanisms, privacy, and protection from malicious attacks. Faculty working on these problems include Professors. Motwani, Boneh, Baker, Mitchell, Shoham, and myself. One place to find additional information is at http://www-db.stanford.edu/peers/ (or better yet, just search for "Stanford Peers" on Google: it is the first link).

Last year I mentioned Professor. Ron Fedkiw's work in the movies "Mummy Returns" and "Jurassic Park III". Well, this year, Ron continues to have fun. He's gone from smoke to mud and cloth! Ron worked on special effects (with Industrial Light + Magic) for Shrek's mud bath and Yoda's robes. If you do not know who Shrek and Yoda are, you have not been watching movies recently. If you want to find out who Shrek and Yoda are, do a Google search ("Google them" as people say these days). If you are interested in how to render mud and robes, you can visit Ron's home page at http://www.cs.stanford.edu/~fedkiw/ (just Google Fedkiw) where he has links to the following two papers (among many others):

  • Foster, N. and Fedkiw, R., "Practical Animation of Liquids", SIGGRAPH 2001, 15-22 (2001). Describes how Shrek's mud was done.
  • Bridson, R., Fedkiw, R. and Anderson, J., "Robust Treatment of Collisions, Contact and Friction for Cloth Animation", SIGGRAPH 2002, ACM Trans. on Graphics 21, 594-603 (2002). Describes how Yoda's robes were done.

How come I never get to write a paper with pictures of Shrek or Yoda? Sigh...

New Faculty

A year ago Eric Roberts became our Senior Associate Dean for Education and Student Affairs at our School of Engineering. This past year he held that post, while continuing to be our department's Associate Chair for Education. (Two jobs, one salary!) But now we have a new Associate Chair, Russ Shackelford, who will be joining us this Fall. Russ was previously Director of Undergraduate Studies at Georgia Tech, where he developed an innovative CS undergraduate program on a massive scale (over 2000 students!). He is also very active and visible in the CS teaching community, through his work with the ACM Education Board and the Computing Curricula 2001 task force where he serves as co-chair with Eric Roberts.

Christos Kozyrakis will also start this Fall as a joint EE/CS assistant professor. Christos did his Ph.D. work at Berkeley, where he worked in the Intelligent RAM (IRAM) project. The project seeks to understand the entire spectrum of issues involved in designing general-purpose computer systems that integrate a processor and DRAM into a single chip. Christos was the lead student on the project and was involved with the design of its vector unit.

A couple of years ago, our colleagues in the Radiology Department, in the School of Medicine, came to us with a proposal for a joint faculty position. It turns out that radiologists have more and more sophisticated instruments (e.g., CAT scaners) that generate huge volumes of information. It has become critical to have computers that can assist the radiologist in sifting through all the information, and identifying "interesting" data (e.g., tumors). I am happy to report that our joint search was a big success, and that Michael Leventon will join us in January with a joint CS/Radiology appointment. Michael, an MIT graduate, has done seminal work in the field of computer vision applied to medical image understanding and computer-aided surgery. For example, Michael has developed a novel approach to segmentation that captures the shape and the common shape variations of anatomical structures. Michael is our second joint appointment with the School of Medicine. (Ken Salisbury is the other.). We expect more such appointments in the future, especially once the new BioeEngineering department gets underway in the near future.

Another Berkeley graduate, Andrew Ng, will be joining us this Fall as a new assistant professor. Andrew has done an impressive amount of work in many areas, including model selection, reinforcement learning, clustering, information retrieval, feature selection, and statistical learning. During his interview talk, Andrew impressed us all by showing a video of a small helicopter he had "taught" to fly. The helicopter is only given some "rules" for actions and rewards (staying steady is a reward). Using the rules, the helicopter "learns" what actions are best for it. Sounds like magic to me, but indeed, there was the helicopter flying in nice smooth circles.

Last but not least, Mihalis Yannakakis will be joining our department this Fall as a Full Professor. Mihalis is a Princeton graduate (Jeff Ullman was his advisor back when Jeff was at Princeton) and worked at Bell Labs and Avaya Labs (a Bell Labs spinoff). Mihalis has done a huge amount of very influential research, in areas such as program verification, database systems, automata theory, and compilers. He is considered by many one of the very top theoreticians in the world, and we are very pleased that he is joining us!

Promotions

Rajeev Motwani was promoted Full Professor.

Nick McKeown was promoted to Associate Professor with tenure.

Balaji Prabhakar was reappointed to Assistant Professor.

Retirements

Last year we saw the retirement of Ed Feigenbaum, one of the original professors of the newly created Stanford Computer Science Department that was created in 1965. Ed has been is a member of elected to the National Academy of Engineering, and the American Academy of Arts and Sciences, and is a Fellow of the American Association for Artificial Intelligence and the American Institute of Medical and Biological Engineering. He was a recipient of the 1994 ACM Turing Award. He was named Kumagai Professor of Computer Science at Stanford University in 1995. He received the U.S. Air Force Exceptional Civilian Service Award in 1997 where (he served as Chief Scientist of the United States Air Force from 1994 to 1997). Ed also served as Chairman of Computer Science from 1977 to 1980.

Bob Floyd and Bob Frezza In Memorandum

I do have some sad news to report in this newsletter.

Professor. Emeritus Robert W. Floyd died at Stanford University Medical Center on September. 25th after a long illness. He was 65. His research included design and analysis of algorithms for finding the shortest paths in a network, parsing (decomposing) programming languages, calculating quantiles, printing shades of gray on a dot printer, sorting information, and selecting random permutations and combinations. His most important scientific achievement, however, was pioneering systematic methods of program verification. His seminal 1967 paper, "Assigning Meanings to Programs," opened the field of program verification. Bob was CS Chairman from 1973 to 1975. He won the Turing Award in 1978. In 1991, he was awarded the IEEE Computer Pioneer Award for his work on early compilers.

One of our undergraduates, Bob Frezza, passed away in December, of diabetes complications. He is remembered fondly by all of us, especially his advisor, Professor. Dan Boneh, who said some very nice words at our commencement ceremony in June. Bob had accumulated enough credits so we could issue him a posthumous BS degree at the ceremony. Bob had worked last summer at Pay Pal, and his mentor at Pay Pal, Max Levchin, attended the graduation ceremony to receive Bob's degree. If you knew Bob, you may want to visit www.bobfrezza.org for some memoirs and photos. His parents and friends are establishing the Robert Mammano Frezza Memorial Scholarship Fund in his honor.

2002 Events

The Knuthfest, a workshop honoring Don Knuth's 64th birthday was held in January. Attending the event were Don's colleagues from Stanford and elsewhere, former students, and Computer Forum members, - in all, about 100 people.

A conference in celebration of Gene Golub's 70th birthday (and the 50th anniversary of Conjugate Gradient Method) was held in Zurich in February.

Our Forsythe Lectures were given by Thomas G. Dietterich, a Stanford graduate who now teaches at Oregon State University. Tom gave two talks, "Machine Learning: Making Computer Science Scientific" and "Action Abstraction in Reinforcement Learning."

Computer Forum News

The Computer Forum continues with its mission to bring industry, faculty, and students together at events and programs throughout the year.

The Sixth Annual Stanford Computer Forum Job Fair was held in January in a circus- sized tent between the Gates Computer Science Building and the David Packard Electrical Engineering Building. where aAffiliate companies and Computer Science and Electrical Engineering students interested in internships, and employment opportunities, seized upon the opportunity to get to know each other. While industry may be in a state of transition, attendance at the Annual Job Fair proved that recruiting computer science and systems students is still going strong. This year's fall and winter recruiting schedules are filling up.

Affiliates Week, held on campus in March, was five days of meetings and workshops, headlined by the 34th Annual Affiliates Meeting. The Annual Meeting provided a snapshot of the research being done in the CS Department and CSL. Our keynote speaker was Don Knuth, who reviewed the work and contributions of Bob Floyd. The dinner speaker was one of our alumsalum , Larry Page, who talked about some of the interesting things going on at Google, and his vision for the future. In additional, three specialized one-day workshops focused on specific topics: computer vision, databases, and computer security.

 

Honors/Awards

Faculty

  • Zohar Manna received a "doctor honoris causa" from the EL��cole Normale Sup�erieure de Cachan, in France.
  • Jean Claude Latombe has been appointed as Kumagai Professor (an endowed chair).
  • Eric Roberts was named a University Fellow in Undergraduate Education.
  • Bill Dally was just elected a Fellow of the IEEE.
  • Oussama Khatib has been appointed President of the International Federation of Robotics Research (IFRR) This is a prestigious appointment. ISRR is the premier symposium for high-quality research in robotics.
  • Armando Fox received the IBM Faculty Award and NSF CAREER award, both for research on Recovery Oriented Computing techniques.
  • Ron Fedkiw received a Presidential Early Career Award for Scientists and Engineers (PECASE). The award ceremony began with a tour of the White House followed by a short speech by President Bush.
  • Nanni DeMicheli is receiving the IEEE E. Priore Technical Field Award.
  • Gene Golub received an honorary degree from Rostov State University in April. And he will receive his tenth honorary degree (!) from Baptist University of Hong Kong.
  • Daphne Koller received the Computers Thought award in August 2001. The Computers and Thought Award is presented biennially by the International Joint Conferences on Artificial Intelligence (IJCAI) to an outstanding young scientist in the field. Daphne was cited for her path-breaking work on reasoning with uncertain information. The award involves a presentation at the IJCAI conference by the recipient. Daphne gave what was reported to me as one of the all-time best presentations.
  • Balaji Prabhakar received the Rollo Davidson Prize, in April 2002. The Rollo Davidson Prize is awarded by the University of Cambridge, UK, to young scientists of outstanding promise and achievements for work in probability, statistics, and related areas. The prize was awarded to Balaji in recognition of his achievements in stochastic network theory applied to communication networks.
  • Yours truly has been elected to the American Academy of Arts and Sciences.

Students

This academic year has been a good one for our student programmers. First, in November 2001, our CS junior Jon McAllister won a $100,000 prize in the TopCoder Invitational Computer Programming Tournament winning a $100,000 prize! And fellow Stanford CS junior Daniel Wright was close behind in second place! (I think he received a $25K prize.) I am told that "Scoring in TopCoder competitions is based on two factors: intensity, or the ability to use a particular coding language well under the pressure of peer-to-peer competition; and velocity, the ability to write good code quickly and accurately. Scores are calculated using TopCoder� s objective assessment model designed to fairly and accurately gauge a contestant's performance."

Anyway, Daniel Wright was apparently not happy with his second place win;, so at the next contest, in April 2002, Daniel beat all 15 other finalists (out of an original 512) to get his very own first prize and his very own $100,000! Two other Stanford CS students were among the finalists, doctoral students Eugene Davydov and Ante Derek, each receiving a $1,000 prize. Pretty amazing, if you ask me!

A different programming contest was held October 2001 here in the Gates Building, to choose three, 3-member teams to compete in the ACM regional programming contest in Fremont, CA on November 10, 2001. Brian Cooper (CS Ph.D. student) ran the local contest. The winners of the local contest were:

 

Team 1
Jon McAlister
Daniel Wright
Chuong Do
Team 2
Siu Hong Yuen
Eran Guendelman
Ben Blum
Team 3
Romain Thibaux
Sanders Chong
Mark Chong

Team 1 placed first in the regional contest in Fremont, so they were was invited to compete in the ACM International Programming Contest in Hawaii March 20-24, 2002. They did extremely well and placed 5th overall (out of an original field of 2400).

Moving on to other student awards:

  • Arthur L. Samuel Thesis Award was won by Pankaj Gupta (nominated by Nick McKeown). The winner of this award is also our nominee for the ACM best Thesis Award.

     

  • Two students, Petros Maniatis (PhD) and Ruchika Agrawal (MS) received the Student Service Awards for their service to the department. Petros has served on several committees in recent years and Ruchika was an M.S. "bureaucrat" (student representative). Both students often volunteered to provide extra service to the CS department.

     

  • Forsythe Teaching Award went to Jan Chong. This award is given to teaching assistants who have shown great aptitude for and dedication to teaching.

     

  • One of our former students, Lydia Kavraki (Jean Claude Latombe was her advisor) received the ACM Grace Murray Hopper Award. This award is conferred on the outstanding young computer professional of the year. Don Knuth was a previous winner! Lydia was also promoted to Associate Professor with tenure in 2001 at Rice University last year.

Other News

If you bring a laptop next time you visit us in Gates Hall, be sure to bring a very fast one, otherwise you'll feel out of place! We have upgraded the Gates network with new switches from Cisco. This upgrade consists of twenty-two Catalyst 4000's providing 10/100/1000 Mbps of data to the desktop. These switches are dual connected to two Cisco 6509 routers. In addition, to the 1200 Gates networked 1200 computers in Gates, we are testing VoIP (Voice over IP) telephone sets. We are currently have in testing 36 sets (located in the 1B area) out of 375 connected to the Gates network. We expect to start installing the remaining sets later this month. The VoIP phones and one of the two routers were gifts from Cisco Systems.

We have also augmented the Gates wireless network by installing the latest 802.11a wireless access points. The gives our user community a much higher data rate (54 Mbps) to their laptops while still support the 802.11b.

We were very fortunate this year to receive equipment gifts from Intel that consisted of: 18 Dell systems (for a new .net class that Robert Plummer is putting together), 4four workstations, and a two Itanium servers (each for two new members of the faculty, Serafim Batzoglou and Christos Kozyrakis), and aone 4 CPU Itanium server replacement for the student/alumni system (called Xenon). In addition to the computers systems mentioned, Intel donated the high-speed 802.11a wireless access points.

Construction continues at a fast pace on the Clark Center, located between Gates Hall and the Medical School. Researchers working on biology-related topics from the Schools of Engineering, Medicine, and Humanities and Sciences will be housed there, all working on biology related topics. Four or five of our faculty plan to have their offices in the new building. Because of the new building and others in the area, parking has become a real problem. So when you come and visit us, leave some extra time for finding a parking spot. I am told there is a new parking structure that replaces the lost parking spots, but the structure is so far that you have to take a bus to it! Fortunately, some of us are still young enough to ride our bicycles, so we have no need to visit the new parking structure.

We had our second Stanford Berkeley Day, this time here in Gates Hall. A bunch of Berkeley faculty and student visited us for one Saturday in February. We heard interesting talks by Armando Fox, Dave Patterson, Christos Papadimitriou, Chris Bregler, and many others. You can see pictures of the event at http://www-db.stanford.edu/~hector/photos/2002/SBDay2002/album.htm, taken by the official CS department photographer, (which happens to be me).

Prof. Vaughan Pratt continues to work on his tiny computers. His company, Tiqit, is a spinoff from the fourth floor wearables lab. They announced a new handheld computer at CeBIT in March --- it is the size and weight of a standard hard drive, runs XP Pro and Linux on a National SC2200 system-on-chip with 256MB/10GB/300MHz/640x480x18, has a battery life of 4 four hours operating and 4four days suspended. Vaughan tells me that making twenty prototypes turned out to be easy compared to taking it to production, with the new economy making some things easier and some harder.

While we�re Oon the topic of industry connections, Professor. David Cheriton founded a company called Granite Systems some years back. The company was acquired by Cisco, and one of the results are is the new Cisco Catalyst 4000 switches. Lots of Stanford people were involved in this enterprise, including former students Andy Bechtolsheim, Ken Duda, Hugh Holbrook, Debby Shepherd, Fusun Ertemalp, Matt Zelesko and Lorenz Redlefsen, current student Fusun Ertemalp, as well as and former staff Christophe Metivier and Christophe Jolie.

Changing topics, Prof. Jeff Ullman plans to retire at the end of this calendar year. His former students are organizing a special symposium to celebrate his 60th birthday and well as his retirement. You can find the details at http://www-db.stanford.edu/jdu-symposium.

Finally, I must report on our mysterious palm tree curse. As a lot of you know, two palm trees grace the main entrance to Gates Hall. When we moved into the building some years ago, huge cranes transplanted the two beautiful palm trees were transplanted, with huge cranes. The one on the left (as you face the building) did fine and is still thriving. The right one, unfortunately, died a slow death; over the course of a year, it shriveled up and died on us. Not to worry, we were told. The tree was insured, so after some time, the crane showed up again, with a brand new palm tree. The new tree did fine, for a few months, and then again, it started to dry up! Apparently our insurance was still good, and tree #2 was carted away, a huge new pit was dug, special sprinklers were installed, new soil was brought in, and a brand new palm tree #3 was transplanted. Well, a year later, #3 is dying on us again.

At this point we got pretty fed up, so Peche Turner, our department manager, suggested that we consult a witch doctor (from Stanford's department of Medieval Studies) to find out what was going on. We brought the expert in, and he indeed verified we had a cursed tree. The witch doctor was not sure how to lift the curse, but he suggested that increased donations gifts by alumni may to the department would do the trick! So.... please send your checks to.... Just kidding... (Just kidding!)

However, the saga of the palm trees is really true... We are indeed waiting for #4 to show up. But I am sure that simply the good wishes of and gifts from of all our CS alums and friends will be enough to make #4 prosper!

Till next year,

hector

P.S. Please send any almumni news to alumninews@cs.stanford.edu so I can include them in next year's newsletter.