Message from new Dean of CIS and new Chair of CSD 2

Cornell in the Information Age 5

Corporate Interactions 6

Industrial Partnerships 6

Industrial Partners 7

Corporate Gifts and Grants 7

Program of Computer Graphics 8

The Cornell theory Center 8

Science Fair - BOOM `99 10

Awards 11

Student Data 12

Courses and Enrollment Statistics 12

Educational Statistics 14

Degrees Granted 14

Research 17

Funded Research Grants 17

Submitted Research Proposals 20

Collaborative Funded Research at Cornell 20

Submitted Collaborative Research Proposals 21

People 63

Faculty, Research and Academic Visitors 63

Administrative Staff 65

Technical Staff 65

Computing Facilities 65

Colloquium and Seminar Speakers 67

Publications 68

Technical Reports 68

Lectures and Publications by Students 69

Cover Photo:

Faculty Advisor and Editor:

Publication Editor: Lizbeth Henson

Design & Layout Editor: Lizbeth Henson

Editorial and Photo Assistant: Karla Consroe

Department of Computer Science

Charles Van-Loan, Chair

4130 Upson Hall

Ithaca, NY 14853

Voice: (607) 255-

Fax: (607) 255-4428

email: chair@cs.cornell.edu

http://www.cs.cornell.edu/

Cornell Department of Computer Science

TABLE OF CONTENTS

in 1995 were commercial restrictions on the Internet lifted. Before that, there was no amazon.com, no eBay, no electronic commerce to speak of. (We have heard it said that by 1995 half of the Web users had never heard of Mosaic --- that is internet-time!) The well-documented and unprecedented run of US economic prosperity was only in its second year. It continues to amaze the experts. Government studies had not yet confirmed that US economic growth is being fueled by the information technology sector.

In 1993 the biologists and we were just beginning to understand the new deep links that would connect us. (There have always been strong ties between computing and biology, e.g., Babbage influenced Darwin, and finite automata arose as abstractions of brain models.) The notion that a massive worldwide digital library would spring up in a matter of years was not widely foreseen. Gerry Salton was still alive and was only beginning to see his field of Information Retrieval move to center stage, and with it, his fundamental contributions. Scholars, historians and journalists are now telling us that there is an information revolution and that our field is at the heart of it. They foresee a revolution on the scale of the Industrial Revolution and beyond. We are fortunate to experience it in our lifetimes.

In 1993, the department had essentially no AI group, no systems lab, no database effort, and no computational biology, and it was just getting started in digital libraries with the launch of the CS Technical Report project in late 1992. We also had just launched our "multimedia" effort. There was no firewall around our computers, about 135 of them, all SUNs and Macs. Rhodes Hall had been around for only a year. We were receiving about $6 million in research funding (almost doubled during John Hopcroft's tenure as chair).

By 1996, the department felt the warm winds of change again gusting hard on our sails. The telltales were from increased research contacts across the university and from the number and quality of students taking CS courses and wanting to major in CS. There were occasional helpful gusts of hot air from the popular press. But even our more sober writings drew attention to something quite remarkable, that modern computer science was relevant to every subject taught at Cornell. Many disciplines were becoming either computational or data-intensive. Faculty in those fields wished to hire people who understood computer science and could

Message from the new Dean of CIS and new Chair of CSD

Robert L. Constable and Charles Van Loan

Charlie and I have adopted the theme of "transitions" for this report. He has become the new CS Chair, and I have become Dean for Computing and Information Science, leading the university's academic initiative in this area. I am responsible to the Provost for the CS Department, and the Department has become the nucleus of a new university-level administrative unit. As a dean, I will remain active in research and teaching, as I did when I was chair. Charlie also plans to follow the CS tradition that the chair stays engaged in teaching and research.

Even larger changes impacting CS are being proposed by the Task Force on Computing and Information Science headed by Dan Huttenlocher. Excerpts of their initial report, "Cornell in the Information Age", follow this introductory section. The full report appears on the department home page (under Quick Links).

Much has happened to the field of computer science since I started my term as acting chair in 1993 and as chair a year later. In 1993, the first web browser, Mosaic, appeared, building on the one-year-old Internet protocol, http, that enabled the World Wide Web. Only

1998-1999 Annual Report

interact with us. Already by this time the central administration was trying to channel additional resources to CS. We formulated a plan for Cornell to broadly profit from the expertise and reputation of the Department of Computer Science and for the department to be enriched by interaction with other fields.

Our Vision Statement was intended to be a blueprint for the growth that we knew must come. We spent a summer faculty retreat drafting our plan, and in the fall of 1996, wrote a document that became known as the "revision statement" because we revised it so much, practically half of the department rewrote some of it. We also worked with Cornell's new President, Hunter R. Rawlings, III, who helped us understand how to build a "computer science community" at Cornell as he put it; even he spent time revising the document!

The Vision Statement has become sharper from the vantage point of a broader department; it has guided our hiring plans and shaped our dialogue with the administration. Eventually, it became the basis for a much wider definition of Computing and Information Science at Cornell. I am pleased with the Vision Statement and its consequences; and, of course, I am proud of the outstanding talent pool of faculty, researchers, and staff that is now assembled in the department.

During my term, we reorganized for growth; this meant more staff, better-trained staff, and new management structures, from the "Nuts & Bolts" advisory committee and senior financial manager to the new senior human resources manager. We needed to manage the increase in research funding to $15.5 million, the expansion of projects, and growth in the faculty and research staff and the legion of computers they brought along. The computing operation went through a phase transition as we created a hybrid environment of PC's, Sun workstations, and servers --- now over 500 machines.

Amidst all this change, salient defining invariants remain. We thrive in an unsurpassed research environment nurtured by one of the world's premier research universities. Cornell has attracted exceptional talent to all of its academic endeavors. It has helped the department remain one of the five best places in the United States to do computer science. We have managed to broaden considerably and yet maintain the quality that distinguishes us. The department is still renowned for

its cohesion and collegiality despite increased diversity and breadth. The number of collaborations across subfield boundaries is exceptional. The faculty's open-door policy to students and the long tradition of regular faculty lunches continues, even without the institutional support of a university faculty club - now we rely on a friendly bagel shop with its outdoor patio (that we used even in February this year).

The fall External Program Review took an official hard look at the CS Department. The Review Committee was headed by Anita Jones and consisted of Hector Garcia-Molina, Randy Katz, Justin Rattner, and Margaret Wright. This was part of a university-mandated review of all departments, so we had help compiling a mountain of statistical data for the review team. Their extremely favorable report helped the university in its planning for CIS. Two of the phrases from the report that we especially appreciated said:

"... it is highly unusual for a small department to rank highly when the department does not cover most major sub-areas of the field. Cornell department leadership over the years has charted a most effective course and maintained Cornell as one of the top CS departments."

"Computation and information science and technology are crucial enablers for advancement in a multitude of disciplines in any university. Cornell is advantaged by having a truly excellent Department of Computer Science!"

We continue to find common ground in our focus on the scientific core that binds computer science into a coherent discipline. That core is documented as a rapidly growing body of knowledge on computing and information, created as the field repeatedly rose to the challenge of very hard technical problems about how computers can be used: what are the limits, what are the laws, how to compute well, how to compute correctly, what can computers help us do better, and what is possible in "cyberspace". This body of knowledge documents our field and has earned it a permanent place in all university curricula (some new universities have started with only CS and a couple of other departments). Its fundamental contributions are widely recognized, more than in 1993, because there is a burgeoning list of artifacts and phenomena whose behavior is governed by laws of information and principles of

Cornell Department of Computer Science

TABLE OF CONTENTS

computation.

Our field is about information: its organization and retrieval. It is about computers: we interact with computers to create knowledge from information. It is about communication: sharing knowledge with others to achieve better understanding. CS also studies the process just described, and is thus about implementing intellectual processes. These concepts are currently grounded in digital computers, but they apply to all information processors, eventually perhaps to quantum computers, to biological computers, surely to the human mind, and to societies of minds. The universal and quantitative character of this body of knowledge ties it to the sciences, while the breadth and abstractness give it an uncommonly intimate reach to the humanities. It is a field that is accelerating the "unity of explanation" that E.O. Wilson has written about in his book Consilience. There he draws attention to this fundamental question: What is the relation between science and the humanities, and how is it important to human welfare?

Anyone who watches an infant growing up knows that humans are inherently and insatiably curious and communicative. The Information Revolution rests ultimately on these basic human instincts. Our field is rewarded because software has enabled computers to satisfy many basic human needs. Their most significant impact is in discovery, communications, commerce, and entertainment. Consequently, the revolution is fueled by tremendous social energy, the energy that we all provide by wanting to know more, talk more, and experience more.

The next several decades will surely see stunning advances in computing and information science as we continue to ride the exponential growth of computing power. Already our computers are marvels, their speed and memory capacity extending the boundaries of many fields. This exponential growth and the corresponding decline in cost spreads both the technology and the ideas of CS into the fabric of science and scholarship, assuring that the field will become even more relevant to the questions of human inquiry, especially to Wilson's question which is central to universities. We intend to insure that Cornell remains a leader in the Information Age by providing the best environment for research and education in computing and information science.

Our faculty continue to make an impact at the national level. Juris Hartmanis returned to the department after serving as Deputy Director at the National Science Foundation. Fred Schneider chaired the National Research Council study on Information Systems Trustworthiness and was the editor of its final report, "Trust in Cyberspace". That report attracted considerable attention from federal policy makers and the popular press. Schneider gave briefings at the White House, NSF, DARPA, NSA, and the FCC about information systems trustworthiness; he was also keynote speaker at all four of the national conferences in Computer Security.

Several faculty received recognition for their accomplishments in research and teaching this year. Charles Van Loan was named the Joseph C. Ford Professor in Engineering. Dan Huttenlocher and Keshav Pingali were promoted to Full Professor. Eva Tardos received a Guggenheim Fellowship. Ken Birman was elected a Fellow of the Association for Computing Machinery (ACM). Several of our newer faculty received awards recognizing their research: Jon Kleinberg as an Office of Naval Research Young Investigator, Bart Selman as an Alfred P. Sloan Research Fellow, and Greg Morrisett with a Career award from the National Science Foundation. Two faculty received honorary degrees: David Gries from Miami University and Juris Hartmanis from the University of Missouri-Kansas City. Stephen Vavasis, Thorsten von Eicken, Praveen Seshadri, and Lillian Lee received College of Engineering Teaching Awards.

1998-1999 Annual Report

Cornell in the Information Age

Initial Report of the Task Force

on Computing and Information Science

June, 1999

The Information Revolution is transforming society - creating new careers, new industries, new academic disciplines, and the need for new programs of education and research. These changes affect how people work and think, two things that are fundamental to universities. While it is perhaps tempting to dismiss the information revolution as hype or as a passing fad, the evidence runs quite to the contrary. For instance, about one third of economic growth in the U.S. since 1992 has been in computing and information technology. Not only are the founders of new high technology companies often barely in their 20's, new careers are also appearing at traditional companies. For example, this year's ranking of the 500 best and worst jobs lists Web Site Designer as the top job in terms of pay, flexibility, and satisfaction. This is a position that did not even exist five years ago, and that requires a combination of skills not easily found in today's educational programs. The Internet and the Web are perhaps the most visible aspects of this change, but it is pervasive, touching nearly every field and discipline, from computational techniques in the physical and biological sciences to new interactive media in the arts. This revolution has already brought fundamental social change; however, we do not yet understand the impact of this change, nor do we know how much more is yet to come.

Being an informed citizen in the information age requires knowledge of computing systems, global communications networks, and interactive information resources. The requisite level of knowledge goes beyond simply being comfortable with computing tools. It requires the ability to apply computational ways of thinking to design, to writing, to experimentation, to artistic expression, and to problem solving - to the very core of human intellectual activity. Just as a higher education requires writing skills that go beyond the mechanics of sentence and paragraph structure, it is also beginning to require computational skills that go beyond the mechanics of programming and software packages. In the information age, our ideas are no

longer constrained solely by what is physically realizable, but by what is computationally realizable. For example, an artist is now able to create an artwork that only exists when someone interacts with it - specifying a framework within which each visitor can create a work of art. A chemist is now able to search more effectively for new compounds by modeling them before ever going into the lab. Nearly every discipline is changing, not just because of new tools, but because of new computational ideas and paradigms.

While the information revolution rests on fundamental advances in many fields, the core enabling disciplines are in the computing and information sciences (CIS). It is the embodiment of knowledge and techniques in computer software and protocols that is driving the change. Perhaps the central underlying theoretical concept is that of the "universal computational machine." While this is a theoretical notion, it has had immense practical consequences. Consider the meteoric rise of the World Wide Web, a fundamental change that has happened in just a few years. Such rapid change was only possible because many people already had computers - which are universal computational machines - in their homes and offices. Prior to the Web, people largely used these machines for word processing and calculation. These same computers have now been transformed from typewriters and calculators into global information resources. While we have gotten used to this notion of universality of computational devices, it is worth noting how different it is from physical devices, which are specialized to a particular function rather than being universal (e.g., physical universality would allow your refrigerator to function as a dishwasher).

In the tradition of Ezra Cornell, we believe that Cornell University should become an institution where anyone can bring ideas from Computing and Information Science to bear on their discipline of study. Cornell has a nearly unrivaled combination of depth and breadth upon which to build - with one of the top computer science departments, outstanding research programs in computational science and engineering coordinated by the Theory Center, the new computational Genomics initiative, and pockets of computational expertise across the campus, in engineering, physical science, arts, humanities, and social science. We believe that it is crucial for Cornell to act quickly to capitalize on this strength, so that we are able to attract and retain the best faculty, and provide the best education for students whose

Cornell Department of Computer Science

TABLE OF CONTENTS

Corporate Interactions

Industrial Partnerships

The department offers opportunities to interact on a number of levels with internationally respected scientists in such vital areas as:

· artificial intelligence

· computational methods for mechanical design and simulation

· digital libraries

· distributed computing and fault tolerance

· formal specification and verification methodologies

· graphics (through affiliation)

· information technology

· natural language, document classification and retrieval

· networking databases

· parallel computing

· programming languages

· programming logics

· remote collaboration technologies

· scientific and numerical computing

· security

· supercomputing (through affiliation)

· theoretical computer science

· vision and image interpretation

Industrial partners are invited to participate directly in the technology development process, through on campus representation, visits, and consulting arrangements. Additional opportunities include access to technical reports, colloquiums, seminars, the department's Annual Report, and resumes submitted by BA, BS, MEng, and PhD candidates expecting to graduate.

interests in computing and electronic information resources are rapidly growing.

Given the above consideration of possible structures, we recommend the establishment of a new kind of academic home for computing and information research, scholarship, and teaching at Cornell. We are calling this home the Faculty of Computing and Information (FCI). The mission of the FCI is to create broad-based programs of education and research that span the campus. Given the high student demand and the fast pace of change in this area we believe that there must be a particularly tight coupling of education and research. Thus, a key part of our reasoning is that the FCI have both teaching and research missions. We have chosen the term "faculty" to highlight that while this proposed structure has some attributes of a college, it would also differ from a college in several critical regards. First, the FCI would have an undergraduate teaching role more like that of a department than that of a college, in that it would offer majors and minors in existing colleges. We further envision that the FCI would offer these programs in several if not all colleges at Cornell. Second, the FCI would have a large number of half-time joint appointments with faculty in the current colleges.

1998-1999 Annual Report

Department of computer science faculty and researchers continue their collaboration with industrial partners. GTE, Intel, Lockheed Martin, Microsoft, and Xerox continued their support this year. Compaq provided funding for new workstations for the fall 1999 incoming PhD class. GTE continued its support of the department's initiative in information technology with startup funding for new faculty. Lockheed Martin provided support to the undergraduate and PhD programs. Xerox continued its support of Dan Huttenlocher's document imaging initiative.

Intel provided major funding to the department for research and instruction. Gifts included $100,000 to equip a new undergraduate workstation lab; $94,000 to support S. Keshav's research on network performance management; $40,000 to support Fred Schneider's research on automatic security; a fellowship to PhD student Lynette Millett; and $87,494 in equipment from Intel's Technology for Education 2000 grant.

Microsoft continued its generous support for research, instruction, and general support. Gifts included $25,000 to support Ramin's Zabih's research on automating visual tasks; $75,000 each to Werner Vogels for his work on cluster computing and Praveen Seshadri for his Predator project, and extensive donations of Microsoft software, books, and hardware.

Industrial Partners

Compaq

Digital Equipment Corporation

GTE

IBM Corporation

Intel Corporation

Lockheed Martin

Microsoft

PeopleSoft

Sun Microsystems

Xerox Corporation

These industrial partnerships are recognized as a vital part of life in this department. We remain grateful for their ongoing support of our research and instructional activities.

Inquiries about industrial partnerships may be addressed to:

Computer Science Partnerships

Department of Computer Science

4130 Upson Hall

Cornell University

Ithaca, NY 14853-7501

Telephone: (607) 255-7316

Fax: (607) 255-4428

email: chair@cs.cornell.edu

Corporate Gifts and Grants

The Department is grateful for the support, including equipment and software, provided by our industrial partners.

Air Products & Chemicals $2,500

Compaq $ 50,000

GTE Foundation $55,000

IBM $100,000

Intel Corporation $371,658

Lockheed Martin $15,000

Microsoft $1,023,918

Proctor & Gamble $5,000

Xerox Corporation $36,300

Cornell Department of Computer Science

TABLE OF CONTENTS

driven by three high-resolution, high-dynamic range digital light valve projectors that provide a life-size, 20' wide image that delivers more than four megapixels of resolution at interactive frame rates.

Our lab has been a pioneer in distance learning through the NSF Graphics and Visualization Center, a distributed center for fundamental research in computer graphics. We have six years of working together remotely, including teaching a collaborative advanced seminar in computer graphics across our five sites (Brown, Caltech, Cornell, UNC-Chapel Hill, and the University of Utah). The value of dedicated, high-bandwidth connections has been proven, but we are pushing forward to enhance the sense of direct person-to-person contact for distance learning through improved telepresence and innovative educational approaches.

The Cornell Theory Center

The Cornell Theory Center (CTC) is Cornell's high-performance computing and interdisciplinary research center. CTC's main technical research and development thrust is in large-scale NT-based cluster computing. Through its Advanced Cluster Computing Consortium (AC³), CTC acquired a 256-processor cluster - AC³ Velocity - which consists of 64 Dell PowerEdge™ servers, each with four Intel Pentium III Xeon™ 500 mhz processors and running Microsoft Windows® NT™. The primary cluster

interconnect is provided by Giganet, Inc.

Cornell is one of the leading institutions for computational science and engineering in the country, due in large part to the resources and expertise available at CTC. Associated researchers work in some of the most computationally challenging fields. The kinds of interdisciplinary research projects that need the power of AC³ Velocity include:

Computational Finance - projects such as investigating new optimization algorithms for large-scale portfolio analysis and value-at-risk calculations.

Digital Material - a virtual working environment for scientists simulating the deformation, fatigue, and failure of materials.

Computational Genomics - development of highly-advanced tools for large-scale data acquisition and analysis to understand the origins of life and the

The Program of

Computer Graphics

The Program of Computer Graphics is best known for pioneering work on realistic image synthesis, including the radiosity method for calculating direct and indirect illumination in synthetic scenes. Our long-term goal is to develop physically-based lighting models and perceptually based rendering procedures to produce images that are visually and measurably indistinguishable from real-world images, and to generate these images in real time.

Over the past two decades, we have articulated and refined a framework for global illumination research incorporating light reflection models, energy transport simulation, and visual display algorithms. Our current goal is to solve these computationally demanding simulations as fast as possible using an experimental cluster of tightly coupled processors and specialized display hardware. We are achieving this goal by taking advantage of increased on-chip processing power, distributed processing using shared memory resources, and instructional-level parallelism of algorithms.

Our graphics research also involves three dimensional modeling of very complex environments and new approaches for modeling architectural designs. We have developed a new paradigm for architectural sketch modeling on new design workstations, which allow sketching with a pen directly on a large display surface. Traditional sketching skills are augmented through 3D interfaces which merge conceptual design with rendered 3D models and allow collaborative sketching across networks, whether in the same room or across the country. These new tools are being tested each semester in a unique undergraduate architectural design studio in our lab.

New developments in image capture are also rapidly changing the way we model and render 3D environments. By extracting depth and orientation from a series of images, we can not only reconstruct seamless panoramas for passive viewing but can merge image data into 3D models for active design manipulation. Both these research projects take full advantage of a calibrated, wide-field display system

1998-1999 Annual Report

molecular processes that underlie life.

Biomedical Research - development of new algorithms and interdisciplinary approaches to molecular structure research, with a special emphasis on protein dynamics.

These projects also benefit from CTC's extensive visualization expertise and resources, including a three-wall CAVE virtual reality environment, where scientists can "immerse" themselves in their application.

CTC is an integral part of Cornell's new Computing and Information Sciences initiative, and is active in attracting new communities, such as business, the arts, and the social sciences, to advanced computing and information technologies. CTC works closely with its AC³ Infrastructure Members, among whom are Dell Computer Corporation, Intel Corporation, Microsoft Corporation, and Giganet, Inc., and with a range of corporations interested in implementing

state-of-the-art cluster environments and in having a strategic window into future technologies.

Juris Hartmanis, Graeme Bailey and Elly Hartmanis

Cornell Department of Computer Science

TABLE OF CONTENTS

Bits On Our Mind (BOOM `99)

