"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...Shang-Hua Teng From Communications of the ACM | December 2023
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...Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva From Communications of the ACM | December 2023
"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...Gordon Fraser From Communications of the ACM | November 2023
"Model Counting Meets Distinct Elements," by A. Pavan et al., gives a surprising connection between model counting and streaming, providing a generic transformation...David P. Woodruff From Communications of the ACM | September 2023
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...A. Pavan, N. V. Vinodchandran, Arnab Bhattacharyya, Kuldeep S. Meel From Communications of the ACM | September 2023
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...Ramesh K. Sitaraman From Communications of the ACM | July 2023
We explore the problem of reducing high internal overhead of flash media which is referred to as write amplification from an algorithmic perspective, considering...Tomer Lange, Joseph (Seffi) Naor, Gala Yadgar From Communications of the ACM | July 2023
"Toward Basing Cryptography on the Hardness of EXP," by Yanyi Liu and Rafael Pass, establishes surprisingly tight bidirectional connections between one-way functions...Gil Segev From Communications of the ACM | May 2023
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...Yanyi Liu, Rafael Pass From Communications of the ACM | May 2023
The breakthrough of "Achieving High Performance the Functional Way," by Bastian Hagedorn et al., is in fundamentally rethinking the design of user-schedulable languages...Jonathan Ragan-Kelley From Communications of the ACM | March 2023
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...Bastian Hagedorn, Johannes Lenfers, Thomas Kœhler, Xueying Qin, Sergei Gorlatch, Michel Steuwer From Communications of the ACM | March 2023
"Proving Data-Poisoning Robustness in Decision Trees," by Samuel Drews et al., addresses the challenge of processing an intractably large set of trained models...Martin Vechev From Communications of the ACM | February 2023
We present a sound verification technique based on abstract interpretation and implement it in a tool called Antidote, which abstractly trains decision trees for...Samuel Drews, Aws Albarghouthi, Loris D'Antoni From Communications of the ACM | February 2023
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...Karthik Dantu From Communications of the ACM | November 2022
In this work, we elucidate the design of a low-cost, low-power GPS receiver for small satellites.
Sujay Narayana, R. Venkatesha Prasad, Vijay S. Rao, Luca Mottola, T. V. Prabhakar From Communications of the ACM | November 2022
We propose several efficient data structures for the exact and approximate variants of the fair near neighbor problem.
Martin Aumüller, Sariel Har-Peled, Sepideh Mahabadi, Rasmus Pagh, Francesco Silvestri From Communications of the ACM | August 2022
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...Qin Zhang From Communications of the ACM | August 2022
"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...Gonzalo Navarro From Communications of the ACM | June 2022
In this paper, we show that r = (z log2 n) holds for every text. This result has numerous implications for text indexing and data compression.
Dominik Kempa, Tomasz Kociumaka From Communications of the ACM | June 2022