The Computer Science Department home page.
Research Interests: Design and analysis of algorithms, including sorting, searching, sampling, digital halftones. A former chairman of the Department of Computer Science, Professor Floyd recently published a textbook on device-based computability theory.
Affiliations: CIS, ISL. Research Interests: Computational complexity and theory of computation, with emphasis on the connections between probability and computation. Noiseless coding and VLSI implementations of data compression.
Affiliation: Theory, Robotics, CSL. Research Interests: Algorithms and data-structures for representing and manipulating real-world objects, including their geometry, illumination, motion, etc.
Such techniques are used by computer systems that sense, model, reason, and act on physical the environment they are in. Most recently Professor Guibas has been working on the development of general tools for the study of geometric arrangements of curves and surfaces in two and three dimensions. Arrangements are structures that are fundamental to geometric computing. He has found many interesting uses of randomization in this domain - such methods give rise to simple and practical algorithms for a variety of problems. He is also studying techniques for making geometric algorithms robust in the presence of numerical errors.
In the graphics area he has been investigating hierarchical Monte-Carlo algorithms for the efficient solution of the global illumination problem. Other current interests include geometric approximations, morphing, robot navigation problems, model-based matching in computer vision, motion planning, physically-based modeling, and algorithmic techniques in predicting the folding and docking of macromolecules such as proteins.
Research Interests: Analysis of algorithms, programming languages, mathematical typography, combinatorial mathematics. Since January 1, 1990, Prof. Knuth has been Professor of the Art of Computer Programming. In recognition of the unique importance of his publications to the foundations of computer science, Knuth's role will be to devote essentially all of his time to writing the remaining volumes of the widely acclaimed work having that title.
Prof. Knuth has received many major awards and honors, including the National Medal of Science.
Research Interests: Prof. Manna's research interests include: automated deduction (theorem proving); semantics, specification, and verification of programs; reactive, real-time, and hybrid systems; systematic development and automatic synthesis of programs; temporal logic and its applications; and automatic and machine-supported verification systems.
Prof. Manna is developing a formal methodology for constructing provably correct systems. Reactive, real-time, and hybrid systems are considered.
The methodology consists of languages for the formal specification of such systems, guidelines for constructing and validating specifications, methods for refinement and transformation of specifications into detailed designs and implementations, and tools for analyzing and verifying proposed or actual implementations against given specifications. Temporal Logic, Statecharts and automata are used in the specification language.
The STeP (Stanford Temporal Prover) system is being developed to support this methodology.
Affiliations: CSLI. Research Interests: Proof theory, logic in computer science, automated deduction. This includes normal form results for derivations, their use in connection with extraction of programs from proofs and for devising efficient proof-search methods.
Affiliations: Theory division, CSL, CSLI. Research Interests: Programming language analysis and design, including module systems, object-oriented programming, type systems, and reasoning about programs; applications of mathematical logic to programming languages and automated reasoning; algorithms for static analysis of programs.
Research Interests: Design and analysis of algorithms with emphasis on approximations, online computations, and randomized algorithms, as well as related complexity theory. Optimization issues in computer systems, compilers and databases. Computational and combinatorial geometry with applications to robotics and vision.
Research Interests: Design and analysis of algorithms for combinatorial optimization problems. Examples of considered problems include multicommodity and generalized flow, scheduling, and other special classes of linear programs. We consider these problems in the context of sequential, parallel, and distributed computation.
We also study the optimization problems arising in the context of design, organization, and management of broadband networks such as ATM. In particular, we work on developing routing and admission control strategies for ATM networks, where the goal is to minimize congestion while maximizing the throughput.
Affiliation: CIS. Research Interests: Description of concurrent systems: their specification, implementation, and verification, for software, hardware, and mechanical systems. Other interests: computer music, digital typography, digital physics.
Affiliation: Computer Science Department. Research Interests: Comparative Concurrency Semantics. His interest are in formal models for the representation of distributed systems and the verification of statements about them; in particular in foundational work investigating the possibilities of such models.
Affiliation: CIS. Research Interests: Database systems. Professor Ullman's interests center around the use of logic as a database query language. He is looking at logic as a constraint language and the implementation of constraints among distributed databases. He also is concerned with languages for integrating information among heterogenous databases.
Affiliation: Research Staff Member, IBM Almaden Research Laboratory. Research Interests: Reasoning about knowledge and probability, fault-tolerant distributed computation, and logics of programs. Professor Halpern is particularly interested in understanding distributed systems better through reasoning about how a processor's state of knowledge changes as a result of communication and in understanding the subtle relationship between knowledge and probability. Current research focuses on finding principled techniques for going from statistical information to degrees of belief. Dr. Halpern has received best paper awards at two IJCAI conferences and two IBM Outstanding Innovation Awards, and is a fellow of the American Association of Artificial Intelligence.
Affiliation: IBM Almaden Research Laboratory. Research Interests: Solving problems using techniques from combinatorial optimization, randomized algorithms and geometry. Application areas include robotics, molecule design and data mining.
Affiliation: Chairperson, Department of Computer Science, Rice University; Research Staff Member at the IBM Almaden Research Center. Research Interests: Database theory, finite-model theory, knowledge theory and its applications to distributed systems and artificial intelligence, logic programming, program specification and verification. A common theme of his research interests is the application of logic and automata theory to the analysis of computer systems.
Affiliations: Principal Scientist, SRI International, KBMS. Research Interests: Deductive approach to program synthesis and related problems in software engineering and artificial intelligence including theorem proving and planning.
The Stanford home page.
The Computer Science Department home page.
The Theory Division home page.