History, Accomplishments, Accolades

Decades of Research

Since the inception of the Department of Computer Science at Rochester, trail-blazing research has changed the face of the discipline and influenced industry. Much of the department’s research spans traditional boundaries not only among sub-areas of computer science, but between computer science and other allied fields such as data science, brain and cognitive science, linguistics, neuroscience, medicine, as well as hardware design and functionality.

Examples of Significant Research Contributions

Drawing inspiration from biological vision systems, Chris Brown, former faculty member Dana Ballard, and their 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.

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.

The language group at Rochester has 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 was one of the earliest most sophisticated fully-functional spoken dialogue systems in the world.

Henry Kautz has made fundamental contributions to the field of efficient commonsense inference, including the planning as satisfiability framework. A 1987 URCS alum, Kautz joined the faculty in 2006 after an illustrious career at Bell Labs, AT&T Labs, and the University of Washington, served as department chair from 2008-2014 and is currently serving a 3-year term as Director of NSF Division for Information and Intelligent Systems.

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 former faculty member 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. Their MSqueue lock has been adopted by many commercial libraries and operating systems. 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. Kai Shen's work on cluster management formed the backbone of Internet search site Ask.com.

Research Summaries by Decade

For information about our more current research, please visit our current research page.

1970s

  • The Rochester Intelligent Gateway (RIG) was a precursor to Mac OS (via Accent, Mach, and NextStep), developed by Jerry Feldman, Rich Rashid, Luidy Bukys, and others. It created an operating system that could manage multiple machines at once.
  • Rochester was one of the first sites to be connected to the ARPAnet, the precursor to the Internet.
  • Games of incomplete information
  • One of the first early raster graphics engine systems provided a means to discover how to label simple images, explore early pattern recognition finding methods, study clustering feature vectors and computer vision.
    Projects: (http://hdl.handle.net/1802/13715); (http://hdl.handle.net/1802/14137)
  • Xerox Alto Machine.
    Xerox Alto Machine
    In 1978 Xerox donated 50 Altos to the Massachusetts Institute of Technology, Stanford University, Carnegie Mellon University,[15] and the University of Rochester (With the Altos (which were named John, George, Paul and Ringo), research on networked machines began. These machines allowed researchers to study supervised learning, and early planning. They also developed methods for organizing data for quick retrieval.) Projects: (http://hdl.handle.net/1802/12601) With these machines came an instance of Xerox’s original (3Mb) Ethernet prototype and a laser printer.
  • Synchronization and distribute computing

1980s

Students wokring in the Hylan computer lab.
Hylan computer lab
  • Research in the 80’s focused on early connectionist theories, the building of neural nets, understanding grammatical structures with sentence parsing, early color vision, representation of world knowledge to assist language understanding, development of connectionist software for use by other researchers and combining partial evidence in visual recognition using Hough transforms. It was a time of great discovery with development of computational models of psycho-physics and neuroanatomy, common sense reasoning using probabilities and logic, and plan recognition in conversation. In imaging, we developed methods for real-time analyses of images using Active Vision, we were able to reconstruct a 3D world from a series of 2D images. A binocular robot head was built in house that allowed for convergence control research.
  • Grammatical inference
  • Algorithmic learning theory
  • The natural language processing group began a long-term project to develop a mechanism that could partake in an extended English dialogue on some reasonably well specified range of topics. The first project was ARGOT, with later research producing TRAINS and TRIPS. (see 1990s)
  • String-matching algorithms
  • Algorithmic information theory
  • Generalizing the Hough transform to detect arbitrary shapes.
  • Kolmogorov-complexity applications in computational complexity
  • Efficient text indexing
  • Mark Crovella and the BBN Butterfly machine.
    Mark Crovella and the BBN Butterfly machine.
    The department housed the BBN Butterfly (a massively parallel computer) built by Bolt, Beranek and Newman. Rochester's 128-node machine had the distinction of being the largest shared-memory multiprocessor in the world at that time. In the course of the work with the Butterfly we ported three compilers, developed five major and several minor library packages, built two different operating systems, and implemented dozens of applications. Our experience clearly demonstrated the practicality of large-scale shared-memory multiprocessors, with non-uniform memory access times. Projects: PSYCHE (link to: http://hdl.handle.net/1802/6047); PPUTTS (link to http://hdl.handle.net/1802/5515)
  • Resource-bounded complexity hierarchies

1990s

Randal Nelson with PUMA robot and MIT hand.
Randal Nelson with PUMA robot and
MIT hand.
  • The addition of a PUMA robot began a series of projects in hand-eye coordination and active vision.
  • John Mellor-Crummey and Michael Scott’s queued spin locks were 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.
  • Algorithms on mesh-connected processor arrays
  • Deictic codes for the embodiment of cognition
  • Multi-view 3D shape and motion recovery on the spatio-temporal curve manifold
  • Collapsed two logspace hierarchies
  • Working with Virtual Research and Applied Science Laboratories,
    Jeff Pelz using head-mounted eyetracker while completing tasks.
    Jeff Pelz using head-mounted
    eyetracker while completing tasks.
    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.
  • Eye movements reveal the spatio-temporal dynamics of visual search.
  • The Rochester Checkers Player, a joint effort between systems and AI, demonstrated the value of multi-model computing. Game strategy, computer vision, and motion planning all ran (in different languages) on the Psyche operating system. The resulting system was featured on the cover of Science News.
  • Developed efficient algorithms for association rule mining.
  • The cover of Science News.Non-Euclidean object representations for calibration-free video overlay
  • Our virtual reality group had 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.
  • Developed the world's first molecular Boolean circuit.
  • Category Learning through Multi-Modality Sensing
  • Enumerative approximation is no easier than exact solution for NP counting problems.
  • Established hardest closure properties for NP's counting version.
  • Cashmere was a software distributed shared memory (S-DSM) system designed for high-performance cluster architectures of the time period—the first to integrate hardware shared memory within machines and software shared memory across machines. The follow-on InterWeave project extended S-DSM to automate the management of cached data across the Internet, with interoperability across a host of programming languages, operating systems, and hardware architectures.
  • Hardware generations through the decadesHardware generations through the decades
  • Lewis Carroll's 1876 election system is complete for parallel access to NP.
  • Optimal lowness theory
  • Memory representations in natural tasks
  • NP lacks unique solutions unless the polynomial hierarchy collapses.
  • Persistent data structures
  • Color Indexing
  • Obtained apportionments of the US House of Representatives that are provably more power-fair than those of the apportionment algorithm currently mandated by law.
  • Probabilistic automata
  • Exploring objects by invariant-based tangential viewpoint control
  • Calibration-Free Augmented Reality
  • The Complexity Adaptive Processing (CAP) project pioneered techniques to dynamically adapt the memory system and microarchitecture to the needs of an application.
  • Altering reality through interactive image and video manipulation.
  • Probabilistic one-bit bottleneck machines suffice to accept all sets from the polynomial hierarchy.
  • Proved that if any one-way function exists then strong, total, commutative, associative one-way functions exist.
  • Structural complexity theory
  • Allen Heeman.
    James Allen and Peter Heeman work
    on language understanding system.
  • Building on the NLP system ARGOT, later research in our natural language group produced TRAINS and TRIPS. Each of these projects furthered human-machine conversational interaction, with task-oriented dialogues between a user and a planning assistant. Later research involved a robust speech act interpretation system, grammar usage and a parsing system.
  • Proved that sparse hard sets for P result in Dubliner algorithms for P
  • The complexity of query order

2000s

  • Complexity of cooperative games
  • Building on work begun in the early 1990s, Rochester became a leading site for research on synchronization, concurrent data structures, and transactional memory. The locally developed MCS queue-based lock and the M&S queue are used in almost every large-scale operating system. Several locally developed data structures are part of the Java standard library.
  • Modeling Embodied Visual Behaviors
  • 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
  • Computational social choice theory
  • Complexity of Counting and Sampling i.e. nearly-optimal sampling-counting connection
  • Multi-view scene capture by surfel sampling: from video streams to non-rigid 3D motion, shape and reflectance.
  • Constructed a black-box in which quantum computers have an exponential advantage over classical computers almost everywhere.
  • George Ferguson interacts with home medication advisor using natural language.
    George Ferguson interacts with home medication advisor
    using natural language.
    Developed a wavelet-based feature extraction algorithm for music genre characterization
  • Medication Advisor Project – conversational agent using spoken dialogue for elderly patients.
  • Locality Theory - to rigorously define, measure and optimize locality of access.
  • A Probabilistic Theory of Occupancy and Emptiness
  • Developed an efficient algorithm for estimating entropy of frequency distributions of network packets.
  • Graph Drawing including understanding differences and similarities between geometric and algebraic versions of crossing numbers and efficient algorithms for compressed curves on surfaces.
  • Dana Ballard and Mary Hayhoe with the virtual reality helmet.
    Dana Ballard and Mary Hayhoe with the virtual
    reality helmet.
    Saccade contingent scene changes in unconstrained virtual reality
  • Established complexity-theoretic analogues of Rice's Theorem.
  • Dichotomy theorems for electoral manipulation, bribery, and control
  • Introduced destructive control of elections
  • Modeling Embodied Visual Behaviors
  • Introduced the complexity-theoretic study of bribery
  • Multi-view scene capture by surfel sampling: from video streams to non-rigid 3D motion, shape and reflectance
  • Proved the resistance to all standard control attacks of Llull's thirteenth-century election system.
  • Large-scale dynamic data adaptation
  • Sorting networks
  • WebTrax: Visualizing Non-Visual Web Interactions
  • The complexity of competing provers
  • Locality Theory - to rigorously define, measure and optimize locality of access.
  • Compassable models and techniques for multicore cache analysis and optimization
  • Theory of semi-feasible algorithms
  • Toward a Domain-Specific Visual Discussion Forum for Learning Computer Programming: An Empirical Study of a Popular MOOC Forum
  • Eastman team.
    Professors Randal Nelson and Chris Brown with grad
    students Paul Ardis and Ross Messing, with undergraduate
    Xiaoqing Tang.
    Finding Your Friends and Following Them To Where You Are
  • A Probabilistic Theory of Occupancy and Emptiness
  • Adaptive Memory Management in Shared Environments
  • Saccade contingent scene changes in unconstrained virtual reality
  • Digital Analysis and Restoration of Daguerreotypes
  • Speculative program parallelization and optimization
  • Using Machine Learning to correct flaws in historical daguerreotypes
  • Codechella: Multi-User Program Visualizations for Real-Time Tutoring and Collaborative Learning