Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 64 Issue 6, October 2017

Section: Statistical Estimation

Estimating the Unseen: Improved Estimators for Entropy and Other Properties
Gregory Valiant, Paul Valiant
Article No.: 37
DOI: 10.1145/3125643

We show that a class of statistical properties of distributions, which includes such practically relevant properties as entropy, the number of distinct elements, and distance metrics between pairs of distributions, can be estimated given a...

Section: Analog Computation

Polynomial Time Corresponds to Solutions of Polynomial Ordinary Differential Equations of Polynomial Length
Olivier Bournez, Daniel S. Graça, Amaury Pouly
Article No.: 38
DOI: 10.1145/3127496

The outcomes of this article are twofold.

Implicit complexity. We provide an implicit characterization of polynomial time computation in terms of ordinary differential equations: we characterize the class P of languages computable in...

Section: Complexity

The Matching Polytope has Exponential Extension Complexity
Thomas Rothvoss
Article No.: 41
DOI: 10.1145/3127497

A popular method in combinatorial optimization is to express polytopes P, which may potentially have exponentially many facets, as solutions of linear programs that use few extra variables to reduce the number of constraints down to a...

Section: Database Systems and Theory

Communication Steps for Parallel Query Processing
Paul Beame, Paraschos Koutris, Dan Suciu
Article No.: 40
DOI: 10.1145/3125644

We study the problem of computing conjunctive queries over large databases on parallel architectures without shared storage. Using the structure of such a query q and the skew in the data, we study tradeoffs between the number of...