Introduction

This issue of our departmental report summarizes many of the accomplishments of the past two academic years. Highlights include:

• Professor Carl de Boor was elected to the National Academy of Sciences. De Boor, a numerical analyst, is particularly well known for his work on the theory of splines. He also received the Society of Industrial and Applied Mathematics 1996 von Neumann Prize for mathematical work that has found wide application. In 1997 the University of Wisconsin named de Boor to a second 10-year term as the Steenbock Chair in the Mathematical Sciences.

• Tashia Morgridge donated funds to support our first endowed chair. Professor Lawrence Landweber, who studies computer networking, was elected as the first John P. Morgridge Professor of Computer Sciences. Landweber is the past-president of the Internet Society and was also named by Newsweek as one of the "Internet 50."

• Professor Stephen Robinson was one of two recipients of the prestigious 1997 George B. Dantzig Prize, which is awarded once every three years by the Mathematical Programming Society and the Society for Industrial and Applied Mathematics. Robinson conducts both theoretical and applied research to develop better methods for quantitative economic planning. Robinson was also awarded a honorary doctorate from the University of Zurich in 1996 and he recently received the College of Engineering's Byron Bird Award for Excellence in a Research Publication.

• Professor Michael Ferris, together with his former Ph.D. student Steven Dirkse, received the 1997 Beale-Orchard-Hays Prize of the Mathematical Programming Society. Ferris and Dirkse received the prize for their work in developing and implementing the PATH Solver, a program to solve certain equilibrium problems that occur very frequently in engineering, economics, transportation modeling, and other areas.

• Professor David DeWitt, together with former UW faculty member Michael Carey and graduate alumni D. Frank, G. Graefe, M. Muralikrishna, J. Richardson, and E. Shakita, received the VLDB Endowment 10-Year Paper Award for co-authoring the most influential paper in the VLDB Proceedings ten years ago.

• Professor Mary Vernon was elected to a three-term on the Computer Research Associates (CRA) Board of Directors. The CRA includes more than 160 North American organizations active in computing research, and focusses on government policy decisions and policy making.

• The MIDSHIP Project, headed by Professors Jeffrey Naughton and James Larus, received a five-year, $1.6 million NSF Institutional Infrastructure Award. This is the fourth such award that the Department has received, going back to 1981. The MIDSHIP (Managing Image Data Sets with Scalable High Performance) project focusses on developing technology to support a wide range of large-scale image applications.

• The Net Scout Project, headed by Research Associate Susan Calcari, received a three-year, $3 million award from NSF to provide services to help researchers and educators use the Internet more effectively.

• The Computer Sciences Department played a key role in a University-wide consortium that recently received a $4.8 million grant from Intel. A focal point for this grant is the Condor Project, headed by Professor Miron Livny, which provides a method for scavenging unused cycles on idle computers.

• Professors Thomas Reps and Gurindar Sohi each received Vilas Associate Awards from the University of Wisconsin. The Vilas Associate Award recognizes outstanding research accomplishments of tenured faculty in mid-career.

• Professor Olvi Mangasarian was the sole 1996 winner of Wisconsin's Hilldale Award in Physical Sciences for his distinguished contributions to education and research in mathematical programming. Mangasarian was also voted one of Madison's 25 smartest people by Madison Magazine for his work on applying optimization techniques to breast cancer diagnosis and prognosis.

• Professor Mark Hill received a Romnes Fellowship. The Romnes Fellowship recognizes outstanding research accomplishments of recently tenured faculty at the University of Wisconsin.

• In 1996 Professor Yannis Ioannidis was one of ten campus winners of the university's Distinguished Teaching awards. Professor John Strikwerda received the 1996 Benjamin Smith Reynolds Award for Excellence in Teaching Engineers.

• Susan Horwitz, Jeffrey Naughton, Raghu Ramakrishnan, and Guri Sohi were promoted to Full Professor. David Wood was promoted to Associate Professor with Tenure.

• Several graduate students were awarded competitive fellowships to support their graduate studies. Sara Bauman was awarded a GAANN fellowship; Elizabeth Bilir received an NSF fellowship; Douglas Burger received a fellowship from Intel; Paul Finley was awarded an Advanced Opportunity fellowship; Xuelin Lu received a Java fellowship; Todd Munson was named a Wallace Givens Research Associate; Eric Neuman received a traineeship from Wisconsin's MaCE program; James Pruyne received an IBM Rochester fellowship; Steven Reinhart was awarded an AT&T fellowship; Min Zhong received a CRA Women Mentor Research Internship; Keivin Cherkauer and Karen Karavanic were awarded NASA fellowships; Kevin Beyer, Babak Falsafi, Johannes Gehrke, Milo Martin, Eric Schnarr, Praveen Seshadri, and Eric Rotenberg received IBM Cooperative fellowships; and Sanjay Agrawal, Rushan Chen, Zheng Li, Zhenlai Lin, Alexey Loginov, Mark Manville, Qingqing Ouyang, Sowmya Subramanian, and Liping Zhu were named Wisconsin Alumni Research Foundation Fellows. In addition, over the past two summers the department has awarded a total of over twenty summer fellowships to new graduate students just starting their research.

