Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: The sparse parity matrix   Let $\mathbf{A}$ be an $n\times n$-matrix over $\mathbb{F}_2$ whose every
entry equals $1$ with probability $d/n$ independently for a fixed $d>0$. Draw a
vector $\mathbf{y}$ randomly from the column space of $\mathbf{A}$. It is a
simple observation that the entries of a random solution $\mathbf{x}$ to
$\mathbf{A} x=\mathbf{y}$ are asymptotically pairwise independent, i.e.,
$\sum_{i<j}\mathbb{E}|\mathbb{P}[\mathbf{x}_i=s,\,\mathbf{x}_j=t\mid\mathbf{A}]-\mathbb{P}[\mathbf{x}_i=s\mid\mathbf{A}]\mathbb{P}[\mathbf{x}_j=t\mid\mathbf{A}]|=o(n^2)$
for $s,t\in\mathbb{F}_2$. But what can we say about the {\em overlap} of two
random solutions $\mathbf{x},\mathbf{x}'$, defined as
$n^{-1}\sum_{i=1}^n\mathbf{1}\{\mathbf{x}_i=\mathbf{x}_i'\}$? We prove that for
$d<\mathrm{e}$ the overlap concentrates on a single deterministic value
$\alpha_*(d)$. By contrast, for $d>\mathrm{e}$ the overlap concentrates on a
single value once we condition on the matrix $\mathbf{A}$, while over the
probability space of $\mathbf{A}$ its conditional expectation vacillates
between two different values $\alpha_*(d)<\alpha^*(d)$, either of which occurs
with probability $1/2+o(1)$. This anti-concentration result provides an
instructive contribution to both the theory of random constraint satisfaction
problems and of inference problems on random structures.

33
The categories of this paper are: plasm-ph
3
The categories of this paper are: physics
11
The categories of this paper are: hep-lat
19
The categories of this paper are: eess
21
The categories of this paper are: adap-org
29
The categories of this paper are: funct-an
12
The categories of this paper are: nucl-th
24
The categories of this paper are: dg-ga
8
The categories of this paper are: hep-ex
20
The categories of this paper are: acc-phys
35
The categories of this paper are: mtrl-th
15
The categories of this paper are: nucl-ex
28
The categories of this paper are: alg-geom
18
The categories of this paper are: econ
26
The categories of this paper are: bayes-an
34
The categories of this paper are: chem-ph