Communications of the ACM
Latest Research
From Communications of the ACM
Technical Perspective: A New Spin on an Old Algorithm
A paper by Ballard, Demmel, Holtz, and Schwartz considers a fundamental problem, adopting a new perspective on an old algorithm that has for years occupied a peculiar...
From Communications of the ACM
Communication Costs of Strassen's Matrix Multiplication
Proving lower bounds on the communication of algorithms and finding algorithms that attain these bounds are fundamental goals.
From Communications of the ACM
Technical Perspective: The Cleanest Garbage Collection
In quite a tour de force, the authors of the following paper have built a provably correct real-time garbage collector for reconfigurable hardware (field programmable...
From Communications of the ACM
And Then There Were None: A Stall-Free Real-Time Garbage Collector For Reconfigurable Hardware
We present a garbage collector synthesized directly to hardware, capable of collecting a heap of uniform objects completely concurrently. These heaps are composed...
From Communications of the ACM
Technical Perspective: The Ray-Tracing Engine That Could
It has been an open question whether it is possible to build GPU-targeted high-performance software systems that are themselves programmable. "GPU Ray Tracing" shows...
From Communications of the ACM
GPU Ray Tracing
The NVIDIA OptiX ray tracing engine builds on the key observation that most ray tracing algorithms can be implemented using a small set of programmable operations...
From Communications of the ACM
Technical Perspective: Visualization, Understanding, and Design
Photographs capture the moment; paintings convey perception, impression, and feeling; illustrations tell stories. Computer graphics aims to enrich all these artistic...
From Communications of the ACM
Illustrating How Mechanical Assemblies Work
How-things-work visualizations use a variety of visual techniques to depict the operation of complex mechanical assemblies. We present an automated approach for...
From Communications of the ACM
Technical Perspective: High-Level Data Structures
This lifting of data structure thinking to the relational level has long inspired computer scientists. In "An Introduction to Data Representation Synthesis," the...
From Communications of the ACM
An Introduction to Data Representation Synthesis
We consider the problem of specifying combinations of data structures with complex sharing in a manner that is declarative and results in provably correct code.
From Communications of the ACM
Technical Perspective: Graph Embeddings and Linear Equations
Algorithmic advances can come from the most unexpected places. The following paper describes an emerging approach to solving linear systems of equations that...
From Communications of the ACM
A Fast Solver For a Class of Linear Systems
The solution of linear systems is a problem of fundamental theoretical importance but also one with a myriad of applications in numerical mathematics, engineering...
From Communications of the ACM
Technical Perspective: A High-Dimensional Surprise
High-dimensional space is a counterintuitive place, where natural geometric intuitions from the familiar three-dimensional world may lead us badly astray.
From Communications of the ACM
Spherical Cubes: Optimal Foams from Computational Hardness Amplification
Foam problems are about how to best partition space into bubbles of minimal surface area. We investigate the case where one unit-volume bubble is required to tile...
From Communications of the ACM
Technical Perspective: Proving Programs Continuous
Proving a program's correctness is usually an all-or-nothing game.
From Communications of the ACM
Continuity and Robustness of Programs
Computer scientists have long believed that software is different from physical systems in one fundamental way: while the latter have continuous dynamics, the former...
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