BOOM, short for "Bits On Our Mind", is our annual undergraduate research fair, highlighting work done by students from around the university in the general area of digital information systems. The fair provides an opportunity for Cornell University students to showcase exceptional projects, research results, and creative applications involving computer-related technologies that they themselves developed or helped to develop.

BOOM '99, held on March 30, was hosted by Cornell's departments of Computer Science and Electrical Engineering and sponsored by Citibank. Over one hundred students participated.

The BOOM '99 Web site, http://www.cs.cornell.edu/boom/ , has more information, including links to descriptions of the projects and photos.

Students receiving awards

President Rawlings and Bart Selman discuss projects with students.

1998-1999 Annual Report

Awards

Teaching Awards

• Stephen Vavasis: Fiona Ip Li Excellence in Teaching Award
• Thorsten von Eicken: Abraham Wong Excellence in Teaching Award
• Praveen Seshadri: Ralph Watts Excellence in Teaching Award
• Lillian Lee: Stephen Miles Excellence in Teaching Award
  
• Outstanding Teaching Assistant Awards
• Rie Ando, Eli Barzilay, Cristian Estan, Indranil Gupta, Deyu Hu

Research Awards

• Eva Tardos: Guggenheim Fellowship
• Jon Kleinberg: Office of Naval Research Young Investigator Award
• Bart Selman: Alfred P. Sloan Research Fellowship
• Greg Morrisett: NSF Career Award

