Sign In

Communications of the ACM

Research Archive


Archives

The Research archive provides access to all Research articles published in past issues of Communications of the ACM.

May 2021


From Communications of the ACM

Technical Perspective: Robust Statistics Tackle New Problems

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


From Communications of the ACM

Robustness Meets Algorithms

Robustness Meets Algorithms

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 is independent of the dimension.


From Communications of the ACM

Isomorphism, Canonization, and Definability for Graphs of Bounded Rank Width

Isomorphism, Canonization, and Definability for Graphs of Bounded Rank Width

In this paper we study the graph isomorphism problem and the closely related graph canonization problem as well as logical definability and descriptive complexity on graph classes of bounded rank width.


From Communications of the ACM

Technical Perspective: A Logical Step Toward the Graph Isomorphism Problem

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 the isomorphism problem for bounded-rank width graphs.