Stuart Allen
Research Associate

Stuart Allen received a bachelor’s degree in computer science from the University of New Orleans in 1978,
and a Ph.D. in computer science from Cornell in 1987. He has held several positions at Cornell since, and is
currently a research associate in CS.

Allen’s principal interest is in making computer manipulable formal data an adjunct to, and ideally a medium for, precise human expression, especially argument. This involves the design, justification, and employment of practical formal systems and notations.

The bulk of his work has been in relation to the PRL project (, which has traditionally focused on constructive theory of types and proof by means of tactics. In addition to theory, application, and explanation of type theory–based practice, he has been interested in formalizing and exploiting conventional mathematical notations, as well as the development of interfaces for user immersion in bodies of formal data.

Most recently, Allen’s efforts (as part of the PRL project) have been directed at designing methods for implementing digital collections grounded in formal material, especially proof, emphasizing theoretical neutrality and anticipating the coexistence of material with distinct, possibly conflicting, formal bases, entailing the need for strict yet extensible logical accounting.

William Y. Arms

William Arms received his B.A. degree in mathematics from Oxford University in 1966, and his M.Sc. (Econ.) from the
London School of Economics in 1967. He obtained his doctorate (D.Phil.) in operational research from the University of Sussex in 1973. He has been a professor in CS since 1999 and director of the Information Science Program since 2002.

Arms’s interests concentrate on Web information systems, digital libraries, and electronic publishing. These fields
integrate methods from many disciplines, so that the work ranges from technical topics, such as distributed computing
and information representation, to the economic and social aspects of change. His book, Digital Libraries, was published by the M.I.T. Press in winter 2000. The Cornell Digital Libraries Research Group received a major grant to build the core system for the NSF’s new digital library for science, mathematics, engineering, and technology education. This is likely to be the largest and most heterogeneous digital library yet attempted. One of Arms’s principal interests is the change in scientific publication as online materials replace printed journals as the primary means of creating, storing, and distributing research information.

Professor Arms has recently completed a term as chair of the Association for Computing Machinery (ACM) Publications Board. He is a member of the M.I.T. Press Management Board, and a member of a strategic-planning committee of the American Physical Society.

“Core Services in the Architecture of the National Digital Library for Science Education (NSDL)”. Joint Conference on Digital Libraries (July, 2002). (With C. Lagoze, S. Gan, D. Hillmann, C. Ingram, D. Krafft, R. Marisa, J. Phipps, J. Saylor, C. Terrizzi, W. Hoehn, D. Millman, J. Allan, S. Guzman-Lara, and T. Kalt)
“A Spectrum of Interoperability. The Site for Science Prototype for the NSDL”. D-Lib Magazine 8(1) (January, 2002). (With D. Hillman, C. Lagoze, D. Krafft, R. Marisa, J. Saylor, C. Terrizzi, and H. Van de Sompel)
“What Are the Alternatives to Peer Review? Quality Control in Scholarly Publishing on the Web”. Journal of Electronic Publishing 8(1) (August 2002).

Graeme Bailey

Graeme Bailey received a bachelor’s degree in mathematics in 1973, and a M.Sc. in pure mathematics in 1974, from the University of Birmingham. He obtained a Ph.D. in pure mathematics (low-dimensional topology and combinatorial group theory) in 1977 from the University of Birmingham as well. He has been a professor in CS and an adjunct
professor in Cornell’s Department of Mathematics since 1988. He is the director of the College of Engineering’s Master of Engineering degree program in computer science.

Originally working in low-dimensional topology and combinatorial group theory, through an odd mixture of circumstances Bailey has become actively involved in research in mathematics and medicine. One of two ongoing research projects in this area is the modeling of lung inflation, together with a research group at the Class One Trauma Center at the Upstate Medical University, in Syracuse, N.Y. This is in the early stages of a program to extend to various pathologies affecting elasticity and aimed towards effective clinical treatments. The group, having made some significant advances in answering questions that had remained unsolved for more than thirty years, is now in the process of trying to obtain reliable mathematical models. This involves building computer simulations of dynamic-packing results under constrained perturbations and deformations.

The other project is in understanding deformations of transmembrane proteins used in cell-signaling processes. This is a carefully constrained version of the protein-folding problems that have been exciting the mathematical-biology community in recent years; the application of a topological viewpoint in collaborating with molecular pharmacologists
and structural biologists has already yielded some intriguing insights.

Bailey is the recipient of the Kenneth A. Goldman ’71 Excellence in Teaching Award 2000, and the Kendall S. Carpenter Memorial Advising Award for 2002.

Martin Burtscher
Assistant Professor
Member of the School of Electrical and Computer Engineering and
the Graduate Field of Computer Science

Martin Burtscher received his Ph.D. degree in computer science from the University of Colorado at Boulder in 2000
and his B.S./M.S. degree in computer science from the Swiss Federal Institute of Technology (ETH) Zurich in 1996.
He is an assistant professor in ECE at Cornell.

His research interests include high-performance microprocessor architecture, instruction-level parallelism, and compiler optimizations. High-end microprocessors rely on a variety of predictors for good performance. Future CPUs will likely need even more predictors to meet the continuing demand for more and more processing power. Designing, evaluating, and improving such predictors is an important focus of Burtscher’s research.

Ongoing projects include locating novel domains that can benefit from prediction, adding compiler support to aid
and simplify the prediction hardware, devising means to reduce predictor sizes and power consumption without
compromising performance, discovering as-of-yet unobserved patterns to build new predictors, and using
value-prediction techniques to enhance branch-prediction accuracy and data-compression rates.

“Hybrid Load-value Predictors”. IEEE Transactions on Computers 51(7) (July, 2002). (with B. Zorn)
“Delphi: Prediction-based Page Prefetching to Improve the Performance of Shared Virtual Memory Systems”. International Conference on Parallel and Distributed Processing Techniques and Applications (June, 2002). (With E. Speight)
“Static Load Classification for Improving the Value Predictability of Data-cache Misses”. Conference on Programming Language Design and Implementation (June, 2002). (With A. Diwan and M. Hauswirth)

Kenneth P. Birman

Ken Birman obtained a bachelor’s degree in computer science at Columbia University in 1978 and a Ph.D. in computer science at the University of California at Berkeley in 1981. He joined the CS faculty in 1982.

Birman’s research is concerned with reliability and security in modern networked environments. In past work on the Isis system, his software became a central part of the New York Stock Exchange and Swiss Stock Exchange (in both settings, Isis runs the core messaging component used to distribute new stock quotes and information about trades
reliably and securely), the French air-traffic control system (Isis is used to keep clusters of three to five controller workstations synchronized, and handles failures), the U.S. Navy’s Aegis warship’s radar system, and other mission-critical computer networks.

Birman’s current focus is on a new system called “Astrolabe”, which was developed as part of a DARPA–funded Spinglass effort ( Spinglass). Astrolabe is like a network-wide database in which each computer or component contributes a live tuple. As data changes, Astrolabe propagates the updates.
The system uses a form of dynamically materialized view to continuously compute summaries of the picture of the network as a whole. This results in a powerful new tool for distributed monitoring, management, control, and live collaboration. A second part of Spinglass is concerned with reliable multicast. Birman’s group has developed a scalable multicast protocol that gives probabilistic consistency guarantees, and integrated it with Astrolabe. Underlying both systems is a class of reliable peer-to-peer communication protocols that are extremely scalable and provide probabilistic reliability techniques. The approach permits the development of systems that work as well with ten thousand computers as they do with just ten.

Birman was named an ACM Fellow in 1999 and won the Stephen ’57 and Marilyn Miles Excellence in Teaching Award in 2000. He was editor in chief of ACM Transactions on Computer Systems from 1993 to 1997, and has served on a number of university committees. Birman is chairman of the Responsible Conduct of Research Committee and is a member of the Founding Committee for the CIS faculty; the Engineering College Policy Committee; and the IP Advisory Council for the Cornell Research Foundation.

“Astrolabe: A Robust and Scalable Technology for Distributed Systems Monitoring, Management, and Data Mining”. In ACM Transactions on Computer Systems (May, 2003) 21(3). (With R. Van Renesse and W. Vogels)
“Bimodal Multicast”. ACM Transactions on Computer Systems 17(2) (May, 1999): 41–88. (With M. Hayden, O. Ozkasap, Z. Xiao, M. Budiu, and Y. Mirsky)
Building Secure and Reliable Network Applications. Manning Publications and Prentice Hall (December, 1996).
“Software for Reliable Networks”. Scientific American 274(5) (May, 1996): 64–69. (With R. van Renesse)

Kavita Bala
Assistant Professor

Kavita Bala received her Ph.D. in computer science at the Massachusetts Institute of Technology (M.I.T.). After her
doctorate, she worked as a post-doctoral researcher in the Program of Computer Graphics at Cornell. She joined CS as an assistant professor in the fall of 2002.

Bala’s research is in the area of computer graphics; her research interests include algorithms and systems for
interactive rendering, image-based modeling and rendering, and augmented reality. Increasingly, technology
is permitting the acquisition of complex data sets; rendering with these data sets remains a challenge. Bala’s
research focus is on scalable algorithms for rendering complex scenes with both high fidelity and interactive
performance. This research is applicable to both synthetic and augmented-reality rendering. Bala has developed
compact, high-dimensional representations and algorithms for interactive rendering of complex dynamic scenes while
bounding approximation error. She has also developed hybrid hardware and software algorithms for fast highfidelity
image generation.

“Combining Edges and Points for Interactive High-Quality Rendering”. In Proceedings of SIGGRAPH 2003 (July, 2003). (With B. Walter and D. Greenberg)
“Adaptoive Shadow Maps”. In Proceedings of SIGGRAPH 2001 (August, 2001). (With R. Fernando, S. Fernandez, and D. Greenberg)
“Radiance Interpolants for Accelerated Bounded-error Ray Tracing”. ACM Transactions on Graphics 18(3) (July, 1999): 213–256. (With J. Dorsey and S. Teller)

Claire Cardie
Associate Professor

Claire Cardie obtained a B.S. in computer science from Yale University in 1982 and an M.S. and Ph.D. in computer
science at the University of Massachusetts at Amherst in 1994. She has been a CS faculty member at Cornell since

Cardie’s research is in the areas of natural language processing and machine learning. In particular, her group
has focused both on building systems for large-scale natural language processing tasks like information
extraction, question-answering, and multidocument summarization, and on developing corpus-based machine
learning techniques to address underlying theoretical problems in the syntactic and semantic analysis of natural

Cardie is a recipient of a NSF Faculty Early Career Development (CAREER) Award (1996–2000) and was
program chair for the Second Conference on Empirical Methods in Natural Language Processing in 1997. She
has been secretary of the Association for Computational Linguistics Special Interest Group on Natural Language
Learning (1999–2001), and is currently serving a four-year term as secretary of the North American Association
for Computational Linguistics.

“Improving Machine Learning Approaches to Coreference Resolution”. Proceedings of the Fortieth Annual Meeting of the Association for Computational Linguistics (2002). (With V. Ng)
“A Cognitive Bias Approach to Feature Selection and Weighting for Case-based Learners”. Machine Learning 41(1) (2000): 85–116.
“Error-driven Pruning of Treebank Grammars for Base Noun Phrase Identification”. In Proceedings of the Annual Conference of the Association for Computational Linguistics (1998): 218–224. (With D. Pierce)

Rich Caruana
Assistant Professor

Rich Caruana obtained his Ph.D. in computer science from Carnegie Mellon University in 1998. Currently he is an assistant professor in CS, where he does research in machine learning and data mining. His current focus is on ensemble learning, inductive transfer, rank learning, adaptive clustering, and applications of these methods to problems in medical-decision making and protein-folding.

Inductive transfer is a subfield of machine learning that aims to achieve better performance by learning related problems simultaneously—surprisingly, sometimes it is easier to learn 100 problems at the same time than to learn any one of them in isolation. Caruana helped create this subfield by publishing the first paper on multitask
learning ten years ago.

Learning rankings is an exciting new area in machine learning that has important applications in information retrieval and medicine. Caruana is developing algorithms that learn rankings for problems in medical-decision making where it may be difficult to assess absolute risk for a patient, but easier to learn to order patients by relative risk. He developed the first machine-learning algorithm specifically designed to learn rankings. This method outperformed a dozen other learning methods in a multiinstitutional pneumonia-risk prediction project.

In 2000–01 Caruana led a team of researchers that developed the first automated system for the early detection of bioterrorist releases of anthrax. The system applies data mining to consumer purchases in supermarkets to look for unexplained increases in the sales of products such as analgesics and cough syrup.

Caruana’s work in ensemble learning and clustering are new focuses for him. His interest in clustering arose from limitations he discovered when applying traditional clustering methods to the protein-folding problem with colleagues in bioinformatics. The research in ensemble learning arose from a competition in a machine-learning course he teaches at Cornell where students use different learning methods to make accurate predictions for a mystery data set.

A theme that runs through all of Professor Caruana’s work is the importance of developing methods that are effective on real-world problems. He likes to mix algorithm development with applications work to insure that the methods are useful.

“Multitask Learning”. Machine Learning 28 (1997): 41–75.
“Using the Future to `Sort Out’ the Present: Rankprop and Multitask Learning for Medical Risk Evaluation”. Advances in Neural Information Processing Systems 8 (1996). (With S. Baluja and T. Mitchell)
“Early Statistical Detection of Anthrax Outbreaks by Tracking Over-the-counter Medication Sales”. Proceedings of
the National Academy of Sciences
99(8) (April, 2002): 5237–5240. (With A. Goldberg, G. Shmueli, and S. Feinberg)

L. Paul Chew
Senior Research Associate

Paul Chew received his Ph.D. in computer science from Purdue University in 1981. He served as a faculty member
at Dartmouth College until 1988 when he joined CS at Cornell as a senior research associate.

Chew’s primary research interest is in geometric algorithms with an emphasis on practical applications. These practical applications have included placement, motion planning, vision, sensing, mesh generation, molecular matching, and protein shape–comparison. The work on protein shape–comparison has been used as part of the evaluation scheme for CAFASP (Critical Assessment of Fully Automated Structure Prediction), a competition held every two years to evaluate the performance of fully automatic servers for protein-structure prediction. Chew developed backwards analysis, a method now widely used for analyzing randomized algorithms. Chew’s work on mesh generation has been motivated by the finite-element method, a technique for finding approximate solutions to
partial differential equations. The first step of this method is to create a mesh, i.e., to divide the given problem
region into simple shapes called elements. For complex geometries mesh generation can be difficult. Chew has
developed methods for automatically generating a high quality mesh. This work is being used in a large,
multidisciplinary project: developing adaptive software for field-driven simulations.

Chew is an associate editor for Pattern Recognition, the journal of the Pattern Recognition Society. He is also a
member of the steering committee for the International Meshing Roundtable.

“Unit-vector RMS (URMS) as a Tool to Analyze Molecular Dynamics Trajectories”. Proteins: Structure, Function and Genetics 37 (1999): 554–564. (With K. Kedem and R. Elber)
“Voronoi Diagrams of Lines in 3-space Under Polyhedral Convex Distance Functions”. Journal of Algorithms 29(2) (1998): 238–255.
(With K. Kedem, M. Sharir, B. Tagansky, and E. Welzl)“Constrained Delaunay Triangulations”. Algorithmica 4(1) (1989): 97–108.

Thomas F. Coleman
Director, Cornell Theory Center
Director, CTC–Manhattan

Thomas F. Coleman obtained his bachelor’s degree in mathematics in 1975, and his master’s in mathematics in 1976, both from the University of Waterloo. He received a Ph.D. in mathematics from Waterloo as well, in 1979. He is currently a professor of computer science and applied mathematics at Cornell, and also the director of both the CTC, a center for the support of large-scale computational science, and CTC–Manhattan, a computational finance center in New York City.

With colleagues Shirish Chinchalkar, Yohan Kim, Yuying Li, Peter Mansfield, and Arun Verma, Coleman is developing a variety of tools and methods for computational finance in the areas of portfolio management and options pricing (and hedging). Several Ph.D. students in the Center for Applied Mathematics are also involved in this work: Jay Henniger, Cristina Patron, Siddharth Alexander, Katharyn Boyle, and Changhong He. In their most recent academic work, “Derivative Portfolio Hedging Based on CVaR”, an efficient new way to hedge large portfolios of derivative
instruments is proposed.

Coleman’s specific interests include the computation of implied volatility surfaces from option prices, hedging techniques, index tracking, portfolio optimization, and the use of parallel computing techniques in computational finance.

Professor Coleman is a member of both the admissions committee and the program committee for the Center for Applied Mathematics. He is the author of two books on computational mathematics, the editor of four proceedings, and has published over sixty journal articles. He was chair of the SIAM Activity Group on Optimization (1998–2001) and serves on the editorial boards of numerous professional journals.

“Reconstructing the Unknown Local Volatility Function”. Journal of Computational Finance 2(3) (Spring, 1999): 77–102. (With Y. Li and A. Verma)
“The Efficient Computation of Sparse Jacobian Matrices Using Automatic Differentiation”. SIAM Journal on Scientific Computing 19(4) (1998): 1210–1233. (With A. Verma)
“Large Sparse Numerical Optimization”. Lecture Notes in Computer Science 165 (May, 1984): 105 p.

Alan J. Demers

Alan J. Demers received his bachelor’s degree in physics from Boston College in 1970. He obtained his Ph.D. in
computer science from Princeton University in 1975. Demers was at Cornell from 1975 to 1984. He then worked
at Xerox PARC in Palo Alto as a principal scientist, and at Oracle Corporation as an architect, before returning to
CS in 2000.

Demers’s research concerns aspects of weakly consistent data replication in databases, sensor networks, and
distributed systems. With Ken Birman, Robbert van Renesse, Johannes Gehrke, and others, he is studying
randomized “gossip protocols”. Such protocols are highly fault-tolerant and, when properly designed, extremely
scalable as well. The group is studying convergence properties of several flat and hierarchical versions
of the basic protocols tailored to specific application requirements.

More specifically, Demers’s focus is approximate evaluation of aggregate queries in such a system. He is studying
age distributions of gossiped data in order to prove probabilistic bounds on the quality of aggregate query results. Alternatively, the group can use this approach to bound the latency required to probabilistically guarantee
a client-specified degree of consistency. In addition, they are considering algorithms for specific problems that
frequently occur in high-level protocols: for example, accurate estimation of the size of a group with no initial

Finally, they are studying graph constructions for which flooding or deterministic gossip partner–choices can be
used, leading to reduced overhead while still retaining most of the desirable properties of randomized gossip.
These techniques are being adapted to achieve energyefficient routing in ad-hoc sensor networks.

“KELIPS: Building an Efficient and Stable P2P DHT through Increased Memory and Background Overhead”. In Proceedings of the Second International Workshop on Peer-to-Peer Systems (IPTS03) (February, 2003). (With I. Gupta, K. Birman, P. Linga, and R. Van Renesse)
“Research Issues in Distributed Mining and Monitoring”. In informal proceedings of the NSF workshop on next-generation data mining (NGDM02) (Baltimore, Maryland: November, 2002). (With J. Gehrke and M. Riedewald)
“Spatial Gossip and Resource Location Protocols”. In Proceedings of the Thirty-third ACM Symposium on Theory of Computing (July, 2001): 163–172. (With D. Kempe and J. Kleinberg)

K-Y. Daisy Fan
Assistant Professor

Daisy Fan obtained her B.Sc. and M.Sc. degrees in civil engineering at the University of Manitoba in 1994 and 1997, respectively, and her Ph.D. degree in civil and environmental engineering at Cornell in 2002. She is currently an assistant professor in CS. Her research interests include the application of systems-analysis techniques for water-resources and environmental problems. Problems she has investigated include optimal control of multiple-reservoir operation using stochastic dynamic programming and river-basin water quality management. She teaches CS 100, and with Professor David Schwartz, develops the academic-excellence workshops that are associated with the programming courses.

Fan is the director of the Summer College Explorations in Engineering Seminar for high school students. She actively participates in outreach initiatives, including Cornell’s CURIE Academy, which showcases engineering to high school girls.

Fan is a recipient of a Graduate Teaching Assistant Award in CS (2000), a New York State American Water Works Association Russell L. Sutphen Scholarship (2000), and a Cornell School of Civil and Environmental Engineering John E. Perry Teaching Assistant Prize (1999).

“Regression Dynamic Programming for High-dimensional Continuous-state Problems”. In preparation for submittal to Operations Research. (With C. Shoemaker and D. Ruppert)
“First Programming Course in Engineering: Balancing Tradition and Application”. In Proceedings of the Annual Conference and Exposition of the ASEE (June, 2003). (With D. Schwartz)
“Stochastic Multiple-reservoir Optimization Using Regression Dynamic Programming”. In Proceedings of World Water and Environmental Resources Congress, (May, 2001).

Robert Constable
Dean for Computing and Information Science

Robert L. Constable is the Dean for Computing and Information Science, and a professor in CS. He obtained his Ph.D. in mathematics from the University of Wisconsin in 1968. He served as CS chair from 1994 to 1999. He was also acting chair from 1993 to 1994.

Constable’s research has focused on building a system called a logical programming environment (LPE). It provides substantial automation in the design, coding, verification, and evolution of large software systems. Generally an LPE will integrate programming languages and logics. In his group’s case, they integrate the ML programming language
and a programming logic based on type theory. Reasoning about ML programs is founded on type theoretic semantics for ML. The LPE also integrates a compiler, a theorem prover, and a formal digital library. Constable’s group uses the latest version of Nuprl as the prover.

He is also working with others to build the formal digital library component of the LPE that will allow interactive access to theorems and proofs from Nuprl, MetaPRL, PVS, and other major theorem provers. The library includes over ten thousand theorems. Many of these are used in system verification, but a large number are from general mathematics.
These general theorems are a valuable resource. The group is funded by the Office of Naval Research (ONR) to further develop and explore the concept of a formal digital library of constructive mathematics built around these theorems. Their theorem provers are used in a variety of other projects as well, including the creation of formal
courseware by S. Allen, the translation of formal proofs into natural language by Amanda Holland–Minkley, the automatic analysis of the computational complexity of higher-order programs by Ralph Benzinger, and efficient reflection being designed and implemented by Eli Barzilay.

Constable is the director of the PRL Project, and a member of the Cognitive Studies executive committee; the applied math policy committee; and the LICS General Committee. He serves as editor for the Journal of Logic and Computation; Formal Methods in System Design; and the Journal of Symbolic Computation.

“Naive Computational Type Theory” In Proof and System Reliability, Proceedings of the International Summer School Marktoberdorf, July 24 to August 5, 2001 (H. Schwichtenberg and R. Steinbruggen, eds): 213–260. NATO Science Series II, Kluwer Academic Publishers, Amsterdam.
“Computational Complexity and Induction for Partial Computable Functions in Type Theory” In Reflections:
A Collection of Essays in Honor of Solomon Feferman, Association for Symbolic Logic
(2001). (With K. Crary)
“Nuprl’s Class Theory and its Applications”. In Foundations of Secure Computation, F. L. Bauer and R. Steinbruggen, eds. IOS Press, 2000: 91–115 (2000).

Ron Elber

Ron Elber obtained a bachelor’s degree in chemistry and physics in 1981, and a Ph.D. in theoretical chemistry in
1984 at the Hebrew University of Jerusalem. He was a postdoctoral fellow in theoretical biophysics from 1984
to 1987 at Harvard University. Ron was on the chemistry faculty of the University of Illinois (1987–1992) and on
the chemistry and biology faculty at Hebrew University of Jerusalem (1992–1999). Since 1999 he has been on the CS
faculty, where he is currently a full professor. Ron is also a faculty member of the Department of Biological Statistics
and Computational Biology.

Ron’s research is in computational biology and bioinformatics. His group is developing novel tools (MOIL) to simulate dynamics of biological macromolecules. His current research focuses on algorithms to extend the time scales of simulations, and to study complex processes such as the kinetics of protein folding. Ron’s techniques for path following and enhanced sampling are in wide use and motivated the development of related algorithms.

His bioinformatic investigations focus on protein annotation, using sequence-to-structure matches (LOOPP).
LOOPP linked a gene that influences the size of the tomato fruit with a human protein that controls cell growth and
may cause cancer.

Ron received the Stein award for his Ph.D. studies (1984), and the Camille and Henry Dreyfus New Faculty Award
(1987–1990). He was a University of Illinois Scholar (1991–1992). Ron received the Alon new faculty award (1992–1994), and the Bergman award (1994).

“An Anatomically Detailed Study of the Folding Pathways of Protein A with the Stochastic Difference Equations”. PNAS 99 (2002). (With A. Ghosh and H. Scheraji)
“Cloning, Transgenic Expression and Function of fw2.2: a Quantitative Trait Locus Key to the Evolution of Tomato Fruit”. Science 289 (July, 2000): 85–88. (With Anne Frary, T. Nesbitt, Amy Frary, S. Grandillo, E. van der Knaap, B. Cong, J. Liu, J. Meller, K. Alpert, and S. Tanksley)
“Anharmonic Wavefunctions of Proteins: Quantum Self-consistent Field Calculations of BPTI”. Science 268 (1995): 1319–1322. (With A. Roitberg, R. Gerber, and M. Ratner)

Johannes Gehrke
Assistant Professor

Johannes Gehrke obtained his Ph.D. in computer science at the University of Wisconsin at Madison in 1999, and he
has been an assistant professor in CS since then.

Gehrke’s research interests are in the areas of data mining, data stream processing, and novel applications of
distributed database technology. In his current research, he is working on integrating complex querying
capabilities into wireless sensor networks and peer-to-peer networks, and he is developing database techniques
for high-speed data streams. His data mining research includes privacy-preserving data mining, theoretical
foundations of data mining, and high-performance data mining algorithms, and his group has developed some
of the fastest known algorithms for several important data mining tasks.

Gehrke is a recipient of an Alfred P. Sloan Fellowship (2003), a National Science Foundation CAREER Award
(2002), an IBM Faculty Award (2000 and 2001), and the Cornell College of Engineering James and Mary Tien
Excellence in Teaching Award (2001).

“Approximate Join Processing over Data Streams”. In Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD 2003) (San Diego, California: June, 2003) (With A. Das and M. Riedewald)
“Limiting Privacy Breaches in Privacy Preserving Data Mining”. In Proceedings of the Twenty-Second ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (San Diego, California: June, 2003). (With A. Evfimievski and R. Srikant)
Database Management Systems, third ed. (2002). McGraw Hill. (With R. Ramakrishnan)

Paul Ginsparg
CIS, joint with Physics

Paul Ginsparg received his A.B. in physics from Harvard University in 1977 and his Ph.D. in physics from Cornell
in 1981 (Quantum Field Theory, thesis advisor: Kenneth G. Wilson). He was in the Harvard Society of Fellows from
1981–84, and a junior faculty member in the Harvard physics department from 1984–90. From 1990–2001, he
was a technical staff member in the theoretical division at the Los Alamos National Laboratory.

Ginsparg came to Cornell in 2001, where he holds a joint appointment with the Department of Physics and the Faculty of CIS. He has been an A. P. Sloane Fellow and a DoE Outstanding Junior Investigator, and has held visiting positions at C.E.N. Saclay, France; Princeton University; Stanford Linear Accelerator Center; the Institute for Advanced Studies, Princeton; the Institute for Theoretical Physics at the University of California at Santa Barbara;
the Mathematical Science Research Institute at University of California at Berkeley; and at Hebrew University of
Jerusalem. In 1991, Ginsparg initiated the “e-print arXiv” as a new form of communications-research infrastructure
for physics.

Ginsparg’s current research in information science investigates the optimal combination of automated text classification, data mining, machine learning, human– computer interaction, quantum field theory, and related techniques for use in research-communications infrastructure.

“A Remnant of Chiral Symmetry on the Lattice”. Physical Review D25 (1982): 2649. (With K. G. Wilson)
“2D Gravity + 1D Matter”. Physics Letters B240 (1990): 333. (With J. Zinn–Justin)
“Winners and Losers in the Global Research Village”. In Proceedings of“Electronic Publishing in Science, Sir R. Elliot and D. Shaw, eds. ICSU Press (1996).

Tarleton Gillespie
Assistant Professor
CIS, joint with Science and Technology Studies

Tarleton Gillespie received his bachelor’s degree in English from Amherst College in 1994, his master’s in communication in 1997, and his Ph.D. in 2002 from the University of California at San Diego.

His work focuses on the cultural and institutional arrangements surrounding media technologies, considering how power and practice are woven into their use, and the cultural notions of their value. In particular, he is interested in the way that law and technology sometimes do battle, but more often are often brought together to regulate knowledge production.

His research uses recent disputes over copyright and the Internet to analyze the historical contest over the nature of authorship, law, and technology. He is interested in the history of copyright, which he feels has borrowed particular romanticized notions of authorship and traditionally neutral notions of technology—to rationalize and naturalize one system of distribution of creative work, i.e., a corporate-driven commercial market system.

His theoretical purpose is to reject the deterministic tone of most claims about media and cultural expression, and replace them with an understanding of technology as a complex material artifact, but one that may be articulated in ways that seem to support one ideological agenda or another. He finds this argument an important one to make, especially now—precisely because the decisions made today will set the standards by which the Internet is developed and regulated in the future.

“Copyright and Commerce: The DCMA, Trusted Systems, and the Stabilization of Distribution”. In The Information Society (forthcoming, Fall 2003).
“The Stories Digital Tools Tell”. In New Media: Theses on Convergence, Media, and Digital Reproduction, (J. Caldwell and A. Everett, eds.) Routledge (February, 2003).

Geri Gay
CIS, joint with Communication

Geri Gay is the director of the Human Computer Interaction Group (HCI Group) and a professor in Department of Communication. She received her Ph.D. from Cornell in 1985. The HCI Group is a research-and-development group whose members design and research the use of computer-mediated learning environments. Current research
focuses on the use and design of PDAs for communication and collaboration (funded by Intel). Other research examines navigation issues, knowledge management, social network analysis (NSF), knowledge representations, collaborative work and learning (NASA and AT&T Foundation), and activity-centered design of mobile devices.

Professor Gay teaches courses in computer-mediated communication, human– computer interaction, and the social design of communication systems. She was awarded the New York State Chancellor’s Award for Excellence in Teaching in 2001.

Activity Centered Design: An Ecological Approach. Boston: M.I.T. Press. [in press] (With H. Hembrooke)
“Collaboration in Wireless Learning Networks”. Proceedings of the HICSS Conference (January, 2002). (With H. Hembrooke)
“E-Graffiti: Evaluating Real-world Use of a Context-Aware System”. Interacting with Computers Special Issue on Universal Usability (2001). (With J. Burrell)

Zygmunt J. Haas
Associate Professor
Member of the School of Electrical and Computer Engineering and the
Graduate Field of Computer Science

Zygmunt J. Haas received his Ph.D. degree from Stanford University in 1988 and subsequently joined AT&T Bell Laboratories, where he pursued research on wireless communications, mobility management, fast protocols, optical networks, and optical switching. In August of 1995, he joined the ECE faculty at Cornell.

Haas is an author of numerous technical papers and holds fifteen patents in the fields of high-speed networking, wireless networks, and optical switching. He has organized several workshops, delivered tutorials at major Institute of Electrical and Electronics Engineers (IEEE) and ACM conferences, and serves as editor of several journals and
magazines, including the IEEE Transactions on Networking and IEEE Transactions on Wireless Communications. He has been a guest editor of three IEEE Journal of Selected Areas on Communications (JSAC) issues (“Gigabit Networks”, “Mobile Computing Networks”, and “Ad-Hoc Networks”). Haas is the chair of the IEEE Technical Committee on Personal Communications.

Haas’s current interests include: mobile and wireless communication and networks, personal communication service, and high-speed communication and protocols. He heads the Wireless Networks Laboratory (WNL) at Cornell, which performs research in the area of mobility management for wireless networks, ad hoc networking (routing, multicasting, medium access control (MAC), and topology control), security of wireless communications, and cross-layer design of communication protocols. The ad hoc networking technology is the central research area of WNL. In particular, Haas’s research group has developed the first hybrid ad hoc routing protocols—the Zone Routing Protocol—which is currently an Internet Engineering Task Force (IETF) draft. The WNL ( has also pioneered in its research on ad hoc network security.

Dr. Haas is a recipient of the Michael Tien College of Engineering Teaching award in the years 1997 and 2000.

“On Multicast Flow Control for Heterogeneous Receivers”. ACM/IEEE Transactions on Networking 10(1)
(February, 2002): 86–101. (With R.–H. Gau and B. Krishnamachari)
“The Performance of Query Control Schemes for the Zone Routing Protocol”. ACM/IEEE Transactions on Networking 9(4) (August, 2001): 427–438. (With M. Pearlman)
“Securing Ad Hoc Networks”. IEEE Network Magazine 13(6) (November/December 1999). (With L. Zhou)

David Gries
Associate Dean of Engineering
for Undergraduate Programs
Professor of Computer Science
Cornell Weiss Presidential Fellow

Professor Gries’s research is aimed at gaining a better understanding of the programming process, with respect to both sequential and concurrent (or parallel) programs. The work requires investigation of theories of program correctness and their application, as well as investigation of other concepts in the semantics of programming languages.

Education is a also a strong interest for Gries, particularly the first few courses in computer science. Under the thesis that logic is the glue that binds together reasoning in all domains, with colleague F. B. Schneider, Gries developed a text, A Logical Approach to Discrete Math, which makes a usable “calculational logic” the foundation for almost all the discrete math topics.

Gries is also heavily involved in writing an introductory programming text, based on Java. Earlier, with his son, he developed a “livetext”—a text that comes on a CD and has more than 250 two- to three-minute recorded lectures with synched animation, as well as other innovative features. They are finishing up a paperback text to accompany it.
Gries received the Dr. rer. nat. degree from the Munich Institute of Technology in 1966; a Doctor of Science degree (Honorary) from Miami University in Oxford, Ohio in 1999; and a Doctor of Laws degree (Honorary) from Daniel Webster College in Nashua, New Hampshire in 1996. He won the ACM Karl V. Karlstrom Outstanding Educator Award in 1996, and the Taylor L. Booth Award Education Award, IEEE Computer Society, in 1995.

A Logical Approach to Discrete Math. Springer Verlag, New York. (1993) (With F. Schneider)
ProgramLive. John Wiley & Sons (2000). (With P. Gries). (This livetext comes on a CD and has over 250 recorded lectures, with synched animation.)

Carla P. Gomes
Associate Professor
CIS, joint with Applied Economics and Management
Director, IISI

Carla P. Gomes obtained a Ph.D. in computer science in the area of artificial intelligence and operations research
from the University of Edinburgh in 1993. She also holds an M.Sc. in applied mathematics from the University of

Gomes’s research has covered many areas in artificial intelligence and computer science, including planning and scheduling, integration of CSP and OR techniques for solving combinatorial problems, software agents, and
algorithm portfolios. Her current projects focus on the interplay between problem structure and computational hardness, the use of approximation methods in large-scale constraint-based reasoning systems, and applications of constraint-based reasoning and optimization in multi-agent optimal control, distributed wireless networks, and combinatorial auctions.

She was the conference chair of the Eighth International Conference on Principles and Practice of Constraint
Programming (CP-2002). Gomes is also the director of the Intelligent Information Systems Institute (IISI) at Cornell.

“An Improved Approximation for the Partial Latin Square Extension Problem”. in Proceedings of the ACM–SIAM Symposium on Discrete Algorithms (SODA). (2003). (With R. Regis and D. Shmoys)
“Artificial Intelligence and Operations Research: Challenges and Opportunities in Planning and Scheduling”. Journal of Knowledge Engineering Review 15(1) (2000): 1–10.
“Heavy-tailed Phenomena in Satisfiability and Constraint Satisfaction Problems”. Journal of Automated Reasoning 24(1/2) (2000): 67–100. (With B. Selman, N. Crato, and H. Kautz)

Donald Greenberg
Member of CIS, the Johnson School
of Management, the Department of Architecture,
and the Graduate Field of Computer Science

Dr. Greenberg received his Ph.D. from Cornell in 1968. He joined the Cornell faculty in 1968, with a joint appointment in the Departments of Architecture and Structural Engineering. His prior education consisted of both the architecture and engineering disciplines at Cornell and Columbia University. From 1960 to 1965, he served as a consulting engineer with Severud Associates, and was involved with the design of numerous building projects, including the St. Louis Arch, New York State Theater of the Dance at Lincoln Center, and Madison Square Garden. Early in his career he taught courses in structural analysis and design, architectural design, shell structures, reinforced concrete, and computer applications in architecture. In 1970–71, he was a guest professor at the ETH in Zurich, Switzerland, and he has been a visiting professor at Yale University.

Professor Greenberg’s current research is primarily concerned with physically based image synthesis and with applying graphic techniques to a variety of disciplines. His specialties include color science, parallel processing, and real-time realistic-image generation. His application work includes medical imaging, architectural design, visual perception, digital photography, and computer animation.

Greenberg is a member of Cornell’s faculty in the Johnson Graduate School of Management, CS, and the Department of Architecture, and a founding member of the Faculty of CIS. In recent years he has taught courses in computer graphics, computer-aided architectural design, digital photography, and disruptive technologies. He is the director of the Program of Computer Graphics and was the founding director of the NSF Science and Technology Center for Computer Graphics and Scientific Visualization.

More than 300 articles on computer graphics have been published by the Program of Computer Graphics and many of Professor Greenberg’s students have been highly recognized in the field, including several who have received the SIGGRAPH Achievement Award and others who have received Hollywood Oscars. Greenberg received the ACM Steven Coons Award in 1987, the highest honor in the graphics field; the National Computer Graphics Association Academic Award in 1989; the ASCA Creative Research Award in Architecture in 1997; and an honorary doctoral degree from New Jersey Institute of Technology. He is an ACM Fellow and a member of the National Academy of Engineering.

“Visions of Light”. Metropolis Magazine (by Jonathan Ringen): 138–144, 185–189 (June, 2002)
“Enhancing and Optimizing the Render Cache”. In Proceedings of the Thirteenth Eurographics Workshop on Rendering (June, 2002). (With B. Walter. G. Drettakis, and O. Deussen)
“Adaptive Shadow Maps”. In Proceedings of SIGGRAPH 2001 (August, 2001). (With R. Fernando, S. Fernandez,
and K. Bala)

Joseph Halpern

Joseph Halpern received a B.Sc. in mathematics from the University of Toronto in 1975 and a Ph.D. in mathematics
from Harvard in 1981. In between, he spent two years as the head of the mathematics department at Bawku Secondary School in Ghana. After a year as a visiting scientist at M.I.T., he joined the IBM Almaden Research
Center in 1982, where he remained until 1996, also serving as a consulting professor at Stanford. In 1996,
he joined CS at Cornell.

Halpern’s major research interests are in reasoning about knowledge and uncertainty, security, distributed
computation, and decision theory. Together with his former student, Yoram Moses, he pioneered the approach
of applying reasoning about knowledge to analyzing distributed protocols and multi-agent systems. He has
coauthored five patents, a book, Reasoning About Knowledge, and over 200 technical publications.

Halpern is a Fellow of the AAAI and the ACM. Among other awards, he received the Godel Prize in 1997, and
was a Guggenheim Fellow and a Fulbright Fellow in 2001–02. Two of his papers have won best-paper prizes
at International Joint Conferences on Artificial Intelligence (IJCAI). Many of his other papers were invited for special issues of journals. He serves as editor-in-chief of the Journal of the ACM and on several other editorial boards.

“Knowledge and Common Knowledge in a Distributed Environment’’. Journal of the ACM 37(3) (1990): 549–587. (With Y. Moses)
“An Analysis of First-order Logics of Probability”. Artificial Intelligence46(3) (1990): 311–350.
“Plausibility Measures and Default Reasoning”. Journal of the ACM 48(4) (2001): 648–685. (With N. Friedman)
OF SCIENCES (Lielo Medalu)

Mark Heinrich
Assistant Professor
Member of the School of Electrical
and Computer Engineering and
the Graduate Field of Computer Science

Mark Heinrich is an assistant professor in ECE at Cornell, a co-founder of its Computer Systems Laboratory, and an
IISI member.

His research interests include active memory and I/O systems, parallel computer architecture, system-area networks, novel computer architectures, embedded architectures, scalable cache-coherence protocols, multiprocessor design and simulation methodology, and hardware/software codesign.

He received his Ph.D. in electrical engineering from Stanford University under John Hennessy in 1998, where he was a principal designer of the FLASH multiprocessor. He was the author of FlashLite, the system-level simulator of the FLASH machine, as well as four cache-coherence protocols for FLASH. He also developed the first model for evaluating the effect of node-controller occupancy in distributed shared-memory machines.

He received his M.S. degree from Stanford in 1993, and his B.S.E. in electrical engineering and computer science from Duke University in 1991. Heinrich was also the co-founder and chief architect of Flashbase, Inc. an Internet company specializing in automated sweepstakes and database-backed forms and tools for customer acquisition. Flashbase was acquired by DoubleClick Inc. in May 2000.

“Leveraging Cache Coherence in Active Memory Systems”. In Proceedings of the Sixteenth ICS (June, 2002). (With D. Kim and M. Chaudhuri)
“Active Memory Clusters: Efficient Multiprocessing on Commodity Clusters”. In Proceedings of the Fourth ISHPC, Lecture Notes in Computer Science 2327 (May, 2002): 78–92. (With E. Speight and M. Chaudhuri)
“FLASH vs. (Simulated) FLASH: Closing the Simulation Loop”. In Proceedings of the Ninth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS) (November, 2000): 49–58. (With J. Gibson, R. Kunz, D. Ofelt, M. Horowitz, and J. Hennessy)

Juris Hartmanis
Emeritus Walter R. Read Professor
of Computer Science and Engineering

Juris Hartmanis obtained his Ph.D. from the California Institute of Technology in 1955. In 1965, he founded CS and was its first chairman. In 1993 he was awarded the Turing Award. In 2001, Hartmanis was a recipient of the Lielo Medalu, the Grand Medal of the Latvian Academy of Sciences.

Hartmanis is also the founder of the field of computational complexity theory. He believes that computational complexity, the study of the quantitative laws that govern computation, is an essential part of the science base needed to guide, harness, and exploit the explosively growing computer technology.

Professor Hartmanis’s current research interests focus on understanding the structure of computational complexity classes and exploring how to view computation as construction of complex objects and relate computational complexity to the complexity of constructed objects.

He is a member of the National Academy of Engineering; a foreign member of the Latvian Academy of Sciences; a Fellow of the American Academy of Arts and Sciences, the New York State Academy of Sciences, the American Association for the Advancement of Science, and ACM. He serves as editor of the Springer-Verlag Lecture Notes
in Computer Science; Journal of Computer and Systems Sciences
; and Fundamenta Informaticae.

“On the Computational Complexity of Algorithms”. Transactions of the American Mathematical Society 117(5) (May, 1965): 285–306. (With R. Stearns)
“On Isomorphisms and Density of NP and Other Complete Sets”. SIAM Journal on Computing 6 (June, 1977): 305–322. (With L. Berman)
“Generalized Kolmogorov Complexity and the Structure of Feasible Computations”. In Proceedings of the Twenty-fourth Annual Symposium on Foundations of Computer Science (November, 1983): 439–445.

Sheila S. Hemami
Associate Professor
Member of the School of Electrical and Computer
Engineering and the Graduate Field of Computer Science

Sheila S. Hemami received her B.S.E.E (1990) and M.S.E.E. (1992) degrees from the University of Michigan. She obtained her Ph.D. degree from Stanford University in 1994. Her doctoral work comprised development of real-time, low-complexity lossy signal-processing techniques to provide reconstruction of image and video data lost in transmission over lossy packet networks. During her last year at Stanford, she was a member of the technical staff at Hewlett Packard Laboratories in Palo Alto, California. Upon completing her Ph.D., she joined the ECE faculty at Cornell, where she currently directs the Visual Communications Laboratory. In 1997, she received a National Science Foundation CAREER Award. In 2000 she received the Eta Kappa Nu C. Holmes MacDonald Outstanding Teaching Award (a national award). In 2002, she was a finalist for the Eta Kappa Nu Outstanding Young Electrical Engineer Award. She is a member of the IEEE, Eta Kappa Nu, and Tau Beta Pi.

The emerging information superhighway provides an example of the flexibility required of image and video-compression and transmission techniques. Varying network capacities, differences in viewing devices, and a broad spectrum of user needs suggest the desirability of coding techniques that can efficiently span large quality and bandwidth ranges. Additionally, coded data must be robust to errors and loss of varying degrees across multiple network segments. For practicality, algorithms must be inexpensive to implement, in either hardware or software. Dr. Hemami’s research interests broadly concern such communication of visual information. Particular topics of interest
include multirate video coding and transmission, compression specific to packet networks and other lossy networks, and psychovisual considerations.

“Efficient Sign Coding and Estimation of Zero-quantized Coefficients in Embedded Wavelet Image Codecs”. IEEE
Transactions on Image Processing
12(4)(2003): 420–30. (With D. Deever)
“Universal Multiple Description Scalar Quantization: Analysis and Design”. Data Compression Conference 2003,
Snowbird, Utah (2001). (With C. Tian)
“Contrast-based Quantization and Rate Control for Wavelet-coded Images”. In Proceedings of the IEEE International Conference on Image Processing (2002). (With D. Chandler)

John Hopcroft

Professor Hopcroft’s research centers on the study of information capture and access. This includes the study of large graphs, spectral analysis of structures, clustering, and queries. He has also been involved in the theoretical aspects of computing, especially analysis of algorithms, formal languages, automata theory, and graph algorithms. He has coauthored four books on formal languages and algorithms with Jeffrey D. Ullman and Alfred V. Aho.

From January 1994 until June 2001, he was the Joseph Silbert Dean of the College of Engineering. He was formerly the associate dean for college affairs and the Joseph C. Ford Professor of Computer Science. After receiving an M.S. (1962) and Ph.D. (1964) in electrical engineering from Stanford University, Professor Hopcroft spent three years on the faculty of Princeton University. In 1967, he joined the Cornell faculty, was named professor in 1972 and served as CS chairman from 1987 to 1992. An undergraduate alumnus of Seattle University, Hopcroft was honored with their Doctor of Humanities degree, Honoris Causa, in 1990.

Formal Languages and Their Relation to Automata. Addison–Wesley (1969). (With J. Ullman)
“Efficient Planarity Testing”. Journal of the ACM 21(4) (October, 1974): 549–568. (With R. Tarjan)
“A Paradigm for Robust Geometric Algorithms”. Algorithmica 7(4) (1992): 339–380. (With P. Kahn)

Thorsten Joachims
Assistant Professor

Thorsten Joachims joined CS as an assistant professor in 2001. Earlier that year, he completed his dissertation,
“The Maximum-margin Approach to Learning Text Classifiers: Methods, Theory, and Algorithms” at the Universität Dortmund, Germany, advised by Katharina Morik.

His research interests center on a synthesis of theory and system building in the field of machine learning, with a focus on support-vector machines, text-mining, and machine learning in information access. In particular, Joachims has worked on WebWatcher, an adaptivebrowsing assistant for the Web. He has authored the SVMLight algorithm and software for support-vector learning. His most recent work is on learning from clickthrough data in search engines, and on using unlabeled data for supervised learning in the framework of transduction.

Joachims taught the course “Advanced Topics in Machine Learning” and co-taught “Language Technologies” with
Claire Cardie.

Joachims received the dissertation award of the Universität Dortmund. He is member of the editorial board of the Journal of Machine Learning Research and the Journal of Artifical Intelligence Research. He serves on the program committees of International Conference on Machine Learning (ICML), European Conference on Machine Learning (ECML), Special Interest Group on Information Retrieval (SIGIR), and others.

Learning to Classify Text Using Support Vector Machines, Kluwer (2002).
“Optimizing Search Engines Using Clickthrough Data”. ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD) (2002).
“Making Large-scale Support Vector Machine Learning Practical” In Advances in Kernel Methods Support Vector Learning, B. Schölkopf, C. Burges, and A. Smola (eds.), M.I.T. Press (1999): 169–184.

Klara Kedem

Klara Kedem obtained her Ph.D. in computer science at Tel-Aviv University in 1989. She is currently spending the summers as a CS professor at Cornell and during the rest of the year she is a professor in the computer science department at Ben-Gurion University in Israel.

Professor Kedem’s research is in computational geometry with applications to robotics, computer vision, and bio-information. She is known for devising the minimum Hausdorff distance for shape matching, a robust method that has had a strong impact and is still being investigated actively.

Recently Professor Kedem and CS collaborators have looked into shape-comparison problems in the life sciences. In computational molecular biology, they have come up with a new metric, the unit-vector root mean square (URMS), to measure substructure resemblance between proteins. This measure has been further applied to the analysis of molecular dynamics. Currently she is working on finding consensus shapes for protein families, and applying string-matching algorithms to protein-shape comparison.

Kedem is on the editorial board of the Journal of the Pattern Recognition Society, and serves as guest editor of Computational Geometry: Theory and Applications. She won the Mary Upson Visiting Professorship at Cornell for 1997–1998.

“The Upper Envelope of Voronoi Surfaces and its Applications”. Discrete and Computational Geometry 9 (1993): 267–291. (With D. Huttenlocher and M. Sharir)
“Fast Detection of Geometric Substructure in Proteins”. Journal of Computational Biology 6(3–4) (1999): 313–325. (With L. Chew, D. Huttenlocher, and J. Kleinberg)
“Unit-vector RMS (URMS) as a Tool to Analyze Molecular Dynamics Trajectories”. Proteins: Structure, Function and Genetics 37 (1999): 554–564. (With L. Chew and R. Elber)

Daniel P. Huttenlocher
John P. and Rilla Neafsey Professor of Computing
and Information Science and Business
Cornell Weiss Presidential Fellow
CIS, joint with the Johnson Graduate School
of Management
Dan Huttenlocher received a dual degree in computer
science and experimental psychology from the University
of Michigan in 1980, and master’s and Ph.D. degrees
in computer science from M.I.T. in 1984 and 1988,
respectively. He has been on the CS faculty since 1988.
He currently holds a joint appointment with the Johnson
Graduate School of Management at Cornell.
Huttenlocher’s research interests are in computer vision,
computational geometry, electronic-collaboration tools,
financial-trading systems, and the principles of software
development. In addition to teaching and research,
Dan has considerable experience managing softwaredevelopment
efforts in corporate and academic settings.
He is chief technical officer of Intelligent Markets, a
leading provider of advanced trading systems. He also
spent more than ten years at the Xerox PARC, directing
work that led to the ISO JBIG2 image-compression
standard, and serving as part of the senior management
Huttenlocher has been recognized on several occasions
for his teaching and research, including being named a
Presidential Young Investigator by the NSF in 1990, the
New York State Professor of the Year by CASE in 1993, and
a Stephen H. Weiss Fellow by Cornell in 1996. He holds
twenty-two U.S. patents and has published more than fifty
technical papers, primarily in the areas of computer vision
and computational geometry.
“Comparing Images using the Hausdorff Distance”. IEEE Transactions on
Pattern Analysis and Machine Intelligence 15(9) (1993): 850–863.
(With G. Klanderman and W. Rucklidge)
“The Upper Envelope of Voronoi Surfaces and its Applications”. Discrete
and Computational Geometry 9(3) (1993): 267–291. (With K. Kedem
and M. Sharir)
“Recognizing Solid Objects by Alignment with an Image”. International
Journal of Computer Vision 5(2) (1990): 195–212. (With S. Ullman)
38 C I S A N N U A L R E P O R T 2 0 0 3 3 9
11101 0000
Dean Krafft
Senior Research Associate
Director of Computing Facilities
Dean Krafft received his Ph.D. in computer science from
Cornell in 1981. He serves as both a CS researcher and
administrator at Cornell. As an administrator, he manages
the Computing Facilities Support group and worries
about a number of issues including computer security,
networking, and building Web services.
On the research side, Krafft is part of the CIS Program in
Digital Libraries (
research/dl/home.html). As part of that effort, Krafft is a
coprincipal investigator on the NSF–funded National
Science Digital Library Project at Cornell
( He is currently working specifically
on both the NSDL user portal and the central metadata
repository. Krafft’s own particular interests focus on
ensuring the availability in the digital world of pre-digital
published and manuscript materials, as well as related
issues on copyright, the public domain, and public access
to older and out-of-print materials.
“Core Services in the Architecture of the National Digital Library for
Science Education (NSDL)”. In Proceedings of the Second ACM/IEEE–CS
Joint Conference on Digital Libraries (July, 2002).
(With Carl Lagoze, et al.)
“Dienst: Building a Production Technical Report Server”. In Advances in
Digital Libraries (May, 1995): 211–223. (With J. Davis and C. Lagoze)
“The Challenge of Robotics for Computer Science”. Advances in Robotics,
Algorithmic and Geometric Aspects of Robotics 1 (1986): 7–42.
J. Schwartz and C. Yap, eds. Lawrence Erlbaum Associates, Inc.
(With J. Hopcroft)
Christoph Kreitz
Senior Research Associate
Christoph Kreitz obtained his Ph.D. in computer science at the FernUniversität Hagen,
Germany in 1984. His research has focused on computational models for infinite objects
and on the application of automated theorem-proving to the design, verification, and
optimization of software systems.
In collaboration with researchers of Robert Constable’s Nuprl and Ken Birman’s Ensemble
groups he has built logic-based tools that automatically improve the code of faulttolerant
communication systems and guarantee that the improvements do not introduce
errors. He has also developed techniques for the formal design and verification of
adaptive distributed systems. He currently investigates the validation of end-to-end
Quality-of-Service behavior of networked systems.
Christoph Kreitz also works on enhancing the automatic reasoning capabilities of tactical
theorem provers. Together with his former students from the Technical University of
Darmstadt, he has developed and implemented proof-search procedures for classical,
intuitionistic, modal, and fragments of linear logic, and algorithms that transform the
machine-found proofs into the proof calculus of other systems. His theorem prover
has been connected to the interactive proof assistants Nuprl, MetaPRL, and Coq,
and is being used to guide the development of proofs in these systems.
“Theory of Representations”. Theoretical Computer Science 38 (1985): 35–53. (With K. Weihrauch)
“Building Reliable, High-performance Systems from Components”. In Proceedings of the Seventeenth ACM
Symposium on Operating System Principles (SOSP ’99), Operating Systems Review 34(5) (December 1999):
80–92. (With X. Liu, R. van Renesse, J. Hickey, M. Hayden, K. Birman, and R. Constable)
“Connection-based Theorem Proving in Classical and Non-classical Logics”. Journal for Universal Computer
Science 5(3) (1999): 88–112. (With J. Otten)
Dexter Kozen
Joseph Newton Pew, Jr. Professor of Engineering
Dexter Kozen received his undergraduate degree in
mathematics from Dartmouth College in 1974 and his
Ph.D. in computer science from Cornell in 1977. After
working as a research staff member at the IBM Thomas J.
Watson Research Center for several years, he returned to
Ithaca to join the Cornell faculty in 1985.
Kozen’s research interests include the design and analysis
of algorithms, computation-complexity theory, the
complexity of decision problems in logic and algebra,
and logics and semantics of programming languages.
He is currently involved in a research project involving
efficient code certification and its application to malicious
firmware. His most recent theoretical project is the
development of the theory of Kleene algebra and Kleene
algebra with tests, including results on complexity,
deductive completeness, expressiveness, and applications
to compiler correctness. He developed and taught a new
course on this topic in spring 2002. Kozen is the author
of three books.
Professor Kozen received the Stephen and Margery Russell
Distinguished Teaching Award from Cornell’s College of
Arts and Sciences in 2001 and was named the Williams
College Class of 1960 Scholar in 2000. He is also a
recipient of an IBM Outstanding Innovation Award and a
former Guggenheim fellow.
“Results on the Propositional mu-calculus”. Theoretical Computer Science
27 (1983): 333–354.
“Kleene Algebra with Tests”. Transactions on Programming Languages and
Systems, (May, 1997): 427–443.
Dynamic Logic. M.I.T. Press (2000). (With D. Harel and J. Tiuryn)
Jon Kleinberg
Associate Professor
Jon Kleinberg received his A.B. in computer science and mathematics from Cornell in
1993 and his Ph.D. in computer science from M.I.T. in 1996. He subsequently spent a
year as a visiting scientist at the IBM Almaden Research Center, and is now an associate
professor in CS at Cornell.
Kleinberg’s research interests are centered around algorithms, particularly those
concerned with the structure of networks and information. He focuses on combinatorial
and randomized methods in the design of algorithms, with applications to information
science, discrete optimization, data mining, and computational biology. His work
introduced the notion of network analysis based on hubs and authorities, a framework
that has been incorporated into a number of prominent search tools on the Web.
Kleinberg is a recipient of an NSF CAREER Award, an ONR Young Investigator Award, an
Alfred P. Sloan Foundation Fellowship, a David and Lucile Packard Foundation Fellowship,
and the 2001 National Academy of Sciences Award for Initiatives in Research. He also
received the Fiona Ip Li and Donald Li Teaching Award from the Cornell College of
Engineering, and the Cornell Association of Computer Science Undergraduates Faculty of
the Year Award for 2001–2002.
“Authoritative Sources in a Hyperlinked Environment”. Journal of the ACM 46(5) (1999): 604–632.
“Navigation in a Small World”. Nature 406 (2000): 845.
“Approximation Algorithms for Classification Problems with Pairwise Relationships: Metric Labeling
and Markov Random Fields”. Journal of the ACM (2002) 49(5): 616–639. (With E. Tardos)
40 C I S A N N U A L R E P O R T 2 0 0 3
Yuying Li
Senior Research Associate
Yuying Li obtained a bachelor’s degree in applied
mathematics at the Sichuan University in China in 1982,
and an Ph.D in computer science at the University of
Waterloo in 1988. She has been a research associate in
CS since.
Li’s research interests include numerical optimization and
scientific computation. In addition, she is interested in
the application of optimization methods to medical,
engineering, and financial problems.
Her current interest has focused on solving problems in
financial applications, e.g., volatility estimation, discrete
hedging, portfolio compression, and portfolio optimization
under different risk measures.
Li is the recipient of the 1993 First Prize of the Sixth Fox
Prize Competition in Numerical Analysis, Oxford, England.
“Dynamic Hedging with a Deterministic Local Volatility Function Model”.
The Journal of Risk 4(1) (2001): 64–90.
“An Interior, Trust Region Approach for Nonlinear Minimization Subject to
Bounds”. SIAM Journal on Optimization 6(2) (1996): 418–445.
(With T. Coleman)
Large-scale Numerical Optimization. SIAM, Philadelphia (1990).
(With T. Coleman)
4 1
/// Carl Lagoze
Senior Research Associate
Carl Lagoze obtained his master’s degree in software
engineering from Wang Institute for Graduate Studies in
1987. He is currently a senior research associate in CIS.
He is concurrently Director of Technology of the
NSF–funded National Science Digital Library (NSDL).
Lagoze’s research investigates policies, organization, and
architecture of distributed-information spaces. The Web
provides the backdrop for the work. The goal is to
understand the services and organization that can be
built on top of this global information base to increase
its functionality, integrity, and ease-of-use. The research
is undertaken with the recognition that any proposed
solutions must balance the economy and speed of
automated solutions against the often-irreplaceable
expertise that comes from human intervention.
Lagoze’s research group is recognized for a number of
advances in distributed-information systems. These
include the Dienst architecture for distributed digital
libraries, the FEDORA digital-object model for complex
digital content, the ABC event-aware descriptive
ontology, and the Open Archives Initiative Protocol for
Metadata Harvesting that has been widely adopted as a
foundation for information-systems interoperability. His
technical leadership of the NSDL provides the opportunity
to realize these advances in a major national resource for
science and mathematics education.
“Core Services in the Architecture of the National Digital Library for
Science Education (NSDL)”. Joint Conference on Digital Libraries
(July, 2002). (With W. Arms, S. Gan, D. Hillmann, C. Ingram,
D.Krafft, R. Marisa, J. Phipps, J. Saylor, C. Terrizzi, W. Hoehn,
D. Millman, J. Allan, S. Guzman-Lara, and T. Kalt)
“The Open Archives Initiative Protocol for Metadata Harvesting”.
Protocol Version 2 (June, 2002). (With H. Van de Sompel,
M. Nelson, and S. Warner)
“The ABC Ontology and Model”. Journal of Digital Information 2(2)
(November, 2001): 18 p. (With J. Hunter)
Lillian Lee
Associate Professor
Lillian Lee (A.B., Cornell, 1993; Ph.D., Harvard University, 1997) is an assistant professor
in CS. Her main research interest is natural language processing, in particular the
development of “knowledge-lean’’ statistical methods that allow computers to
automatically learn linguistic and domain knowledge directly from text. A major focus
has been the study of distributional similarity and distributional clustering. She and her
colleagues have also considered applications ranging from finding word boundaries in
streams of Japanese to creating English versions of computer-generated mathematical
Lee is a recipient of an Alfred P. Sloan Research Fellowship, the Stephen and Marilyn
Miles Excellence in Teaching Award, and the James and Mary Tien Excellence in Teaching
Award. Her professional activities include serving as the program chair of the 2001
Conference on Empirical Methods in Natural Language Processing, an area chair for the
2001 Annual Meeting of the Association for Computational Linguistics, a member of the
editorial boards of the journals Computational Linguistics and Machine Learning, and a
member of the executive board of SIGDAT, the ACL Special Interest Group on Linguistic
Data and Corpus-based Approaches.
“Fast Context-free Grammar Parsing Requires Fast Boolean Matrix Multiplication”. Journal of the ACM 49(1)
(2002): 1–15.
“Iterative Residual Rescaling: An Analysis and Generalization of LSI”. In Proceedings of the Twenty-fourth
Annual International Conference on Research and Development in Information Retrieval (SIGIR) (2001):
154–162. (With R. Ando)
“Distributional Clustering of English Words”. In Proceedings of the Thirty-first Annual Meeting of the ACL (1993):
183–190. (With F. Pereira and N. Tishby)
Hod Lipson
Assistant Professor
CIS, joint with Mechanical and Aerospace Engineering
Hod Lipson joined the Faculty of CIS and the faculty of the Sibley School of Mechanical
and Aerospace Engineering in 2001 as an assistant professor. Prior to this appointment,
he was a postdoctoral researcher at Brandeis University’s computer science department,
working on evolutionary computation and evolutionary robotics, where he led the Golem
Project—creating the first physical artificial life forms. He was also a lecturer in M.I.T.’s
mechanical-engineering department, where he taught design and conducted research
in design automation.
Professor Lipson’s Ph.D. (Technion, 1998) research was on the reconstruction of a threedimensional
object from a single freehand sketch, as a means for human–computer
interaction for CAD. Before joining academia, Lipson spent several years as a design
engineer in the mechanical, electronic, and software industries, and cofounded two
currently-active companies.
Lipson’s research interests are in the area of computational synthesis: How do we
combine basic building blocks to achieve some high-level functionality? He is interested
in understanding the synthesis process of design and emulating it computationally, and
he focuses on the ideas of self-organization and self-replication as new paradigms of
fully automated design, fabrication, and learning. Primary questions concern automatic
discovery of modules, regular and hierarchical composition, and automatic abstraction
of functionality. Cornell’s computational-synthesis group develops both new theoretical
ideas and applies them to various engineering problems, from evolutionary robotics and
structures to circuits and game players. Lipson believes that fully automated synthesis
holds the key to future competitiveness, and presents a largely unaddressed challenge
across engineering, biology, and AI.
Among the awards and honors Lipson has received are: Time Magazine’s Annual 2001;
EXPO 2000 (“Shaping the Future”); and the CIRP International F. W. Taylor Medal
in 1997.
“Correlation-based Reconstruction of a 3D Object from a Single Freehand Sketch”. AAAI 2002 Spring
Symposium on Sketch Understanding (2002): 99–104. (With M. Shpitalni)
“Uncontrolled Engineering: A Review of Evolutionary Robotics”. Artificial Life 7(4) (2001): 419–424.
“Automatic Design and Manufacture of Robotic Lifeforms”. Nature 406 (2000): 974–978. (With J. Pollack)
42 C I S A N N U A L R E P O R T 2 0 0 3 4 3
Jeanna Neefe Matthews
Assistant Professor
Jeanna Matthews obtained her Ph.D. in computer science
at the University of California at Berkeley in 2000. She is
currently an assistant professor in CS. Matthews’ research
lies in the areas of operating systems, storage systems,
and networks. She is actively involved in several projects
aimed at integrating hands-on exposure to research
results into computer science courses.
“Improving the Performance of Log-structured File Systems with Adaptive
Methods”. In Proceedings of the Sixteenth ACM Symposium on Operating
System Principles (October, 1997): 238–251. (With D. Roselli,
A. Costello, R. Wang, and T. Anderson)
“Serverless Network File Systems”. In Proceedings of the ACM Symposium
on Computer Systems (February, 1996). (With T. Anderson, M. Dahlin,
D. Patterson, D. Roselli, and R. Wang)
“Serverless Network File Systems”. (Award paper) Proceedings of the
Fifteenth ACM Symposium on Operating System Principles (December,
1995): 109–126. (With T. Anderson, M. Dahlin, D. Patterson,
D. Roselli, and R. Wang)
Greg Morrisett
Associate Professor
Greg Morrisett obtained his Ph.D. in computer science from Carnegie Mellon University
in 1995. He is currently an associate professor in CS at Cornell.
Morrisett’s research focuses on programming-language design, implementation,
and semantics. He is particularly interested in the emerging area of language-based
security. He is best known for the development of TAL and Certifying Compilation. These
are important mechanisms that can be used to automatically verify an important class
of safety properties for machine code. More recently, Morrisett has concentrated on type
systems for legacy software. His Cyclone project provides type safety for C code without
sacrificing control over data structures, calling conventions, or memory management.
Other projects include work on run-time code specialization, type-safe reflection, typebased
alias analysis, region-based memory management, and in-lined reference monitors.
Morrisett is an editor for the Journal of Functional Programming, and an associate editor
for ACM Transactions on Programming Languages and Systems. In 2000, he was given
a Presidential Early Career Award for Scientists and Engineers. He is also a recipient of
a Sloan Foundation Fellowship, an NSF CAREER Award, and the Allen Newell Medal of
Research Excellence.
“Cyclone: A Safe Dialect of C”. In Usenix Annual Technical Conference (June, 2002): 275–288. (With T. Jim, D.
Grossman, M. Hicks, J. Cheney, and Y. Wang)
“Syntactic Type Abstraction”. In ACM Transactions on Programming Languages and Systems 22(6)
(November, 2000): 1037–1080. (With D. Grossman and S. Zdancewic)
“From System F to Typed Assembly Language”. In ACM Transactions on Programming Languages and Systems 21(3)
(May, 1999): 528–569. (With D. Walker, K. Crary, and N. Glew) 10001
Rajit Manohar
Assistant Professor
Member of the School of Electrical and Computer Engineering
and the Graduate Field of Computer Science
Rajit Manohar obtained his B.S. (1994), M.S. (1995) and Ph.D. (1998) degrees
in computer science from the California Institute of Technology. He is currently
an assistant professor in ECE, and a member of the graduate fields of computer
science and applied mathematics. The focus of his research effort is on the
design of efficient computation structures. His group is currently working on the
The SNAP project develops novel energy-efficient clockless architectures for
sensor network applications. The NoC project (joint with Professor Lang Tong) has
demonstrated that asynchronous circuit techniques applied to wireless network
modeling can provide three-orders-of-magnitude increase in simulation speed,
compared to traditional approaches.
Professor Manohar received the NSF CAREER Award (2000–2004), the Cornell IEEE
Teacher of the Year Award (2001), the College of Engineering Sonny Yau Excellence
in Teaching Award (2001), and the Tau Beta Pi and Cornell Society of Engineers
Excellence in Teaching Award (2000).
“SNAP: A Sensor-Network Asynchronous Processor”. In Proceedings of the Nonth International Symposium
on Asynchronous Curcuits and Systems (May 2003). (With C. Kelly and V. Ekanayake)
“Network on a Chip: Modeling Wireless Networks with Asynchronous VLSI”. IEEE Communications
Magazine 39(11) (November, 2001). (With Clinton Kelly IV)
“Slack Elasticity in Concurrent Computing”. In Proceedings of the Fourth International Conference on the
Mathematics of Program Construction, Lecture Notes in Computer Science 1422 (June, 1998): 272–285.
Springer-Verlag. (With A. Martin)
Steve Marschner
Assistant Professor, CS
Steve Marschner obtained his B.S. degree in mathematics
and computer science from Brown University in 1993 and
his Ph.D. from Cornell in 1998. He held research positions
at Hewlett–Packard Labs, Microsoft Research, and Stanford
University before joining the CS faculty in 2002.
Marschner’s research interests are in the field of
computer graphics, focusing on realistic rendering,
especially models for light reflection and scattering, and
high-resolution geometric modeling. Recent projects
include a new model to efficiently simulate translucent
materials, which has been widely implemented by the
film-effects industry; ongoing work on processing very
high resolution geometric data for the Digital
Michelangelo Project at Stanford; and an experimental
and theoretical investigation into the scattering of light
from human hair. The overall goal of his work is to use
measurements to capture the complexity of real objects
and understand the subtleties of real materials, thereby
increasing the richness and realism of computer generated
images .
“Light Scattering from Human Hair Fibers”. ACM Transactions on Graphics
22: 3. Proceedings of SIGGRAPH 2003 (2003). (With H. Jensen,
M. Cammarano, and P. Hanrahan)
“A Practical Model for Subsurface Light Transport”. In Proceedings of
SIGGRAPH 2001 (August, 2001). (With H. Jensen, M. Levoy, and
P. Hanrahan)
“Image-based BRDF Measurement Including Human Skin”. In Proceedings
of 10th Eurographics Workshop on Rendering (June, 1999): 139–152.
(With S. Westin, E. Lafortune, K. Torrance, and D. Greenberg)
44 C I S A N N U A L R E P O R T 2 0 0 3 4 5 //
Keshav Pingali
Keshav Pingali obtained a bachelor’s degree in electrical engineering at the Indian
Institute of Technology (I.I.T.), Kanpur in 1978, and an Sc.D. in computer science
at M.I.T. in 1986. Since 1986, he has been on the CS faculty where he is currently
a full professor. Pingali is also an ECE faculty member.
Pingali’s research has focused on programming languages and compiler technology for
program understanding, restructuring, and optimization. His group is known for its
contributions to memory-hierarchy optimization; some of these have been patented.
Algorithms and tools developed by his projects are used in many commercial products
such as Intel’s IA-64 compiler, SGI’s MIPSPro compiler, and Hewlett–Packard’s PA-RISC
compiler. In his current research, he is investigating language-based fault-tolerance,
and highly adaptive software systems for large-scale simulations.
Among other awards, Pingali has won the President’s Gold Medal at I.I.T., Kanpur (1978),
IBM Faculty Development award (1986–87), NSF Presidential Young Investigator award
(1989–94), Ip-Lee teaching award of the College of Engineering at Cornell (1997),
and the Russell teaching award of the College of Arts and Sciences at Cornell (1998).
In 2000, he was a visiting professor at I.I.T., Kanpur where he held the Rama Rao
Chaired Professorship.
“Algorithms for Computing the Static Single Assignment Form”. Journal of the ACM (2003): 375–425. (With G.
“A Comparison of Empirical and Model-driven Optimization”. ACM Programming Language Design and
Implementation (PLDI) (June, 2003): 52–66. (With K. Yotov et al.)
“Fractal Symbolic Analysis”. International Conference on Supercomputing (June, 2001): 38–49.
(With N. Mateev and V. Menon)
Professor Keshav Pingali
[second from left] with Ph.D.
students Greg Bronevetsky [left],
Kamen Yotov [second from right],
and Rohit Fernandes [right].
11110 10001
Andrew Myers
Assistant Professor
Andrew Myers received his Ph.D. in computer science from
M.I.T. in 1999. He is currently an assistant professor in CS.
Myers is particularly interested in using language-level
information to improve security guarantees, performance,
and transparency for distributed systems and mobile code.
A current focus is on the protection of confidential data,
a problem that is gaining importance in our connected
world. Methods are needed for building practical systems
while guaranteeing that they enforce strong security
properties. Myers has developed novel and efficient
static-analysis techniques to identify and control privacy
violations in complex programs. These techniques have
been employed in the Jif compiler and run-time system
for writing secure programs. Jif has been applied to
distributed systems containing untrusted components,
and to systems in which security requirements change
Myers received a NSF CAREER award in 2001, and the
Alfred P. Sloan Research Fellowship and the Excellence in
Teaching Award from the College of Engineering in 2002.
“Using Replication and Partitioning to Build Secure Distributed Systems”.
In IEEE Symposium on Security and Privacy (May, 2003). (With L.
Zheng, S. Chong, and S. Zdancewic)
“Language-based Information-flow Security”. In IEEE Journal on Selected
Areas in Communications, special issue on Formal Methods for Security
(January, 2003) 21(12): 5–19. (With A. Sabelfeld)
“Secure Program Partitioning”. ACM Transactions on Computing Systems
(TOCS) 20(3)(August, 2002): 283–328. (With S. Zdancewic, L. Zheng,
and N. Nystrom)
Anil Nerode
Goldwin Smith Professor of Mathematics
Member of the Graduate Field of Computer Science
Anil Nerode obtained his Ph.D. in mathematics, under
Saunders MacLane, from the University of Chicago in 1956.
He was a NSF postdoctoral fellow with Kurt Godel, at the
Institute for Advanced Study, from 1957–58; visiting
assistant professor with Alfred Tarski at the University
of California at Berkeley from 1958–59; was brought to
Cornell by J. Barkley Rosser in 1959; appointed professor
in 1965; and named Goldwin Smith Professor in 1990.
He served as chair of the Department of Mathematics from
1982–87, and was director of the Mathematical Sciences
Institute from 1987–1996. He also served as director of
the Center for Foundations of Intelligent Systems from
Nerode’s research areas include mathematical logic,
computability theory, recursive mathematics, nonstandard
logics, nonmonotonic logics, AI, applied mathematics,
control theory, hybrid systems, and complex system design.
“Control Synthesis in Hybrid Systems with Finsler Dynamics” Houston
Journal of Mathematics 28(2) (2002): 352–375. (With Kohn Wolf
and Vladimir Brayman)
[in preparation] Constructive Logics and Lambda Calculi: 500 p.
(With G. Odifreddi)
Automata Theory and Its Applications: Birkhauser (2001). 480 p.
(With B. Khoussainov)
46 C I S A N N U A L R E P O R T 2 0 0 3 4 7
Mats Rooth
CIS, joint with Linguistics
Mats Rooth’s research is concerned with theories and
applications in linguistics and computational linguistics,
which combine theoretical–linguistic formalisms,
knowledge, and problem statements with numerical
modeling and parameter-estimation techniques. Using
current methodology, it is possible to create approximately
complete grammars of human languages, and using parsing
algorithms and the grammars, to map sentences to
representations that represent their syntax and meaning.
However, sentences of human languages are very
ambiguous, to the extent that it would be possible know
everything about the syntax of a language, without having
any operative means of identifying the intended syntax
and meaning of the sentences that people use. This
problem is addressed by numerical models that put
weights on possible representations. Numerical models and
optimization algorithms also allow linguistic information
(in particular, syntactic and semantic properties of
individual words) to be learned from large data samples.
Rooth, whose appointment is joint with the Department of
Linguistics and the Faculty of CIS, also works on the
semantics of natural language, using logical methods and
formalisms. He developed an approach to the meaning
of intonation, which is known as alternative semantics.
Currently, he is working on interactions between the
grammar of ellipsis and the grammar of intonation.
Rooth has a B.S. degree in mathematics from M.I.T., and
a Ph.D. in linguistics from the University of Massachusetts
at Amherst. Before joining the Cornell faculty, he was chair
of theoretical computational linguistics at the University
of Stuttgart, and member of the technical staff at AT&T
Bell Laboratories.
“A Theory of Focus Interpretation”. Natural Language Semantics 1 (1992):
“Inside–outside Estimation of a Lexicalized PCFG for German”. In
Proceedings of the Thirty-seventh Annual Meeting of the Association for
Computational Linguistics (1999). (With F. Beil, G. Carroll, D. Prescher,
and S. Riezler)
“Parse Forest Computation of Expected Governors”. In Proceedings of the
Thirty-ninth Annual Meeting of the Association for Computational
Linguistics (2001): 458–465. (With H. Schmid)
Fred B. Schneider
Director, Information Assurance Institute
Chief Scientist, Griffiss Institute
Fred B. Schneider has studied concurrent and distributed systems since joining Cornell’s
faculty in 1978. His early work concerned programming methodology and formal methods.
He is known for formalizing “safety” and “liveness” properties as well as for developing
methods to reason about concurrent and distributed programs. His work in fault-tolerant
distributed systems led to now well-known protocols and structures (including the
“failstop processor” abstraction, a seminal survey on the state machine approach,
hypervisor-based fault tolerance, and various protocols used in today’s air-traffic–control
Most recently, Schneider’s attention has turned to questions related to computer security:
• exploiting insights from formal methods and programming languages as a basis
for relocating trust and enforcing application-specific security policies; and
• the design of systems and protocols to support both fault-tolerance and security
in distributed systems.
Both of these efforts have led to practical new tools. For example, Schneider and
collaborators are currently building a third-generation inlined reference monitor suite
(targeted to Microsoft’s CLR) to better understand practical problems with enforcing
fine-grained security policies through rewriting object-code. Work also continues with
collaborators on the COCA (Cornell On-line Certification Authority) project, with attention
now focused on implementing secure and scalable publish/subscribe protocols.
Schneider has been professor-at-large at the University of Trömso (Norway) since 1996,
is a fellow of ACM and AAAS, and received an honorary doctorate in May 2003 from the
University of Newcastle-upon-Tyne. He is associate editor-in-chief for IEEE Security
and Privacy and serves on the editorial boards of several other journals.
On Concurrent Programming. Springer-Verlag, N.Y. (1997): 473 p.
Trust in Cyberspace. (ed.) National Academy Press (December, 1998): 331 p.
“Enforceable Security Policies”. ACM Transactions on Information and
System Security 3(1) (February, 2000): 30–50.
Fred Scheider was
awarded an honorary
doctorate degree by
the University of
in 2003.
Radu Rugina
Assistant Professor
Radu Rugina received a bachelor’s degree in computer
science from the University Politechnica of Bucharest in
1996, and a Ph.D. degree in computer science from the
University of California at Santa Barbara in 2001. Between
1997 and 2001 he was a visiting scholar at the Laboratory
for Computer Science at M.I.T.
His research interests lie in the area of programming
languages and compiler support for program
understanding, maintaining, and debugging; for
checking safety properties of programs; and for program
transformations and optimizations. Rugina has developed
program analysis techniques capable of analyzing memory
accesses in recursive and multithreaded programs that
heavily manipulate pointers. Concrete applications of these
analyses include automatic parallelization of sophisticated
divide-and-conquer problems, static detection of
array-bounds violations, and data-race detection in
multithreaded programs that use pointers and pointer
In his current research, he is investigating program
analysis approaches to improve software reliability and
security, by automating the process of checking the
properties that guarantee program safety and functionality.
“Static Analysis of Accessed Regions in Recursive Data Structures”.
In Proceedings of the Tenth International Static Analysis Symposium
(June, 2003). (With S. Chong)
“Pointer Analysis for Structured Parallel Programs”. In ACM Transactions
on Programming Languages and Systems 25(1) (January, 2003).
(With M. Rinard)
“Symbolic Bounds Analysis of Pointers, Array Indices, and Accessed
Memory Regions”. In Proceedings of the ACM SIGPLAN 2000 Conference
on Programming Languages Design and Implementation (June, 2000).
(With M. Rinard)
Robbert van Renesse
Senior Research Associate
Robbert van Renesse received his M.Sc. in mathematics and computer science from the
Vrije Universiteit in 1985, under the supervision of Andrew S. Tanenbaum, with the
honorary addendum cum laude. He obtained his Ph.D. in computer science from the
Vrije Universiteit in 1989, also under the supervision of Professor Tanenbaum.
His research focus is in large-scale, self-organizing network protocols and distributed
applications. Currently, he is involved in four projects. First, the Astrolabe system is a
peer-to-peer implementation of a DNS–like directory service that supports on-the-fly
aggregation of resource information. It incorporates epidemic algorithms to ensure
robustness and efficiency, and is used among others to build scalable multicast protocols.
This is joint work with Ken Birman and Werner Vogels. Second, with Lidong Zhou, he is
developing an implementation of IPv6 as an overlay network, using distributed hash
tables and Astrolabe. Third, the MediaNet system is a distributed multimedia facility that
supports user-specified adaptation. This is joint work with Mike Hicks, Bob Constable,
Mark Bickford, and Christoph Kreitz. Fourth, with Fred Schneider and Visiting Professor
Dag Johansen, he is investigating techniques for filtering high volume–event streams.
In addition to his current research, van Renesse is a technical advisor for Fast Search
and Transfer, ASA, a company that develops search engines.
“Astrolabe: A Robust and Scalable Technology for Distributed Systems Monitoring, Management, and Data
Mining”. In ACM Transactions on Computer Systems (May, 2003) 21(3). (With K. Birman and W. Vogels)
“User-specified Adaptive Scheduling in a Streaming Media Network”. Proceedings of Open ARCH 03 (April, 2003).
(With M. Hicks and A. Nagarjan)
“COCA: A Secure Distributed Online Certification Authority ”. In ACM Transactions on Computer Systems
(November, 2002). (With L. Zhou and F. Schneider)
48 4 9 C I S A N N U A L R E P O R T 2 0 0 3
Bart Selman
Associate Professor
Bart Selman obtained a Ph.D. in computer science from the University of Toronto in
1991. Currently an associate professor in CS, he spent the previous six years at AT&T
Bell Laboratories in the principles of artificial intelligence–research department.
His research has covered many areas in artificial intelligence and computer science,
including tractable inference, knowledge representation, stochastic search methods,
theory approximation, knowledge compilation, planning, default reasoning, and the
connections between computer science and statistical physics (phase-transition
phenomena). His current projects focus on planning, multi-agent systems, and the
integration of learning and reasoning techniques.
Bart Selman has received an NSF CAREER Award (1998–2002) and an Alfred P. Sloan
Research Fellowship (1999–2001). He has received four best paper awards at the
American and Canadian national artificial-intelligence conferences, and at the
International Conference on Knowledge Representation.
“Heavy-tailed Phenomena in Satisfiability and Constraint Satisfaction Problems”. Journal of Automated
Reasoning 24(1/2) (2000): 67–100. (With C. Gomes, N. Crato, and H. Kautz)
“Determining Computational Complexity from Characteristic Phase Transitions”. Nature 400(8) (1999): 133–137.
(With R. Monasson, R. Zecchina, S. Kirkpatrick, and L. Troyansky)
“Knowledge Compilation and Theory Approximation”. Journal of the ACM 43(2) (1996): 193–224.
(With H. Kautz)
Phoebe Sengers was
a recipient of a
Bart Selman was the
recipient of an AAAS
in 2003.
David I. Schwartz
Assistant Professor
David I. Schwartz obtained his Ph.D. in civil engineering
at the State University of New York at Buffalo in 1999.
He is currently an assistant professor in CS.
Schwartz’s research and interests involve educational
technology, the support of undergraduate research,
textbook writing, and graduate-student development.
He continues to work on developing a multidisciplinarian
curriculum for computer game–design courses that
incorporates technical and artistic aesthetics of computergame
design in a collaborative environment. Students from
diverse backgrounds in engineering, computer science,
fine art, and music formed teams that developed and
implemented computer games and associated gamedevelopment
tools. The project encourages women and
underrepresented minorities to enter the field of computer
Introduction to Mapl.e (2nd ed.) Prentice Hall: New Jersey (2003).
Introduction to UNIX. Prentice Hall: New Jersey (1999).
“A Constraint-based Approach for Qualitative Matrix Structural Analysis”.
Artificial Intelligence for Engineering Design, Analysis and
Manufacturing 9 (1995): 23–36. (With S. Chen)
CIS Professor Phoebe Sengers discusses switches
with CIS Professor Paul Ginsparg.
Phoebe Sengers
Assistant Professor
CIS, joint with Science and Technology Studies
Phoebe Sengers received her Ph.D. in artificial intelligence and cultural theory in 1998
from Carnegie Mellon University. She was a Fulbright Scholar at the Center for Art and
Media Technology (ZKM) in Karlsruhe, Germany, and spent two years as a research
scientist at the German National Research Center for Information Technology (GMD).
She joined the Faculty of CIS in October, 2001, and has a joint appointment with the
Department of Science and Technology Studies.
Sengers works in human–computer interaction, especially problems that bridge cultural
issues and technology design. She develops culturally embedded systems; i.e., new kinds
of interactive technology that respond to and encourage critical reflection on the place
of technology in culture. Her current research, funded by a five-year NSF CAREER Award,
explores everyday computing, or interactive media devices for non-work contexts, and
draws on techniques from computer science, cultural analysis, design, and the arts.
She uses insights from analysis of consumer culture to rethink the work-based
assumptions underlying technologies for the home, developing both new application
areas for everyday computing, including systems to support personal reflection, and new
techniques for designing systems, including the use of self-experiemnt in design and new
forms of evaluation for open-ended systems. She works on the National Research Council’s
Committee on Information Technology and Creativity, which develops policy suggestions
for interdisciplinary research in information technology and the arts, humanities, and
other creative areas.
“The Enigmatics of Affect”. Conference on Designing Interactive Systems (June, 2002). (With R. Liesendahl,
W. Magar, C. Seibert, B. Müller, T. Joachims, W. Geng, P. Mårtensson, and K. Höök)
“Practices for Machine Culture: A Case Study of Integrating Artificial Intelligence and Cultural Theory”.
Surfaces 8 (1999).
“Designing Comprehensible Agents”. In Proceedings of the Sixteenth International Joint Conference on Artificial
Intelligence (August, 1999): 1227–1232.
50 C I S A N N U A L R E P O R T 2 0 0 3
Emin Gün Sirer
Assistant Professor
Emin Gün Sirer obtained his Ph.D. from the University of
Washington in 2002. His research interests span operating
systems, networking, distributed systems, and ubiquitous
computing, with recent emphasis on ad hoc networks,
peer-to-peer systems, and secure network services.
Professor Sirer is currently involved in four projects. The
MagnetOS project investigates operating-system support
for ad hoc and sensor networks. Specifically, Sirer’s group
is designing and building a new operating system that
improves the longevity and reliability of ad hoc networks
through energy-aware, adaptive object migration,
multipath route selection, and novel hybrid routing
protocols. The CliqueNet project is a peer-to-peer,
self-organizing system for anonymous communication that
provides an information-theoretic guarantee of privacy.
The Pepper system, with Professors Gehrke and
Shanmugasundaram, examines peer-to-peer data-location
techniques for ubiquitous computers. Finally, the
WebGuard project investigates how to build secure Web
Sirer’s past work on the SPIN and Kimera projects
examined novel operating-system architectures. The SPIN
kernel developed the techniques for safely extending
operating systems with application-specific code. The
Kimera system introduced a new virtual-machine
architecture that enables Java systems of drastically
higher manageability, security, and performance, while
reducing their resource requirements. The techniques
developed in the Kimera project have been adopted
throughout the industry, including Hewlett–Packard,
Microsoft, Sun, and Schlumberger Inc.
“SHARP: A Hybrid Adaptive Routing Protocol for Mobile Ad Hoc
Networks”. In Proceedings of the Symposium on Mobile Ad Hoc
Networking (June, 2003). (With V. Ramasubramanian and Z. Haas)
“Path-set Selection in Mobile Ad Hoc Networks”. In Proceedings of the
Third ACM International Symposium on Mobile Ad Hoc Networking
and Computing (2002). (With P. Papadimitratos and Z. Haas)
“On the Need for System-level Support for Ad hoc and Sensor Networks”.
ACM Operating Systems Review 36(2) (April, 2002): 1–5.
(With R. Barr, J. Bicket, D. Dantas, B. Du, T. Kim, and B. Zhou)
Evan Speight
Assistant Professor
Member of the School of Electrical and Computer
Engineering and the Graduate Field of Computer Science
Evan Speight obtained his Ph.D. in electrical engineering
at Rice University in 1998. Speight is an assistant professor
in ECE, and is a field member of CS. His research interests
include distributed and parallel computing, computer
architecture, and affinity-directed mobility in mobile
computing environments.
Speight’s current projects include Active Memory Clusters
(joint work with Professor Mark Heinrich), which seeks to
leverage the increased functionality of a programmable
memory controller to provide hardware-distributed sharedmemory
performance from commodity clusters. The Delphi
project (joint work with Professor Martin Burtscher)
explores the benefits of utilizing value-prediction techniques
borrowed from the architectural community in improving the
performance of cluster-based shared-memory multiprocessors.
The Tern project represents work on examining the possible
performance and fault-tolerant benefits of thread migration
between hosts in an MPI parallel-runtime environment.
Finally, the Bifrost project (joint work with Professor John
Bennett at the University of Colorado at Boulder and
sponsored by Microsoft) provides a framework for mobile
computing that relies on “affinity” to automatically direct
application and data throughout a wide geographic region
for optimal user access.
“Delphi: Prediction-based Page Prefetching to Improve the Performance of
Shared Virtual Memory Systems”. In Proceedings of the International
Conference on Parallel and Distributed Processing Techniques and
Applications (June, 2002). (With M. Burtscher)
“Active Memory Clusters: Efficient Multiprocessing on Commodity Clusters”. In
Proceedings of the Fourth International Symposium on High Performance
Computing, Lecture Notes in Computer Science 2327 (May, 2002): 78–92
(With M. Heinrich and M. Chaudhuri)
“Using Multicast and Multithreading to Reduce Communication in Software
DSM Systems. In Proceedings of the Fourth Symposium on HPCA (1998):
312–323. (With J. Bennett)
5 1
David B. Shmoys
Member of the School of Operations Research and Industrial Engineering
and the Graduate Field of Computer Science
David Shmoys obtained his Ph.D. in computer science at the University of California at
Berkeley in 1984. He has faculty appointments in both CS and the School of Operations
Research and Industrial Engineering. Shmoys’ research has focused on the design and
analysis of efficient algorithms for discrete optimization problems.
His work has highlighted the central role that linear programming plays in the design of
approximation algorithms for NP–hard problems. In particular, he is known for his results
on scheduling and clustering problems, including the first constant-performance
guarantees for several problems central to the literature, including the k-center and
k-median problems, the generalized-assignment problem, as well as scheduling problems
in which the aim is to minimize the average job-completion time. Furthermore, his work
on polynomial-time approximation schemes for scheduling problems introduced techniques
that have subsequently been applied to a variety of other settings. His current work
includes the application of discrete optimization techniques to several issues in
computational biology.
Professor Shmoys is a Fellow of the ACM, and is the recipient of a National Science
Foundation Presidential Young Investigator’s Award and the Cornell College of Engineering
Sonny Yau Excellence in Teaching Award (twice). He is currently editor-in-chief of SIAM
Journal on Discrete Mathematics, and on the editorial board of several other journals,
including SIAM Journal on Computing, and Mathematics of Operations Research.
“Using Dual Approximation Algorithms for Scheduling Problems: Theoretical and Practical Results”. Journal
of the ACM 34(1) (1987): 144–162. (With D. Hochbaum)
“Fast Approximation Algorithms for Fractional Packing and Covering Problems’’. Mathematics of Operations
Research 20: 257–301 (1995). (With S. Plotkin and E. Tardos).
“Scheduling to Minimize the Average Completion Time: On-line and Off-line Approximation Algorithms”.
Mathematics of Operations Research 22 (1997): 513–544. (With L. Hall, A. Schulz, and J. Wein)
Jayavel Shanmugasundaram
Assistant Professor
Jayavel Shanmugasundaram obtained his Ph.D. degree
in computer science from the University of Wisconsin at
Madison in 2001. He is currently an assistant professor
in CS.
Shanmugasundaram’s research interests include Internet
data management, information retrieval, and query
processing in emerging system architectures. His research
group is currently working on three projects. The Quark
project aims to unify the database and information
retrieval worlds by developing a next-generation datamanagement
system for handling both structured and
unstructured data. The Deep Glue project develops a
platform for integrating and querying Internet-attached
databases, also referred to as the “deep web”. The Pepper
project (joint with Johannes Gehrke) develops highly
robust indexing and query-processing strategies for
evaluating complex queries over large-scale, distributed
peer-to-peer systems.
Shanmugasundaram’s research ideas have been
incorporated in commercial data-management products,
and have resulted in several patents.
Shanmugasundaram is a recipient of an IBM Faculty
Partnership Award.
“XRANK: Ranked Keyword Search Over XML Documents”. In ACM SIGMOD
Conference on Management of Data (2003). (With L. Guo, F. Shao, and
C. Botev)
“Querying XML Views of Relational Data”. In Proceedings of the Conference
on Very Large Data Bases (2001): 261–270. (With J. Kiernan,
E. Shekita, C. Fan, and J. Funderburk)
“Relational Databases for Querying XML Documents: Limitations and
Opportunities”. In Proceedings of the Conference on Very Large Data
Bases (1999): 302–314. (With K. Tufte, C. Zhang, G. He, D. DeWitt,
and J. Naughton)
52 C I S A N N U A L R E P O R T 2 0 0 3
Tim Teitelbaum
Associate Professor
Tim Teitelbaum received a B.S. in mathematics from the Massachusetts Institute of
Technology in 1964, and his Ph.D. in computer science from Carnegie Mellon University
in 1975.
His research is concerned with the use of fine-grain dependence graphs for specification,
development, and analysis of software and hardware systems. The objective is a new
generation of tools that provide precise and complete information about the structure
of complex systems. He is working to improve the performance and functionality of
generic dependence-graph technology, and also exploring the use of the technology
in various application domains, including software development, maintenance and
reengineering of legacy code, test-data generation, security-assurance and safetyassurance
inspection, and semantic interference checking in configuration-management
Teitelbaum’s earlier work on programming environments and incremental computation
resulted in the Cornell Program Synthesizer and the Synthesizer Generator, two of the
earliest systems to have demonstrated the viability of integrated language-based
programming environments and syntax-directed editors.
He is a cofounder and chairman of GrammaTech, Inc., and a panelist for the National
Science Foundation.
“The Cornell Program Synthesizer: A Syntax-directed Programming Environment”. Communications of the ACM
24(9) (September, 1981): 563–573. (With T. Reps)
“Incremental Context-dependent Analysis for Language-based Editors”. ACM Transactions on Programming
Languages and Systems (TOPLAS) 5(3) (July, 1983): 49–477 (With T. Reps and A. Demers)
“Systematic Derivation of Incremental Programs”. Science of Computer Programming 24(1) (1995): 1–39.
(With Y. Liu)
5 3
Charles Van Loan
Professor and Chair, CS
Charles Van Loan received his Ph.D. in mathematics
from the University of Michigan in 1973. After being
a postdoctoral research fellow at the University of
Manchester, he joined CS as an assistant professor in 1975.
Professor Van Loan works in the matrix-computation field,
specializing in least-squares and eigenvalue problems that
arise in control engineering and signal processing. Blockmatrix
computations are a current interest with a special
emphasis on novel algorithms that exploit Kroneckerproduct
structure. Kronecker products are increasingly
important because of the role that they play in fast
transforms and various multilinear applications. He is
currently focusing on low-rank approximations of highdimensional
tensors using the singular value
Professor Van Loan is the author of five textbooks:
Matrix Computations (with G. H. Golub), Computational
Frameworks for the Fast Fourier Transform, Introduction to
Scientific Computation—A Matrix Vector Approach Using
Matlab, Introduction to Computational Science and
Mathematics, and Handbook for Matrix Computations
(with T. Coleman).
“An Analysis of the Total Least Squares Problem”. SIAM Journal on
Numerical Analysis 17(1980): 883–893. (With G. Golub)
“The WY Representation for Products of Householder Transformations”.
SIAM Journal of Scientific and Statistical Computing 8 (1987): s2–s13
(1987). (With C. Bischof)
“The Ubiquitous Kronecker Product”. Journal of Computational and
Applied Mathematics 123 (2000): 85–100.
Éva Tardos
Éva Tardos received her Ph.D. at the Eötvös University in Budapest, Hungary in 1984.
After teaching at Eötvös and at M.I.T., she joined Cornell in 1989. She is currently a
full professor in CS. She is a member of the American Academy of Arts and Sciences,
an ACM Fellow, was a Guggenheim Fellow, a David and Lucille Packard Fellow in Science
and Engineering, a Sloan Fellow; a Presidential Young Investigator; and has received
the Fulkerson Prize in 1988 (awarded jointly by the American Mathematical Society
and the Mathematical Programming Society for a paper in discrete mathematics).
She is the editor of several journals.
Tardos’s research interest focuses on the design and analysis of efficient algorithms
for combinatorial-optimization problems on graphs or networks. Such problems arise in
many applications such as vision, and the design, maintenance, and management of
communication networks. She is mostly interested in fast combinatorial algorithms that
provide provably optimal or close-to-optimal results. She is most known for her work on
network-flow algorithms, approximation algorithms for network flows, cut, and clustering
problems. Her recent work focuses on algorithmic game theory, an emerging new area of
designing systems and algorithms for selfish users.
“How Bad is Selfish Routing?” Journal of the ACM, 49(2) (2002): 236–259. (With T. Roughgarden)
“Approximation Algorithms for Classification Problems with Pair-wise Relationships: Metric Labeling and Markov
Random Fields”. In Journal of the ACM 49(5) (2002): 616–639. (With J. Kleinberg)
“A Strongly Polynomial Minimum Cost Circulation Algorithm”. Combinatorica 5(3) (1985): 247–255.
Paul Stodghill
Research Associate
Paul Stodghill obtained his bachelor’s degree in mathematics
and computer science from Dickinson College in 1988.
He obtained his Ph.D. in computer science from Cornell in
1997. Since 1997, he has been a post-doctoral research
associate and research associate in CS.
With the deployment of high-bandwidth networks,
computational science is entering a new era of distributed
and collaborative computing. Stodhill’s research interests
focus on supporting this effort. For example, he has
worked closely with a number of computational scientists
to develop novel, high-performance distributed scientific
applications. Currently, he is developing fault-tolerant
support for parallel applications and infrastructure for
deploying scientific simulations as Web services. He is also
helping to develop model-based and empirical optimization
techniques that allow codes to be migrated between
platforms without loss of performance.
“Computational Science Simulations Based on Web Services”. In
International Conference on Computational Science 2003. (With L. Chew,
et al.)
“Automated Application-level Checkpointing of MPI Programs”. In
Principles and Practices of Parallel Programming (PPOPP) (July, 2003).
(With C. Bronevetsky, D. Marques, and K. Pingali)
“A Comparison of Empiricxal and Model-driven Optimization” In
Programming Languages Design and Implementation (PLDI) (2003).
(With K. Yotov)
Professor Éva Tardos with a student.
54 C I S A N N U A L R E P O R T 2 0 0 3 5 5
Ramin Zabih
Associate Professor
Ramin Zabih received undergraduate degrees in computer
science and in mathematics from the Massachusetts
Institute of Technology, and a Ph.D. in computer science
from Stanford University in 1994. He joined CS in 1994,
and was promoted to associate professor in 2001. In 2001,
he was also given a joint appointment in the Department
of Radiology at Cornell’s Joan and Sanford I. Weill Medical
Zabih’s research interests are in computer vision and its
applications, especially in medical imaging. He is best
known for the work his group has done in applying
combinatorial-optimization methods, such as graph cuts,
to computer-vision problems. He is currently supervising
several Ph.D. students who are working on applying such
methods to the automated analysis of magnetic resonance
imagery. He has also done extensive consulting for
Microsoft, where his work had a major impact on Internet
He received the Abraham Wong teaching award from the
College of Engineering in 1995. In 2002 he received the
best paper award at the European Conference in Computer
“Fast Approximate Energy Minimization via Graph Cuts”. IEEE Transactions
on Pattern Analysis and Machine Intelligence 23(11) (November, 2001):
122–1239. (With Y. Boykov and O. Veksler)
“Color-spatial Indexing and Applications”. International Journal of
Computer Vision 35(3) (1999): 245–268. (With J. Huang, S. Kumar,
M. Mitra, and W.-J. Zhu)
“Non-parametric Local Transforms for Computing Visual Correspondence”.
In Proceedings of the Third European Conference on Computer Vision 94
(May, 1994): 151–158. (With J. Woodfill)
Golan Yona
Assistant Professor
Golan Yona obtained a bachelor’s degree (honor program) in physics and mathematics,
and Ph.D. in computer science at the Hebrew University of Jerusalem in 1999.
He was a Burroughs–Welcome postdoctoral fellow in computational molecular biology
at Stanford University from 1998 until 2000.
Yona’s research focuses on computational molecular biology, with an emphasis on
developing tools and methodologies for large-scale analysis of the protein universe.
The goal of his research is to explore high-order organization and obtain a global view
of the protein space. The global view is expected to yield valuable insights about the
nature and function of new genes and can lead to the discovery of global principles
in the protein space.
Yona’s research is rooted in two different disciplines, computer science and molecular
biology, and is related to fields of intensive research in both. It incorporates study
and development of methods for metric embedding, unsupervised learning techniques,
efficient graph algorithms, parallel applications, and efficient database management.
On the computational biology side it is involved with development of new algorithms
and approaches for protein comparison, statistical models of protein families, and
study of the mapping from sequences to structures. A great emphasis is on developing
novel machine-learning–based techniques, both in the context of the study of the
protein space, and as general-purpose tools. His study so far resulted in two large
databases that are being used by biologists to study new genes, ProtoMap
( and BioSpace (
Professor Yona is recipient of a National Science Foundation CAREER Award (2002).
“Towards a Complete Map of the Protein Space based on a Unified Sequence and Structure Analysis
of all Known Proteins”. In Proceedings of ISMB 2000: 395–406, AAAI Press. (With M. Levitt)
“ProtoMap: Automatic Classification of Protein Sequences, a Hierarchy of Protein Families, and Local
Maps of the Protein Space”. Proteins: Structure, Function and Genetics 37 (1999): 360–378.
(With N. Linial and M. Linial)
“Global Self Organization of All Known Protein Sequences Reveals Inherent Biological Signatures”.
Journal of Molecular Biology 268 (1997): 539–556 (With M. Linial, N, Linial, and N. Tishby)
Werner Vogels
Research Associate
Werner Vogels obtained his Ingenieur Hogere Informatica degree in 1989 from the Haagse
Hogeschool in The Hague, The Netherlands. After a number of years as a researcher in
various European Esprit projects, he joined CS in 1994, where he is now a research
Vogels’ research interest is in communication technologies for scalable distributed
systems, with a focus on the interaction between applications, operating systems and
network protocols, and in the design of high-performance run-time systems for advanced
distributed operations on cluster-computing systems. He is a principal investigator in the
Spinglass project, where, in collaboration with Ken Birman and Robbert van Renesse, he
works on the development of a new generation of high-scalable reliable network protocols
based on the principles of epidemic information dissemination. He also leads the Galaxy
project, which focuses on the distributed-systems needs of enterprise cluster-computing
systems, in particular providing practical solutions to the scalability problems that arise
in these systems.
“An Overview of the Galaxy Management Framework for Scalable Enterprise Cluster Computing”. In Proceedings
of the IEEE International Conference on Cluster Computing: Cluster–2000 (December, 2000).
(With D. Dumitriu)
“File System Usage in Windows NT 4.0”. In Proceedings of the Seventeenth ACM Symposium on Operating
Systems Principles (December, 1999).
“U-Net: A User-level Network Interface for Parallel and Distributed Computing”. In Proceedings of the
Fifteenth ACM Symposium on Operating Systems Principles (December, 1995). (With T. von Eicken,
A. Basu, and V. Buch)
Stephen A. Vavasis
Stephen Vavasis received his Ph.D. in computer science
from Stanford University in 1989. Since then, he has
taught at Cornell where he is currently a full professor.
He has also held summer and sabbatical research positions
at Sandia National Laboratories, RIACS, Xerox PARC, Bell
Labs, and Argonne National Laboratory.
Vavasis’s research centers on scientific computing. He is
known for bridging the gap between theory and practice
in numerical algorithms. His contributions include the first
provably good mesh generator for three-dimensional
finite-element analysis (with former student S. Mitchell,
now at Sandia), the first interior-point method for linear
programming whose polynomial running time does not
depend on the objective function or constraint right-hand
side (with Y. Ye of Stanford), and guaranteed-quality
geometric mesh partitioning (with Miller, Teng, and
Thurston). More recently (with former student G. Jonsson,
now at deCode), he has developed the first resultant-based
algorithm for solving polynomial equations with provable
accuracy guarantees.
Since coming to Cornell, Vavasis has received a
Presidential Young Investigator Award (1990–1995),
a Guggenheim Fellowship (1996–1997), and an Ip-Lee
Teaching Award (1999).
“A Primal-dual Interior Point Method Whose Running Time Depends Only
on the Constraint Matrix”. Mathematical Programming 74 (1996):
79–120. (With Y. Ye)
“Geometric Separators for Finite–Element Meshes”. SIAM Journal of
Scientific Computing 19 (1998): 364–386. (With G. Miller, S.–H. Teng,
and W. Thurston)
“Quality Mesh Generation in Higher Dimensions”. SIAM Journal of
Computing 29 (2000): 1334–1370. (With S. Mitchell)