A Personal View of Computer Science at Berkeley - Richard Karp

campanile


I arrived in Berkeley just before Christmas of 1968, full of anticipation and enthusiasm. It was not just that Berkeley was a good university in a pleasant and interesting city. In my view UC Berkeley was the best university, and the Berkeley environment was the best place for me to be. Nothing in the past 35 years has changed my view. 1968 was a period of radical social change and Berkeley was at the center of every liberation movement and antiwar protest action. The Free Speech Movement was still resonating and the Peoples' Park confrontation was soon to come. I well remember the closing of the campus at the height of the protests against the Cambodian invasion, and driving out to Santa Rita prison in the middle of the night to bail my friend and colleague Gene Lawler out of jail after his arrest for participating in an antiwar protest march. On the academic side Clark Kerr's 1960 master plan for public higher education in California had put the UC system on a course to become the envy of the world, and Berkeley was the flagship of the system. The first National Research Council rankings had established Berkeley as the top graduate school, with more highly ranked departments than any other place. Names like Tarski, Neyman, Lawrence, Seaborg and Oppenheimer added to Berkeley's luster.

In 1968 computer science at Berkeley was problematic, with two departments working independently to develop programs. Let me trace some of the history that led up to this situation. Digital computation at Berkeley began in 1948 when Paul Morton, an Electrical Engineering professor, began building Caldic, the California digital computer, a vacuum tube machine with a magnetic drum memory. His students included Al Hoagland, who was to become a pioneer in magnetic recording, and Doug Englebart, who was ahead of his time in understanding how computers could augment human intellect. Paul Morton taught the first computer courses and opened the first computing service center at Berkeley. Harry Huskey, who had worked with the Eniac group and with Turing, and had built the Bendix g-15 and SWAC computers, was a professor in the Electrical Engineering Department from 1957 to 1965 before moving on to found computer science at Santa Cruz. At Berkeley he worked on Neliac, a dialect of Algol, with his students Niklaus Wirth and Ken Thompson, who later won Turing awards for their work in programming languages.