Other Awards

• Kenneth P. Birman: named Fellow, Association for Computing Machinery
• David Gries: Honorary degree of Doctor of Science (D.Sc.) from Miami University
• Juris Hartmanis: Honorary Doctor of Humane Letters Honoris Causa from the University of Missouri-Kansas City
• Charles Van Loan named to Joseph C. Ford Professorship
• Eva Tardos: Miller Visiting Professorship from UC - Berkeley
• Cornell's team won the regional competition of ACM's International Collegiate Programming Contest. The team members are David Kempe, a first-year PhD student, Erik Dangremond, a senior CS major, and Mike Smullens, a junior in biology. As regional winner, the team competed in the World Finals in Eindhoven, The Netherlands, in April, finishing in the top third at 18th. Adam Florence, the coach, is also a CS graduate student.

Graduate Student Awards

• Lynnette Millett: Intel Graduate Fellowship

Undergraduate Student Awards

• 1998-99 CRA Outstanding Undergraduate Awards: Pedro Felzenszwalb, runner-up; David Liben-Nowell, honorable mention
• Merrill Fellowships: Matthew Chiu (advisor: Brian Smith), David Liben-Nowell (advisor: Jon Kleinberg), Vladimir Livshits (advisor: Ira Wasserman, Astronomy)
• Churchill Scholar: David Liben-Nowell
• Michael Kassoff: 1999 Microsoft Junior Award
• Abhideep Singh: Frank and Rosa Rhodes Scholarship
• Jonathan E. Marx Memorial Senior Prize: Sally Chu, Ashutosh Agrawal
• Alan S. Marx Memorial Prize for Excellence Supporting Undergraduate Education: Christopher H. Jeuell
• Recipient of the Computer Science Prize for Academic Excellence: David Liben-Nowell
• Lockheed Martin Awards for Outstanding Achievement and Academic Service: Jeremy Kubica, Matthew Harren, David Feldman, Ayan Mandal, Aleksey Kliger

