Communications of the ACM
Latest Research
From Communications of the ACM
The Complexity of Computing a Nash Equilibrium
Traditionally, computational problems fall into two classes: those that have a polynomial-time algorithm and those that are NP-hard. However, the concept of NP-hardness...
From Communications of the ACM
Technical Perspective: The Complexity of Computing Nash Equilibrium
Computer science and game theory go back to the same individual, John von Neumann, and both subjects deal with the...
From Communications of the ACM
Building Secure Web Applications With Automatic Partitioning
Swift is a new, principled approach to building Web applications that are secure by construction. Swift automatically partitions application code while providing...
From Communications of the ACM
Technical Perspective: Tools For Information to Flow Securely and Swift-ly
Back in the old days of the Web (before 1995), Web browsers were fairly simple devices. The server's Web interface was simple enough that an auditor could at least...
From Communications of the ACM
Voyagers and Voyeurs: Supporting Asynchronous Collaborative Visualization
This article describes mechanisms for asynchronous collaboration in the context of information visualization, recasting visualizations as not just analytic tools...
From Communications of the ACM
Technical Perspective: Finding and Telling Stories with Data
Visual analysis, a powerful method for finding and telling stories with data, is moving from research into widespread use.
From Communications of the ACM
Technical Perspective: Patching Program Errors
C programmers are are all too familiar with out-of-bounds memory errors. The paper here presents an intriguing technique for...
From Communications of the ACM
Technical Perspective: One Size Fits All: An Idea Whose Time Has Come and Gone
Beginning in the early to mid-1980s the relational model of data has dominated the DBMS landscape. Moreover, descendents of...
From Communications of the ACM
Exterminator: Automatically Correcting Memory Errors with High Probability
Programs written in C and C++ are susceptible to memory errors, including buffer overflows and dangling pointers. We present Exterminator, a system that automatically...
From Communications of the ACM
Breaking the Memory Wall in MonetDB
In this paper, we report how research around the MonetDB database system has led to a redesign of database architecture in order to take advantage of modern hardware...
From Communications of the ACM
Polaris: A System For Query, Analysis, and Visualization of Multidimensional Databases
In this paper, we address these demands by presenting the Polaris formalism, a visual query language for precisely describing a wide range of table-based graphical...
From Communications of the ACM
Technical Perspective: Safeguarding Online Information Against Failures and Attacks
Users need storage that is highly reliable (it is not lost) and highly available (accessible when needed). Guaranteeing...
From Communications of the ACM
Technical Perspective: The Polaris Tableau System
Jim Gray nominated the Polaris paper for the Research Highlights section and wrote the first draft of this Technical Perspective in November 2006. David Patterson...
From Communications of the ACM
Zyzzyva: Speculative Byzantine Fault Tolerance
A longstanding vision in distributed systems is to build reliable systems from unreliable components. An enticing formulation of this vision is Byzantine fault-tolerant...
From Communications of the ACM
Technical Perspective: Computational Photography on Large Collections of Images
This paper wil strike a familiar chord with anyone who has ever taken a picture. The problem is easy to understand— replacing unwanted parts of a photograph.
From Communications of the ACM
Geometry, Flows, and Graph-Partitioning Algorithms
"Graph partitioning" refers to a family of computational problems in which the vertices of a graph have to be partitioned...
From Communications of the ACM
Scene Completion Using Millions of Photographs
What can you do with a million images? In this paper, we present a new image completion algorithm powered by a huge database of photographs gathered from the Web...
From Communications of the ACM
Technical Perspective: New Developments in Graph Partitioning
Arora, Rao, and Vazirani discuss the most important developments in approximation algorithms over the last two decades.
From Communications of the ACM
Technical Perspective: Transactional Memory in the Operating System
The long tradition of building ever-faster processors is ending, with the computer industry instead putting more...
From Communications of the ACM