This is the fifth in a series of articles devoted to showing that a typical
covering map of large degree to a fixed, regular graph has its new adjacency
eigenvalues within the bound conjectured by Alon for random regular graphs.
In this article we use the results of Articles~III and IV in this series to
prove that if the base graph is regular, then as the degree, $n$, of the
covering map tends to infinity, some new adjacency eigenvalue has absolute
value outside the Alon bound with probability bounded by $O(1/n)$. In addition,
we give upper and lower bounds on this probability that are tight to within a
multiplicative constant times the degree of the covering map. These bounds
depend on two positive integers, the \emph{algebraic power} (which can also be
$+\infty$) and the \emph{tangle power} of the model of random covering map.
We conjecture that the algebraic power of the models we study is always
$+\infty$, and in Article~VI we prove this when the base graph is regular and
\emph{Ramanujan}. When the algebraic power of the...

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 0

Unqiue Words: 0

The group testing problem is concerned with identifying a small number $k
\sim n^\theta$ for $\theta \in (0,1)$ of infected individuals in a large
population of size $n$. At our disposal is a testing procedure that allows us
to test groups of individuals. This paper considers two-stage designs where the
test results of the first stage can inform the design of the second stage. We
are interested in the minimum number of tests to recover the set of infected
individuals w.h.p. Equipped with a novel algorithm for one-stage group testing
from [Coja-Oghlan, Gebhard, Hahn-Klimroth \& Loick 2019], we propose a
polynomial-time two-stage algorithm that matches the universal
information-theoretic lower bound of group testing. This result improves on
results from [M\'ezard \& Toninelli 2011] and resolves open problems
prominently posed in [Aldridge, Johnson \& Scarlett 2019, Berger \& Levenshtein
2002, Damaschke \& Muhammad 2012].

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 0

Unqiue Words: 0

Assert is a website where the best academic papers on arXiv (computer science, math, physics), bioRxiv (biology), BITSS (reproducibility), EarthArXiv (earth science), engrXiv (engineering), LawArXiv (law), PsyArXiv (psychology), SocArXiv (social science), and SportRxiv (sport research) bubble to the top each day.

Papers are scored (in real-time) based on how verifiable they are (as determined by their Github repos) and how interesting they are (based on Twitter).

To see top papers, follow us on twitter @assertpub_ (arXiv), @assert_pub (bioRxiv), and @assertpub_dev (everything else).

To see beautiful figures extracted from papers, follow us on Instagram.

*Tracking 223,556 papers.*

Sort results based on if they are interesting or reproducible.

Interesting

Reproducible