URCS (logo)



Home
directions
news
Department
ugrad program
grad program
courses
Research
AI
systems
theory
tech reports
talks/events
facilities
People
faculty
staff
grads
undergrads
alumni
others
U of R
related depts.

URCS Measures of Excellence

There are many ways to measure the quality of a Computer Science department. By almost any measure URCS does very well.
     


Faculty

The URCS faculty includes 14 tenure-track professors (James Allen, Chris Brown, Chen Ding, Sandhya Dwarkadas, Daniel Gildea, Lane Hemaspaandra, Henry Kautz, Randal Nelson, Mitsu Ogihara, Len Schubert, Michael Scott, Joel Seiferas, Kai Shen, Daniel Stefankovic), one research professor (George Ferguson), one teaching professor (Ted Pawlicki), one research scientist (Mary Swift), and 5 affiliated faculty members, from Brain and Cognitive Science (Robbie Jacobs, David Knill), Electrical and Computer Engineering (Wendi Heinzelman, Michael Huang), and Philosophy (Henry Kyburg).

Recent Professional Leadership

Awards


Students

Graduate students are the lifeblood of a CS research program. As of October 2007, the department has 44 Ph.D. students. Of these, 13 are citizens of the US or Canada. The rest come from a variety of countries around the world, including Bangladesh, China, Colombia, India, Greece, Italy, Iraq, Iran, and Poland.

URCS students routinely lead the College in GRE scores and University Fellowships. (For the entering classes of 2004–2006, Median verbal and quantitative GRE scores were 630 and 800, respectively.) Many students are supported by external corporate and foundation fellowships. All others receive full department stipends, and all receive tuition waivers.

At the undergraduate level, the department graduates about 30 majors a year, many of whom are actively involved in research. The undergraduate mobile robot team took first place in the 2002 AAAI mobile robot host competition. David Eisenstat, now a Ph.D. student at Princeton, took first place, nationwide, in the 2006 Outstanding Undergraduate Award program of the Computing Research Association. Pete Barnum and Micha Elsner received honorable mention in the 2005 competition. Gautam Altekar (now a graduate student at UC-Berkeley) was a finalist in 2004; Al Robinson received honorable mention. All four URCS nominees received honorable mention in 2003. There is an active undergraduate council, a student chapter of the ACM, and a Computer Interest Floor in the undergraduate dorms.


Alumni

Between 1980 and 2006, URCS awarded 156 Ph.D. degrees. URCS graduate alumni have gone on to outstanding careers in academia and industry. Danny Sabbah (Ph.D. 1982) is Vice President for AIM Development at IBM. Rick Rashid (Ph.D. 1980) is Senior Vice President for Research at Microsoft. Avi Tevanian (M.S. 1984) went on to earn a Ph.D. at CMU, and was Chief Technology Officer of Apple from 1997 to 2006.

A little over a third of the department’s Ph.D. alumni have gone on to academic careers. At least 32 now hold senior faculty positions, at Boston University (Crovella); Carnegie Mellon University (Schneider); Colgate University (Sanchis [deceased]); Concordia University (Narayanan); Federal University of Minas Gerais, Brazil (Meira); Nassau Community College (Sher); Ohio State University (Parthasarathy); Pacific Lutheran University (Hauser); Rensselaer Polytechnic Institute (Zaki); Rice University (Cox, Mellor-Crummey); Rutgers University (Kahrs, Bianchini); The National University of Singapore (Jain); The Rochester Institute of Technology (Heliotis, Vallino); The State University of New York at Albany (Haas); Towson University (Zimand); The University of Alberta, Canada (Jägersand); The University of California at San Diego (Cottrell); The University of Crete (Markatos); The University of Electro-Communications, Tokyo (Tarui); The University of Essex, England (Poesio); The University of Florida (Newman); The University of Leicester (Raman); The University of Maryland (Aloimonos, Perlis); The University of Massachusetts (McCallum); The University of Pittsburgh (Litman); The University of Rochester (Kautz); The University of Washington, Seattle (Rao); The University of Washington, Tacoma (Tenenberg); The University of Texas, El Paso (Fuentes); The University of York, England (Frisch); Washington University in St. Louis (Loui); and the University of Wisconsin–Oshkosh (Kyburg). At least 32 more recent grads hold junior academic positions.

