Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Coarse Reducibility and Algorithmic Randomness   A coarse description of a subset A of omega is a subset D of omega such that
the symmetric difference of A and D has asymptotic density 0. We study the
extent to which noncomputable information can be effectively recovered from all
coarse descriptions of a given set A, especially when A is effectively random
in some sense. We show that if A is 1-random and B is computable from every
coarse description D of A, then B is K-trivial, which implies that if A is in
fact weakly 2-random then B is computable. Our main tool is a kind of
compactness theorem for cone-avoiding descriptions, which also allows us to
prove the same result for 1-genericity in place of weak 2-randomness. In the
other direction, we show that if A is a 1-random set which Turing-reduces to
0', then there is a noncomputable c.e. set computable from every coarse
description of A, but that not all K-trivial sets are computable from every
coarse description of some 1-random set. We study both uniform and nonuniform
notions of coarse reducibility. A set Y is uniformly coarsely reducible to X if
there is a Turing functional Phi such that if D is a coarse description of X,
then Phi^D is a coarse description of Y. A set B is nonuniformly coarsely
reducible to A if every coarse description of A computes a coarse description
of B. We show that a certain natural embedding of the Turing degrees into the
coarse degrees (both uniform and nonuniform) is not surjective. We also show
that if two sets are mutually weakly 3-random, then their coarse degrees form a
minimal pair, in both the uniform and nonuniform cases, but that the same is
not true of every pair of relatively 2-random sets, at least in the nonuniform
coarse degrees.

1
The categories of this paper are: cs
32
The categories of this paper are: atom-ph
0
The categories of this paper are: hep-ph
22
The categories of this paper are: chao-dyn
8
The categories of this paper are: hep-ex
14
The categories of this paper are: math-ph
18
The categories of this paper are: econ
10
The categories of this paper are: q-bio
15
The categories of this paper are: nucl-ex
5
The categories of this paper are: gr-qc
33
The categories of this paper are: plasm-ph
26
The categories of this paper are: bayes-an
4
The categories of this paper are: cond-mat
28
The categories of this paper are: alg-geom
7
The categories of this paper are: hep-th
3
The categories of this paper are: physics