Julia Panke and Dexter Kozen

Cornell Department of Computer Science

TABLE OF CONTENTS

Courses and Enrollment Statistics

1998-1999 Annual Report

Courses and Enrollment Statistics

Cornell Department of Computer Science

TABLE OF CONTENTS

Educational Statistics

Courses Students Credit Hours

Fall 44 2840 9873

Spring 42 2928 10385

Total 86 5768 20258

Degrees Conferred

Degrees conferred during the 1998-1999 academic year:

159 Bachelor Degrees

47 Bachelor of Arts

112 Bachelor of Science

55 Master of Engineering

15 Doctoral Degrees

287 Total Doctoral Degrees

Awarded by the department to date

Degrees Granted

Doctor of Philosophy

August 1998

James L. Caldwell II

Professor Robert Constable

Decidability Extracted: Synthesizing "Correct-by-Construction" Decision Procedures from Constructive Proofs

Karl Fredrick Crary

Professor Robert Constable

Type-Theoretic Methodology for Practical Programming Languages

Wee-Liang Heng

Professor Eva Tardos

Approximately Optimal Elimination Orderings for Sparce Matrices

Takako Matoba Hickey

Professor Fred Schneider

Availability and Consistency in a Partitionable Low Bandwidth Network

Jing Huang

Professor Ramin Zabih

