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
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
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.
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.
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.
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.
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 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
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.
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.
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.
Saccade contingent scene changes in unconstrained virtual reality
Established complexity-theoretic analogues of Rice's Theorem.
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
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
Non-Euclidean object representations for calibration-free video overlay