Under Lotfi Zadeh, who served as chair during the mid `60s, the Electrical Engineering Department built up a significant computer science group, including many who later became core members of the Computer Sciences Division. In 1965 the name of the department was changed from EE to EECS. Lotfi had a clear vision of the potential of computer science to become a key enabling discipline for every branch of human activity, but his view was not universally shared within the department; after all, electrical engineering was also a broad and inclusive field, and there were close parallels between the activities in the two fields: the switching and automata theory that Mike Harrison and Arthur Gill were doing was closely related to work going on in control theory and information theory, and computer architecture and logic design had their roots in circuits and devices.

Tensions grew between the separatists and the conservatives, and in 1967 Mike Harrison, Butler Lampson and Marty Graham split off to form a new Computer Science Department in the College of Letters and Science. They were joined by Beresford Parlett from math, who became chair of the new department. I have always enjoyed Beresford's wry sense of humor: It was he who taught me the following words to live by: “if it's not worth doing, it's not worth doing well.”

The new department was given several positions to fill. It was not difficult for Mike Harrison to persuade me to join, and Beresford succeeded in attracting his admired colleague Velvel Kahan. Efforts were made to hire a third K, Don Knuth, but he chose to go elsewhere. At the junior level, Jim Morris, now the Dean at CMU, was hired from MIT and Jay Earley came from Carnegie-Mellon, where he had written a brilliant thesis under Bob Floyd; Jay's interests gravitated away from computer science and he left the field to become a transformational psychologist. Steve Cook was primarily in math but also in the new CS Department. It is to our everlasting shame that we were unable to persuade the math department to give him tenure. Perhaps they would have done so if he had published his proof of the np-completeness of satisfiability a little earlier. Laura Gould, the first computer scientist to win a Distinguished Teaching Award, offered courses on computing in the humanities. The top students included Jim Gray, Bruce Lindsay, Vaughan Pratt, Barbara Grosz, and Peter Deutsch.

Around this time Lampson, Deutsch, Chuck Thacker and others founded the Berkeley Computer Company. It was an outgrowth of project Genie, led by Prof. Bob Evans in EECS, which had added paged virtual memory to a machine called the SDS-930. Lampson, Thacker and Deutsch all moved on to become key members of Xerox Parc. Butler and Chuck just shared in the Draper Prize, recognizing their contributions at Xerox Parc to the personal computer revolution.

Over time it became clear that Berkeley could not afford two computer science departments developing independent and largely parallel curricula. Marty Graham, who had succeeded Beresford as chair of the L & S CS Department, convened a committee to review the department. As I recall the committee included Dave Evans and Dana Scott. The committee's report led the campus administration to review the overall situation in computer science. I can only conjecture that Marty had foreseen, and welcomed, the chain of events that the committee's visit set into motion.

It fell to Vice-Chancellor Mark Christensen to recommend a resolution to the two-department situation. The faculty were highly polarized. While a few wanted to maintain the two-department situation, most realized that computer science would have to be centralized, either in a new CS department within the College of Engineering or within the existing EECS Department. The peacemakers among us organized a series of lunch meetings to clear the air, but the situation remained tense. It did not help that the administration was playing its cards close to the vest, so that the faculty felt shut out of the process and could only guess what politics might be going on behind the scenes.

The administration decided to create a Computer Science Division within EECS, with a substantial degree of autonomy and its own associate chair, reporting to the department chair. The division was to run separate undergraduate majors for L & S students and for engineering students. This arrangement continued for many years, and gradually morphed into a more symmetric version with associate chairs for both CS and EE, with the chairman coming from either wing of the department. Randy Katz was the first chair to come from CS. Christensen's decision, hotly disputed at the time, has worked out very well thanks to the good will of the colleagues who have served as chairs and associate chairs.

Primarily because I had remained aloof from the politics and had not made any enemies, I was appointed as the first associate chair. People accepted the decision as a fait accompli and began to cooperate. The Computer Science Division was shoehorned into Evans Hall where we had to contest for space, not too successfully, with the entrenched occupants from mathematics and statistics. I was inexperienced in the workings of the University and made some rookie mistakes. For example, when the College of Engineering curriculum committee denied my request for a separate graduate degree in computer science I was prepared to accept the verdict, and only because of advice from more forceful colleagues did I finally make an end run around the college committee and get the degree approved by the dean of the Graduate Division, who took great pleasure in one-upping his arch-enemy, the College of Engineering.

It was my enormous good fortune that Tom Everhart was the department chair when I became associate chair. Tom understood the CS Division's needs for autonomy and gave me tremendous latitude and support, setting the tone for future chairs and associate chairs. We developed a great deal of mutual respect, and I have warm feelings for Tom to this day.

Gene Lawler and Manuel Blum, who joined the CS Division after the merger, became my closest colleagues. Gene, who died at the age of 61 in 1994, made important contributions to combinatorial optimization and computational genomics. He was also the social conscience of the CS Division, always looking out for the welfare of students and especially concerned for women, minorities and handicapped students. Gene worked closely with Sheila Humphreys, who ran our very successful reentry program for women and minorities entering computer science from nonstandard backgrounds.

Manuel Blum has always been a role model and an inspiration for me. Manuel is a phenomenal teacher who, in some mysterious and inimitable way, calls forth the creativity of the students in his classes and those who do research with him. A great many of our most brilliant and original theory students have worked with Manuel and gone on to brilliant careers. Part of Manuel's secret is his deep concern and consideration for all those around him. I once complained to Manuel that some of the students in my undergraduate class were slow at grasping the material. I will always remember his reply, “You may be better than they are at what you do, but you have something to learn from every one of them.”

Just after the merger, our CS Division was not as highly regarded as it is now. Stanford, MIT and CMU were the big 3, with their AI labs, DARPA grants and PDP-10s. The Cornell department was also ranked well above us. It was the Berkeley UNIX project, led by Bob Fabry with major contributions by Ken Thompson, Deomenico Ferrari, Bill Joy and many others, that first put us on the map in the systems area. Berkeley UNIX was the first example of a large-scale open-source software project at a university. It demonstrated the potential of an open environment for innovation, paving the way for later successful projects such as Linux. Another major early success was the INGRES database system project led by Mike Stonebraker and Gene Wong. It was this project that first clearly established the superiority of Ted Codd's relational model over earlier models of data.

These early successes were followed during the `80s and `90s by a succession of landmark achievements by Berkeley faculty and students. I will mention just a few of the many examples.

Velvel Kahan was the main architect behind the development of the IEEE 754 standard for floating point arithmetic, which has been in force for almost 20 years. Kahan has a long history of pointing out the anomalies and aberrations of many floating point implementations. The force of his rational arguments persuaded his colleagues on the IEEE committee to set aside their differences and rally behind his design. We are fortunate that Velvel has thought deeply about floating point arithmetic, so that the rest of us will not have to.

Reduced instruction set microprocessor designs pioneered by David Patterson and Carlo Sequin have led to tremendous improvements in the cost and performance of computers. Throughout the `80s Berkeley students led by Patterson, Sequin and Katz have built prototypes for several increasingly powerful RISC designs.