Color-Spatial Image Indexing and Applications

Induprakas Kodukula

Professor Keshav Pingali

Data-Centric Compilation

Stephen Robert Marschner

Professor D. Greenberg

Inverse Rendering for Computer Graphics

Pavel Gennadyevich Naumov

Professor Robert Constable

Formalizing Reference Types in NuPRL

Rosen Sharma

Professor S. Keshav

Internet TV

Kristen Maria Summers

Professor J. Hopcroft

Automatic Discovery of Logical Document Structure

Aswin Aalt van den Berg

Professor Tim Teitelbaum

Data Abstraction by Program Transformation in a Higher-Order Attribute-Grammar Framework

Divakar Mirle Viswanath

Professor L. Trefethen

Lyapunov Exponents from Random Fibonacci Sequences to the Lorenz Equations

Bruce Jonathan Walter

Professor D. Greenberg

Density Estimation Techniques for Global Illumination

January 1999

Vladimir Kotlyar

Professor Keshav Pingali

Relational Algebraic Techniques for the Synthesis of Sparse Matrix Programs

Mandar Mitra

Professor Claire Cardie

High-Precision Information Retrieval

1998-1999 Annual Report

Aric Phillip Shafran

Pratap Vikram Singh

Hubert YauKin Siu

Michael Sokoryansky

Daniel Jules Switkin

Bhavin Warandas Thacker

Bjorn Thordarson

Robert Liehyuan Tsai

Yiwen Wang

Victoria R. Weissman

Philip D. Yen

Brent Alexander Young

Bachelor of Arts

August 1998

Maxim Evgenevich Orlov

Jonathan Rynd

Charles Edward Saulino

January 1999

Max Attar Feingold

Melissa Rita Ho

Adi Atmaputra Jajuli

Jang Yoon Johnny Kim

Stanislav Krutonogiy

Kevin H. Lau

Roman Lobkovsky

Brian Sabino

May 1999

Robert Paul Braddock

Elizabeth Hai-ning Chan