• Lecturer James Skrentny (1995-96) and Professor Susan Horwitz (96-97) received the department's Caroln Rosner Excellent Educator Award. Lorene Webber (95-96) and Marie Johnson (96-97) received the department's Outstanding Departmental Service Award. Andrew Whitsitt (95-96) and Chad Lane (96-97) were named the department's Outstanding Graduate Student Instructor, while Steven Reinhardt (95-96) and Satish Chandra (96-97) were chosen as the Outstanding Graduate Student Researcher. In 1996, Professor Anne Condon was honored by the student chapter of the ACM (SACM) as the Students' Choice Professor of the Year, while in 1997 Professor Barton Miller won this award. Also in 1997, SACM gave Professor Yannis Ioannidis a lifetime award for excellence in teaching.

• Professor James Goodman was named Department Chair in 1996 after Professor Marvin Solomon completed his three-year term.

Professor Seymour V. Parter retired in February 1996. He continues to teach on a part time basis until June 1999. Parter joined the university in 1963 as a member of the Department of Numerical Analysis, as well as the Mathematics Department. He was instrumental in changing the name of our department (and its focus) to the Computer Sciences Department in 1964. He served as chair of Computer Sciences 1968-70, was the president of the Society for Industrial and Applied Mathematics (SIAM) 1981-1982, and was the chair of the Conference Board of the Mathematical Sciences in 1983. He is a Fellow of the American Association for the Advancement of Science. During his 34 years in the department he taught courses and carried on an active research program in numerical analysis. Five students completed PhD's in Computer Sciences and nine in Mathematics under his direction.

Educational Program

The quality of our undergraduate and graduate programs in computer science is acknowledged nationally and internationally. This allows us to keep undergraduate and graduate standards very high. Admission into our M.S. and Ph.D. programs is highly competitive; less than one out of every three students who applied to our graduate program last year was accepted with support. Fifty-seven new graduate students entered the department this fall, giving a total of 206. We currently have 214 undergraduate majors. During the last two academic years, we granted 1xx B.S./B.A., 1xx M.S., and 27 Ph.D. degrees.

Our graduates are in great demand in both industry and academia. Of our recent Ph.D. graduates, 9 took academic positions and 18 took positions in industrial research and development laboratories. Many of our bachelor and masters graduates were hired by our industrial affiliates. In the past year, nine of our recent alumni who are assistant professors received prestigious Career Awards from the National Science Foundation.

Our Undergraduate Projects Laboratory (UPL) provides state-of-the-art equipment and allows undergraduates to explore projects of their own interest. Especially notable are the impressive computer graphics that the students produce.

The local student chapter of the Association for Computing Machinery (SACM) is open to all Computer Sciences students. SACM sponsors a fall orientation program for new graduate students, several social and sports events during the year, the department photo board, and financial aid for conference registration fees. Funds for these activities are raised through soda sales to department members from a computerized vending machine.

Each year the department sponsors a special colloquium series that brings leading researchers to campus. This series complements our regular weekly seminar programs. The Spring 1997 program was partially sponsored by Lucent Technologies and AT&T.

The Internet and Beyond

Distinguished Lecturer Series - Spring 1997

Sandy Fraser, Vice President - Research, AT&T Laboratories

Broadband Communications for Consumers

Thomas DeFanti, Professor, University of Illinois - Chicago

The Coming Defenestration: Immersive Environments Without Windows

Daniel Lynch, Chairman, CyberCash

Micropayments -- The Energy Pill for a New World Order

Paul Mockapetris, Chief Technology Officer, Software.Com

Next Generation Internet: The Cable Perspective

Eric Schmidt, Chief Executive Officer, Novell

Evolution or Revolution? The Future of Network Computing

John Morgridge, Chairman, Cisco Systems

Catching the WAVE

We also have an annual lecture given in memory of Professor Barkley Rosser, who served the University of Wisconsin and our department with distinction. The sixth annual J. Barkley Rosser Memorial Lecture was given by Kenneth Kennedy of Rice University, who spoke on "Compiler Support for Architecture-Independent Parallel Programming." The seventh talk in this series was given by Cambridge University's Robin Milner; his lecture was titled "Computing is Interaction."

Faculty Research Programs

