Sign In

Communications of the ACM

Latest Research



From Communications of the ACM

Technical Perspective: The Equivalence Problem for Finite Automata

As the equivalence problem is essential in many applications, we need algorithms that avoid the worst-case complexity as often as possible. In "Hacking Nondeterminism...

Hacking Nondeterminism with Induction and Coinduction
From Communications of the ACM

Hacking Nondeterminism with Induction and Coinduction

We introduce bisimulation up to congruence as a technique for proving language equivalence of nondeterministic finite automata.

From Communications of the ACM

Technical Perspective: Rethinking Caches for Throughput Processors

As GPUs have become mainstream parallel processing engines, many applications targeting GPUs now have data locality more amenable to traditional caching. The...

Learning Your Limit
From Communications of the ACM

Learning Your Limit: Managing Massively Multithreaded Caches Through Scheduling

This paper studies the effect of accelerating highly parallel workloads with significant locality on a massively multithreaded GPU.

From Communications of the ACM

Technical Perspective: Attacking a Problem from the Middle

"Dissection: A New Paradigm for Solving Bicomposite Search Problems," by Itai Dinur, Orr Dunkelman, Nathan Keller, and Adi Shamir, presents an elegant new algorithm...

Dissection
From Communications of the ACM

Dissection: A New Paradigm for Solving Bicomposite Search Problems

In this paper, we introduce the new notion of bicomposite search problems, and show that they can be solved with improved combinations of time and space complexities...

From Communications of the ACM

Technical Perspective: A New Spin on an Old Algorithm

A paper by Ballard, Demmel, Holtz, and Schwartz considers a fundamental problem, adopting a new perspective on an old algorithm that has for years occupied a peculiar...

Communication Costs of Strassen's Matrix Multiplication
From Communications of the ACM

Communication Costs of Strassen's Matrix Multiplication

Proving lower bounds on the communication of algorithms and finding algorithms that attain these bounds are fundamental goals. 

From Communications of the ACM

Technical Perspective: Graph Embeddings and Linear Equations

Algorithmic advances can come from the most unexpected places. The following paper describes an emerging approach to solving linear systems of equations that...

A Fast Solver for a Class of Linear Systems
From Communications of the ACM

A Fast Solver for a Class of Linear Systems

The solution of linear systems is a problem of fundamental theoretical importance but also one with a myriad of applications in numerical mathematics, engineering...

From Communications of the ACM

Technical Perspective: A High-Dimensional Surprise

High-dimensional space is a counterintuitive place, where natural geometric intuitions from the familiar three-dimensional world may lead us badly astray.

Spherical Cubes
From Communications of the ACM

Spherical Cubes: Optimal Foams from Computational Hardness Amplification

Foam problems are about how to best partition space into bubbles of minimal surface area. We investigate the case where one unit-volume bubble is required to tile...

From Communications of the ACM

Technical Perspective: Proving Programs Continuous

Proving a program's correctness is usually an all-or-nothing game.

Continuity and Robustness of Programs
From Communications of the ACM

Continuity and Robustness of Programs

Computer scientists have long believed that software is different from physical systems in one fundamental way: while the latter have continuous dynamics, the former...

From Communications of the ACM

Technical Perspective: Why Study the Price of Anarchy?

In 1999, Elias Koutsoupias and Christos Papadimitriou initiated the study of "How much worse off are we due to selfishness?" They compared the worst case pure...

Intrinsic Robustness of the Price of Anarchy
From Communications of the ACM

Intrinsic Robustness of the Price of Anarchy

The price of anarchy, defined as the ratio of the worst-case objective function value of a Nash equilibrium of a game and that of an optimal outcome, quantifies...

Exact Matrix Completion via Convex Optimization
From Communications of the ACM

Exact Matrix Completion via Convex Optimization

Suppose that one observes an incomplete subset of entries selected from a low-rank matrix. When is it possible to complete the matrix and recover the entries that...

From Communications of the ACM

Technical Perspective: Reconstructing the Unknown, Balancing Structure and Uncertainty

The problem of estimating or reconstructing an unknown structured object from incomplete, partial, noisy measurements is a fundamental one in scientific and technological...

From Communications of the ACM

Technical Perspective: Compiling What to How

The following paper by Viktor Kuncak et al. integrates declarative programming into a general-purpose language, allowing one to escape the host language when...

Software Synthesis Procedures
From Communications of the ACM

Software Synthesis Procedures

Automated synthesis of program fragments from specifications can make programs easier to write and easier to reason about. To integrate synthesis into programming...
Sign In for Full Access
» Forgot Password? » Create an ACM Web Account
Read CACM in a free mobile app!
Access the latest issue, plus archived issues and more
ACM Logo
  • ACM CACM apps available for iPad, iPhone and iPod Touch, and Android platforms
  • ACM Digital Library apps available for iOS, Android, and Windows devices
  • Download an app and sign in to it with your ACM Web Account
Find the app for your mobile device
ACM DL Logo