Yelena Chigirinskaya

Timothy Chorma

Sally Chu

Christine W. Chung

Christopher L. Comarato

Harold Ober Fox

Jason Grollman

David Gutierrez

Andrew Oliver Hall

Thomas Y. Hwang

Andrew J. Lee

Blair C. Lee

Kevin Kuen-jia Lee

Brian T. Lewis

David Liben-Nowell

Gary K. Lin

Vladimir A. Livshits

Hui Qin (Fion) Luo

James Margaris

Kevin Edwin Neijstrom

Tina Ann Nolte

Yooki Park

Avery Travis Pickford

Valdis Mark Rigdon

Daniel Ryazansky

Michael C. Shen

Craig K. Sheppard

Matthew D. Steinberg

Ashish Vaidya

Martin J. Wasiak

Westley Weimer

Karen A. Wellwood

David Conrad Welte

Herman Yau

Bachelor of Science

August 1998

Pantaleo de Candia

Benjamin F. Ellett

Chris Yi-Cheng Ho

Kim Bashirul Mawla

January 1999

Stacy Ann Biko

Matthew Yu Tak Chiu

Ernest Pierre Gremillion III

Daanish Mumtaz Khan

Seth Daniel Kromholz

Joe S. Lee

Hooi Ming Ng

James Sraw Singh

Pui-yin Winfred Wong

Yu Zhao

May 1999

Ashutosh Agrawal

Mohammad Waqar Alam

Vincent Joseph Amoroso, Jr.

Michael James Babish

Anthony Peter W. J. Balandiuk

Theodore J. Bonkenburg

Reeves Hoppe Briggs

Ryan M. Burkhardt

Bryan J. Camilli

Marc S. Casalaina

Master of Engineering (CS)

August 1998

Kwan Hong Lee

Rachit Siamwalla

January 1999

Max Attar Feingold

Martin Handwerker

Han-Yang Lo

Kelly Kristine Mayoros

Mark Howard Rogge

Yevgeniy Rozenfeld

Sajani Ajesh Shah

Robert James Sudol

Joyce Jeanpin Wang

Daniel Benjamin Witriol

Ya Jie Ying

May 1999

James Thomas Ahlborn

Peter Frank Birdsall

Milos Borojevic

Stephen H. Chan

Seema Kumaran Cherangara

Chung-A Choi

Randolph Chung

Dan Mihai Dumitriu

Jason John Howes

James M. Kao

Kristopher Alan Kujawski

Jed Lin Lau

Yuan-Wei Li

Zhongwei Li

Ming Hai Lim

Newton P. Liu

Ming Lu

Xiangjiang Ma

Daniel Sunanto Mahashin

Patrick Anthony McEvoy

Shen-Ban Meng

Hooi Ming Ng

Ivan Jozef Oprencak

Michael William Panitz

David Patariu

Ernest M. Post

Salman Qureshi

Sigrun Ragnarsdottir

David Lawrence Roxe

Cornell Department of Computer Science

TABLE OF CONTENTS

Bachelor of Science

May 1999

Hsi Chan

Albert H. Chen

Po Jui Chen

Richard Ming Chen

Yen-an Chen

Victor Cheng

Jonathan J. Chern

Kevin Joseph Chipalowsky

King Chow Andy Choi

Shuo-yen Choo

Benjamin David Cichy

Yaniv Cohen

Paul Warner Coleman

Christopher Robert Como

George Leonidas Coulouris

Erik Gregory Dangremond

Giuseppe De Candia

Zheng Diao

Brian Andrew Fallik

Pedro Filipe Felzenszwalb

William James Feth

Daniel Ethan Gerstenzang

Eliot Carleton Gillum

Steven Edward Gold

Paul Anthony Gregson

Paul Seung Hahn

Jhony Pangestu Harianti

Basil B. Hayek

Jason John Howes

Sandra Janel Jackson

Christopher H. Jeuell

Todd David Johnson

Elaine Peggy Kao

Annika Karin Karlsson

Ryan Patrick Kennedy

Rishi Khanna

Gaurav Subhash Kittur

David Y. Krasnopolsky

Sidharth Kshatriya

Hian Tiat Kwa

Guo Chew Lam

Lee Yeong Wee

Joseph Paul Lemay

Maria Socorro Lemay

David Gok Louie

Christopher Kent Ma

Ned Callen McClain

Sean Michael McKenna

Martin Thomas McNamara

Nalin Mittal

Matthew Michael Monte

Michael Peter Napoleone

Adam Daniel Nathan

Andrew Clark O'Meara

Stephen Matthew Ostermiller

Warren Ouyang

Julia Elizabeth Panke

Jason Francis Pettiss

Tomasz Piech

Robert Eaton Pohl III

Kevin James Powell

Joel Manojit Raha

Madhav Ranjan

Felix Alberto Rodriguez

Jason T. Rosenthal

Subhabrata Saha

Manish Mahesh Sambhu

Alexandra Savino

Aric Phillip Shafran

Anurag Sharma

Anton Y. Shevchenko

Alexander Shvarts

Abhideep Singh

Jiesang Song

Tee Soong Tan

Victor Tao

Joshua Barnett Thorp

Lindsey Beth Weinger

Edward Weiss

Gabriel Leonard Weisz

Daniel James Wineman

Kevin Michael Wood

Thomas Francis Woodard

Jingyang Xu

Di Yan

David Charles Young

Yue Yu

Leonid Zeltser

Jon Kleinberg and David Libben-Nowell

1998-1999 Annual Report

Funded Research

Investigator Sponsor Title Award Period of Award

Birman BBN Metacomputer Across WANs 138,031 8/28/96 - 8/28/99