Many of our 32 faculty have received notable awards in honor of their outstanding research and educational achievements. Carl de Boor is a member of the National Academy of Science, the National Academy of Engineering, and the American Academy of Arts and Sciences; he also holds the Steenbock Chair in Mathematical Sciences. Lawrence Landweber is the John P. Morgridge Professor of Computer Sciences. Olvi Mangasarian holds the John von Neumann Chair of Mathematics and Computer Sciences. David DeWitt, Lawrence Landweber, and Mary Vernon are ACM Fellows. DeWitt and Mark Hill are Romnes Fellows, while Thomas Reps and Guri Sohi are Vilas Associates. Thirteen current faculty members have received Presidential or NSF Young Investigator awards, two were awarded Packard Foundation Fellowships, three have received ACM doctoral dissertation awards, one has been given an ACM SIGMOD Innovations Award, one has received an NSF Faculty Award for Women in Science and Engineering, one has received a DEC Incentives for Excellence Award, and three have received IBM Faculty Development Awards.

We perform research in a wide variety of areas of computer science and receive funding from government agencies, industrial companies, and private foundations. The current research directions of the department are summarized below, while a later section of this report provides further details on each faculty members's research focus and sample publications. Our web site (www.cs.wisc.edu) should be visited to access more in-depth information.

Artificial Intelligence

Computer vision, machine learning, robotics, and automated deduction are topics of research in our AI group. Research directions include synthesis of images from new camera viewpoints by combining a set of images of a real environment; integration of symbolic and connectionist approaches to AI, applied to the design of instructable software agents for information finding on the World-Wide Web; sensor-based robot motion planning; and computer generation of formal proofs in logical systems.

Computer Architecture

Recognized as one of the world's premier computer architecture groups, our group has focused on research in two directions. Efforts in multiprocessor memory system design, which have developed snooping caches, the IEEE Scalable Coherent Interface, memory consistency models, and cooperative shared memory, are now targeting extensible shared-memory systems. Work on instruction-level parallelism has moved from decoupled architectures to the multiscalar and datascalar paradigms, which can push performance beyond ten instructions per cycle and exploit the potential of merged memory and logic circuit technologies.

Databases

Our top-ranked database group is widely recognized for its strength and diversity. Research is being pursued in a number of directions, including database integration, database programming languages, heterogeneous object stores, information visualization, object-relational databases, parallel database systems, query optimization (including cost estimation via sampling, complex query evaluation, parallel and multimedia query scheduling, and error estimation), scientific databases, spatial databases, and user interfaces.

Mathematical Programming

The research of our mathematical programming group covers theory and algorithms of linear and nonlinear programming, with applications to machine learning, data mining and network flows; parallel genetic algorithms; stochastic optimization; nonlinear optimization and equilibrium problems; medical diagnosis and prognosis via linear programming; and the theory of error bounds.

Numerical Analysis

Our numerical analysis group has research interests in approximation theory, particularly multivariate approximation by splines and wavelets, and partial differential equations, multigrid methods and domain decomposition with applications to computational fluid dynamics.

Operating Systems and Networking

Research in operating systems and networking covers operating system design and implementation, wide-area information systems, gigabit networks and distributed systems. Our research includes optimizing system performance, extensible operating systems, caching in the World Wide Web, distributed resource utilization, high throughput computing, network support for visualization of physical phenomena, and multi-media conferencing. We are also designing systems that dynamically instrument applications and perform various optimizations.

Performance Evaluation

Our research in the performance evaluation of computing systems focuses on developing effective simulation and analytical modeling techniques, as well as applying these techniques to parallel/distributed architectures and systems, data management, and communication network design issues. Applications of current interest include high performance and high throughput scheduling policies for parallel and distributed systems, multimedia server design issues, global memory management in networks of workstations (NOWs), and end-to-end performance modeling of large heterogeneous adaptive parallel/distributed computer/communication systems.

Programming Languages

Our research in this area focuses on parallel programming languages, techniques for compiling for shared-memory parallel computers, efficient performance evaluation tools, language-specific tools to aid in large-scale software development, program slicing, dataflow analysis and abstract interpretation, incremental algorithms, interactive programming environments, automatic code selection, optimal code scheduling, and global and interprocedural register allocation.

Theoretical Computer Science

The primary research areas in our theory group are average-case analysis of data structures and algorithms, computational biology, and DNA computing. Other research topics include computational number theory, parallel algorithms, approximation algorithms for NP-hard problems, structural complexity theory, and algebraic complexity theory.

---

Press one of the arrows above to move around in this report.

Send comments about this publication to pubs@cs.wisc.edu.
Mail general questions about the department to cs@cs.wisc.edu.

---