"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
This paper presents a study on the practicality of operating system kernel debloating, that is, reducing kernel code that is not needed by the target applications...Hsuan-Chi Kuo, Jianyan Chen, Sibin Mohan, Tianyin Xu From Communications of the ACM | May 2022
In "FANG," the authors focus on a strategy of automatically detecting disinformation campaigns on online media with a new graph-based, contextual technique for...Philippe Cudré-Mauroux From Communications of the ACM | April 2022
We propose Factual News Graph (FANG), a novel graphical social context representation and learning framework for fake news detection.
Van-Hoang Nguyen, Kazunari Sugiyama, Preslav Nakov, Min-Yen Kan From Communications of the ACM | April 2022
"Here We Go Again: Why Is It Difficult for Developers to Learn Another Programming Language?" by Shrestha et al. provides insight into the difficulty of learning...Jonathan Aldrich From Communications of the ACM | March 2022
Our findings demonstrate that interference is a widespread phenomenon, forcing programmers to adopt suboptimal, opportunistic learning strategies.
Nischal Shrestha, Colton Botta, Titus Barik, Chris Parnin From Communications of the ACM | March 2022
"Toward Systematic Architectural Design of Near-Term Trapped Ion Quantum Computers" presents a study on scaling trapped-ion quantum architectures, and challenges...Frederic T. Chong From Communications of the ACM | March 2022
Toward realizing QCCD-based trapped ion systems with 50-100 qubits, we perform an extensive application-driven architectural study evaluating the key design choices...Prakash Murali, Dripto M. Debroy, Kenneth R. Brown, Margaret Martonosi From Communications of the ACM | March 2022