Birman DARPA/ Secure Realtime Process Groups in Horus: 2,620,284 6/15/96 6/14/99

ONR A Communications Infrastructure for Remote

Collaboration

Birman / DARPA Spinglass Adaptive Probabilistic 3,839,383 7/01/99 6/31/02

Constable Tools for Advanced Networks

Cardie NSF (CAREER) Knowledge Acquisition 200,000 4/1/96 3/31/00

for Natural Language Understanding
Cardie DARPA/ Improving End-User Efficiency in a 12/1/96 11/30/99

TIPSTER TIPSTER-Compliant IR System

text Prog.
Coleman DOE Efficient Algorithms for Large-Scale 1,287,288 5/1/86 9/14/00
Constrained Optimization with Application
to Inverse Problems

Constable/ DARPA/ Construction Methodologies for Improving 3,348,555 8/15/95 9/30/00
Birman AF Distributed System Security
Constable ONR Steps Toward A Unified Theory of Algori- 590,000 6/1/92 11/30/98

thms, Propositions, & Types
Constable DARPA/ An Open Logical Programming Environ- 1,250,000 6/2/98 6/1/00

AF ment: A Practical Framework for Sharing
Formal Models
Constable NSF Creating and Evaluating Interactive Formal 283,975 1/1/99 12/31/01

Courseware for Mathematics and Computing
Constable NSF Unified Theory of Algorithms 590,000 6/01/92 9/30/98
Department NSF A Next Generation Computing and Comm- 1,271,298 7/1/97 6/30/02

unications Substrate
Elber NIH Physiology of Ionic Channels: Extended 62,325 1/1/99 4/30/00

Simulations
Gomes/ AF Integration of AI/OR Techniques 203,677 3/1/98 2/28/99

Selman
Gomes / AF Compute-Intensive Methods for Combinat- 395,817 3/1/99 2/28/00
Selman orial Problems

Gomes AF A Platform for the Experimental Study of 158,076 3/15/99 3/14/00
Compute-Intensive Combinatorial Methods

in Planning

Gomes AF Hybrid Approaches for Combinatorial 304,835 3/1/99 2/28/00
Problems

Halpern NSF A Qualitative Framework for Reasoning Un- 348,000 9/1/96 8/30/99
der Uncertainty

Huttenlocher/ DARPA/ Robust, Online Event Detection and Class- 1,180,699 4/1/97 3/31/02
Zabih ARO ification for Video Monitoring

Cornell Department of Computer Science

RESEARCH

Funded Research
Investgator Sponsor Title Award Period of Award

Keshav Sloan Sloan Research Fellowship 35,000 9/16/97 8/15/99
Keshav Intel Network Performance Management 80,000 6/1/98 6/30/99

Kleinberg NSF (CAREER) Algorithmic Methods for Networks 200,000 4/1/97 3/31/01
Kleinberg Sloan Sloan Research Fellowship 35,000 9/16/97 9/15/99

Kleinberg ONR YIP: Algorithms for Networks and Link-Struct- 305,000 5/1/99 4/30/02
ured Data

Kozen DARPA/ Formal Methods for Software Certification 291,000 8/15/97 7/31/00

NSF

Krafft DARPA/ Network CS Technical Report Library: A Com- 900,000 8/1/96 7/31/99

CNRI munity Resource & Laboratory

Lagoze / CNRI Digital Library Testbed Program 915,000 4/1/98 3/31/01

Arms

Morrisett NSF Safe Low-Level Program Languages 205,000 3/1/99 2/28/03

Morrisett Sloan Sloan Research Fellowship 35,000 9/16/98 9/15/00

Morrisett NSF CAREER: Design, Applications, and Foundations 205,000 3/01/99 2/28/03

of Safe, Low-Level Programming Languages
Pingali NSF Automatic Blocking of Dense Matrix Codes for 368,689 8/15/97 8/31/00

Memory Hierarchies
Rubinfeld ONR/ Semantic Consistency in Information Exchange 450,000 4/30/97 4/29/02

Stanford
Rubinfeld ONR The Theory and Implementation of Self-correcting, 139,575 5/1/95 4/30/99

Self-testing and Checking Programs (AASERT)
Rubinfeld NSF (CAREER) Algorithms for Self-testing/correcting 200,000 5/15/96 4/30/00

Programs and Learning

Rubinfeld Sloan Sloan Research Fellowship 35,000 9/16/96 9/15/99

Schneider DARPA/Formal Support for High Assurance Systems 632,751 4/1/94 3/31/99
NASA

Schneider/ AFOSR Mobile Agents and System Principles 697,485 12/15/96 12/14/99
Morrisett

Schneider DARPA/Survivability of Information Systems 1,038,680 9/1/96 8/31/99
AF

Schneider Intel Security Automation SFI 40,000 6/1/98 6/30/99
Schneider/ DARPA Containment and Integrity for Mobile Code 2,197,784 6/16/99 6/15/02

Myers
Selman NSF (CAREER) Compute Intensive Methods for AI 300,000 6/1/98 5/31/02

Seshadri NSF Jaguar: JAVA in Next-Generation Database System 370,000 9/1/98 8/31/01

Seshadri NSF (CAREER) Database Query Processing for 289,000 9/1/97 8/31/02
Complex Data

Seshadri AF JAGUAR: Extending the Predator Database 200,000 9/30/98 3/31/00
System with Java

Smith Sloan Sloan Research Fellowship 35,000 9/16/97 8/15/99

1998-1999 Annual Report

RESEARCH

Funded Research

Investgator Sponsor Title Award Period of Award

Smith/ DARPA/ Platform Technologies for Advanced Remote 2,022,987 6/1/95 6/30/99
Von Eicken ONR Collaboration

Tardos DARPA/ Efficient Resource Management in High-Speed 801,548 4/1/98 3/31/01
ONR Networks