In industry and government service, URCS graduate alumni are members of technical staff at many of the world’s leading research labs, including IBM (13), Google (7), Microsoft (6), Bell Labs (3), Intel (3), Xerox (3), Cisco (2), GE (2), NEC (2), Amazon, Ask Jeeves, the Canadian Space Agency, Equinox, Kodak, Lockheed Martin, Los Alamos, The National Renewable Energy Laboratory, Sarnoff, Siemens, Sprint, Texas Instruments, VMware, and Yahoo.

While larger departments can boast larger numbers of distinguished alumni, the overall quality of professional placements from URCS is hard to beat.


Research

Field-shaping ideas

Over the years, research at Rochester has changed the face of Computer Science.

The algorithms and complexity theory research group at the University of Rochester has made many field-shaping contributions, both foundational and applied. These are described on the URCS theory contributions web page.

Drawing inspiration from biological vision systems, Chris Brown, former faculty member Dana Ballard, and students developed the active vision paradigm, embedding computer vision in the physical world, applying it to concrete tasks, and leveraging information from moving camera platforms and task-specific knowledge. Freed from a focus on the static analysis of images, computer vision research blossomed in the 1980s. More recently, ground-breaking research in neural models of behavior has leveraged virtual reality to provide a powerful new window into the processes of human cognition, allowing researchers to control perception and measure response with unprecedented accuracy.

Interval-based temporal logic, developed by James Allen and his students, is now the standard temporal formalism for much of artificial intelligence and natural language processing, and forms the basis for much recent work on temporal ontologies. The language group at Rochester has also made seminal contributions to speech-act plan-based models of dialogue, including the first computational models of intention recognition for language understanding, the first multi-level plan representations for capturing dialogue intentions, and the most influential formalization of the plan recognition process. Rochester’s TRIPS system is probably the most sophisticated fully-functional spoken dialogue system in the world today.

Henry Kautz has made fundamental contributions to the field of efficient common-sense inference, including the planning as satisfiability framework. A 1987 URCS alum, Kautz recently joined the faculty after an illustrious career at Bell Labs, AT&T Labs, and the University of Washington.

Henry Kyburg is widely known for his formulation of logics of uncertain inference based on statistical evidence. His infamous “lottery paradox” has played an important role in both artificial intelligence and philosophy. He has also contributed to the understanding of the foundations of probability. In October of 2004 the departments of Philosophy and Computer Science hosted a major symposium on Probability and Inference in honor of Prof. Kyburg.

In parallel computing, the Rochester Intelligent Gateway project of the late 1970s and early 1980s laid the groundwork for modern network-centric operating systems, and is a direct ancestor of such commercially important systems as OSF Unix and MacOS X. In the mid 1980s, Rochester’s 128-node BBN Butterfly Parallel Processor was the largest shared-memory multiprocessor in the world. Work with the Butterfly influenced a whole generation of parallel operating systems and applications. The work of Tom LeBlanc and his students helped shape the field of parallel program debugging and performance analysis. Michael Scott’s work with URCS alum John Mellor-Crummey served to launch the field of scalable synchronization. Nonblocking data structures developed by Scott and his students are part of the Java standard library. Sandhya Dwarkadas’s work on the Treadmarks and FASTLINK systems played a major role in the discovery of the gene responsible for Parkinson’s disease.

For further information on current research programs, try the following links:

Cross-disciplinary focus

