Alloy: A Language and Tool for Exploring Software Designs
Exploiting a simple, expressive logic based on relations to describe designs and automate their analysis.
Theory
Advertisement
Scaling Static Analyses at Facebook
Key lessons for designing static analysis tools deployed to find bugs in hundreds of millions of lines of code.
Heavy Hitters via Cluster-Preserving Clustering
We develop a new algorithm for the turnstile heavy hitters problem in general turnstile streams, the EXPANDERSKETCH, which finds the approximate top-k items in a universe of size n using the same asymptotic O(k log n) words of memory and O(log n) update time as the COUNTMIN and COUNTSKETCH, but requiring only O(k poly(log n)) time to answer queries instead of the O(n log n) time of the other two. The notion of "approximation" is the same l2 sense as the COUNTSKETCH, which given known lower bounds is the strongest guarantee one can achieve in sublinear memory. Our main innovation is an efficient reduction from the heavy hitters problem to a clustering problem in which each heavy hitter is encoded as some form of noisy spectral cluster in a graph, and the goal is to identify every cluster.
Technical Perspective: The True Cost of Popularity
The main focus of "Heavy Hitters via Cluster-Preserving Clustering" by Kasper Green Larsen et al. is on building up sufficient information to allow a more effective search process.
Good Algorithms Make Good Neighbors
Many computer scientists doubted ad hoc methods would ever give way to a more general approach to finding nearest neighbors. They were wrong.
A new framework is being used to secure the 2020 U.S. Census from database reconstruction attacks.
How long can the silicon foundry sector continue to adapt, as physical limits make further shrinkage virtually impossible?
Garbage Collection as a Joint Venture
A collaborative approach to reclaiming memory in heterogeneous software systems.
The Limit of Blockchains: Infeasibility of a Smart Obama-Trump Contract
Although smart contracts are Turing complete, it is a misconception that they can fulfill all routine contracts.
Tracing some of the latest advancements in algorithmic randomness.
Net Neutrality: Unexpected Solution to Blockchain Scaling
Cloud-delivery networks could dramatically improve blockchains' scalability, but clouds must be provably neutral first.
APIs, Standards, and Enabling Infrastructure
The widespread sharing of common or standardized APIs confers rich opportunities for choices of operating system or library implementations for the programming of applications.
Soundness and Completeness: Defined With Precision
The two key properties of program analysis are dual of each other.
Pondering Variables and Direct Instruction
Robin K. Hill considers the nature of variables, while Mark Guzdial reflects on renewed interest in the "direct instruction model."
Toward a European Exascale Ecosystem: The EuroHPC Joint Undertaking
European supercomputing infrastructures represent a strategic resource for understanding and responding to the increasing challenges European citizens will face in the years to come.
Connected Things Connecting Europe
Modern embedded system microcontroller and transceiver technology advancements have brought forth the kinds of systems we have defined for some time in Europe as "embedded intelligence."
Work in finance, marketing, human resources, and operations increasingly relies on analytics—with more to come.
Fully Device Independent Quantum Key Distribution
We rigorously provide the device-independent security of an entanglement-based protocol building on Ekert's original proposal for quantum key distribution.
Technical Perspective: Was Edgar Allan Poe Wrong After All?
Umesh Vazirani and Thomas Vidick's "Fully Device Independent Quantum Key Distribution" provides an unexpectedly simple and elegant secure protocol solution, indeed one that is almost within reach of current technology.
Shape the Future of Computing
ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.
Get InvolvedCommunications of the ACM (CACM) is now a fully Open Access publication.
By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer.
Learn More