Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Sharp threshold rates for random codes   Suppose that $\mathcal{P}$ is a property that may be satisfied by a random
code $C \subset \Sigma^n$. For example, for some $p \in (0,1)$, $\mathcal{P}$
might be the property that there exist three elements of $C$ that lie in some
Hamming ball of radius $pn$. We say that $R^*$ is the threshold rate for
$\mathcal{P}$ if a random code of rate $R^{*} + \varepsilon$ is very likely to
satisfy $\mathcal{P}$, while a random code of rate $R^{*} - \varepsilon$ is
very unlikely to satisfy $\mathcal{P}$. While random codes are well-studied in
coding theory, even the threshold rates for relatively simple properties like
the one above are not well understood.
  We characterize threshold rates for a rich class of properties. These
properties, like the example above, are defined by the inclusion of specific
sets of codewords which are also suitably "symmetric." For properties in this
class, we show that the threshold rate is in fact equal to the lower bound that
a simple first-moment calculation obtains. Our techniques not only pin down the
threshold rate for the property $\mathcal{P}$ above, they give sharp bounds on
the threshold rate for list-recovery in several parameter regimes, as well as
an efficient algorithm for estimating the threshold rates for list-recovery in
general.

6
The categories of this paper are: astro-ph
27
The categories of this paper are: comp-gas
5
The categories of this paper are: gr-qc
36
The categories of this paper are: cmp-lg
11
The categories of this paper are: hep-lat
8
The categories of this paper are: hep-ex
9
The categories of this paper are: nlin
13
The categories of this paper are: quant-ph
4
The categories of this paper are: cond-mat
3
The categories of this paper are: physics
15
The categories of this paper are: nucl-ex
22
The categories of this paper are: chao-dyn
19
The categories of this paper are: eess
14
The categories of this paper are: math-ph
23
The categories of this paper are: solv-int
25
The categories of this paper are: patt-sol