Much of the department’s research spans traditional boundaries not only among subareas of computer science, but between computer science and other allied fields.

  • Together with biologist Animesh Ray and others, Mitsunori Ogihara has studied the use of DNA for massively parallel computation. In particular, he developed a method to simulate logic gates using standard techniques of biochemistry. Supported in part by NSF grants (CCR-9701911, CCR-9725021, and DUE-9980943) he developed undergraduate courses that bridge between Biology and Computer Science: BIO/CSC120Q: Introduction to Computation Biology, BIO/CSC264: Computation Biology, and BIO/CSC290: Biomolecular Computation.
  • Prof. Ogihara has also been collaborating broadly with scientists in the School of Medicine and Dentistry on the analysis of microarray data, with support from the National Institutes of Health and the Alzheimer’s Foundation. His collaborators include Andrew Brooks, Ph.D., Director of the Functional Genomics Center; Paul Coleman, Ph.D., of the Center for Aging and Developmental Biology; Howard Federoff, M.D., Ph.D., Senior Associate Dean for Basic Research and Director of the Center for Aging and Developmental Biology; and David Pearce, Ph.D., of the Center for Aging and Developmental Biology. Ogihara also directs the Bioinformatics/Biostatistics Core of the Nathan Shock Center of Excellence in the Basic Biology of Aging, (Howard Federoff, Director).
  • The Center for Future Health aims to empower individuals in their health care by developing technologies inexpensive and user-friendly enough to deploy in the home, rather than the doctor’s office or hospital. Several CS faculty, including James Allen, George Ferguson, Wendi Heinzelman, and Randal Nelson are actively involved.
  • Henry Kautz brings to the University of Rochester an ambitious initiative in Assisted Cognition, which aims to create computer systems to help people suffering from cognitive disorders, such as the effects of Alzheimer's disease. Fundamental and applied problems in this project range over such diverse topics as probabilistic reasoning, plan recognition, ubiquitous computing, data fusion, user interfaces, and cognitive psychology.
  • The Center for Language Sciences is an interdisciplinary center spanning Linguistics, Psychology, Cognitive Science, Neuroscience, Computer Science, Engineering, and Philosophy. It fosters research both within and between these more traditional disciplines, through a colloquium series, workshops, access to working papers, formal coursework in contributing departments, shared laboratory and computational facilities, and a pre- and post-doctoral training grant from the National Institutes of Health.
  • The Computer Circuits and Systems Group is a joint venture of the departments of Computer Science and Electrical and Computer Engineering. As of spring 2005 it has a faculty of nine: 5 from ECE and 4 from CS. Two members of the ECE faculty (Heinzelman and Huang) have secondary appointments in CS; one member of the CS faculty (Dwarkadas) has a secondary appointment in ECE. The group functions smoothly as a cross-department entity: there are jointly supervised students, joint papers, joint meetings, and joint grants. Among other topics, cross-department projects are addressing power-aware system design and wireless computing.
  • During a Bridging Fellowship at the UR Political Science Department, Lane Hemaspaandra started a research project that now includes researchers at three Rochester-area schools, on the computational complexity of voting and apportionment systems. Among other things, this work has revealed that determining the winner in a famous voting system proposed by Lewis Carroll in 1876 is complete for parallel access to NP.
  • The University’s Laboratory for Laser Energetics houses the world’s most powerful X-ray laser, and is the leading site for research in (laser-induced) inertial confinement fusion. Members of the Computer Systems group (Scott, Dwarkadas, and Shen) have collaborated with colleagues at LLE on the high-end computer simulations that drive the understanding of experimental results and the design of future experiments.
  • Members of the CS faculty maintain active research ties with several other UR departments and centers. They routinely serve on Ph.D. committees in other departments, and co-supervise interdisciplinary degrees.

International collaborations

