"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
In "Isomorphism, Canonization, and Definability for Graphs of Bounded Rank Width," Grohe and Neuen show that the Weisfeiler-Leman algorithm in its plain form solves...Pascal Schweitzer From Communications of the ACM | May 2021
In this paper we study the graph isomorphism problem and the closely related graph canonization problem as well as logical definability and descriptive complexity...Martin Grohe, Daniel Neuen From Communications of the ACM | May 2021
The authors of "Succinct Range Filters" make a critical and insightful observation: For a given set of queries, the upper levels of the trie incur many more accesses...Stratos Idreos From Communications of the ACM | April 2021
We present the Succinct Range Filter (SuRF), a fast and compact data structure for approximate membership tests.
Huanchen Zhang, Hyeontaek Lim, Viktor Leis, David G. Andersen, Michael Kaminsky, Kimberly Keeton, Andrew Pavlo From Communications of the ACM | April 2021
"Understanding Deep Learning (Still) Requires Rethinking Generalization," Chiyuan Zhang, et al., brings a fundamental new theoretical challenge: Why don't today's...Sanjeev Arora From Communications of the ACM | March 2021
In this work, we presented a simple experimental framework for interrogating purported measures of generalization.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, Oriol Vinyals From Communications of the ACM | March 2021
"3D Localization for Subcentimeter-Sized Devices," by Iyer, et al., neatly separates and solves the problems of robotic locomotion, sensing, localization, and communications...Prabal Dutta From Communications of the ACM | March 2021
We present the first localization system that consumes microwatts of power at a mobile device and can be localized across multiple rooms in settings such as homes...Rajalakshmi Nandakumar, Vikram Iyer, Shyamnath Gollakota From Communications of the ACM | March 2021
"Scalable Signal Reconstruction for a Broad Range of Applications," by Abolfazl Asudeh, et al. shows that algorithmic insights about SRP, combined with database...Zachary G. Ives From Communications of the ACM | February 2021
Most of the common approaches for solving signal reconstruction problem do not scale to large problem sizes. We propose a novel and scalable algorithm for solving...Abolfazl Asudeh, Jees Augustine, Saravanan Thirumuruganathan, Azade Nazi, Nan Zhang, Gautam Das, Divesh Srivastava From Communications of the ACM | February 2021
The approach taken in "BioScript," by Jason Ott, et al., is an example of how programming languages can help develop executable protocols that are conforming, understandable...Nada Amin From Communications of the ACM | February 2021
This paper introduces BioScript, a domain-specific language for programmable biochemistry that executes on emerging microfluidic platforms.
Jason Ott, Tyson Loveless, Chris Curtis, Mohsen Lesani, Philip Brisk From Communications of the ACM | February 2021
"SkyCore," by Mehrdad Moradi, et al., addresses an exciting use case for Unmanned Aerial Vehicles in which UAVs can act as mobile base stations for the cellular...Richard Han From Communications of the ACM | January 2021
We argue for and propose an alternate, radical edge evolved packet core design, called SkyCore, that pushes the EPC functionality to the extreme edge of the core...Mehrdad Moradi, Karthikeyan Sundaresan, Eugene Chai, Sampath Rangarajan, Z. Morley Mao From Communications of the ACM | January 2021
In "Constant Overhead Quantum Fault Tolerance with Quantum Expander Codes," by Omar Fawzi, et al., the authors produce an algorithm that can rapidly deduce the...Daniel Gottesman From Communications of the ACM | January 2021
In this paper, we study the asymptotic scaling of the space overhead needed for fault-tolerant quantum computation.
Omar Fawzi, Antoine Grospellier, Anthony Leverrier From Communications of the ACM | January 2021
The system described in "SATURN: An Introduction to the Internet of Materials" works passively, energized essentially by static electricity generated as layers...Joseph A. Paradiso From Communications of the ACM | December 2020
We propose an Internet of Materials, where the very materials of objects and surfaces are augmented or manufactured to have computational capabilities.
Nivedita Arora, Thad Starner, Gregory D. Abowd From Communications of the ACM | December 2020