Fetching the paper…

Reading the bibliography…

2010

The Equivalence of Sampling and Searching

Aaronson, Scott

Original
PDF
Post on X

Understand

In a sampling problem, we are given an input x, and asked to sample approximately from a probability distribution D_x.

In a search problem, we are given an input x, and asked to find a member of a nonempty set A_x with high probability.
(An example is finding a Nash equilibrium.) In this paper, we use tools from Kolmogorov complexity and algorithmic information theory to show that sampling and search problems are essentially equivalent.
More precisely, for any sampling problem S, there exists a search problem R_S such that, if C is any "reasonable" complexity class, then R_S is in the search version of C if and only if S is in the sampling version.

The Equivalence of Sampling and Searching · Around

Built on

PP is as hard as the polynomial-time hierarchy
S. Toda · 1991
Earlier work this paper cites.
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
P. W. Shor · 1994
Earlier work this paper cites.
Non-Black-Box Techniques in Cryptography
B. Barak · 2003
Earlier work this paper cites.

Similar

The complexity of computing a Nash equilibrium
C. Daskalakis, P. W. Goldberg, and C. H. Papadimitriou · 2006
Cited alongside, same era.
On promise problems: a survey
O. Goldreich · 2006
Cited alongside, same era.
An Introduction to Kolmogorov Complexity and Its Applications (3rd ed.)
M. Li and P. M. B. Vitányi · 2008
Cited alongside, same era.

Then

Parallel repetition in projection games and a concentration bound
A. Rao · 2008
Later among the works it cites.
The computational complexity of linear optics
S. Aaronson and A. Arkhipov · 2010
Closest in time.
Lecture notes on descriptional complexity and randomness
P. Gács · 2010
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…