Communications of the ACM
Latest Research
From Communications of the ACM
Technical Perspective: Why Study the Price of Anarchy?
In 1999, Elias Koutsoupias and Christos Papadimitriou initiated the study of "How much worse off are we due to selfishness?" They compared the worst case pure...
From Communications of the ACM
Intrinsic Robustness of the Price of Anarchy
The price of anarchy, defined as the ratio of the worst-case objective function value of a Nash equilibrium of a game and that of an optimal outcome, quantifies...
From Communications of the ACM
Technical Perspective: For Better or Worse, Benchmarks Shape a Field
Like other IT fields, computer architects initially reported incomparable results. We quickly saw the folly of this approach. We then went through a sequence...
From Communications of the ACM
Looking Back and Looking Forward: Power, Performance, and Upheaval
The past 10 years have delivered two significant revolutions. Microprocessor design has been transformed — leading to multicore processors. And an entirely new...
From Communications of the ACM
Lightweight Modular Staging: A Pragmatic Approach to Runtime Code Generation and Compiled DSLs
Good software engineering practice demands generalization and abstraction, whereas high performance demands specialization and concretization. These goals are at...
From Communications of the ACM
Technical Perspective: The Fox and the Hedgehog
"The fox knows many things, but the hedgehog knows one big thing." Philosophers have used this line, attributed to the ancient Greek poet Archilochus, to capture...
From Communications of the ACM
Exact Matrix Completion via Convex Optimization
Suppose that one observes an incomplete subset of entries selected from a low-rank matrix. When is it possible to complete the matrix and recover the entries that...
From Communications of the ACM
Technical Perspective: Reconstructing the Unknown, Balancing Structure and Uncertainty
The problem of estimating or reconstructing an unknown structured object from incomplete, partial, noisy measurements is a fundamental one in scientific and technological...
From Communications of the ACM
Technical Perspective: An Experiment in Determinism
It is widely held that parallel programming is far more difficult and error prone than writing sequential code. In particular, the myriad allowable interleavings...
From Communications of the ACM
Efficient System-Enforced Deterministic Parallelism
We introduce a new parallel programming model addressing the issues facing current methods of executing parallel programs deterministically, and use Determinator...
From Communications of the ACM
Technical Perspective: Best Algorithms + Best Computers = Powerful Match
Say you want to simulate the motion over time of the stars in a galaxy to learn about how galaxies formed and why the universe appears as it does. Is it feasible...
From Communications of the ACM
A Massively Parallel Adaptive Fast Multipole Method on Heterogeneous Architectures
We describe a parallel fast multipole method for highly nonuniform distributions of particles. We employ both distributed memory parallelism and shared memory parallelism...
From Communications of the ACM
The Grand Challenge of Computer Go: Monte Carlo Tree Search and Extensions
The ancient oriental game of Go has long been considered a grand challenge for artificial intelligence. However, computer Go programs based on Monte-Carlo tree...
From Communications of the ACM
Technical Perspective: A New Way to Search Game Trees
Researchers in artificial intelligence know that computers still lag far behind human levels of play in many games of strategy. One such contest of wits is Go...
From Communications of the ACM
Technical Perspective: The Benefits of Capability-Based Protection
Affordable personal computing hardware and the usable GUI-based PC operating systems made the vision of "a computer on every desktop and in every home" a reality...
From Communications of the ACM
A Taste of Capsicum: Practical Capabilities For Unix
Capsicum is a lightweight operating system capability and sandbox framework planned for inclusion in FreeBSD 9. Capsicum extends, rather than replaces, UNIX APIs...
From Communications of the ACM
Technical Perspective: Modeling High-Dimensional Data
Data in high dimension is difficult to visualize and understand. This has always been the case and is even more apparent now with the availability of large high...
From Communications of the ACM
Disentangling Gaussians
The Gaussian mixture model is one of the oldest and most widely used statistical models. Our work focuses on the case where the mixture consists of a small but...
From Communications of the ACM
Technical Perspective: Compiling What to How
The following paper by Viktor Kuncak et al. integrates declarative programming into a general-purpose language, allowing one to escape the host language when...
From Communications of the ACM