Members of the department maintain active collaborations with colleagues around the world.

  • James Allen has received funding from NSF for a collaborative project with the spoken dialogue group at IIMAS in Mexico City, headed by Luis Pineda. They are working on examining how well the Rochester spoken dialogue system can be used for Spanish.
  • Lane Hemaspaandra has long worked closely with researchers from Japan and Germany, participating in an NSF international collaboration grant with Japan and two with Germany, and an Alexander von Humboldt Foundation TransCoop collaboration grant with Germany. He has worked particularly closely with Wagner, Watanabe, Wechsung, Hempel, and Rothe, and is currently jointly with Wagner, Nickelsen, and Kosub studying cluster/interval computation and adding algebraic properties to selectors.
  • Mitsunori Ogihara has long worked closely with researchers from Japan, participating in two NSF international collaboration grants between Japan and the USA. He has worked particularly closely with Toda and Watanabe, and is currently working jointly with Toda and Liskiewicz researching self-avoiding walks.
  • Lenhart Schubert is working with Alfonso Gerevini of the University of Brescia, Italy, on the DISCOPLAN system for automated discovery of state invariants (“laws”) in planning domains. Such invariants have been used to speed up automated planning by orders of magnitude.
  • The department hosts a steady stream of postdocs and long-term research visitors in a variety of research areas. Recent countries of origin have included Argentina, Brazil, China, Germany, Italy, The Netherlands, Portugal, and Russia (as well as the United States), many of them supported by highly competitive international fellowship programs.

Local collaborations

Closer to home, the department works with several groups at nearby schools.

Field-shaping texts

Michael Scott’s Programming Language Pragmatics (Morgan Kaufmann, Second edition 2006) addresses the fundamental principles at work in the most important contemporary languages. It highlights the critical relationship between language design and language implementation, and devotes special attention to issues of importance to the expert programmer. With adoptions at over 120 schools, it occupies the #2 sales position in the field. Hemaspaandra and Torenvliet’s Theory of Semi-Feasible Algorithms (Springer-Verlag, 2003) presents the first consolidated survey of the vibrant field of research known as the theory of semi-feasible algorithms. It showcases the richness of, and contrasts between, the central notions of complexity: running time, nonuniform complexity, lowness, and NP-hardness.
Hemaspaandra and Ogihara’s The Complexity Theory Companion (Springer-Verlag, 2002) is an accessible, algorithmically oriented, research-centered, up-to-date guide to some of the most interesting techniques of complexity theory. The book’s thesis is that simple algorithms are at the heart of complexity theory. Its proof methods are algorithmic, and to highlight the role of algorithmic techniques, it is organized by technique rather than by topic. James Allen’s Natural Language Understanding (Addison-Wesley, 2nd edition, 1995), is the leading text in the field. It delivers a synthesis of the major modern techniques and the most current research in natural language processing. The approach is unique in its coverage of semantic interpretation and discourse alongside the foundational material in syntactic processing.
Uncertain Inference (Cambridge University Press, 2001), co-written by Henry Kyburg and former student Choh Man Teng, gathers approaches to the problem of uncertain inference into a framework unifying philosophy, computer science, and artificial intelligence. In an attempt to introduce readers to material traditionally covered in only one subdiscipline, it includes chapters on evidential probability, nonmonotonic reasoning and theory replacement, Mill’s methods, and statistical inference. Reasoning About Plans (Morgan Kaufmann, 1991), co-written by James Allen, Henry Kautz, Josh Tenenberg, and Richard Pelavin, presents an integrated framework for temporal reasoning, planning, and plan recognition.
Mitsunori Ogihara's Hierarchies in Complexity Theory (Kyoritsu Publishing Company, 2006) is an introductory complexity theory book in Japanese that covers a broad range of topics. Chapters are divided into Preliminaries; Turing Machines; Standard Hierarchy Theorems; NP-complete Problems; Complete Problems for P, NL, PSPACE, EXPTIME, and NEXPTIME; and The Polynomial Hierarchy. The last chapter contains expositions of Kadin's boolean hierarchy result and of Miller-Rabin primality testing algorithm. Ballard and Brown’s Computer Vision (Prentice Hall, 1982) was for many years the defining text for the field, and remains to this day a central resource for computer vision research.
Other books by Henry Kyburg:
Science and Reason
(Oxford University Press, 1990)
Theory and Measurement
(Cambridge University Press, 1984)
Epistemology and Inference
(University of Minnesota Press, 1983)
The Logical Foundations of Statistical Inference
(Reidel, Dordrecht, 1974)


