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...Ariel D. Procaccia From Communications of the ACM | April 2020
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...Haris Aziz, Simon Mackenzie From Communications of the ACM | April 2020
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...Rebecca Isaacs From Communications of the ACM | March 2020
This paper presents Pivot Tracing, a monitoring framework for distributed systems, which addresses the limitations of today's monitoring and diagnosis tools by...Jonathan Mace, Ryan Roelke, Rodrigo Fonseca From Communications of the ACM | March 2020
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...David G. Andersen From Communications of the ACM | November 2019
We design, implement, and evaluate DeepXplore, the first white-box framework for systematically testing real-world deep learning systems.
Kexin Pei, Yinzhi Cao, Junfeng Yang, Suman Jana From Communications of the ACM | November 2019
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...Andrew W. Appel From Communications of the ACM | October 2019
In this work, we present CertiKOS, a novel compositional framework for building verified concurrent OS kernels.
Ronghui Gu, Zhong Shao, Hao Chen, Jieung Kim, Jérémie Koenig, Xiongnan (Newman) Wu, Vilhelm Sjöberg, David Costanzo From Communications of the ACM | October 2019
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...Graham Cormode From Communications of the ACM | August 2019
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...Kasper Green Larsen, Jelani Nelson, Huy L. Nguyễn, Mikkel Thorup From Communications of the ACM | August 2019
Umesh Vazirani and Thomas Vidick's "Fully Device Independent Quantum Key Distribution" provides an unexpectedly simple and elegant secure protocol solution, indeed...Gilles Brassard From Communications of the ACM | April 2019
We rigorously provide the device-independent security of an entanglement-based protocol building on Ekert's original proposal for quantum key distribution.
Umesh Vazirani, Thomas Vidick From Communications of the ACM | April 2019
Whether there exists a deterministic parallel algorithm for bipartite matching remains an outstanding question at the frontiers of our understanding of the role...Nisheeth K. Vishnoi From Communications of the ACM | March 2019
In this article, we give an almost complete derandomization of the Isolation Lemma for perfect matchings in bipartite graphs.
Stephen Fenner, Rohit Gurjar, Thomas Thierauf From Communications of the ACM | March 2019
"Predicting Program Properties from 'Big Code'" presents new techniques for leveraging big code to automate two programming activities: selecting understandable...Martin C. Rinard From Communications of the ACM | March 2019
The authors of "Distributed Strategies for Computational Sprints" bring the rich theory of allocating scarce resources to the challenge of managing computational...Thomas F. Wenisch From Communications of the ACM | February 2019
We describe a computational sprinting architecture in which many, independent chip multiprocessors share a power supply and sprints are constrained by the chips'...Songchun Fan, Seyed Majid Zahedi, Benjamin C. Lee From Communications of the ACM | February 2019
"Scalable Computation of High-Order Optimization Queries," by Brucato et al., makes a case for marrying the well-established paradigms of constrained optimization...Surajit Chaudhuri From Communications of the ACM | February 2019
We present a complete system that supports package queries, a new query model that extends traditional database queries to handle complex constraints and preferences...Matteo Brucato, Azza Abouzied, Alexandra Meliou From Communications of the ACM | February 2019