enter search term and/or author name
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
Ye  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...
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
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 −...
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,...
Steiner Tree Approximation via Iterative Randomized Rounding
Jarosław Byrka, Fabrizio Grandoni, Thomas Rothvoss, Laura Sanità
Article No.: 6
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...