Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 60 Issue 1, February 2013

Strategy Iteration Is Strongly Polynomial for 2-Player Turn-Based Stochastic Games with a Constant Discount Factor
Thomas Dueholm Hansen, Peter Bro Miltersen, Uri Zwick
Article No.: 1
DOI: 10.1145/2432622.2432623

Ye [2011] showed recently that the simplex method with Dantzig’s pivoting rule, as well as Howard’s policy iteration algorithm, solve discounted Markov decision processes (MDPs), with a constant discount factor, in strongly...

Distributed Random Walks
Atish Das Sarma, Danupon Nanongkai, Gopal Pandurangan, Prasad Tetali
Article No.: 2
DOI: 10.1145/2432622.2432624

Performing random walks in networks is a fundamental primitive that has found applications in many areas of computer science, including distributed computing. In this article, we focus on the problem of sampling random walks efficiently in a...

Testing Product States, Quantum Merlin-Arthur Games and Tensor Optimization
Aram W. Harrow, Ashley Montanaro
Article No.: 3
DOI: 10.1145/2432622.2432625

We give a test that can distinguish efficiently between product states of n quantum systems and states that are far from product. If applied to a state |ψ⟩ whose maximum overlap with a product state is 1 −...

Testing Closeness of Discrete Distributions
Tuğkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, Patrick White
Article No.: 4
DOI: 10.1145/2432622.2432626

Given samples from two distributions over an n-element set, we wish to test whether these distributions are statistically close. We present an algorithm which uses sublinear in n, specifically,...

Invited Article Foreword
Victor Vianu
Article No.: 5
DOI: 10.1145/2432622.2432627

Steiner Tree Approximation via Iterative Randomized Rounding
Jarosław Byrka, Fabrizio Grandoni, Thomas Rothvoss, Laura Sanità
Article No.: 6
DOI: 10.1145/2432622.2432628

The Steiner tree problem is one of the most fundamental NP-hard problems: given a weighted undirected graph and a subset of terminal nodes, find a minimum-cost tree spanning the terminals. In a sequence of papers, the approximation ratio...