Communications of the ACM
Latest Research
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: SQL on an Encrypted Database
There is some risk in trusting the cloud providers with sensitive data. Why not encrypt the data stored in cloud services?
From Communications of the ACM
CryptDB: Processing Queries on an Encrypted Database
An ideal solution to satisfying the dual goals of protecting data confidentiality and running computations is to enable a server to compute over encrypted data,...
From Communications of the ACM
Technical Perspective: Innovative Interaction: From Concept to the Wild
The history of the relationship between writing systems and technology is as long as it is varied. Likewise, the challenge of entering text using portable gadgets...
From Communications of the ACM
The Word-Gesture Keyboard: Reimagining Keyboard Interaction
As computing technologies expanded beyond the confines of the desktop, the need for effective text entry methods alternative to the ubiquitous desktop keyboards...
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: Example-Driven Program Synthesis For End-User Programming
As information technology has come to permeate our society, broader classes of users have developed the need for more sophisticated data manipulation and processing...
From Communications of the ACM
Spreadsheet Data Manipulation Using Examples
Millions of computer end users need to perform tasks over large spreadsheet data, yet lack the programming knowledge to do such tasks automatically. We present...
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