Starting in 1989 Patterson and Randy Katz argued the case for redundant arrays of independent disks and oversaw the development of a series of RAID prototypes. Industry has made a very large investment in this approach to the design of storage systems.

David Culler led the Berkeley Millennium project - a campus-wide cluster of clusters to support advanced applications in scientific computing, simulation and modeling.

Lotfi Zadeh's theory of fuzzy logic, originally developed in the mid-60's, found many successful applications in the design of control systems during the `80s and early `90s. Lotfi has often stood alone in his scientific opinions, and many have criticized his work, but he never wavered and in the end has been vindicated. Lotfi's deep scientific convictions are altered neither by criticism nor by praise. He once told me, “Whatever anyone says about you, take it as a compliment.”

In 1974 a student named Ralph Merkle began dropping in on faculty to explain how it might be possible to create a communication system in which anyone can send a secret message to a person (later called Bob in the cryptography literature), but only Bob can decipher these messages. Merkle had discovered public key cryptography. However, his explanation was not very lucid or technically fleshed out, and none of us grasped the revolutionary nature of his idea. Eventually he learned that Diffie and Hellman had independently come up with the same idea, and he moved to Stanford to work with them. Despite this lost opportunity Berkeley has made its mark in cryptography. Two of the three seminal 1982 papers on the complexity-theoretic foundations of cryptography came from Berkeley: the brilliant work of Shafi Goldwasser and Silvio Micali on probabilistic encryption, and the Blum-Micali paper on cryptographically secure random number generation.

Christos Papadimitriou, in his talk this morning, has covered some of the other key achievements in the theory of computation at Berkeley: P-completeness, Karmarkar's great algorithm for linear programming, Gary Miller's primality test, the foundational work of Bernstein and Vazirani on quantum computing, and the contributions of Arora and Sudan and their coworkers to the amazing theory of probabilistically checkable proofs and its application to showing that certain NP-hard optimization problems cannot be solved, even approximately, in polynomial time unless P=NP. Manuel Blum and Shafi Goldwasser also had a hand in the research that led up to this great breakthrough.

Another notable achievement was the interactive architectural walkthrough of Soda, created by Carlo Sequin, Seth Teller and the UC Berkeley walkthrough group. This kind of graphics support for architecture is common now, but was way ahead of its time in 1994.

Many of us have written influential books. These include Mike Clancy's best-seller Oh! Pascal!, Mike Harrison's definitive book on formal languages, and Gene Lawler's influential book on combinatorial optimization, as well as several books that have become the canonical texts for entire fields in computer science: Russell and Norvig in artificial intelligence, Patterson and Hennessy in computer architecture, and Katz in logic design. I am especially fond of Winning Ways, the brilliant two-volume treatment of combinatorial games by Conway, Guy and Berlekamp. This is the only I know that combines delightful readability with a high level of rigor. In his novel Turing, Christos Papadimitriou provides a brilliant exposition of the theory of computation while also exhibiting a poetic imagination that must be unique among computer scientists.

