Communications of the ACM
Latest Research
From Communications of the ACM
Technical Perspective: Algorithm Selection as a Learning Problem
"Data-Driven Algorithm Design," by Rishi Gupta and Tim Roughgarden, addresses the issue that the best algorithm to use for many problems depends on what the input...
From Communications of the ACM
Data-Driven Algorithm Design
We model the problem of identifying a good algorithm from data as a statistical learning problem.
From Communications of the ACM
Technical Perspective: An Answer to Fair Division's Most Enigmatic Question
The envy-free cake-cutting problem stood its ground for two decades, until it was cracked by Aziz and Mackenzie. Their solution is presented in "A Bounded and Envy...
From Communications of the ACM
A Bounded and Envy-Free Cake Cutting Algorithm
We report on our algorithm that resolved the well-studied cake cutting problem in which the goal is to find an envy-free allocation of a divisible resource based...
From Communications of the ACM
Technical Perspective: A Perspective on Pivot Tracing
Instead of handing trace records off to a collector for long-term storage and future processing, the system described in "Pivot Tracing: Dynamic Causal Monitoring...
From Communications of the ACM
Pivot Tracing: Dynamic Causal Monitoring for Distributed Systems
This paper presents Pivot Tracing, a monitoring framework for distributed systems, which addresses the limitations of today's monitoring and diagnosis tools by...
From Communications of the ACM
Technical Perspective: A Whitebox Solution for Blackbox-Like Behaviors
DeepXplore brings a software testing perspective to deep neural networks and, in doing so, creates the opportunity for enormous amounts of follow-on work in several...
From Communications of the ACM
DeepXplore: Automated Whitebox Testing of Deep Learning Systems
We design, implement, and evaluate DeepXplore, the first white-box framework for systematically testing real-world deep learning systems.
From Communications of the ACM
Technical Perspective: The Scalability of CertiKOS
The authors of "Building Certified Concurrent OS Kernels" illustrate that formal verification can scale up to a moderate-size program (6,500 lines of C) that has...
From Communications of the ACM
Building Certified Concurrent OS Kernels
In this work, we present CertiKOS, a novel compositional framework for building verified concurrent OS kernels.
From Communications of the ACM
Technical Perspective: The True Cost of Popularity
The main focus of "Heavy Hitters via Cluster-Preserving Clustering" by Kasper Green Larsen et al. is on building up sufficient information to allow a more effective...
From Communications of the ACM
Heavy Hitters via Cluster-Preserving Clustering
We develop a new algorithm for the turnstile heavy hitters problem in general turnstile streams, the EXPANDERSKETCH, which finds the approximate top-k items in...
From Communications of the ACM
Technical Perspective: Was Edgar Allan Poe Wrong After All?
Umesh Vazirani and Thomas Vidick's "Fully Device Independent Quantum Key Distribution" provides an unexpectedly simple and elegant secure protocol solution, indeed...
From Communications of the ACM
Fully Device Independent Quantum Key Distribution
We rigorously provide the device-independent security of an entanglement-based protocol building on Ekert's original proposal for quantum key distribution.
From Communications of the ACM
Technical Perspective: Isolating a Matching When Your Coins Go Missing
Whether there exists a deterministic parallel algorithm for bipartite matching remains an outstanding question at the frontiers of our understanding of the role...
From Communications of the ACM
A Deterministic Parallel Algorithm for Bipartite Perfect Matching
In this article, we give an almost complete derandomization of the Isolation Lemma for perfect matchings in bipartite graphs.
From Communications of the ACM
Technical Perspective: Borrowing Big Code to Automate Programming Activities
"Predicting Program Properties from 'Big Code'" presents new techniques for leveraging big code to automate two programming activities: selecting understandable...
From Communications of the ACM
Predicting Program Properties from 'Big Code'
We present a new approach for predicting program properties from large codebases (aka "Big Code").
From Communications of the ACM
Technical Perspective: How Economic Theories Can Help Computers Beat the Heat
The authors of "Distributed Strategies for Computational Sprints" bring the rich theory of allocating scarce resources to the challenge of managing computational...
From Communications of the ACM