"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
In this work, we study a fourth modification to the notion of efficient verification that originates in the study of quantum entanglement.
Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen From Communications of the ACM | November 2021
"Multi-Itinerary Optimization as Cloud Service," by Alexandru Cristian et al., makes accessible an end-to-end cloud service that produces traffic-aware, real-time...Pascal Van Hentenryck From Communications of the ACM | November 2021
We describe multi-itinerary optimization, a novel Bing Maps service that automates the process of building itineraries for multiple agents while optimizing their...Alexandru Cristian, Luke Marshall, Mihai Negrea, Flavius Stoichescu, Peiwei Cao, Ishai Menache From Communications of the ACM | November 2021
We present the first approach for checking the internal validity of online experiments statically, that is, from code alone.
Emma Tosch, Eytan Bakshy, Emery D. Berger, David D. Jensen, J. Eliot B. Moss From Communications of the ACM | September 2021
"Optimal Auctions Through Deep Learning," by Paul Dütting et al., contributes a very interesting and forward-looking new take on the optimal multi-item mechanism...Constantinos Daskalakis From Communications of the ACM | August 2021
We overview recent research results that show how tools from deep learning are shaping up to become a powerful tool for the automated design of near-optimal auctions...Paul Dütting, Zhe Feng, Harikrishna Narasimhan, David C. Parkes, Sai S. Ravindranath From Communications of the ACM | August 2021
"Robustness Meets Algorithms," by Ilias Diakonikolas, et al., represents the beginning of a long and productive line of work on robust statistics in high dimensions...Jacob S. Steinhardt From Communications of the ACM | May 2021
We give the first efficient algorithm for estimating the parameters of a high-dimensional Gaussian that is able to tolerate a constant fraction of corruptions that...Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, Alistair Stewart From Communications of the ACM | May 2021