It was Domenico Ferrari who first took seriously the idea of getting a new building for computer science. Many in the college and department helped with the fundraising. Our success in getting support from industry, especially in Japan, stemmed in large part from the phenomenal reputation of the EECS Department. In a way, Soda Hall is the department's payback for SPICE and the other design tools that our EE colleagues had created. Soda Hall was a shot in the arm for the CS Division. It is a very functional and attractive building, and Carlo deserves great credit for his tireless work with the architects.

In 1994 the University, motivated by a lean budget and a fat pension system, offered an early retirement program called VERIP that was very attractive for the senior faculty. Domenico Ferrari, Mike Harrison, Gene Lawler, Beresford Parlett, Mike Stonebraker and I succumbed to the offer. I moved to the University of Washington, but couldn't stay away, and returned to Berkeley and ICSI in 1999.

There were dire predictions about the future of the campus after VERIP, but the Computer Science Division rebounded superbly, with a host of brilliant recruiting successes. I returned to Berkeley and ICSI in 1999 to find that the division had become much more of a powerhouse than it was when I left. There were new initiatives in networking and communications, computer security and human-computer interfaces, and these were soon followed by ventures into computational biology and by the founding of CITRIS to investigate societal applications, with an emphasis on sensornets.

By 1999 it was clear that the Internet, the Web, and distributed and mobile computing and communications had permanently changed the face of both computer science and electrical engineering. The department's response to this new reality is a perfect illustration of why it is a good idea for computer science and electrical engineering to be together. Because we are together we have been able to create a wide spectrum of synergistic activities and collaborations, ranging from Smart Dust to multimedia tablet computers to Oceanstore, with theoretical support from information theorists, system theorists and algorithm and protocol designers.

More generally, it has been a blessing for computer science at Berkeley to be affiliated with electrical engineering. The great reputation of Berkeley electrical engineering preceded us and smoothed the way for us. More and more, the entire department revolves around information technology. I count at least fifteen faculty who currently sit in Cory Hall, in information theory, communications, optimization, control and design automation, who could easily be classified as computer scientists. We benefit greatly from their support and cooperation.

Well, enough about our great scientific achievements. What about the CS Division as a community and as a teaching institution? I am struck by how many of us contribute to the leadership of the division. Eleven times since 1973 one of us has been persuaded, more or less against his will, to take his turn as chair or associate chair, and each has performed with distinction. Apart from the associate chairs, others who have taken on heavy management responsibilities include Rujena Bacsy, Jim Demmel, David Culler, Sue Graham, Larry Rowe, Mike Clancy and Brian Harvey. At our faculty lunches we can always count on Velvel to espouse a position that goes against the conventional wisdom but turns out to make a great deal of sense, Robert Wilensky to crystallize and clarify the issues, Lotfi to give us the benefit of his wisdom and experience, and Alan Smith to remind us that, “if it ain't broke, don't fix it.” Randy Katz, Dave Patterson, Sue Graham, Mike Harrison, Ruzena Bacsy and others have contributed to the policy dialogue at the national level.

We have been incredibly lucky in recruiting and developing young faculty. Every one of our junior faculty has met our expectations, and I believe we are meeting theirs by helping them adapt to the multiple responsibilities of research, teaching, course design, student supervision and grantsmanship.

I believe that our Ph.D. students are enjoying their time here and growing as computer scientists. They are certainly selected with great care. Each research area does it in a different way, but each creates a rich scientific and social environment for its students. I wish my own Ph.D. experience had been half as stimulating.

Our undergraduates are capable and hard working, and we offer them well designed and demanding courses. I wish we could find a way to engage with them on a more personal level, teach them in smaller sections and involve more of them in research, or at least in capstone design courses that would prepare them for high-level development work. We will have to constantly monitor our curriculum to make sure that our students reach a level of innovation and performance that cannot be duplicated by outsourcing to foreign competitors.