Communications of the ACM
Latest Research
From Communications of the ACM
Technical Perspective: Maximum Flow through a Network: A Storied Problem and a Groundbreaking Solution
"Almost-Linear-Time Algorithms for Maximum Flow and Minimum-Cost Flow," by Li Chen et al., comes within striking distance of answering the question: "Does maximum...
From Communications of the ACM
Almost-Linear-Time Algorithms for Maximum Flow and Minimum-Cost Flow
We present an algorithm that computes exact maximum flows and minimum-cost flows on directed graphs with m edges and polynomially bounded integral demands, costs...
From Communications of the ACM
Technical Perspective: What's All the Fuss about Fuzzing?
"Boosting Fuzzer Efficiency: An Information Theoretic Perspective," by Marcel Böhme, Valentin J.M. Manès, and Sang Kil Cha, presents a novel twist to fuzzing that...
From Communications of the ACM
Boosting Fuzzer Efficiency: An Information Theoretic Perspective
In this paper, we take the fundamental perspective of fuzzing as a learning process.
From Communications of the ACM
Technical Perspective: Tapping the Link between Algorithmic Model Counting and Streaming
"Model Counting Meets Distinct Elements," by A. Pavan et al., gives a surprising connection between model counting and streaming, providing a generic transformation...
From Communications of the ACM
Model Counting Meets Distinct Elements
In this work, we seek to investigate whether bridging the seeming communication gap between two different domains of computer science may pave the way to richer...
From Communications of the ACM
Technical Perspective: Opening the Door to SSD Algorithmics
The authors of "Offline and Online Algorithms for SSD Management" propose a more accurate theoretical model of flash-based SSDs that views each page as containing...
From Communications of the ACM
Offline and Online Algorithms for SSD Management
We explore the problem of reducing high internal overhead of flash media which is referred to as write amplification from an algorithmic perspective, considering...
From Communications of the ACM
Technical Perspective: Finding Connections between One-Way Functions and Kolmogorov Complexity
"Toward Basing Cryptography on the Hardness of EXP," by Yanyi Liu and Rafael Pass, establishes surprisingly tight bidirectional connections between one-way functions...
From Communications of the ACM
Toward Basing Cryptography on the Hardness of EXP
We show that the only "gap" toward getting (infinitely-often) OWFs from the assumption that EXP ≠ BPP is the seemingly "minor" technical gap between two-sided error...
From Communications of the ACM
Technical Perspective: Reconsidering the Design of User-Schedulable Languages
The breakthrough of "Achieving High Performance the Functional Way," by Bastian Hagedorn et al., is in fundamentally rethinking the design of user-schedulable languages...
From Communications of the ACM
Achieving High Performance the Functional Way: Expressing High-Performance Optimizations as Rewrite Strategies
We show how to employ functional programming techniques to solve with elegance the challenge of using a high-level language to describe functionality and a separate...
From Communications of the ACM
Technical Perspective: Beautiful Symbolic Abstractions for Safe and Secure Machine Learning
"Proving Data-Poisoning Robustness in Decision Trees," by Samuel Drews et al., addresses the challenge of processing an intractably large set of trained models...
From Communications of the ACM
Proving Data-Poisoning Robustness in Decision Trees
We present a sound verification technique based on abstract interpretation and implement it in a tool called Antidote, which abstractly trains decision trees for...
From Communications of the ACM
Technical Perspective: The Power of Low-Power GPS Receivers for Nanosats
The work explored in "Hummingbird," by Sujay Narayana et al., focuses on the energy consumption of a typical GPS receiver and its operational challenges in a nanosat...
From Communications of the ACM
Hummingbird: An Energy-Efficient GPS Receiver for Small Satellites
In this work, we elucidate the design of a low-cost, low-power GPS receiver for small satellites.
From Communications of the ACM
Sampling Near Neighbors in Search for Fairness
We propose several efficient data structures for the exact and approximate variants of the fair near neighbor problem.
From Communications of the ACM
Technical Perspective: Can Data Structures Treat Us Fairly?
In "Sampling Near Neighbors in Search for Fairness," Aumüller et al. investigate a basic problem in similarity search called near neighbor in the context of fair...
From Communications of the ACM
Technical Perspective: The Compression Power of the BWT
"Resolution of the Burrows-Wheeler Transform Conjecture," by Dominik Kempa and Tomasz Kociumaka, finally settles the question of how well r in the BWT captures...
From Communications of the ACM