Probability and Inductive Logic
(Macmillan, 1970)
Probability Theory
(Prentice-Hall, 1969)
Philosophy of Science
(Macmillan, 1968)
Probability and the Logic of Rational Belief
(Wesleyan University Press, 1961)

Technology transfer

Though the focus at Rochester is on long-term research, we value our many ties to industry, and endeavor to transfer our work into practice whenever appropriate.

  • Henry Kautz leads the new Kodak Intelligent Systems Research Center, which is spearheading the company’s drive to make the capturing, editing and storage of digital images more intuitive and effective by employing artificial intelligence.
  • Working with Virtual Research and Applied Science Laboratories, our virtual reality group was the first to integrate eye tracking into a head-mount display for high-resolution real-time monitoring of user focus in virtual environments.
  • Our virtual reality group has also worked with Sensable Technologies to create the first haptic (force feedback) system able to cover an entire table-top environment with a two-fingered grip touch interface.
  • Chen Ding's work on Memory Reference Affinity (with student Xipeng Shen, now on faculty at the College of William and Mary) has been implemented in IBM's C/C++ and Fortran production compilers, leading to dramatic speedups on several of the SPECfp 2000 benchmarks.
  • Mellor-Crummey & Scott queued spin locks have been incorporated into a variety of academic and commercial systems, including Compaq’s True64 Unix, IBM’s K42 multiprocessor OS, and Mercury Computer Corp.’s parallel real-time OS.
  • Michael & Scott’s lock-free queues have been incorporated into the Java 5 standard library.
  • Scherer & Scott’s Exchanger and SynchronousQueue algorithms (co-developed with Doug Lea of SUNY Oswego) have been adopted for Java 6.
  • Department research has resulted in a variety of patents and pending applications, including music feature extraction, the Cashmere-2L coherence protocol, scalable queue locks with timeout, and several aspects of Complexity-Adaptive Processing.
  • Department research has been supported in recent years by financial or equipment donations from Boeing, Compaq, IBM, Intel, Kodak, Mercury, Microsoft, and Sun.

External recognition

  • The 1993 NRC rankings of research-doctorate programs in computer science placed URCS 30th in the nation overall. These statistics are strongly correlated with size (see scatterplot). On more size-independent submetrics, URCS ranked
    • 5th in publications per faculty member
    • 14th in citations per faculty member
    • 14th in the effectiveness of the graduate program
  • Rochester has the rare distinction of having received continuous funding from the National Science Foundation Research Infrastructure program from 1984 to 2005. Also known by the earlier names CER (Coordinated Experimental Research) and IIP (Institutional Infrastructure Program), RI grants fund the acquisition of unique, large-scale hardware resources for interdisciplinary work. At Rochester these grants recognized ground-breaking collaboration among researchers in Computer Systems, Spatial AI, Symbolic AI, and Theory.
  • With an annual budget of over $5M, and research expenditures around $3M, URCS external funding averages well over $200K/faculty member per year. While larger departments often have larger total budgets, per capita funding at Rochester is very strong.

Facilities

URCS Research facilities are by any measure outstanding (see separate page). Particularly noteworthy are the Vision and Robotics Lab, and the Computer Systems Lab.

Significant hardware donations in recent years have come from Compaq, IBM, Intel, Microsoft, and Sun. Of particular note, the department in spring 2002 received a $1.2M award under IBM’s Shared University Research program, allowing it to acquire a 32-processor IBM pSeries 690 (“Regatta”) machine. More recent awards From Sun Microsystems Laboratories have provided the department with 8 and 16-processor SunFire multiprocessors.


The academic program

