acm-header
Sign In

Communications of the ACM

Latest Research



Technical Perspective: How Easy Is It to Describe Hard Polynomials?
From Communications of the ACM

Technical Perspective: How Easy Is It to Describe Hard Polynomials?

"Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits," by Nutan Limaye et al., achieves a landmark in the larger quest of understanding hardness,...

Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits
From Communications of the ACM

Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits

In this paper, we prove the first superpolynomial lower bounds against algebraic circuits of all constant depths over all fields of characteristic 0.

Technical Perspective: Bridging AI with Real-Time Systems
From Communications of the ACM

Technical Perspective: Bridging AI with Real-Time Systems

"Taming Algorithmic Priority Inversion in Mission-Critical Perception Pipelines," by Shengzhong Liu et al., proposes a new methodology for overcoming the limitations...

Taming Algorithmic Priority Inversion in Mission-Critical Perception Pipelines
From Communications of the ACM

Taming Algorithmic Priority Inversion in Mission-Critical Perception Pipelines

This paper discusses algorithmic priority inversion in mission-critical machine inference pipelines used in modern neural-network-based perception subsystems and...

Technical Perspective: Maximum Flow through a Network: A Storied Problem and a Groundbreaking Solution
From Communications of the ACM

Technical Perspective: Maximum Flow through a Network: A Storied Problem and a Groundbreaking Solution

"Almost-Linear-Time Algorithms for Maximum Flow and Minimum-Cost Flow," by Li Chen et al., comes within striking distance of answering the question: "Does maximum...

Almost-Linear-Time Algorithms for Maximum Flow and Minimum-Cost Flow
From Communications of the ACM

Almost-Linear-Time Algorithms for Maximum Flow and Minimum-Cost Flow

We present an algorithm that computes exact maximum flows and minimum-cost flows on directed graphs with m edges and polynomially bounded integral demands, costs...

Technical Perspective: What's All the Fuss about Fuzzing?
From Communications of the ACM

Technical Perspective: What's All the Fuss about Fuzzing?

"Boosting Fuzzer Efficiency: An Information Theoretic Perspective," by Marcel Böhme, Valentin J.M. Manès, and Sang Kil Cha, presents a novel twist to fuzzing that...

Boosting Fuzzer Efficiency: An Information Theoretic Perspective
From Communications of the ACM

Boosting Fuzzer Efficiency: An Information Theoretic Perspective

In this paper, we take the fundamental perspective of fuzzing as a learning process.

Technical Perspective: Tapping the Link between Algorithmic Model Counting and Streaming
From Communications of the ACM

Technical Perspective: Tapping the Link between Algorithmic Model Counting and Streaming

"Model Counting Meets Distinct Elements," by A. Pavan et al., gives a surprising connection between model counting and streaming, providing a generic transformation...

Model Counting Meets Distinct Elements
From Communications of the ACM

Model Counting Meets Distinct Elements

In this work, we seek to investigate whether bridging the seeming communication gap between two different domains of computer science may pave the way to richer...

Technical Perspective: Opening the Door to SSD Algorithmics
From Communications of the ACM

Technical Perspective: Opening the Door to SSD Algorithmics

The authors of "Offline and Online Algorithms for SSD Management" propose a more accurate theoretical model of flash-based SSDs that views each page as containing...

Offline and Online Algorithms for SSD Management
From Communications of the ACM

Offline and Online Algorithms for SSD Management

We explore the problem of reducing high internal overhead of flash media which is referred to as write amplification from an algorithmic perspective, considering...

Technical Perspective: Finding Connections between One-Way Functions and Kolmogorov Complexity
From Communications of the ACM

Technical Perspective: Finding Connections between One-Way Functions and Kolmogorov Complexity

"Toward Basing Cryptography on the Hardness of EXP," by Yanyi Liu and Rafael Pass, establishes surprisingly tight bidirectional connections between one-way functions...

Toward Basing Cryptography on the Hardness of EXP
From Communications of the ACM

Toward Basing Cryptography on the Hardness of EXP

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...

Technical Perspective: Reconsidering the Design of User-Schedulable Languages
From Communications of the ACM

Technical Perspective: Reconsidering the Design of User-Schedulable Languages

The breakthrough of "Achieving High Performance the Functional Way," by Bastian Hagedorn et al., is in fundamentally rethinking the design of user-schedulable languages...

Achieving High Performance the Functional Way
From Communications of the ACM

Achieving High Performance the Functional Way: Expressing High-Performance Optimizations as Rewrite Strategies

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...
Sign In for Full Access
» Forgot Password? » Create an ACM Web Account