Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 58 Issue 2, April 2011

On P vs. NP and geometric complexity theory: Dedicated to Sri Ramakrishna
Ketan D. Mulmuley
Article No.: 5
DOI: 10.1145/1944345.1944346

This article gives an overview of the geometric complexity theory (GCT) approach towards the P vs. NP and related problems focusing on its main complexity theoretic results. These are: (1) two concrete lower bounds, which are currently the best...

Delaunay triangulations in O(sort(n)) time and more
Kevin Buchin, Wolfgang Mulzer
Article No.: 6
DOI: 10.1145/1944345.1944347

We present several results about Delaunay triangulations (DTs) and convex hulls in transdichotomous and hereditary settings: (i) the DT of a planar point set can be computed in expected time O(sort(n)) on a word RAM, where...

Dynamic atomic storage without consensus
Marcos K. Aguilera, Idit Keidar, Dahlia Malkhi, Alexander Shraer
Article No.: 7
DOI: 10.1145/1944345.1944348

This article deals with the emulation of atomic read/write (R/W) storage in dynamic asynchronous message passing systems. In static settings, it is well known that atomic R/W storage can be implemented in a fault-tolerant manner even if the...

Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix
Haim Avron, Sivan Toledo
Article No.: 8
DOI: 10.1145/1944345.1944349

We analyze the convergence of randomized trace estimators. Starting at 1989, several algorithms have been proposed for estimating the trace of a matrix by 1/M∑i=1M ziT...