URCS was founded as a Ph.D.-only department in 1974. The first degrees were awarded in 1980. The department typically admits 10–12 Ph.D. students each fall, and graduates about 7 every year. Time to completion of the Ph.D. is just over 5 years on average. The department also offers a “3-2” combined B.S./M.S. program, and a small professional Master’s program.

While the department has taught undergraduates from the outset (largely through the Applied Mathematics: Computer Science program in the Math department), it did not administer its own B.S. and B.A. programs until 1995, with the first degrees awarded in the spring of 1996. In 2004 the department received the University’s Goergen award for curricular achievement.

As noted above, the National Research Council ranked URCS 14th in the nation in the “effectiveness of the graduate program”. James Allen has received the University’s Curtis award for graduate teaching. Michael Scott has received the University’s Goergen award for undergraduate teaching. Wendi Heinzelman has received the University’s Curtis award for teaching by a non-tenured member of the faculty.


The value of being small

Most other top-ranked departments are 3 to 4 times our size. Smallness has an impact, of course, on the total number of students and publications, the total size of the budget, the total number of alumni, etc., but it does not have an impact on the things that really matter: the output of the department per person, and the quality of the research, the people, and the programs.

While it is difficult for a small department to compete with the sheer volume and variety of work at larger schools, there are significant advantages to being small. Many of these advantages impact quality of life, making URCS is a great place to work or to get a degree. Many, however, impact research quality as well, inspiring us to do research that we probably wouldn’t do at a larger school.

  • Cross-disciplinary focus — As noted above, the department places a heavy emphasis on interdisciplinary work. Small size facilitates this emphasis: groups naturally seek each other out to help build critical mass. At the University level, administrative policies make it easy to share funding and appointments across departments and schools. More locally, the department deliberately encourages “cross fertilization” by mixing student office space by area: the typical room houses students with three different research advisiors, working in AI, Systems, and Theory.
  • Personal attention — With about 3–4 Ph.D. students per faculty member, on average, doctoral candidates receive a great deal of personal attention. Most students become active in research during their first year of graduate study. Beyond that first year, most learning occurs one-on-one or in small groups at the whiteboard, rather than in a classroom setting.
  • Communal resource model — The department pools financial resources to the maximum extent consistent with granting agency guidelines. Every Ph.D. student is guaranteed support throughout the course of graduate studies, regardless of choice of advisor or research topic. A department-wide committee coordinates all major equipment purchases, to maximize the potential to meet multiple research needs. Machines are then uniformly available to all faculty, grad students, visitors, and postdocs. All Unix and NT machines run a common password file, and all file systems are universally cross-mounted, so one can log on anywhere and feel at home.
  • Collaborative decision making — Because the entire faculty will fit around one table, decisions can be made almost entirely by consensus. Graduate student representatives serve on all department committees, and play a major role in graduate admissions, facilities, and curricular development.
  • Collegial atmosphere — Because everyone in the department knows everyone else, the social and professional atmosphere is unusually warm and collegial. There are weekly parties, and department teams in the intramural sports leagues (hockey is a long-time favorite).

The city and quality of life

Recently ranked as one of the Northeast’s 10 “Best Places to Live in America” by Money magazine, Rochester has also been listed as one of the “Most Livable Cities” in America by Partners for Livable Communities, a rating based on Rochester’s technology-focused economy, recreational opportunities, and historic neighborhoods. There is a thriving arts and entertainment scene, fueled in part by the UR’s own Eastman School of Music (the number one music school in the country). There is a wide variety of affordable housing within easy distance of campus. The surrounding countryside is gorgeous. There are four real seasons, each with its distinctive charm, and contrary to rumors you may have heard, winter is not significantly longer than the other three :-).

For more information on the Greater Rochester Area, check out the pages maintained by the UR Public Relations Department and the UR Admissions Office.


For further information

To learn more about department life and academic programs, or to apply to the Ph.D. program, CLICK HERE.


Maintained by the Recruitment Committee. Last change: October 16, 2007
Please report problems with the server to www@cs.rochester.edu.