Tardos NSF Algorithmic Issues in Communication Networks 249,559 7/1/97 6/30/00

Toueg NSF Applications of Failure Detection 230,000 9/1/97 8/31/00

Trefethen NSF Non-Normal Matrices and Operators: Analysis, 276,500 8/1/95 7/31/98

Computations, Applications

Van Loan NSF New Applications and Algorithms that Involve 247,874 8/01/99 7/31/02

the Kronecker Product

Vavasis NSF Applications of Weighted Least Squares 117,562 7/1/97 6/30/00

von Eicken Sloan Sloan Research Fellowship 30,000 9/16/95 9/15/98
von Eicken NSF (CAREER) Developing Secure Systems for 205,000 4/1/97 3/31/01

Network Appliances
von Eicken Intel U-Net Cluster: A Communication Architecture for 61,000 12/1/96 Open

High-Performance PC Clusters

Zabih NSF Dynamic Contextual Recognition of Moving Objects 150,000 9/1/99 8/31/02

Zippel/ DARPA/ Active Models in Support of Collaborative Design 1,080,000 4/1/96 12/31/99
Constable ONR

Jon Kleinberg, Mrs Liben-Nowell, David Liben-Nowell and Dan Huttenlocher

Cornell Department of Computer Science

TABLE OF CONTENTS

Submitted Research Proposals

Investigator Sponsor Title Award Period of Award
Arms NSF Reference Links As a Measure of Changing 591,317 1/01/00 12/31/02 Scientific Communication

Constable NSF Enhancing Proof Assistant Systems 22,200 1/01/00 12/31/01

Cardie NSF An Integrated Approach for Reducing Infor- 565,723 1/01/00 12/31/02
mation Overload in Digital Library Text Retr-

ieval Systems

Cardie DARPA Rapidly Portable Translingual Information 2,073,410 1/01/00 12/31/03

Extraction and Interactive Multidocument

Summarization

Elber NIH Long Time Dynamics of Biomolecules 1,625,600 4/01/00 3/31/05

Elber NSF Kinetics of Ion Channels by Atomically 465,644 4/1/00 3/31/03

Detailed Computer Simulations

Gomes DARPA Fusion of Concepts from Artificial Intell- 705,780 8/01/99 2/28/01

igence, Operations Research and Control

Theory for Command and Control of Military
Operations
Lagoze NSF Integrating and Navigating Eprint Archives 291,651 9/01/99 8/31/02

Through Citation-Linking
Lagoze NSF Metadata for Resource Discovery of Multi- 240,000 6/01/99 5/31/02
media Digital Objects

Lee NSF CAREER: Exploiting Unannotated Data for 471,500 1/01/00 12/31/03

Natural Language Processing
Pingali/Illinois NSF Advanced Compilation Techniques for 399,999 6/1/99 5/31/02

MATLAB
Pingali/Dela. NSF Next Generation Software 503,665 5/1/99 4/30/02
Pingali/Dela. NSF A Threaded Virtual Machine for a New Gen- 244,706 2/1/00 1/31/03
eration of High Performance Parallel Systems

Schneider/ AFOSR Language Based Security for Extensible 846,391 1/01/00 12/31/02
Morrisett Systems

Seshadri DARPA Flexible Decision Support in Device-Satura- 2,695,390 6/01/99 5/31/02
ted Environments

Collaborative Funded Research at Cornell

Investigator Sponsor Title Award Period of Award
Birman / NSF EPRI - Minimizing Failures While Maintai- 600,000 1/1/99 12/31/03

Schneider/ EE / ning Efficiency of Complex Interactive Net-

Theory Ctr worked Systems
Coleman / NIH Parallel Processing Resource for Biomedical 5,002,410 11/15/97 11/30/01

Theory Ctr Scientists
Coleman/ NSF Efficient Algorithms for Large Scale Linear 28,000 8/15/97 7/31/00

Applied Math and Non-linear Finite Element Computations
with Applications to Thin Shell Structures

1998-1999 Annual Report

Investigator Sponsor Title Award Period of Award

Coleman/ NSF Center for Theory & Simulation in Science 110,000,000 10/1/90 12/31/98
Theory Ctr & Engineering
Coleman / SGI Cornell Computational Finance Institute 913,670 3/23/99 11/29/01

Theory Ctr
Coleman / NYS Dorm- Supercomputer Center Operational Support 1,200,000 5/1/98 4/30/99

Theory Ctr Authority
Coleman / NSF Parallelism & Practical Application of Auto- 46,200 5/1/97 4/30/99
Theory Ctr matic Differentiation

Department NSF Computational Aspects of Cognitive Science 562,500 9/1/95 8/31/00

(Training Grant)

Lagoze/ NSF Security and Reliability in Component-based 2,268,608 5/1/99 4/30/03

Birman/ Digital Libraries
Schneider/

Library
Pingali/

Vavasis/CEE NSF Crack Propagation on Tera Flop Computers 1,799,924 1/15/98 12/31/00
Tardos/MSI ONR Computational and Mathematical Investiga- 345,994 10/1/95 9/30/98

tion in Optimization

Submitted Collaborative Research Proposals
Investigator Sponsor Title Award Period of Award

Pingali/ NSF A Two Tier Computation and Visualization 1,500,000 7/1/99 6/30/04
Theory Center Facility for Multiscale Problems
Pingali NSF Advanced Compilation Techniques for 400,000 6/1/99 5/31/02
MATLAB

Selman/ NSF Modeling and Decision-Making for Fourth 942,197 9/1/99 8/31/02
Halpern / Generation Wireless Systems

EE

Total expenditures for fiscal year 1998-1999: $ 8,978,968

Cornell Department of Computer Science