11institutetext: Brunel University London, UK 22institutetext: Xi’an Jiaotong
University, China 33institutetext: Northwestern Polytechnical University,
China

# The Prevalence of Errors in Machine Learning Experiments

Martin Shepperd 11 Yuchen Guo 22 Ning Li 33 Mahir Arzoky 11 Andrea Capiluppi
11 Steve Counsell 11 Giuseppe Destefanis 11 Stephen Swift 11 Allan Tucker 11
Leila Yousefi 11

###### Abstract

_Context_ : Conducting experiments is central to research machine learning
research to benchmark, evaluate and compare learning algorithms. Consequently
it is important we conduct reliable, trustworthy experiments.
_Objective_ : We investigate the incidence of errors in a sample of machine
learning experiments in the domain of software defect prediction. Our focus is
simple arithmetical and statistical errors.
_Method_ : We analyse 49 papers describing 2456 individual experimental
results from a previously undertaken systematic review comparing supervised
and unsupervised defect prediction classifiers. We extract the confusion
matrices and test for relevant constraints, e.g., the marginal probabilities
must sum to one. We also check for multiple statistical significance testing
errors.
_Results_ : We find that a total of 22 out of 49 papers contain demonstrable
errors. Of these 7 were statistical and 16 related to confusion matrix
inconsistency (one paper contained both classes of error).
_Conclusions_ : Whilst some errors may be of a relatively trivial nature,
e.g., transcription errors their presence does not engender confidence. We
strongly urge researchers to follow open science principles so errors can be
more easily be detected and corrected, thus as a community reduce this
worryingly high error rate with our computational experiments.

###### Keywords:

Classifier Computational experiment Reliability Error.

##  1 Introduction

In recent years there has been a proliferation in machine learning research
and its deployment in a wide range of application domains. The primary vehicle
for evaluation has been empirical via experiments. Typically an experiment
seeks to assess the behaviour of learning algorithms over one or more data
sets by varying the treatment and examining the response variables, e.g.,
predictive performance and execution time. Unfortunately, a challenge has been
to construct a consistent or even coherent picture from the many experimental
results. For instance, in software defect prediction, a major meta-analysis of
results found that the single largest determinant of predictive performance
was not the choice of algorithm but which research group undertook the work
[17].

As a side effect of a recent systematic review of supervised and unsupervised
classifiers [13] conducted by three of the authors (NL, MS and YG), we
observed quality problems with a surprising proportion of studies when trying
to reconstruct confusion matrices in order to obtain comparable classification
performance statistics. These involved violations of simple integrity
constraints regarding the confusion matrix such as marginal probabilities not
summing to one [4]. One likely driver for these kinds of errors is that
computational experiments can be extremely complex, involving data pre-
processing, feature subset selection, imbalanced learning, complex cross-
validation design and tuning of hyper-parameters over many, often large, data
sets.

In this study we explore the phenomenon of simple arithmetical and statistical
errors in machine learning experiments and investigate one particular domain
of classifying software components as defect or not defect-prone. This is an
active and economically important area. For overviews see [6, 10]. Note we do
not consider the more complex challenges of appropriate experimental design
and analysis [11] nor the ongoing debate concerning the validity of null
hypothesis significance testing (NHST) [7].

The remainder of this paper is organised as follows. The next section provides
some background on error checking in experiments. We then summarise how our
data were extracted from a systematic review comparing unsupervised and
supervised learners in Section 3. Next, in Section 4 we explain how we checked
for errors and the outcome of this analysis. We conclude with a discussion of
the significance of our findings, possible steps the research community might
adopt and suggestions for further work.

##  2 Background

For some time, researchers have expressed concerns about the reliability of
individual experiments [9] from a range of causes including simple errors.
Brown and Heathers [5] analysed a series of empirical psychology studies for
simple arithmetic errors e.g., if there are 10 participants, a proportion
could not take on the value of 17%. They entitle their method granularity-
related inconsistency of means (GRIM) and found that of 71 testable articles
around half (36/71) appeared to contain at least one inconsistent mean.

An alternative approach is presented by Nuijten et al. [15] who provide an R
package to assist in the checking of inferential statistics such as
$\chi^{2}$, ANOVA and t-tests. However, their automated procedure requires the
reporting of inferential statistics using the APA format which is not
commonplace in computer science. Nevertheless it is sobering to note that in
their analysis of 250,000 p-values from psychology experiments, half of all
published papers contained at least one p-value that was inconsistent with its
test statistic and degrees of freedom. In 12% of papers the error was
sufficient to potentially impact the statistical conclusion.

More specific to experiments based on learning classifiers is the work by
Bowes et al. [4] to reverse engineer the confusion matrix111A confusion matrix
is a $2\times 2$ contingency table where the cells represent true positives
(TP), false negatives (FN), false positives (FP) and true negatives (TN)
respectively. Most classification performance statistics, e.g. precision,
recall and the Matthews correlation coefficient (MCC), can be defined from
this matrix. from partial information, and check the satisfaction of various
integrity constraints. This has been extended and applied by Li et al. [13].

This paper integrates the Li et al. [13] analysis with an additional category
of error relating to performing multiple NHSTs without correction of the
acceptance threshold, usually denoted $\alpha$ and conventionally set to 0.05.
However, NHST with multiple tests becomes problematic [1]. When many tests are
made, the probability of making at least one Type I error amongst the
comparisons grows linearly with the number of tests. Since some experiments
make many tens or even hundreds of comparisons and rely on NHST as a means of
inferencing this is a very real threat to experimental validity. Therefore a
correction should be made to the $\alpha$ acceptance threshold. The best
known, though conservative, method is the Bonferroni correction which is
$\alpha^{\prime}=\alpha/n$ where $n$ is the number of tests or comparisons.
More modern approaches include Benjamini-Hochberg which controls for the false
discovery rate [3] and the Nemenyi post hoc procedure [8].

##  3 Systematic Review

In a systematic review of studies comparing the performance of unsupervised
and supervised learners, we (LN, MS and YC) identified 49 relevant studies
that satisfy the inclusion criteria given in Table 1. An extended description
can be found in [13]. The conduct of the review was guided by the method and
principles set out by Kitchenham et al. [12]. We were then able to use these
49 primary studies as a convenience sample to assess the error-proneness of
computational experiments in machine learning.

Table 1: Systematic Review Inclusion Criteria Criterion |  Description
---|---
Language |  Written in English.
Topic |  Applies at least one unsupervised learning method for predicting defect-prone software modules.
Availability |  Full content must be available.
Date |  January 2000 – March 2018.
Reviewed |  All papers that indicated some minimal peer review process, however, we observed some outlets appear on Geoff Beall’s controversial ‘predatory’ publisher list [16].
Duplicates |  Includes new (only the most recent version used when multiple reports of a single experiment) software defect prediction experiments. We do not count re-analysis of previously published experiments.
Software system |  Uses real data (not simulations).
Reporting |  Sufficient detail to enable meta-analysis.

There is a one-to-many mapping from paper to result with the papers containing
between 1 and 751 (median = 12) results apiece. The papers cover 14 different
unsupervised prediction techniques (e.g., Fuzzy CMeans and Fuzzy Self
Organising Maps) coupled with 7 different cluster labelling techniques (e.g.,
distribution-based and majority voting). The full list of papers and raw data
may be found online222Our data may be retrieved from Figshare
http://tiny.cc/vvvqbz.

##  4 Analysis

We examine three questions. First the prevalence of inconsistency errors
relating to the confusion matrix. Here we investigate result by result.
Second, we look at the occurrence of a particular statistical error relating
to a failure to adjust the $\alpha$ threshold when using NHST form of
statistical inference. Here the unit is paper since the error relates to
making _multiple_ tests. Third, we examine the extent to which these problems
co-occur and therefore the proportion of papers implicated.

###  4.1 Inconsistency errors in the confusion matrix

Our approach was to use the DConfusion tool [4] to reconstruct the confusion
matrix of classification performance for each result. This can often, but not
always, be accomplished from a partial set of reported results. For instance,
if precision, recall and false positive rate are reported one can reconstruct
the complete confusion matrix. Of course, some cases (for us $\sim 33\%$ or
$823/2456$) failed to report sufficient information so we cannot undertake
consistency checking. Incomplete reporting also hinders meta-analysis.

The next step is to test for six integrity constraints (expressed as rules
that should be false). If one or more rules are true then we know that there
is some issue with the results as reported. The cause could be as simple as a
wrongly transcribed value to some deeper error. However, from the perspective
of our analysis all we can say is there is a problem. Note that the DConfusion
tool also handles rounding errors which could lead to small differences in
results and consequently the appearance of an inconsistency problem. In total,
262 out of 2456 experimental results were inconsistent (see Tables 2 and 3).

Table 2: Distribution of confusion matrix errors

Rule | Count
---|---
1: Performance metric out of range e.g., FMeasure $\notin[0,1]$ or MCC $\notin[-1,1].$ | 171
2: Recomputed defect density $d$ is zero. | 7
3: Recomputed $d$ differs from original reported defect percentage by more than 0.1 (i.e., we allow for small rounding errors). | 60
4: Recomputed performance metrics differ from known original ones by more than 0.05 (i.e., we allow for small rounding errors). NB, the rounding error ranges are computed by adding $\pm 0.05$ to the original data unlike the more conservative range 0.01 used in [4]. | 3
5: Internal consistency of the re-computed confusion matrix. | 19
6: Other obvious reporting errors within paper e.g., the confusion matrix is inconsistent with their dataset or dataset summary statistics. | 2
Total errors | 262
Checkable and consistent | 1479

For a full explanation for all consistency rules refer to the figshare project
http://tiny.cc/vvvqbz.

Table 3: Proportions (with rounding) of inconsistently reported experimental results Result | Count | % of total
---|---|---
Inconsistent results | 262 |  10.7%
Other results | 2194 | 89.3%
(Other) Cannot check | 715 | 29.1%
(Other) Can check - ok | 1479 | 60.2%
Total | 2456 | 100%

###  4.2 Failure to adjust acceptance threshold for NHST errors

Irrespective of one’s views regarding the validity of null hypothesis
significance testing (NHST) [7] it is demonstrably an error to set $\alpha$ at
a particular level333Of 13 papers using NHST, 12 have $\alpha=0.05$ and,
unusually, one study interprets $0.05<p<0.1$ with $p=0.077$ as being
‘significant’. and then undertake multiple tests without making some
adjustment to this threshold [2]. A range of adjustment methods have been
proposed subsequent to the classic Bonferroni method. In our sample, we noted
researchers used either Benjamini-Hochberg [3] or the Nemenyi procedure [8]
procedure. In terms of assessing the experiment we are agnostic as to which is
the ‘correct’ adjustment.

The number of significance tests ranges from 1 to 2000 with the median=100.
Naturally the experiment that only undertakes a single NHST does not require
to correct $\alpha$, however the remaining 12 experiments do. Table 4
summarises the results. Note the experiment that makes partial corrections
uses the Nemenyi post hoc test procedure for some analyses but not for the
remaining 84 tests. We thus still consider this as an error. So more than half
($(6+1)/13$) of the experiments that make use of NHST-based analysis are in
error. Since this is part of researchers’ inferencing procedures e.g., to
determine if classifier X is to be preferred to classifier Y, this is
worrisome.

Table 4: Failure to adjust the acceptance threshold when performing _multiple_ NHSTs  Adjust? | Count
---|---
No | 6
Partial | 1
Yes | 5
Total | 12

###  4.3 Do different types of error co-occur?

Finally, we ask the question: is a paper that commits one class of error more
likely to commit other types of error? Table 5 gives the contingency table of
the two types of error. There does not seem to be much evidence that
experimenters who make errors with confusion matrices are more likely to
incorrectly deploy NHST. Consequently a highly disturbing 22 out of 35 papers
contain demonstrable errors. We cannot easily comment on the remaining 14
papers since they provide insufficient information for us to check the
consistency confusion matrices (although one also contains NHST errors).

Table 5: Co-occurrence of different classes of error by paper | NHST Error | No NHST Error
---|---|---
Inconsistent confusion matrix | 1 | 15
Consistent confusion matrix | 3 | 16
Incomplete reporting | 3 | 11

##  5 Discussion and Conclusions

In this study we have audited 49 papers describing experiments based on
supervised learners for software defect prediction. They were identified by a
systematic review of research in this area. We then checked for arithmetic
errors and inconsistencies related to confusion matrices. These are important
since they form the basis for calculating most classification performance
statistics; errors could therefore lead to wrong conclusions. In contrast, we
also checked that experiments that made use of NHST type inferencing adjusted
the significance threshold $\alpha$ when undertaking multiple tests to prevent
inflation of the false discovery rate. This type of statistical error can also
lead to wrong conclusions for researchers who wish to use p-values as a means
of determining whether a result is significant or not.

Obviously there are other classes of error one could check for in experiments.
We chose confusion matrix errors and failure to adjust significance testing
for pragmatic reasons: they are objective and can be undertaken without access
to the original data. Nevertheless one must have concern that the true picture
is likely to be worse than we have uncovered. Moreover, 29% of experimental
studies fail to report sufficient information for us to be able to check for
consistency. Thus an overall (knowable) error rate of $\sim 45\%$ (22/49) of
papers across all publication venues (which is likely to be an underestimate)
does not inspire confidence in the quality of our machine learning experiments
or at least our attention to detail.

In summary:

  1. 1.

We have identified a number of inconsistencies or errors in a surprisingly
high proportion of published machine learning experiments. These may or may
not be consequential but do raise some concerns about the reliability of
analyses.

  2. 2.

There are also a proportion of studies that have not published sufficient
information for checking and there are of course other errors that are
difficult to detect using the procedures at our disposal.

  3. 3.

Our sample of experiments is a convenience sample and so is not necessarily
representative of other areas of machine learning.

  4. 4.

We strongly recommend that researchers adopt the principles of Open Science
[14] so that data, experimental results and code are available for scrutiny.

  5. 5.

It is our intention to communicate with the affected authors to highlight data
analysis issues that _seem_ to require correction. However, we recognise that
mistakes can be made by all of us, so error checking is a process that needs
to be undertaken with civility and professionalism.

Our analysis of errors in a sample of 49 machine learning experiments has
uncovered some worrying findings. Errors, both arithmetic and statistical are
surprisingly commonplace with discoverable problems in almost 45% of papers.
This appears broadly in line with similar analyses in experimental psychology
[5, 15]. Nor do error rates appear to be much improved in the more obviously
peer-reviewed literature. We suggest three future lines of enquiry. First, our
sample is relatively small and non-random. It would be interesting to see how
other areas of machine learning research compare. Second, the range of errors
— particularly statistical ones — might usefully be explored. Third, dialogue
with authors might help us better understand the nature of errors and their
significance. As we have stated our analysis of confusion matrices identifies
inconsistencies but not the underlying causes. Then we will be in a better
position to answer the question: do the errors have material impact upon
experimental conclusions?

Finally, we strongly believe these findings should give additional impetus to
the move to open science and publication of all research data, code and
results. When conducting complex computational experiments, errors may be hard
to completely avoid; openness better helps us to detect and fix them.

## References

  * [1] Benavoli, A., Corani, G., Demšar, J., Zaffalon, M.: Time for a change: a tutorial for comparing multiple classifiers through Bayesian analysis. The Journal of Machine Learning Research 18(1), 2653–2688 (2017)
  * [2] Bender, R., Lange, S.: Adjusting for multiple testing – when and how? Journal of Clinical Epidemiology 54(4), 343–349 (2001)
  * [3] Benjamini, Y., Hochberg, Y.: Controlling the false discovery rate: a practical and powerful approach to multiple testing. Journal of the Royal Statistical Society: Series B (Methodological) 57(1), 289–300 (1995)
  * [4] Bowes, D., Hall, T., Gray, D.: DConfusion: a technique to allow cross study performance evaluation of fault prediction studies. Automated Software Engineering 21(2), 287–313 (2014)
  * [5] Brown, N., Heathers, J.: The GRIM test: A simple technique detects numerous anomalies in the reporting of results in psychology. Social Psychological and Personality Science 8(4), 363–369 (2017)
  * [6] Catal, C., Diri, B.: A systematic review of software fault prediction studies. Expert Systems with Applications 36(4), 7346–7354 (2009)
  * [7] Colquhoun, D.: An investigation of the false discovery rate and the misinterpretation of p-values. Royal Society Open Science 1(140216) (2014)
  * [8] Demšar, J.: Statistical comparisons of classifiers over multiple data sets. Journal of Machine Learning Research 7, 1–30 (2006)
  * [9] Earp, B., Trafimow, D.: Replication, falsification, and the crisis of confidence in social psychology. Frontiers in Psychology 6, 621 (2015)
  * [10] Hall, T., Beecham, S., Bowes, D., Gray, D., Counsell, S.: A systematic literature review on fault prediction performance in software engineering. IEEE Transactions on Software Engineering 38(6), 1276–1304 (2012)
  * [11] Ioannidis, J.: Why most published research findings are false. PLoS Medicine 2(8), e124 (2005)
  * [12] Kitchenham, B., Budgen, D., Brereton, P.: Evidence-based software engineering and systematic reviews. CRC Press, Boca Raton, Fl, US (2015)
  * [13] Li, N., Shepperd, M., Guo, Y.: A systematic review of unsupervised learning techniques for software defect prediction. Information and Software Technology Under review (2019)
  * [14] Munafò, M., Nosek, B., Bishop, D., Button, K., Chambers, C., du Sert, N., Simonsohn, U., Wagenmakers, E., Ware, J., Ioannidis, J.: A manifesto for reproducible science. Nature Human Behaviour 1(1), 0021 (2017)
  * [15] Nuijten, M., Hartgerink, C., van Assen, M., Epskamp, S., Wicherts, J.: The prevalence of statistical reporting errors in psychology (1985–2013). Behavior Research Methods 48(4), 1205–1226 (2016)
  * [16] Perlin, M., Imasato, T., Borenstein, D.: Is predatory publishing a real threat? Evidence from a large database study. Scientometrics online (2018). https://doi.org/https://doi.org/10.1007/s11192-018-2750-6
  * [17] Shepperd, M., Bowes, D., Hall, T.: Researcher bias: The use of machine learning in software defect prediction. IEEE Transactions on Software Engineering 40(6), 603–616 (2014)


\Pr[A_S\in \mathcal{S}_{2k,k}\setminus \mathcal{S}_{2k,k}']&\leq \Pr\left[\Bin\left(2k, \frac{4k}{n}\right) \geq k+1\right]\cdot\Pr[L_S=2k].
\end{align*}

Another application of the Claim <ref> gives us:

\begin{align*}
\Pr[A_S\in \mathcal{S}_{2k,k}\setminus \mathcal{S}_{2k, k}']&\leq \left(p^{\gamma d+c_{\ref{claim:abc1}}\log_p(\gamma d)}\right)^k \left(\frac{k}{n}\right)^{k+1}.
\end{align*}

It follows that

\begin{align*}
\Pr[A_S\in \mathcal{M}_k\backslash (\mathcal{T}_{k}\cup \mathcal{T}_{k}^+\cup \mathcal{T}_{k}^C)]&\leq \left(p^{\gamma d+c_{\ref{claim:abc1}}\log_p(\gamma d)}\right) \left(\frac{k}{n}\right)^{k+1}+\sum_{\ell=2k+1}^{\gamma d k}\Pr[A_S\in \mathcal{S}_{\ell, k}]\\
&\leq \left(p^{\gamma d+c_{\ref{claim:abc1}}\log_p(\gamma d)}\right) \left(\frac{k}{n}\right)^{k+1} +\sum_{\ell=2k+1}^{\gamma d k}\Pr\left[\Bin\left(\ell, \frac{2\ell}{n}\right) \geq \frac{\ell}{2}\right]\cdot\Pr[L_S = \ell].
\end{align*}

To bound the final term, we use the second bound in Lemma <ref>.

This gives us the desired result for sufficiently large $\gamma$ and $d$:

\begin{align*}
\Pr[A_S\in \mathcal{M}_k\backslash (\mathcal{T}_{k}\cup \mathcal{T}_{k}^+\cup \mathcal{T}_{k}^C)]&\leq \left(p^{\gamma d+c_{\ref{claim:abc1}}\log_p(\gamma d)}\right)^k \left(\frac{k}{n}\right)^{k+1}+ e^{-k}\left(\frac{k}{n}\right)^{k+1/2} = O\left(e^{-k}\left(\frac{k}{n}\right)^{k+1/2}\right).
\end{align*}

This yields the first statement in the lemma.

§.§ Large Case

The main goal of the large case is to prove the following lemma.

We begin by proving the following anti-concentration Lemma.

For $i \in \{1,...,d\}$, let $j_i \sim \text{Uniform}([N])$, and let $X_i := v_{j_i}$.

\begin{equation}\label{eq:anti}
\Pr[x\cdot v=w] = \Pr\left[\sum_{i=1}^d X_i =w\ | \text{All $j_i$ are unique}\right] \leq \frac{\Pr\left[\sum_{i=1}^d X_i =w\right]}{\Pr\left[\text{All $j_i$ are unique}\right]}.
\end{equation}

\begin{equation*}
\Pr\left[\text{All $j_i$ are unique}\right] \geq 1 - \frac{d^2}{N}.
\end{equation*}

By a union bound,

\begin{align*}
\Pr\left[\exists i \neq \ell: j_i = j_{\ell} \right] &\leq \binom{d}{2}\cdot \Pr\left[j_1 = j_2\right]=\binom{d}{2}\left(\frac{1}{N}\right) \leq \frac{d^2}{N}.
\end{align*}

Next we show by induction on $d$ that $\Pr\left[\sum_{i=1}^d X_i = w\right] \leq 1/2$ for all $w\in \mathbb{R}\backslash\{da\}$. For $d=1$, we note that the chosen element $w$ cannot be the most common element $a$. Thus, $w$ is at worst equally as common as the most common element $a$. This implies that the number of times $w$ appears in $v$ is at most $\frac{N}{2}$, hence $\Pr[X_1 = w]\leq \frac{1}{2}$.

Now assume that $\Pr\left[\sum_{i=1}^{d-1} X_i = u\right]\leq 1/2$ holds for all $u\not=(d-1)a$. For $w\not=da$, we write:

\begin{align*}
\Pr\left[\sum_{i=1}^{d} X_i = w\right] &=\sum_{x\in \text{Supp($X_d$)}} \Pr\left[X_d = x\right]\cdot \Pr\left[\sum_{i=1}^{d-1} X_i = w-x\right]\\
&=\Pr\left[X_d=a\right]\cdot \Pr\left[\sum_{i=1}^{d-1}X_i=w-a\right] +\sum_{x\in \text{Supp($X_d$)$\backslash\{a\}$}} \Pr\left[X_d = x\right]\cdot \Pr\left[\sum_{i=1}^{d-1} X_i = w-x\right]
\end{align*}

Let $p_x := \Pr\left[\sum_{i=1}^{d-1}X_i=w-x\right]$ such that by the induction hypothesis $p_a \leq 1/2$ as $w-a=(d-1)a$ if and only if $w=da$. Thus, we conclude:

\begin{align*}
\Pr\left[\sum_{i=1}^{d} X_i = w\right] &\leq \max_{p_a \leq 1/2, \sum_{x}p_x \leq 1}\left(\Pr\left[X_d=a\right]\cdot p_a + \sum_{x\in \text{Supp($X_d$)$\backslash\{a\}$}} \Pr\left[X_d = x\right]\cdot p_x\right) \\
&\leq \max_{\sum_{x \neq a}p_x \leq 1/2}\left(\Pr\left[X_d=a\right]\cdot \left(1/2\right) + \sum_{x\in \text{Supp($X_d$)$\backslash\{a\}$}} \Pr\left[X_d = x\right]\cdot p_x\right) \\
&\leq \max_{\sum_{x \neq a}p_x \leq 1/2}\left(\Pr\left[X_d=a\right]\cdot (1/2) + \left(\sum_{x\in \text{Supp($X_d$)$\backslash\{a\}$}} P(X_d = x)\right)\cdot \left(\sum_{x\in \text{Supp($X_d$)$\backslash\{a\}$}}p_x\right)\right)\\
&= \Pr\left[X_d=a\right]\cdot (1/2)+(1-\Pr[X_d=a])\cdot(1/2) = 1/2.
\end{align*}

Here the second inequality follows from the fact that the optimum over the $p_x$ is achieved by putting the maximum possible mass on $p_a$, that is, $p_a = 1/2$.

Returning to eq. <ref>, we have for all $w \neq ad$ and $d \leq \sqrt{\frac{N}{2}}$,

\begin{align*}
\Pr[x\cdot v=w] &\leq \frac{\Pr\left[\sum_{i=1}^d X_i =w\right]}{\Pr\left[\text{All $j_i$ are unique}\right]} \leq \frac{1/2}{1 - \frac{d^2}{N}} \leq 1/2 + \frac{d^2}{N},
\end{align*}

where the final inequality follows from the fact that $\frac{1}{1 - x} \leq 1 + 2x$ for $0 \leq x \leq 1/2$.

To prove Lemma <ref>, we take a similar approach to the large case for the BGC. For a fixed set $S$ of size $k$, we consider the stochastic process $A_S^{[1]}, A_S^{[2]}, \ldots$ in which we add the rows of $A_S$ one by one. We define the space:
$$D(A_S^{[j]})=\Span\left(\{v\in (\mathbb{R}\backslash\{0\})^k: A_S^{[j]}v =0 \}\right),$$

and let $R_j := \text{Rank}(D(A_S^{[j]})).$ If $R_{\gamma n(1-p)} =0$, then $A_S$ is not a minimal dependency.

Each time we add a new column, $R_j$ either stays constant or decreases by at least $1$ (note that $R_j$ can decrease by more than $1$: if a new row $j$ has exactly one $1$, then $R_j = R_{j+1} = \ldots = 0$ no matter what $R_{j-1}$ was). We will use the following lemma to show for $j \leq \gamma n/2$, each column we add is close to random. Then, using Lemma <ref>, we show that with decent probability, $R_j$ decreases. We can then apply a Chernoff Bound to show that $R_{\gamma n/2} = 0$ with high probability.

More formally, we consider the process of constructing $H \in \{0,1\}^{\gamma n(1-p) \times \gamma d n}$ (the column half-edge occupancy matrix) one row at a time by pairing the $d$ half-edges from each row-node at each step to a random set of $d$ unpaired column-half-edges.

Define $e(S, j) := \gamma d k - |\supp(H^{[j]}(S))|$, that is the number of unpaired half-edges among the $k$ column-nodes in $S$ after the first $j$ row-nodes have randomly paired their half-edges. Observe that $e(S, j) \sim \textnormal{HypGeo}(\gamma d n, \gamma d k, \gamma d n - dj)$. The following lemma uses standard concentration bounds to show that for the first $\gamma n/2$ columns, there are many unpaired half-edges out of row-nodes in $S$.

Let $A \sim \textnormal{ABC}_p(n, \gamma, d)$. Let $\Omega$ be the event in which for any set $S$ with $|S| \geq \frac{n}{18e\gamma^2 d^2}$ and for any $j\in[1,\frac{\gamma}{2}n]$, we have
$\frac{e(S,j)}{\gamma dn-dj}\geq \frac{k}{2n}$.
For $\gamma \geq 2$, there exists a constant $d_0(\gamma)$ such that for $d \geq d_0$, we have $\Pr[\Omega] \geq 1 - \gamma ne^{-n/d^3}$.

For $d$ larger than some constant $d_0(\gamma)$, we have $\frac{n}{d^3} \leq \frac{n}{18e\gamma^2 d^2}$, hence it suffices to prove the result for all $k\in[n/d^3,n)$. Fix $k$ and let us define $\eta_k$ to be the ratio $k/n$. Choose a subset $S$ of size $k$. Furthermore, fix $j\leq \frac{\gamma}{2}n$. We proceed by applying the following tail bound on Hypergeometric distributions to $e(S,j)$ which is clear from [10].

Let $X \sim \textnormal{HypGeo}(A, B, c)$. Then for all $t < \frac{B}{A}$,

\begin{equation*}
\Pr\left[X \leq tc \right] \leq e^{-cD_{KL}(t||B/A)}.
\end{equation*}

Similarly, letting $Y \sim \textnormal{HypGeo}(A, A - B, c)$, for $t > \frac{B}{A}$, we have

\begin{equation*}
\Pr\left[X \geq tc \right] = \Pr[Y \leq (1 - t)c] \leq e^{-cD_{KL}(1 - t||1 - B/A)} = e^{-cD_{KL}(t||B/A)}.
\end{equation*}

Using this bound, we have

\begin{align*}
\Pr[e(S,j)\leq ({\eta_k-t})(\gamma d n-dj)]&\leq e^{-D_{KL}\left(\eta_k-t||\eta_k\right)(\gamma d n-dj)}\leq e^{-D_{KL}\left(\eta_k-t||\eta_k\right)\frac{\gamma dn}{2}}
\end{align*}

for all $t\in(0,\eta_k)$. The following claims expands this KL-divergence for $t = \eta_k/2$.

\begin{equation*}
\begin{split}
D_{KL}\left(\eta_k-\eta_k/2||\eta_k\right) \geq \frac{\eta_k}{12}.
\end{split}
\end{equation*}

\begin{equation*}
\begin{split}
D_{KL}\left(\eta_k/2||\eta_k\right)  &= \frac{\eta_k}{2}\ln(1/2) + \left(1 - \frac{\eta_k}{2}\right)\ln\left(\frac{1 - \eta_k/2}{1 - \eta_k}\right) \\
&\geq \frac{\eta_k}{2}\ln(1/2) + \left(1 - \frac{\eta_k}{2}\right)\left(\frac{\eta_k}{2} + \frac{3\eta_k^2}{8}\right) \\
&= \frac{\eta_k}{2}\left(\ln(1/2) + \left(1 - \frac{\eta_k}{2}\right)\left(1 + \frac{3\eta_k}{4}\right)\right) \geq \frac{\eta_k}{12}.
\end{split}
\end{equation*}

Here the first inequality follows by taylor expanding $
\ln(1 - x)$. The final inequality follows by noting that the quadratic $\ln(1/2) + \left(1 - \frac{\eta_k}{2}\right)\left(1 + \frac{3\eta_k}{4}\right)$ is minimized over $\eta_k \in [0, 1]$ at $\eta_k \in \{0, 1\}$.

Union bounding over all $\binom{n}{k}$ sets $S$ of size $k$, we have

\begin{align*}
\Pr\left[\exists S, k:=|S| \in [n/d^3, n]: e(S,j)\leq \frac{\eta_k}{2}(\gamma dn-dj)\right]
&\leq \sum_{k=n/d^3}^n \binom{n}{k}e^{-\frac{\eta_k\gamma dn}{24}}
\leq \sum_{k=n/d^3}^n \left(\frac{en}{k}\right)^ke^{-\frac{k\gamma d}{24}} \\
%  &=  \sum_{k=n/d^3}^n e^{-k\left(\frac{\gamma d}{24}- \ln(1/\eta_k) - 1\right)} \\
&\leq \sum_{k=n/d^3}^n e^{-k\left(\frac{\gamma d}{24}- \ln(d^3) - 1\right)}
\leq \sum_{k=n/d^3}^n e^{-k}
\leq 2e^{-n/d^3}.
\end{align*}

We take a union bound over $j \in [1, \gamma n/2]$ to achieve

\begin{align*}
\Pr\left[\exists S, k := |S| \in[n/d^3,n] : e(S,j)\leq \frac{\eta_k}{2}(\gamma dn-dj)\right] \leq \gamma ne^{-n/d^3}.
\end{align*}

Conditioned on $\Omega$, we can use the anti-concentration bound in Lemma <ref> to show that for $j \leq \gamma n/2$, $R_j$ often decreases.

For $j \leq \gamma n/2$, conditioned on $\Omega$, if $R_j \geq 1$, then with probability at least
$$\mu_k := \frac{1}{2}\left(1 - e^{-\frac{dk}{2n}}\right) - \frac{3\gamma d^3}{k},$$
we have $R_{j} \leq R_{j-1} - 1.$

Suppose $R_{j - 1} \geq 1$, and let $v$ be any vector in $(\mathbb{R}\backslash\{0\})^k$ such that $A_S^{[j - 1]}v=0$. Let $v' \in \mathbb{R}^{\gamma dk}$ be the vector which repeats each coordinate of $v$ $\gamma d$ times: that is, $v'_i = v_{\lceil \frac{i}{\gamma d}\rceil}$.

Let $h_j \in \{0, 1\}^{\gamma dn}$ be $j$th row of $H$, which has exactly $d$ $1$'s indicating the half-edges matched to the $d$ half-edges from the row-node $j$. Let $h_j(S) \in \{0, 1\}^{\gamma d k}$ be the restriction of $h_j$ to the entries corresponding to half-edges from column-nodes in $S$.

If at most one half-edge is matched from column-node $j$ to a single row-node in $S$ and $h_j(S) \cdot v' \neq 0$, then $R_{j} \leq R_{j-1} - 1$.

If at most one half-edge is matched from column-node $j$ to a single row-node in $S$, then
$$(A_S)^j v =  \sum_{i \in S}A_{ji}v_i = \sum_{i \in S}\mathbbm{1}(\exists \ell, \gamma d(i-1) < \ell \leq \gamma di, H_{j \ell} = 1 )v_i = \sum_{i \in S}v_i\sum_{\ell = \gamma d(i - 1) + 1}^{\gamma di} H_{j\ell} = h_j(S)\cdot v' \neq 0.$$
Hence $v \notin D(A_S^{[j]})$, so the rank of $D(A_S^{[j]})$ is strictly smaller than that of $D(A_S^{[j-1]})$.

\begin{equation*}
\Pr[h_j(S) \cdot v' = 0 | \Omega] \leq  \frac{1}{2}\left(1 + e^{-\frac{dk}{2n}}\right) +  \frac{d}{\gamma k}.
\end{equation*}

We condition on the number of $1$'s in $h_j(S)$, which we denote $s$. Observe that conditioned on $s$, the vector $h_j(S)$ is a uniformly random vector from the set of all vectors in $\{0, 1\}^{\gamma d k}$ with $s$ 1s. This holds even when we conditioned on $\Omega$, because this event says nothing about which half-edges among the nodes in $S$ have been paired. By Lemma <ref>, since $v'$ contains no zeros (and hence its most common element is not zero), we have

\begin{equation}\label{eq:sneq0}
\Pr[h_j(S) \cdot v' = 0 | s \geq 1, \Omega] \leq 1/2 + \frac{d}{\gamma k}.
\end{equation}

It remains to consider the probability that $s = 0$, since in this case, we always have $h_j(S) \cdot v' = 0$. We know that $s$ is distributed like a hypergeometric random variable $\text{HypGeo}(\gamma d n - dj, d, e(S, j))$. Indeed, there are $d$ half-edges that are paired with the addition of the $(j + 1)$-th column, there are $e(S, j)$ unpaired half-edges among the nodes in $S$, and there are $\gamma d n - dj$ total unpaired half-edges among the row nodes. Since we have conditioned on $\Omega$, we know that $\frac{e(S,j)}{\gamma d n-dj}\geq \frac{k}{2n}$. Hence we have

\begin{equation}\label{eq:s0}
\Pr[s = 0 | \Omega] \leq \left(1 - \frac{k}{2n}\right)^{d} \leq e^{-\frac{dk}{2n}}.
\end{equation}

Combining eqs. <ref> and <ref>, it follows that

\begin{equation*}
\begin{split}
\Pr[h_j(S) \cdot v' = 0 | \Omega] &= \Pr[s = 0| \Omega] + \left(1 - \Pr[s = 0| \Omega]\right)\Pr[h_j(S) \cdot v' = 0 | s \geq 1, \Omega]\\
&\leq \Pr[s = 0| \Omega] + \left(1 - \Pr[s = 0| \Omega]\right)\left(1/2 + \frac{d}{\gamma k}\right)\\
&\leq \Pr[s = 0| \Omega] + \left(1 - \Pr[s = 0| \Omega]\right)\left(1/2\right) + \frac{d}{\gamma k} \\
&= \frac{1}{2}\left(1 + \Pr[s = 0| \Omega]\right) +  \frac{d}{\gamma k}
\leq \frac{1}{2}\left(1 + e^{-\frac{dk}{2n}}\right) +  \frac{d}{\gamma k}.
\end{split}
\end{equation*}

The probability that more than one half-edge is matched from a column-node $j$ to a single row-node in $S$ is at most $\frac{2\gamma d^3}{k}$.

$\binom{d}{2}\left(\frac{\gamma d}{k/4}\right) \leq \frac{2\gamma d^3}{k}.$

It follows from the previous two claims that the probability that $h_j(S) \cdot v' \neq 0$ and at most one half-edge is match from a row-node $j$ to a single column-node in $S$ is at least

\begin{equation*}
\begin{split}
1 - \Pr[\textnormal{Event in Claim~\ref{claim:double_match} occurs}] - \Pr[h_j(S)\cdot v' = 0 | \Omega ]&\geq
1 - \frac{2\gamma d^3}{k} - \frac{d}{\gamma k} - \frac{1}{2}\left(1 + e^{-\frac{dk}{2n}}\right) \\
&= \frac{1}{2}\left(1 - e^{-\frac{dk}{2n}}\right) - \frac{2\gamma d^3}{k} - \frac{d}{\gamma k} \\
&\geq \frac{1}{2}\left(1 - e^{-\frac{dk}{2n}}\right) - \frac{3\gamma d^3}{k}.
\end{split}
\end{equation*}

Using Claim <ref>, this proves the lemma.

We are now ready to prove Lemma <ref>.

Recall that our goal is to show that with high probability, for all $k \geq \frac{n}{18e\gamma^2 d^2}$, for all sets $S$ of size $k$, we have $R_{\gamma n/2} = 0$. Throughout the rest of the proof, we assume that we have conditioned on $\Omega$, since $\Pr[\Omega] = 1 - o(1)$.

For a fixed set $S$ of size $k$, by Lemma <ref>, conditioned on each term being positive, the random process $R_0, R_1, R_2, \cdots, R_{\gamma n/2}$ is stochastically dominated by the random process $Y_0 = R_0, Y_1, Y_2, \ldots ,Y_{\gamma n/2}$, where $Y_{i + 1} = Y_i - \Ber(\mu_k)$ and
$$\mu_k = \frac{1}{2}\left(1 - e^{-\frac{dk}{2n}}\right) - \frac{3\gamma d^3}{k}.$$

Hence $\Pr[R_{\gamma n/2} > 0] \leq \Pr[Y_{\gamma n/2} > 0]$. By a Chernoff Bound, since $Y_0 = k$, for any $\mu \leq \mu_k$,

\begin{equation*}
\begin{split}
\Pr[Y_{\gamma n/2} > 0] &= \Pr[Y_{0} - Y_{\gamma n/2} < k] = \Pr[\Ber(k, \mu_k) < k] \leq e^{-\gamma n\mu/2}\left(\frac{e\gamma n\mu}{2k}\right)^k.
\end{split}
\end{equation*}

Define $\eta_k := k/n$. Taking a union bound over all sets $S$ of size $k$, conditioned on $\Omega$, the probability that at least one set $S$ has $R{\gamma n/2} > 0$ is at most

\begin{equation}\label{large_union}
\begin{split}
\binom{n}{k}e^{-\gamma n\mu/2}\left(\frac{e\gamma n\mu}{2k}\right)^k &\leq \left(\frac{en}{k}\right)^ke^{-\gamma n\mu/2}\left(\frac{e\gamma n\mu}{2k}\right)^k
= e^{-\gamma n\mu/2}\left(\frac{e^2\gamma n^2\mu}{2k^2}\right)^k \\
&= e^{-\gamma n\mu/2+ k\log\left(\frac{e^2\gamma n^2\mu}{k^2}\right)}
= e^{k\left(-\frac{\gamma\mu}{2\eta_k} + \log\left(\frac{e^2\gamma\mu}{2\eta_k^2}\right)\right)}.
\end{split}
\end{equation}

We consider the two cases $\frac{n}{18e\gamma^2 d^2} \leq k \leq \frac{5n}{d}$ and $k \geq \frac{5n}{d}$.

In the first case, since $1 - e^{-x} \geq x/2$ for $0 < x < 1$, for $n$ large enough, we have
$$\mu_k \geq \frac{1}{2}\left(\frac{d\eta_k}{4}\right) - \frac{3\gamma d^3}{k} \geq
\frac{d\eta_k}{10}.$$

Hence for $\mu = \frac{d\eta_k}{10}$, we have

\begin{equation*}
-\frac{\gamma \mu}{2\eta_k} + \log\left(\frac{e^2\gamma \mu}{2\eta_k^2}\right) \leq -\frac{\gamma d}{20} + \log\left(\frac{e^2\gamma d}{20\eta_k^2}\right) \leq -\frac{\gamma d}{20} + \log\left(\frac{18^2e^3\gamma^5d^5}{20}\right) \leq  -0.25
\end{equation*}

for $d$ larger than some constant $d_0$.

In the second case, we have $\mu_k \geq 0.45$, and hence for $\mu = 0.45$ and $\gamma \geq 16$, we have

\begin{equation*}
-\frac{\gamma \mu_k}{2\eta_k} + \log\left(\frac{e^2\gamma \mu_k}{2\eta_k^2}\right) \leq \max_{\eta \leq 1} -\frac{3.6}{\eta} + \log\left(\frac{3.6e^2}{\eta^2}\right)  \leq -0.25.
\end{equation*}

Returning to eq. <ref>, conditioned on $\Omega$, the probability that there is a set $S$ of size $k$ for which $R_{\gamma n/2} > 0$ is at most $e^{-k/4}$. Summing over all $k \geq \frac{n}{18e\gamma^2 d^2}$ yields a probability of failure among any $k$ of at most
$$\frac{e^{-\frac{n}{18e\gamma^2 d^2}}}{1 - e^{-1/4}} \leq 5e^{-\frac{n}{18e\gamma^2 d^2}}.$$

Unioning with the probability that $\Omega$ doesn't occur from Lemma <ref> yields Lemma <ref>.

§.§ Proof of Theorem <ref>

We are now ready to prove Theorem <ref>.

We will use the following lemma on the concentrations of functions of a random permutation from [15], Lemma 3.3.[In an earlier version of this paper predating [15], we instead used a longer second moment argument. For simplicity, we have replaced this argument with a shorter argument which uses this lemma.]

Let $m\in \mathbb{N}$, let $S$ be any finite set of size $|S| \ge m$, let $\mathcal F$ be the set of functions $[m] \to S$ and let $\mathcal{I}\subseteq \mathcal F$ be the set of injections
$[m] \to S$. Consider a function $f:\mathcal F\to\mathbb{R}$
satisfying the property that if $\pi,\pi'$ agree except that $\pi(i)\ne \pi'(i)$, then $|f(\pi)-f(\pi')|\le c_{i}$.
Let $\pi\in\mathcal{I}$ be a uniformly random injection. Then for $t\ge 0$,

\[
\mb{P}\left[|f(\pi)-\mb{E} f(\pi)|\ge t\right]\le 2\exp\left(-\frac{t^{2}}{8\sum_{i=1}^{m}c_{i}^{2}}\right).
\]

We restate Theorem <ref> for the reader's convenience.

Let $\Omega$ be the event the there are no minimal dependencies among $k$ columns of $A$ that are not in
$$\bigcup_{k \leq \log(n)}\mathcal{T}_k \cup \mathcal{T}_k^+ \cup \mathcal{T}_k^C .$$
By combining the result of the small case, Lemma <ref>, with the result of the large case, Lemma <ref>, we observe that $\Pr[\Omega] = 1 - o(1)$. This proves the first statement in the theorem. Next we bound the size of the set of columns involved in linear dependencies. We will do this by studying the expected number of linearly dependent columns and showing concentration via Lemma <ref>. We begin with some set-up.

We extend the mapping in Definition <ref> from permutations $\rho \in \mathcal{S}_{\gamma d n}$ to matrices in $\{0, 1\}^{\gamma n \times n}$ to be a more general mapping from $\mathcal{F}$, the set of functions $[\gamma n d] \rightarrow [\gamma n d]$ to matrices in $\{0, 1\}^{\gamma n \times n}$. Create $\gamma n$ row-nodes with $d$ half-edges each and $n$ column-nodes with $\gamma d$ half-edges as per Definition <ref>. Given a function $\pi \in \mathcal{F}$, for $i \in [\gamma d n]$, attach the $i$th right half-edge to the $\pi(i)$th left half-edge. Note that some half-edges on the right may have multiple half-edges connected to it on the right. Let $A_0 \in \{0, 1\}^{\gamma n \times n}$ be the matrix where $(A_0)_{ij} = 1$ if and only if there is at least one half-edge from row-node $i$ connected to a half-edge from column-node $j$. As before, let $A$ be the submatrix containing the first $(1-p)\gamma n$ rows of $A_0$.

Let $\mathcal{S}(\pi) := \{S: A_S \in \mathcal{T}_k \cup \mathcal{T}_k^+ \cup \mathcal{T}_k^C, |S| \leq \log(n)\}$, and let $\mathcal{D}(\pi) := \cup_{S \in \mathcal{S}(\pi)} S$. For $\pi \in \Omega$, define $f(\pi) := |\mathcal{D}(\pi)|$. The following shows that $f$ satisfies a certain Lipshitz property on $\Omega.$

For any $\pi, \pi' \in \Omega$, we have $|f(\pi) - f(\pi')|\leq \log(n)\on{dist}(\pi, \pi')$.

Let $\tau = \{i : \pi(i) \neq \pi'(i)\}$. Without loss of generality, assume $|\mathcal{D}(\pi)| > |\mathcal{D}(\pi')|$, and let $\Delta = \mathcal{D}(\pi) \setminus \mathcal{D}(\pi')$. Let $\mathcal{X}$ be a set of linearly independent vectors constructed in the following way: While there exists some $j \in \Delta$ which is not contained in any of the vectors in $\mathcal{X}$, add to $\mathcal{X}$ some vector $x$ such that $A(\pi)x = 0$, and $j \in \supp(x)$ and $|\supp(x)| \leq \log(n)$. Since $\pi \in \Omega$, it is always possible to find such a vector. Further, letting $\mathcal{X}_{\Delta} = \{x_{\Delta} : x \in \mathcal{X}\}$ be the set $\mathcal{X}$ restricted to indices in $\Delta$, we see that the set of vectors $\mathcal{X}_{\Delta}$ is linearly independent. Finally, we must have $|\mathcal{X}| \geq \frac{|\Delta|}{\log(n)}$.

Assume for the sake of contradiction that $\frac{|\Delta|}{\log(n)} > |\tau|$. Then let $X \in \mathbb{R}^{n \times |\mathcal{X}|}$ be the matrix with the vectors of $\mathcal{X}$ as its columns, and let $a$ be some vector such that:

* $(Xa)_i = 0$ for all $i \in \tau$;

* $\supp(Xa) \cap \Delta \neq \emptyset$.

Such a vector $a$ must exist because the rank of $X^{\Delta}$ is at least $\frac{|\Delta|}{\log(n)} > |\tau|$, which means that there mush be some row in $X^{\Delta}$ which is not in the span of the $|\tau|$ rows of $X^{\tau}$.

Let $x = Xa$. For any $k \in \supp(x)$, by Lemma <ref>, there exists some set $S \subset \supp(x)$ such that $A(\pi)_S \in \mathcal{M}_{|S|}$. However, since $\tau \cap \supp(x) = \emptyset$, it follows that $A(\pi')_S \in  \mathcal{M}_{|S|}$, and hence since $\pi' \in \Omega$, we must have $\supp(x) \subset \mathcal{D}(\pi')$. Since $\supp(x) \cap \Delta \neq \emptyset$, this is a contradiction.

We now extend $f$ to $\mathcal{F} \setminus \Omega$. Define $\on{dist}(\pi, \pi') = |\{i : \pi(i) \neq \pi'(i)\}|$  Let $G$ be a graph with the node set $\mathcal{F}$, and let there be an edge of weight $\log(n)$ between any pair of vertices $\pi$ and $\pi'$ with $\on{dist}(\pi, \pi') = 1$. Construct an additional vertex $s$ with an edge of weight $f(\pi)$ from $s$ to $\pi$ for any $\pi \in \Omega$. Now define $f(\pi) := \on{dist}_G(\pi, s)$ to be the shortest-path distance in $G$ from $s$ to $\pi$ for any $\pi \in \mathcal{F}$. It is immediate from the triangle inequality that for any $\pi, \pi'$ with $\on{dist}(\pi, \pi') = 1$, $|f(\pi) - f(\pi')|\leq \log(n)$.

In the following claim, we bound the expectation of $f$.
For some constant $c$,
$\mathbb{E}_{\rho \sim \mathcal{S}_{\gamma d n}} f(\rho) \leq np^{\gamma d - c\log(\gamma d)}$.

For a set $S \subset [n]$, let $X_S$ be the indicator of the event that $A_S \in \mathcal{T}_k \cup \mathcal{T}_k^+ \cup \mathcal{T}_k^C$. Notice that if $\rho \in \Omega$, $f(\rho)$ is at most
$X := \sum_{S \subset [n], |S| \leq \log(n)}|S|X_S$.

By Lemma <ref>, for some constant $c_{\ref{lemma:abc_small}}$, we have

\begin{equation*}
\begin{split}
\mathbb{E}[X] &= \sum_{S: |S| \leq \log(n)}{|S|\Pr[A_S \in \mathcal{T}_k \cup \mathcal{T}_k^+ \cup \mathcal{T}_k^C]}
\leq \sum_{k \geq 1}k\binom{n}{k}\left(\frac{k}{n}\right)^{k - 1}p^{\gamma dk + c_{\ref{lemma:abc_small}}k\log(\gamma d)} \\
&\leq n \sum_{k \geq 1}p^{\gamma d k + (c_{\ref{lemma:abc_small}} + 1)k\log(\gamma d)} \leq n p^{\gamma d - c_1\log(\gamma d)}
\end{split}
\end{equation*}

for some constant $c_1$. Since $\Pr[\Omega] = 1 - o(1)$, and $f \leq n$ always, we have $\mathbb{E}[f(\rho)] \leq o(n) + n p^{\gamma d - c_1\log(\gamma d)} \leq n p^{\gamma d - c_1\log(\gamma d) - o(1)} \leq n p^{\gamma d - c\log(\gamma d)}$ for some constant $c$.

We now use Lemma <ref> with $t = n^{3/4}$ to show that with probability $1 - o(1)$, $f(\pi) \leq \mathbb{E}[f(\pi)] + n^{3/4} \leq n p^{\gamma d - c\log(\gamma d)}$ for some constant $c$. Finally, using the fact that $f(\pi) = \left|\bigcup_{x : Ax = 0} \supp(x) \right|$ for $\pi \in \Omega$, we have
$$\Pr\left[\left|\bigcup_{x : Ax = 0} \supp(x) \right|\leq n p^{\gamma d - c\log(\gamma d)}\right] \geq 1 - o(1).$$

§.§ Gradient Coding Results

In this section, we prove the applications to gradient coding.

While the first bound will be a direct corollary of Corollary $\ref{abc_random}$, the second bound relies on some external lemmas that will be introduced below. Thus, for the sake of clarity, we will split the proof of Theorem $\ref{abc_stacked}$ into the following two lemmas.

Let $c,\gamma_0,d_0$ be the universal constants from Corollary $\ref{abc_random}$. Choose any $\gamma, d\in\mathbb{Z}^+$ such that $\gamma \geq \gamma_0$, $\gamma \mid d$, and $\frac{d}{\gamma }\geq d_0$. For any $n$ such that $\gamma \mid n$, let $B\sim \on{ABC}_{\gamma-\on{stacked}}(n,d)$. Then with probability $1-o(1)$ over the choice of $B$, we have that for any $p<\frac{1}{2}$:

\begin{equation*}
\frac{1}{n}\mathbb{E}_{S\sim\binom{[n]}{pn}} \textnormal{err}(B, S) \leq p^{d + c\log(d)}+o(1).
\end{equation*}

Let $\gamma,d$ be such that $\gamma \mid d$ and $\gamma \mid n$. Let $B\sim \on{ABC}_{\gamma-\on{stacked}}(n,d)$. With constant probability, we have:

\begin{equation*}
\frac{1}{n}\max_{S \in \binom{[n]}{pn}}\left( \textnormal{err}(B, S)\right) \leq  \left(\frac{8\gamma^3p}{d}\right)+o(1).
\end{equation*}

Temporarily assuming these lemmas, we note that Theorem <ref> follows immediately. We will now prove Lemma $\ref{stacked_prop1}$.

Let $A_0\sim \textnormal{ABC}(n/\gamma,\gamma,d/\gamma)$  denote the ABC matrix which is stacked $\gamma$ times to generate $B$, then it follows that:

\begin{align*}
\frac{1}{n}\mathbb{E}_{S \sim \binom{[n]}{pn}}{ \textnormal{err}(B, S)}&= \frac{1}{n}\mathbb{E}_{S \sim \binom{[n]}{pn}}\min_{w: w_j = 0 \: \forall \: j \in S}|Bw - \mathbbm{1}|_2^2\\
&=  \frac{\gamma}{n}\mathbb{E}_{S \sim \binom{[n]}{pn}}\min_{w: w_j = 0 \: \forall \: j \in S}|A_0^\top w - \mathbbm{1}|_2^2\\
&=  \frac{\gamma}{n}\mathbb{E}\left[\min_{w}|A^\top w - \mathbbm{1}|_2^2\right]
\end{align*}

where $A\sim \textnormal{ABC}_p(n/\gamma,\gamma,d/\gamma)$. By Corollary <ref>, for some constant $c$, there is a $1-o(1)$ chance that $A_0$ has the property that the following holds with probability $1-o(1)$ over the choice of $S$:

\begin{equation*}
\frac{\gamma}{n}\min_{w}|A^\top w - \mathbbm{1}|_2^2\leq p^{d-c\log(d)}.
\end{equation*}

Thus with probability $1 - o(1)$ over the choice of $B$, since $ \frac{\gamma}{n}\min_{w}|A^\top w - \mathbbm{1}|_2^2$ is always at most $1$,

\begin{equation*}
\frac{1}{n}\mathbb{E}_{S \sim \binom{[n]}{pn}}{ \textnormal{err}(B, S)} = \frac{\gamma}{n}\mathbb{E}\left[\min_{w}|A^\top w - \mathbbm{1}|_2^2\right]\leq p^{\gamma d+c\log_p(\gamma d)} + o(1).
\end{equation*}

Lemma <ref> requires a bit more machinery. We employ the following lemma from [17] which allows us to bound the adversarial error of a gradient code as a function of the second largest singular value. Formally, we have the following lemma.

Let $A\in \{0,1\}^{N\times M}$ be an assignment matrix such that each row has exactly $D$ $1$'s. Let $\sigma_2$ be the largest singular value of $A$. Then for any set of stragglers $S$ such that $|S|=s$, we have:

\begin{equation*}
\frac{1}{N}\textnormal{err}(A,S)\leq\frac{1}{N}\left(\frac{\sigma_2}{D}\right)^2\frac{sM}{M-s}
\end{equation*}

To calculate an upper bound on the second largest singular value of an ABC matrix, we first need a result from [5] which states that with constant probability, the configuration model we use to generate our ABC matrix has no rows which map to the same column node more than once ie., the bipartite graph produced is simple.

Let $\mathcal{G}(n, \gamma n, d, \gamma d)$ denote the uniform distribution on simple $(d, \gamma d)$-biregular bipartite graphs with $n$ left nodes and $\gamma n$ right nodes.

Let $A_0\sim \on{ABC}(n,\gamma,d)$, then the probability that $\begin{pmatrix}
0 & A_0\\
A_0^\top & 0
\end{pmatrix}$
is the adjacency matrix of a bipartite, biregular random graph $G$ is at least $\varepsilon(d)>0$. Furthermore, if we condition on this event occurring, then $G\sim\mathcal{G}(n,\gamma n,d,\gamma d)$.

The previous lemma allows us to apply the following result of [7] to bound the second largest singular value of these well behaved ABC matrices.

Let $A=\begin{pmatrix}
0 & X\\
X^\top & 0
\end{pmatrix}$ be the adjacency matrix of a bipartite, biregular random graph $G\sim \mathcal{G}(n,\gamma n,d,\gamma d)$. Then, with probability $1-o(1)$, $A$'s second largest eigenvalue $\lambda_2$ satisfies
$$\lambda_2 \leq \sqrt{d_1-1}+\sqrt{d_2-1}+o(1).$$

We are now ready to prove Lemma <ref>.

Let $A_0\sim \textnormal{ABC}(n/\gamma ,\gamma,d/\gamma)$ denote the $ABC$ matrix which is stacked $\gamma$ times to generate $B$. It follows that:

\begin{align*}
\frac{1}{n}\max_{S \in \binom{[n]}{pn}}{ \textnormal{err}(B, S)}&= \frac{1}{n}\max_{S \in \binom{[n]}{pn}}\min_{w: w_j = 0 \: \forall \: j \in S}|Bw - \mathbbm{1}|_2^2\\
&=  \frac{\gamma}{n}\max_{S \in \binom{[n]}{pn}}\min_{w: w_j = 0 \: \forall \: j \in S}|A_0^\top w - \mathbbm{1}|_2^2\\
&= \frac{\gamma}{n}\max_{S \in \binom{[n]}{pn}} \on{err}(A_0^\top,S).
\end{align*}

By Lemma $\ref{stacked_lemma2}$, with constant probability, $A'=\begin{pmatrix}
0 & A_0\\
A_0^\top & 0
\end{pmatrix}$ is the adjacency matrix of a bipartite, biregular random graph $G$. Condition on this event occurring. Then $G$ is uniformly sampled from $\mathcal{G}(n/\gamma,n,d/\gamma,d)$. By Lemma $\ref{stacked_lemma3}$, with probability $1-o(1)$, the second largest eigenvalue of $A'$ is $\lambda_2\leq \sqrt{d/\gamma-1}+\sqrt{d-1}+o(1)$. Thus, the second largest singular value of $A_0$ is $\sigma_2 \leq \sqrt{d/\gamma-1}+\sqrt{d-1}+o(1)$. Hence, by Lemma $\ref{stacked_lemma1}$, we have

\begin{align*}
\frac{\gamma}{n}\max_{S \in \binom{[n]}{pn}} \on{err}(A_0^\top,S)&\leq\frac{\gamma}{n}\left(\frac{\gamma\sigma_2}{d}\right)^2\frac{pn^2}{(1-p)n}
\leq \gamma^3\left(\frac{2\sqrt{d}+o(1)}{d}\right)^2\frac{p}{(1-p)}\\
&\leq \left(\frac{4\gamma^3p}{d(1-p)}\right)+o(1)
\leq \left(\frac{8\gamma^3p}{d}\right)+o(1).
\end{align*}

§ ACKNOWLEDGEMENTS

Thanks to Mary Wootters, Matthew Kwan, Vishesh Jain, Ashwin Sah, and Mehtaab Sawhney for helpful conversations and feedback.

[1]
Louigi Addario-Berry and Laura Eslava.
Hitting time theorems for random matrices.
Combinatorics, Probability and Computing, 23(5):635–669, 2014.

[2]
Jonathan Aronson, Alan Frieze, and Boris G Pittel.
Maximum matchings in sparse random graphs: Karp–sipser revisited.
Random Structures & Algorithms, 12(2):111–177, 1998.

[3]
Anirban Basak and Mark Rudelson.
Sharp transition of the invertibility of the adjacency matrices of
sparse random graphs.
Probability Theory and Related Fields, 180:233––308, 2021.

[4]
Rawad Bitar, Mary Wootters, and Salim El Rouayheb.
Stochastic gradient coding for straggler mitigation in distributed
IEEE Journal on Selected Areas in Information Theory, 2020.

[5]
Béla Bollobás and Bollobás Béla.
Random graphs.
Cambridge university press, 2001.

[6]
Charles Bordenave, Marc Lelarge, and Justin Salez.
The rank of diluted random graphs.
The Annals of Probability, pages 1097–1121, 2011.

[7]
Gerandy Brito, Ioana Dumitriu, and Kameron Decker Harris.
Spectral gap in random bipartite biregular graphs and applications.
arXiv preprint arXiv:1804.07808, 2018.

[8]
Zachary Charles and Dimitris Papailiopoulos.
Gradient coding using the stochastic block model.
In 2018 IEEE International Symposium on Information Theory
(ISIT), pages 1998–2002. IEEE, 2018.

[9]
Zachary Charles, Dimitris Papailiopoulos, and Jordan Ellenberg.
Approximate gradient coding via sparse random graphs.
arXiv preprint arXiv:1711.06771, 2017.

[10]
Vasek Chvátal.
The tail of the hypergeometric distribution.
Discrete Mathematics, 25(3):285–287, 1979.

[11]
Amin Coja-Oghlan, Alperen A Ergür, Pu Gao, Samuel Hetterich, and Maurice
The rank of sparse random matrices.
In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on
Discrete Algorithms, pages 579–591. SIAM, 2020.

[12]
Kevin P Costello, Terence Tao, and Van Vu.
Random symmetric matrices are almost surely nonsingular.
Duke Mathematical Journal, 135(2):395–413, 2006.

[13]
Kevin P Costello and Van Vu.
On the rank of random sparse matrices.
arXiv preprint arXiv:0711.2696, 2007.

[14]
Kevin P Costello and Van H Vu.
The rank of random graphs.
Random Structures & Algorithms, 33(3):269–285, 2008.

[15]
Asaf Ferber, Matthew Kwan, Ashwin Sah, and Mehtaab Sawhney.
Singularity of the k-core of a random graph.
arXiv preprint arXiv:2106.05719, 2021.

[16]
Asaf Ferber, Matthew Kwan, and Lisa Sauermann.
Singularity of sparse random matrices: simple proofs, 2020.

[17]
Margalit Glasgow and Mary Wootters.
Approximate gradient coding with optimal decoding.
arXiv preprint arXiv:2006.09638, 2020.

[18]
Han Huang.
Rank of sparse bernoulli matrices.
https://arxiv.org/pdf/2009.13726.pdf, 2021.

[19]
Vishesh Jain, Ashwin Sah, and Mehtaab Sawhney.
Singularity of discrete random matrices ii.
arXiv preprint arXiv:2010.06554, 2020.

[20]
Vishesh Jain, Ashwin Sah, and Mehtaab Sawhney.
Rank deficiency of random matrices.
arXiv preprint arXiv:2103.02467, 2021.

[21]
Swanand Kadhe, O Ozan Koyluoglu, and Kannan Ramchandran.
Gradient coding based on block designs for mitigating adversarial
In 2019 IEEE International Symposium on Information Theory
(ISIT), pages 2813–2817. IEEE, 2019.

[22]
Richard Karp and Michael Sipser.
Maximum matchings in sparse random graphs.
In Proceedings of the Twenty-Second IEEE Annual Symposium on
Foundations of Computer Science, pages 364––375. IEEE Computer Society,

[23]
János Komlós.
On the determinant of (0-1) matrices.
Studia Scientiarium Mathematicarum Hungarica, 2:7–21, 1967.

[24]
Tomasz Łuczak.
Size and connectivity of the k-core of a random graph.
Discrete Mathematics, 91(1):61–68, 1991.

[25]
Boris Pittel, Joel Spencer, and Nicholas Wormald.
Sudden emergence of a giantk-core in a random graph.
Journal of Combinatorial Theory, Series B, 67(1):111–151,

[26]
Netanel Raviv, Rashish Tandon, Alex Dimakis, and Itzhak Tamo.
Gradient coding from cyclic mds codes and expander graphs.
In International Conference on Machine Learning, pages
4305–4313, 2018.

[27]
Mark Rudelson and Roman Vershynin.
The littlewood–offord problem and invertibility of random matrices.
Advances in Mathematics, 218(2):600–633, 2008.

[28]
Rashish Tandon, Qi Lei, Alexandros G Dimakis, and Nikos Karampatziakis.
Gradient coding: Avoiding stragglers in distributed learning.
In International Conference on Machine Learning, pages
3368–3376, 2017.

[29]
Konstantin Tikhomirov.
Singularity of random bernoulli matrices.
Annals of Mathematics, 191(2):593–634, 2020.

[30]
Van Vu.
Recent progress in combinatorial random matrix theory.
arXiv preprint arXiv:2005.02797, 2020.

[31]
Hongyi Wang, Zachary Charles, and Dimitris Papailiopoulos.
Erasurehead: Distributed gradient descent without delays using
approximate gradient coding.
arXiv preprint arXiv:1901.09671, 2019.

[32]
Sinong Wang, Jiashang Liu, and Ness Shroff.
Fundamental limits of approximate gradient coding.
Proceedings of the ACM on Measurement and Analysis of Computing
Systems, 3(3):1–22, 2019.

§ TAIL BOUNDS

We include the following version of the Chernoff Bound for reference.

Let $X_i \in [0, 1]$ be i.i.d. random variables with $\mathbb{E}[X_i] = p$. Then for $q \leq p$,

\begin{equation*}
\Pr\left[\sum_i X_i \leq qn \right] \leq e^{\frac{-n(p - q)^2}{2p}}.
\end{equation*}

We also use the following lemma.
[Tail Bound on Binomial]lemmataillemma
If $t \geq 2np$, then

\begin{equation*}
\Pr\left[\Bin(n, p) \geq t\right] \leq 2\left(\frac{enp}{t}\right)^t.
\end{equation*}

\begin{equation*}
\begin{split}
\Pr\left[\Bin(n, p) \geq t\right] &\leq \sum_{i = t}^{n}\binom{n}{i}p^i
\leq \sum_{i = t}^{n}\binom{n}{t}p^i\prod_{j = t + 1}^i\left(\frac{n - j + 1}{j}\right) \\
&\leq \sum_{i = t}^{n}\binom{n}{t}p^i\prod_{j = t + 1}^i\left(\frac{n}{t}\right)
= \sum_{i = t}^{n}\binom{n}{t}p^t\left(\frac{pn}{t}\right)^{i - t} \\
&\leq  \binom{n}{t}p^t\sum_{j = 0}^{\infty}\left(\frac{pn}{t}\right)^{j}
= \frac{\binom{n}{t}p^t}{1 - \frac{pn}{t}}.
\end{split}
\end{equation*}

For $t \geq 2np$, plugging in Sterling's formula yields the lemma.

§ PROOF OF LEMMA <REF> AND  <REF> FOR CLASSIFICATION OF MINIMAL DEPENDENCIES

We restate Lemma <ref>.

Suppose $G$ was not connected, and without loss of generality let $[1,\ldots,L], [L+1,\ldots,k]$ be two disconnected components of $G$ for $1 \leq L \leq k-1$. By definition of $\mathcal{M}_k$ there is non-zero $v \in \mathbb{R}^k$ with $M v = 0$, and $v$ has all non-zero entries. Let $v^{(L)}, v^{(R)} \in \mathbb{R}^k$ with $v^{(L)} = (v_1,v_2,\ldots,v_L,0,0,\ldots,0)$ and $v^{(R)} = (0,0,\ldots,0,v_{L+1},v_{L+2},\ldots,v_k)$, such that
$$M (v^{(L)} + v^{(R)}) = M  v = 0.$$
By the disconnectedness of $[1,\ldots,L]$ and $[L+1,\ldots,k]$, the set of rows of $M$ having non-zero entries in columns $[1,\ldots,L]$ is disjoint from the set of rows of $M$ having non-zero entries in columns $[L+1,\ldots, k]$. Thus $M v^{(L)}$ and $M v^{(R)}$ are non-zero in disjoint coordinates. Thus $M(v^{(L)} + v^{(R)}) = 0$ implies that $Mv^{(L)} = M  v^{(R)} = 0$. This implies the kernel of $M$ has rank at least two, which contradicts that $M$ has rank $k-1$. Thus $G$ is a connected graph.

Recall Lemma <ref>:

We break the proof of Lemma <ref> into three lemmas, which we prove independently.

$\mathcal{S}_{2k-2, k} = \mathcal{T}_k$. Further, for $B \in \mathcal{T}_k = \mathcal{S}_{2k - 2, k}$, there is a unique (up to constant multiple) non-zero vector $v$ satisfying $B  v = 0$, where $v_i = (-1)^{d_G(i,j)} v_j$, and $d_G(i,j)$ is the path length from vertex $i$ to $j$ in the graph $G$ with edge-vertex incidence matrix $B$.

We prove this by showing both inclusions in the following two claims.

$\mathcal{T}_k \subseteq \mathcal{S}_{2k-2, k}$.

Let $B \in \mathcal{T}_k$. Since $B$ has $k-1$ non-zero rows, it has rank at most $k-1$, and so the nullspace of $B$ has dimension at least $1$. Let $v$ be any vector such that $Bv = 0$. Suppose $(i,j)$ is an edge in the tree $G$ with edge-vertex incidence matrix $B$. Then there is a row $r$ of $B$ such that row $B^{\{r\}}$ has $1$'s at, and only at, coordinates $i$ and $j$. We have $B^{\{r\}} \cdot v = 0$ thus $v_j = -v_i$. Applying this to paths of multiple edges gives that $v_i = (-1)^{d_G(i,j)} v_j$. By this formula, if any $v_i$ is non-zero, then all other entries of $v$ are non-zero, and are uniquely determined by $v_i$. Thus $B$ has rank $k-1$. We also know that $B$ has $k-1$ non-zero rows each with two $1$'s, so it has $2k-2$ ones total. Thus $B \in \mathcal{S}_{2k - 2, k}$. In addition, by the description of $v$, this establishes the second statement of the lemma.

$\mathcal{S}_{2k - 2, k} \subseteq \mathcal{T}_k$.

Suppose $B \in \mathcal{S}_{2k - 2, k}$. Because $B$ has rank $k-1$, $B$ must have at least $k-1$ non-zero rows. Recall that by Observation <ref>, no row of $B$ can have exactly one $1$. Thus, $B$ must have exactly $k-1$ non-zero rows, each with exactly two $1$'s. Let $G$ be be the graph on vertices $[1,\ldots,k]$ encoded by edge-vertex incidence matrix given by the non-zero rows of $B$. By Lemma <ref>, $G$ is connected.  Because $G$ is a connected graph on $k$ vertices with at most $k-1$ edges, $G$ must be a tree, and all its $k-1$ non-zero rows encode distinct edges. Thus $B \in \mathcal{T}_k$.

$\mathcal{T}_k^+ = \mathcal{S}_{2k - 1, k}$

We prove this by showing both inclusions in the following two claims.

$\mathcal{T}_k^+ \subseteq \mathcal{S}_{2k - 1, k}$.

Suppose $B \in \mathcal{T}_k^+$, such that $B$ is the hyperedge-vertex incidence matrix of a forest with two trees connected by a $3$-hyperedge. Without loss of generality, assume the first row of $B$ encodes this $3$-hyperedge and that $B_{11} = B_{12} = B_{1k} = 1$, with vertices $1$ and $2$ in the same tree and connected by an even path, and vertex $k$ in the other tree. We may further assume without loss of generality that rows $1,2,\ldots,L$ correspond to one tree, and $L+1,\ldots,k$ correspond to the other, for some $L$ with $2 \leq L \leq k-1$.

Observe that $B^{/1}_{[L]}$ is the edge-vertex incidence matrix of some tree $T_1$. So by the second statement of Lemma <ref>, there is a unique (up to constant multiple) non-zero vector $v_1 \in \mathbb{R}^L$ satisfying $B^{/1}_{[L]}v_\ell = 0$. Similarly, there is a unique (up to constant multiple) non-zero vector $v_2 \in \mathbb{R}^{k-L}$ satisfying $B^{/1}_{[k] \setminus [L]}  v_2 = 0$. By the disjointness of the two trees, the nullspace of $B^{/1}$ is precisely spanned by the two vectors $v^1 := (v_1, 0^{k - L})$ and $v^2 := (0^L, v_2)$. It follows that the null space of $B$ is the set of vectors

$$\alpha v^1 + \beta v^2: \alpha, \beta \in \mathbb{R} \textnormal{ subject to }\alpha (v^1_1 + v^1_2) + \beta v^2_k = 0$$

Since vertices $1$ and $2$ are connected by an even path $T_1$, we have $v^1_1 = v^1_2$, so $v^1_1 + v^1_2 \neq 0$. Thus, the nullspace of $B$ is spanned solely by the vector $v := v^2_k v^1 - (v^1_1 +v^1_2)v^2$. Observe that $v$ has all non-zero entries because the coefficients $v^2_k$ and $v^1_1 + v^1_2$ are non-zero, and vectors $v^1$ and $v^2$ have disjoint support. Thus $B \in \mathcal{S}_{2k - 1, k}$.

$\mathcal{S}_{2k - 1, k} \subseteq \mathcal{T}_k^+$.

Suppose $B \in \mathcal{S}_{2k - 1, k}$. Since $B$ is a minimal dependency, none of its rows have a single $1$. Further, $B$ must have at least $k - 1$ non-zero rows since $B$ must have rank $k - 1$. Hence $B$ has $k-2$ rows with two $1$'s and one row with three $1$s. Without loss of generality, assume $B$'s first row has three $1$'s. Because $B$'s non-zero rows are linearly independent, $B^{/1}$ has rank $k-2$.

We first show that $B^{/1}$ is the edge-vertex incident matrix of a graph $G$ with two disjoint trees. First, we show that $G$ cannot have more than two disjoint components. Suppose it did have three disjoint components $X, Y$, and $Z$, with $X \cup Y \cup Z = [k]$. Then for a set $S \subseteq [k]$ and a vector $v \in \mathbb{R}^k$, let $v_S \in \mathbb{R}^k$ denote the vector with $(v_S)_i = v_i$ for $i \in S$, $(v_S)_i = 0$ otherwise. Thus, $v = v_X + v_Y + v_Z$, and $v_X, v_Y, v_Z$. Now if $Bv = 0$, then $B^{/1}v = 0$, and hence by the disjointness of the components $X, Y, Z$ in $G$, we have $B^{/1}v_X = B^{/1}v_Y = B^{/1}v_Z = 0$. Thus the nullity of $B^{/1}$ is at least $3$, which contradicts the fact that $\rank(B^{/1}) = k-2$. Thus, $G$ has at most two connected components. Because $B^{/1}$ has $k-2$ non-zero rows, $G$ has $k-2$ edges and $k$. So $G$ must be two disjoint trees $T_1$ and $T_2$.

We return to the first row of $B$. Without loss of generality let vertices $[1,\ldots, L]$ correspond to one of the disjoint trees in $G$, and $[L+1,\ldots,k]$ the others, with $1 \leq L \leq k-1$. We want to reason about the locations $a,b,c$ of the three coordinates with $B_{1a} = B_{1a} = B_{1a} = 1$. Applying Lemma <ref> to $B^{/1}_{[L]}$ and $B^{/1}_{[k] \setminus [L]}$, yields two vectors $v^{(\ell)}, v^{r)} \in \mathbb{R}^k$ with $\supp(v^{(\ell)}) = [L]$ and $\supp(v^{(r)}) = [k] \setminus [L]$, and $B^{/1}v^{(\ell)} = B^{/1}v^{(r)} = 0$. We can rule out that all of $a,b,c \in [L]$: Suppose for sake of contradiction this was the case. Then letting $u := v^{(r)}$ satisfies $(B u)_1 = 1 v^{(r)}_a + 1 v^{(r)}_b + 1 v^{(r)}_c = 0 + 0 + 0 = 0$, and $B^{/1} v^{(r)} = 0$, so $Bu = 0$. Then $u$ is a non-zero kernel vector of $B$, which contradicts $B \in \mathcal{S}_{2k - 2, k}$. Similarly, we cannot have all of $a,b,c \in [L+1,\ldots, k]$.

Without loss of generality, assume $a,b \in [1,\ldots,L], c \in [L+1,\ldots,k]$. Suppose for sake of contradiction that $a$ and $b$ are connected by an odd length path in $T_1$. Then $v^{(\ell)}_a = -v^{(\ell)}_b$. It follows that $v^{(\ell)}$ is a kernel vector of $B$, which again contradicts having $B \in \mathcal{S}_{2k - 2, k}$. Thus $a$ and $b$ are connected by an even length path in $T_1$.

$\mathcal{S}_{2k, k}' = \mathcal{T}_k^C$.

We prove this by showing both inclusions in the following two claims.
$\mathcal{T}_k^C \subseteq \mathcal{S}_{2k, k}'$

Suppose $B \in \mathcal{T}_k^C$. Then $B$ has $k$ rows with two $1$'s each. Without loss of generality, assume the first row of $B$ is an edge in the cycle. Then $B^{/1} \in \mathcal{T}_k$, so $B^{/1} \in \mathcal{S}_{2k - 2, k}$ by Lemma <ref>. Hence there is a unique (up to constant multiple) $v$ with $B^{/1} v = 0$, and all non-zero entries. Write the first row of $B$ as $e_x^\top + e_y^\top$, for $1 \leq x < y \leq k$.

We claim that $e_x^\top + e_y^\top$ is in the span of the rows of $B^{/1}$. By definition, the edge $(x,y)$ is part of an even length cycle in the graph with incidence matrix $B$, given by the ordered vertices $x = a_1, a_2, \ldots, a_n = y$ for some even $n$. For $1 \leq i \leq n - 1$, $e_{a_i}^\top + e_{a_{i + 1}}^\top$ is a row of $B^{/1}$. Observe that
$$\sum_{i = 1}^{n - 1}(-1)^{i + 1}(e_{a_i}^\top + e_{a_{i + 1}}^\top) = e_{a_1}^\top + e_{a_{n}}^\top = e_x^\top + e_y^\top.$$

Thus the first row of $B$ is in the row span of $B^{/1}$, so $Bv = 0$. Because $B^{/1}$ has rank $k-1$, so does $B$. So $B \in \mathcal{S}_{2k, k}$. Moreover, $B \in \mathcal{S}_{2k, k}'$ because it has $k$ non-zero columns each with two $1$'s.

$\mathcal{S}_{2k, k}' \subseteq \mathcal{T}_k^C$.

Let $B \in \mathcal{S}_{2k, k}'$. Because $B$ has rank $k-1$, and $k$ non-zero rows, there is a subset of $k-1$ rows of $B$ with rank $k-1$. Without loss of generality, assume the first row of $B$ is in the span of the other rows. Let $v$ be such that $B v = 0$, and $\supp(v). =[k]$. Then clearly $B^{/1} v = 0$. Further because $B^{/1}$ has rank $k-1$, the rank of the nullspace of $B^{/1}$ is $1$. Thus $v$ must be the unique (up to constant multiple) non-zero vector satisfying $B^{/1} v = 0$. So $B^{/1} \in \mathcal{S}_{2k - 2, k} = \mathcal{T}_{k}$. Write the first row of $B$ as $e_x^\top + e_y^\top$ for $1 \leq x < y \leq k$. To show $B \in \mathcal{T}_k^C$, we must show that $x$ and $y$ are connected by an odd length path in the tree with incidence matrix $B^{/1}$. We know that $e_x^\top + e_y^\top$ is in the span of the rows of $B^{/1}$, so we can write
$e_x + e_y = \sum_{i=2}^{m} \alpha_i (e_{a_i} + e_{b_i}),$
where $m$ is the height of $B$, and for each $i$ where $\alpha \neq 0$ and the row $B^{\{i\}}$ is non-zero, we have $B^{\{i\}} = e_{a_i}^\top + e_{b_i}^\top$. Let $S = \{i : \alpha_i \neq 0 \land B^{\{i\}} \neq 0\}$. If some $1 \leq j \leq k$ appears in only one pair in $\{(a_i,b_i)\}_{i \in S}$, it must be the case that $\sum_{i=1}^{m} \alpha_i (e_{a_i} + e_{b_i})$ has non-zero $e_j$ coefficient. So $\{(a_i,b_i)\}_{i \in S}$, is a collection of edges of a tree such that at most two vertices ($x$ and $y$) belong to only one edge. Then $\{(a_i,b_i)\}_{i \in S}$, must be a path, with $x$ and $y$ at the end points. Without loss of generality let $a_2 = x, b_{|S| + 1} = y$ and $a_i = b_{i+1}$ for $2 \leq i \leq |S|$. For $2 \leq i \leq |S|$, because $e_{b_i} \perp e_x + e_y$, we must have that $\alpha_{i+1} = -\alpha_i$ so that the sum will cancel in coordinate $b_i$. It follows that

$$e_x + e_y = \sum_{i=2}^{|S| + 1} (-1)^i \alpha_2 (e_{a_i} + e_{b_i}) = \alpha_2 e_x + (-1)^{|S| + 1} \alpha_2 e_y.$$

It is clear that $|S|$ must be odd. Thus $(x, y)$ fulfills the conditions of the additional edge forming an even cycle in $\mathcal{T}_k^C$. We thus have $B \in \mathcal{T}_k^C$.

§ PROOFS OF LEMMAS <REF> AND <REF> ON BOUNDS OF BINOMIAL DISTRIBUTIONS

We break down this sum as follows.

\begin{equation}\label{masterbreakdown}
\begin{split}
\sum_{\ell \geq 1}^{\infty}&\Pr\left[\Bin\left(\ell, \frac{\ell + k}{\gamma n}\right) \geq \max\left(j, \frac{\ell}{2}\right)\right]\Pr[\Bin(\gamma nk, d/n) = \ell] \\
&\leq  \sum_{\ell = j}^{2j}\Pr\left[\Bin\left(\ell, \frac{\ell + k}{\gamma n}\right) \geq j\right]\Pr[\Bin(\gamma nk, d/n) = \ell]\\
&\qquad + \sum_{\ell \geq 2j + 1}^ {n/3}\Pr\left[\Bin\left(\ell, \frac{\ell + k}{\gamma n}\right) \geq \frac{\ell}{2}\right]\Pr[\Bin(\gamma nk, d/n) = \ell] \\
&\qquad + \sum_{\ell \geq n/3}^{\infty}\Pr\left[\Bin\left(\ell, \frac{\ell + k}{\gamma n}\right) \geq \frac{\ell}{2}\right]\Pr[\Bin(\gamma nk, d/n) = \ell]
\end{split}
\end{equation}

We bound the first term in the following claim.

\begin{equation*}
\sum_{\ell = j}^{2j}\Pr\left[\Bin\left(\ell, \frac{\ell + k}{\gamma n}\right) \geq j\right]\Pr[\Bin(\gamma nk, d/n) = \ell] \leq 8k\left(\frac{20ek}{\gamma n}\right)^j\left(2e\gamma d\right)^{4k}e^{-\gamma dk}.
\end{equation*}

\begin{equation}\label{breakdown1}
\begin{split}
\sum_{\ell = j}^{2j}&\Pr\left[\Bin\left(\ell, \frac{\ell + k}{\gamma n}\right) \geq j\right]\Pr[\Bin(\gamma nk, d/n) = \ell] \\
&\leq 2j\Pr\left[\Bin\left(2j, \frac{2j + k}{\gamma n}\right) \geq j\right]\Pr[\Bin(\gamma nk, d/n) \leq 2j] \\
& \leq 4j\left(\frac{e2j(2j + k)}{\gamma nj}\right)^j\Pr[\Bin(\gamma nk, d/n) \leq 2j]
\leq 8k\left(\frac{20ek}{\gamma n}\right)^j\Pr[\Bin(\gamma nk, d/n) \leq 2j].
\end{split}
\end{equation}

Here the first inequality follows from the fact that the summand is highest for $\ell = 2j$, the second inequality follows from the tail bound in Lemma <ref>, and the third inequality follows from the fact that $j \leq k + 1 \leq 2k$. Now

\begin{equation*}
\begin{split}
\Pr[\Bin(\gamma  nk, d/n) \leq 2j] &\leq \Pr[\Bin(\gamma  nk, d/n) \leq 2j]
\leq \binom{\gamma  nk}{2j}\left(\frac{d}{n}\right)^{2j}\left(1 - \frac{d}{n}\right)^{\gamma  nk - 2j} \\
&\leq \left(\frac{e\gamma  nk}{2j}\right)^{2j}\left(\frac{d}{n - d}\right)^{2j}\left(1 - \frac{d}{n}\right)^{\gamma nk}
\leq \left(\frac{e\gamma dk}{j}\right)^{2j}e^{-\gamma dk}
\leq \left(2e\gamma d\right)^{4k}e^{-\gamma dk}.
\end{split}
\end{equation*}

Combining this with eq. <ref> yields the claim.

We bound the second term in eq. <ref> in the following claim.

\begin{equation*}
\sum_{\ell \geq 2j + 1}^ {n/3}\Pr\left[\Bin\left(\ell, \frac{\ell + k}{\gamma n}\right) \geq \frac{\ell}{2}\right]\Pr[\Bin(\gamma nk, d/n) = \ell] \leq 4e^{-\gamma dk}\left(\frac{8e^3\gamma d^2k}{n}\right)^{j + 1}.
\end{equation*}

For $\ell \leq n/3$, using Lemma <ref> and Sterling's forumla, we have

\begin{equation}\label{eq:med}
\begin{split}
\Pr&\left[\Bin\left(\ell, \frac{\ell + k}{\gamma n}\right) \geq \frac{\ell}{2}\right]\Pr[\Bin(\gamma nk, d/n) = \ell]\\
&\leq 2\left(\frac{e\ell(\ell + k)}{\gamma n\frac{\ell}{2}}\right)^{\lceil{\ell/2}\rceil}\Pr[\Bin(\gamma nk, d/n) = \ell]
= 2\left(\frac{2e(\ell + k)}{\gamma n}\right)^{\lceil{\ell/2}\rceil}\Pr[\Bin(\gamma nk, d/n) = \ell] \\
% &= 2\left(\frac{2e(\ell + k)}{\gamma n}\right)^{\lceil{\ell/2}\rceil}\binom{\gamma nk}{\ell}\left(\frac{d}{n}\right)^\ell\left(1 - \frac{d}{n}\right)^{\gamma nk - \ell}
&\leq 2\left(\frac{2e(\ell + k)}{\gamma n}\right)^{\lceil{\ell/2}\rceil}\left(\frac{e\gamma nk}{\ell}\right)^{\ell}\left(\frac{d}{n - d}\right)^\ell\left(1 - \frac{d}{n}\right)^{\gamma nk}
% &\leq 2\left(\frac{2e(\ell + k)}{\gamma n}\right)^{\lceil{\ell/2}\rceil}\left(\frac{e\gamma nk}{\ell}\right)^{\ell}\left(\frac{d}{n - d}\right)^\ell e^{-\gamma dk}
\leq 2\left(\frac{4e\ell}{\gamma n}\right)^{\lceil{\ell/2}\rceil}\left(\frac{2e\gamma dk}{\ell}\right)^{\ell} e^{-\gamma dk}.
\end{split}
\end{equation}

We do casework on the parity of $\ell$.
Let $\ell = 2a + b$, where $b \in \{0, 1\}$. If $b = 1$, then

\begin{equation*}
\begin{split}
\left(\frac{4e\ell}{\gamma n}\right)^{\lceil{\ell/2}\rceil}\left(\frac{2e\gamma dk}{\ell}\right)^{\ell} &= \left(\frac{4e(2a+1)}{\gamma n}\right)^{a + 1}\left(\frac{2e\gamma dk}{2a + 1}\right)^{2a + 1} \\
&= \left(\frac{16e^3\gamma ^2d^2k^2(2a+1)}{\gamma n(2a + 1)^2}\right)^a\left(\frac{8e^2\gamma dk(2a+1)}{\gamma n(2a + 1)}\right) \\
&\leq \left(\frac{8e^3\gamma d^2k^2}{na}\right)^a\left(\frac{8e^2dk}{n}\right).
\end{split}
\end{equation*}

Now since the maximum over $x$ of $f(x) = \left(\frac{y}{x}\right)^x$ is achieved at $x = y/e$, and above this value of $x$, the $f(x)$ is decreasing, since $j \geq k - 1 \geq \frac{e8e^3\gamma d^2k^2}{n}$, we have for all $a \geq j$,

\begin{equation*}
\begin{split}
\left(\frac{8e^3\gamma d^2k^2}{na}\right)^a\left(\frac{8e^2dk}{n}\right) &\leq
\left(\frac{8e^3\gamma d^2k^2}{nj}\right)^a\left(\frac{8e^2dk}{n}\right)
\leq \left(\frac{8e^3\gamma d^2k^2}{n(k - 1)}\right)^a\left(\frac{8e^2dk}{n}\right)
\leq \left(\frac{8e^3\gamma d^2k}{n}\right)^{a + 1}.
\end{split}
\end{equation*}

If $b = 0$, then

\begin{equation*}
\left(\frac{4e\ell}{\gamma n}\right)^{\lceil{\ell/2}\rceil}\left(\frac{2e\gamma dk}{\ell}\right)^{\ell} = \left(\frac{8ea}{\gamma n}\right)^{a}\left(\frac{2e\gamma dk}{2a}\right)^{2a}
= \left(\frac{8e^3\gamma d^2k^2}{na}\right)^a.
\end{equation*}

By the same reasoning as before, we have for all $a \geq j + 1$,

\begin{equation*}
\left(\frac{8e^3\gamma d^2k^2}{na}\right)^a \leq \left(\frac{8e^3\gamma d^2k^2}{n(j + 1)}\right)^{a} \leq \left(\frac{8e^3\gamma d^2k}{n}\right)^{a}.
\end{equation*}

Combining these two cases back into eq. <ref>, we have for all $\ell \geq 2j + 1$,

\begin{equation*}
\Pr\left[\Bin\left(\ell, \frac{\ell + k}{\gamma n}\right) \geq \frac{\ell}{2}\right]\Pr[\Bin(\gamma nk, d/n) = \ell] \leq 2e^{-\gamma dk}\left(\frac{8e^3\gamma d^2k}{n}\right)^{\lceil{\frac{\ell}{2}}\rceil}.
\end{equation*}

Summing over all $\ell \geq 2j + 1$, we have

\begin{equation*}
\sum_{\ell \geq 2j + 1}^ {n/3}\Pr\left[\Bin\left(\ell, \frac{\ell + k}{\gamma n}\right) \geq \frac{\ell}{2}\right]\Pr[\Bin(\gamma nk, d/n) = \ell] \leq 4e^{-\gamma dk}\left(\frac{8e^3\gamma d^2k}{n}\right)^{j + 1}.
\end{equation*}

Finally, we bound the third term in eq. <ref> in the following claim.

\begin{equation*}
\sum_{\ell \geq n/3}^{\infty}\Pr\left[\Bin\left(\ell, \frac{\ell + k}{\gamma n}\right) \geq \frac{\ell}{2}\right]\Pr[\Bin(\gamma nk, d/n) = \ell] \leq  2\left(\frac{3e\gamma dk}{n}\right)^{n/3}.
\end{equation*}

It suffices to bound the probability $\Pr[\Bin(\gamma nk, d/n) \geq n/3]$. Using Lemma <ref>, we have

\begin{equation*}
\Pr[\Bin(\gamma nk, d/n) \geq n/3] \leq 2\left(\frac{3e\gamma dk}{n}\right)^{n/3}.
\end{equation*}

Combining claims <ref>, <ref> and <ref>, we have

\begin{equation*}
\begin{split}
\sum_{\ell \geq 1}^{\infty}&\Pr\left[\Bin\left(\ell, \frac{\ell + k}{\gamma n}\right) \geq \max\left(j, \frac{\ell}{2}\right)\right]\Pr[\Bin(\gamma nk, d/n) = \ell] \\
&\leq 8k\left(\frac{20ek}{\gamma n}\right)^j\left(2e\gamma d\right)^{4k}e^{-\gamma dk}
+ 4e^{-\gamma dk}\left(\frac{8e^3\gamma d^2k}{n}\right)^{j + 1}
+ 2\left(\frac{3e\gamma dk}{n}\right)^{n/3}.
\end{split}
\end{equation*}

One can check that this sum is dominated by the first term, so for a universal constant $c_{\ref{masterlemma:small}}$,

\begin{equation*}
\begin{split}
\sum_{\ell \geq 1}^{\infty}&\Pr\left[\Bin\left(\ell, \frac{\ell + k}{\gamma n}\right) \geq \max\left(j, \frac{\ell}{2}\right)\right]\Pr[\Bin(\gamma nk, d/n) = \ell] \\
&\leq 16k\left(\frac{20ek}{\gamma n}\right)^j\left(2e\gamma d\right)^{4k}e^{-\gamma dk}
\leq \left(\frac{k}{n}\right)^je^{-\gamma dk + c_{\ref{masterlemma:small}}k\log(\gamma d)}.
\end{split}
\end{equation*}

Because $n/2 < n-k-1$, we may bound the probability by:

\begin{equation*}
\begin{split}
\Pr\left[\Bin\left(n - k - 1, 1 - \frac{1}{\sqrt{kd/n}}
\right) < k\right] &\leq \Pr\left[\Bin\left(\frac{n}{2}, 1 - \frac{1}{\sqrt{kd/n}}\right) < k\right].
\end{split}
\end{equation*}

We use the Chernoff bound $\Pr[X \leq (1 - \delta)\mu] \leq e^{-\mu \delta^2/2}$ for $\mu = \mathbb{E}[X]$, plugging in $\mu = \frac{n}{2}\left(1 - \frac{1}{\sqrt{kd/n}}\right)$ and $\delta = (1 - \frac{1}{\sqrt{kd/n}})^{-1} \left(1 - \frac{1}{\sqrt{kd/n}} - \frac{2k}{n}\right)$. This gives

\begin{equation*}
\begin{split}
\Pr\left[\Bin\left(n - k - 1, 1 - \frac{1}{\sqrt{kd/n}}\right) < k\right] &\leq \Pr\left[\Bin\left(\frac{n}{2}, 1 - \frac{1}{\sqrt{kd/n}}\right) < k\right]\\
&\leq e^{-\frac{n}{2}\left(1 - \frac{1}{\sqrt{kd/n}}\right)\left(1 - \frac{1}{\sqrt{kd/n}} - \frac{2k}{n}\right)^2}
\leq  e^{-n\epsilon},
\end{split}
\end{equation*}

where $\epsilon \geq 1/36$. To achieve this value of $\epsilon$, we plugged in  $k < \frac{n}{12}$ in the last inequality.

Now we compute the sum over $k$:

\begin{equation*}
\sum_{k = \frac{2n}{d}}^{\frac{n}{C}}\binom{n}{k}e^{-\epsilon n} \leq n \binom{n}{n/C} e^{-\epsilon n} \leq n (eC)^{n/C} e^{-\epsilon n} = e^{n(\frac{\log n}{n} + \frac{1 + \log C}{C} - \epsilon)},
\end{equation*}

which for constant $C$ large enough, is $e^{-\Theta(n)}$.

§ PROOF OF LEMMAS FOR $3$-CORE

We prove Lemma <ref>, which we restate here.

The lemma will follow immediately from the following two lemmas:

For any $2 \leq k \leq n$ and $\ell \leq \frac{1}{4}n^{\epsilon}k^{1 - \epsilon}$,

\begin{equation*}
\Pr\left[\Bin\left(\ell, \frac{k + \ell}{n}\right) \geq Q\right] \leq 2\left(\frac{k}{3n}\right)^{k + \frac{1}{3}},
\end{equation*}

where $\epsilon = \frac{1}{12}$ and $Q = \ceil*{\frac{3k-1}{2}}$.

For any $d$ larger than some constant, for any $2 \leq k \leq \frac{n}{d^7}$ and $\ell \leq 3dk$, with $Q = \ceil*{\frac{3k-1}{2}}$,

\begin{equation*}
\Pr\left[\Bin\left(\ell, \frac{k + \ell}{n}\right) \geq Q\right] \leq 2\left(\frac{k}{3n}\right)^{k + \frac{1}{3}}.
\end{equation*}

We will use Lemma <ref> to bound the binomial. We first check that the hypothesis of the lemma is satisfied, namely that $2\ell \frac{k + \ell}{n} \leq Q$ for $\ell \leq \frac{1}{4}n^{\epsilon}k^{1 - \epsilon}$ and $\ell \geq Q \geq k$:

\begin{equation}\label{eq:eps_1}
\begin{split}
\frac{\ell(\ell + k)}{nQ} & \leq \frac{2\ell^2}{nQ}
\leq \frac{2\left(\frac{1}{4}n^{\epsilon}k^{1 - \epsilon}\right)^2}{kn}
=  \frac{1}{8}\left(\frac{k}{n}\right)^{1 - 2\epsilon}.
\end{split}
\end{equation}

Since $k \leq n$, this value in eq.<ref> at most $\frac{1}{2}$. Hence the conditions of Lemma <ref> are satisfied, so

\begin{equation*}
\begin{split}
\Pr\left[\Bin\left(\ell, \frac{k + \ell}{n}\right) \geq Q\right] \leq 2\left(\frac{e\ell (k + \ell)}{Q n}\right)^Q.
\end{split}
\end{equation*}

Plugging in $Q = \ceil*{\frac{3k - 1}{2}}$ and $k \geq 2$, we can bound

\begin{equation*}
\begin{split}
\Pr\left[\Bin\left(\ell, \frac{k + \ell}{n}\right) \geq Q\right]  &\leq 2\left(\frac{e\ell(k + \ell)}{Q n}\right)^{\lceil{\frac{3k - 1}{2}}\rceil}
\leq  2\left(\frac{e}{8}\left(\frac{k}{n}\right)^{1 - 2\epsilon}\right)^{\lceil{\frac{3k - 1}{2}}\rceil}\\
&\leq 2\left(\left(\frac{k}{3n}\right)^{1 - 2\epsilon}\right)^{\lceil{\frac{3k - 1}{2}}\rceil}
\leq 2\left(\frac{k}{3n}\right)^{k + \frac{1}{3}}.
\end{split}
\end{equation*}

Here the second inequality plugs in the result of eq.<ref>, the third inequality uses the fact that $\left(\frac{e}{8}\right)^{6/5} \leq 1/3$, and the final inequality uses the fact that $(1 - 2\epsilon)\lceil{\frac{3k - 1}{2}}\rceil = \frac{5}{6}\lceil{\frac{3k - 1}{2}}\rceil \geq k + \frac{1}{3}$ for integers $k \geq 2$. This proves the lemma.

We will use Lemma <ref> to bound the binomial. We first check that the hypothesis of the lemma is satisfied, namely that $2\ell \frac{k + \ell}{n} \leq Q$ for $\ell \leq 3dk$ and $\ell \geq Q \geq k$:

\begin{equation}\label{eq:eps_2}
\frac{\ell(\ell + k)}{nQ} \leq \frac{3d(3d+1)k^2}{kn} = \frac{3d(3d+1)k}{n} \leq \frac{10d^2k}{n}.
\end{equation}

Since we have $k \leq \frac{n}{d^7}$, if $d$ is larger than some constant, the value in eq.<ref> at most $\frac{1}{2}$. Hence the conditions of Lemma <ref> are satisfied, so

\begin{equation*}
\begin{split}
\Pr\left[\Bin\left(\ell, \frac{k + \ell}{n}\right) \geq Q\right] \leq 2\left(\frac{e\ell (k + \ell)}{Q n}\right)^Q.
\end{split}
\end{equation*}

Plugging in $Q = \ceil*{\frac{3k - 1}{2}}$ and using the fact that
$$\ceil*{\frac{3k - 1}{2}} = k + \floor*{\frac{k}{2}} = 3\floor*{\frac{k}{2}} + \mathbf{1}_{k  \text{ odd}},$$
for any positive integer $k$,

\begin{equation}\label{eq:jenson}
\begin{split}
\Pr\left[\Bin\left(\ell, \frac{k + \ell}{n}\right) \geq Q\right]  &\leq 2\left(\frac{e\ell(k + \ell)}{Q n}\right)^{\lceil{\frac{3k - 1}{2}}\rceil}
\leq  2\left(\frac{10ed^2k}{n}\right)^{\ceil*{\frac{3k - 1}{2}}}\\
&= 2\left(\frac{k}{3n}\right)^{k + \frac{1}{3}}\left(\frac{k}{3n}\right)^{\lfloor{\frac{k}{2}}\rfloor - \frac{1}{3}}\left(\frac{30ed^2}{1}\right)^{\lceil{\frac{3k - 1}{2}}\rceil}\\
&= 2\left(\frac{k}{3n}\right)^{k + \frac{1}{3}}\left(\frac{k(30ed^2)^3}{3n}\right)^{\lfloor{\frac{k}{2}}\rfloor - \frac{1}{3}}\left(\frac{30ed^2}{1}\right)^{1 + \mathbf{1}_{k  \text{ odd}}}.
\end{split}
\end{equation}

Note that the function
$$\left(\frac{k(30ed^2)^3}{3n}\right)^{\lfloor{\frac{k}{2}}\rfloor - \frac{1}{3}}\left(\frac{30ed^2}{1}\right)^{1 + \mathbf{1}_{k  \text{ odd}}} $$

is convex in $k$ (when the parity of $k$ is fixed), so its maximum is achieved at either the minimum or maximum value of $k$, up to parity.

It is easy to check by plugging in the minimum and maximum odd and even values of $k$ for $2 \leq k \leq \frac{n}{d^7}$, that since $\frac{n}{d^7} < \frac{3n}{2(30ed^2)^3}$ for $d$ and $n$ large enough, we have

\begin{equation*}
\left(\frac{k(30ed^2)^3}{3n}\right)^{\lfloor{\frac{k}{2}}\rfloor - \frac{1}{3}}\left(\frac{30ed^2}{1}\right)^{1 + \mathbf{1}_{k  \text{ odd}}} < 1.
\end{equation*}

Plugging this in to eq.<ref>, we have

\begin{equation}
\Pr\left[\Bin\left(\ell, \frac{k + \ell}{n}\right) \geq Q\right] \leq 2\left(\frac{k}{3n}\right)^{k + \frac{1}{3}}.
\end{equation}

Next we prove the following lemma, which we restate here.

By Lemma <ref>,

\begin{equation*}
\begin{split}
\Pr\left[\Bin\left(kn, \frac{d}{n}\right) \geq L_{max}\right] \leq 2\left(\frac{dke}{L_{max}}\right)^{L_{max}},
\end{split}
\end{equation*}

Let $\gamma := \log_n(n/k)$ such that $L_{max} = k\max\left(\frac{n^{\gamma\epsilon}}{4}, 3d\right)$. Then

\begin{equation}\label{R_max_bd}
\begin{split}
\Pr\left[\Bin\left(kn, \frac{d}{n}\right) \geq L_{max}\right] &\leq 2\left(\frac{de}{\max\left(\frac{n^{\gamma\epsilon}}{4}, 3d\right)}\right)^{k\max\left(\frac{n^{\gamma\epsilon}}{4}, 3d\right)} \\
&= 2\left(\frac{k}{en}\right)^k\left(\left(\frac{de}{\max\left(\frac{n^{\gamma\epsilon}}{4}, 3d\right)}\right)^{\max\left(\frac{n^{\gamma\epsilon}}{4}, 3d\right)}\frac{ne}{k}\right)^k \\
&= 2\left(\frac{k}{en}\right)^k\left(\left(\frac{de}{\max\left(\frac{n^{\gamma\epsilon}}{4}, 3d\right)}\right)^{\max\left(\frac{n^{\gamma\epsilon}}{4}, 3d\right)}n^{\gamma}e\right)^{n^{1 - \gamma}}. \\
\end{split}
\end{equation}

If $n^{\gamma\epsilon} < (4de)^2$, then

\begin{equation}\label{case:small_r}
\begin{split}
\left(\left(\frac{de}{\max\left(\frac{n^{\gamma\epsilon}}{e}, 3d\right)}\right)^{\max\left(\frac{n^{\gamma\epsilon}}{e}, 3d\right)}n^\gamma e\right)^{n^{1 - \gamma}} &\leq \left(\left(\frac{e}{3}\right)^{3d}e(4de)^{2/\epsilon}\right)^{n^{1-\gamma}} \\
&= e^{n^{1-\gamma}\left(3d\log(\frac{e}{3}) + \frac{4}{\epsilon}\log(4de) + 1\right)}
\leq e^{n^{1-\gamma}}
\leq e^{-n^{1/2}},
\end{split}
\end{equation}

where the second to last inequality follows from taking $d$ large enough, and the final inequality from the fact that by assumption, $\gamma \leq \frac{2\log(4ed)}{\epsilon\log(n)} \leq \frac{1}{2}$ for large enough $n$.

If $n^{\gamma\epsilon} \geq (4de)^2$,

\begin{equation*}
\begin{split}
\left(\left(\frac{de}{\max\left(\frac{n^{\gamma\epsilon}}{4}, 3d\right)}\right)^{\max\left(\frac{n^{\gamma\epsilon}}{4}, 3d\right)}n^\gamma e\right)^{n^{1 - \gamma}} &=  \left(\left(\frac{de}{\frac{n^{\gamma\epsilon}}{4}}\right)^{\frac{n^{\gamma\epsilon}}{4}}n^\gamma e\right)^{n^{1 - \gamma}}
=  \left(\left(\frac{4de}{n^{\gamma\epsilon}}\right)^{\frac{n^{\gamma\epsilon}}{4}}n^{2\gamma}\right)^{n^{1 - \gamma}} \\
&\leq \left(\left(\frac{1}{n^{\gamma\epsilon}}\right)^{\frac{n^{\gamma\epsilon}}{8}}n^{2\gamma}\right)^{n^{1 - \gamma}}.
\end{split}
\end{equation*}

Taking a logarithm, we have

\begin{equation*}
\begin{split}
\log\left(\left(\frac{1}{n^{\gamma\epsilon}}\right)^{\frac{n^{\gamma\epsilon}}{8}}n^{2\gamma}\right)^{n^{1 - \gamma}} &= n^{1-\gamma}\left(2\gamma\log(n) -\frac{\gamma\epsilon}{8} n^{\gamma\epsilon}\log(n)\right)\\
&= n^{1-\gamma}\gamma\log(n)\left(2 - \frac{\epsilon n^{\gamma\epsilon}}{8}\right)
\leq -2n^{1-\gamma}\gamma\log(n),
\end{split}
\end{equation*}

where in the inequality, we used $n^{\gamma\epsilon} > (4ed)^2$ to show $\frac{\epsilon n^{\gamma\epsilon}}{8} \geq \frac{\epsilon(4de^2)^{2}}{8} \geq 4$ for $d$ large enough. Now  $n^{\gamma\epsilon} > (4de)^2$ implies $\gamma > \frac{2\log(4de)}{\epsilon\log(n)}$. The function $n^{1-\gamma}\gamma$ achieves its minimum at one endpoint of the interval $\gamma \in [\frac{2\log(4de)}{\epsilon\log(n)}, 1]$ (one can verify that the log of the function is concave in $\gamma$). Thus

\begin{equation*}
-2n^{1-\gamma}\gamma\log(n) \leq \max\left(-2n^{1- \frac{2\log(4de)}{\epsilon\log(n)}}\frac{2\log(4de)}{\epsilon}, -2\log(n)\right) \leq -2\log(n),
\end{equation*}

so if $n^{\gamma\epsilon} \geq (4de)^2$, we have

\begin{equation}\label{case:big_r}
\left(\left(\frac{de}{\max\left(\frac{n^{\gamma\epsilon}}{4}, 3d\right)}\right)^{\max\left(\frac{n^{\gamma\epsilon}}{4}, 3d\right)}n^\gamma e\right)^{n^{1 - \gamma}} \leq e^{-2\log(n)}.
\end{equation}

Combining the two cases (eqs. <ref> and <ref>) into eq. <ref>, we have

\begin{equation*}
\Pr\left[\Bin\left(kn, \frac{d}{n}\right) \geq L_{max}\right] \leq 2\left(\frac{k}{en}\right)^ke^{-2\log(n)}.
\end{equation*}

§ GRADIENT CODING

In the following Appendix, we prove the claims stated in the proof of Lemma $\ref{lemma:abc_small}$. First, we need the approximation for the probability mass function of a HyperGeometric distribution.

Let $\mathcal{X}\sim \text{HyperGeom}(A,B,n)$. Furthermore, let us define $(1-q)=\frac{B}{A}$. Then

Furthermore, assuming $n\leq \frac{3}{2}qA$ and $q\leq 1/2$, we have:

\begin{equation*}
\begin{split}
\Pr[\mathcal{X}=k]&\leq \binom{n}{k}(1-q)^k q^{n-k}\left(e^{\left({{6ek}}\right)}\right)
\leq \left(\frac{en}{k}\right)^k(1-q)^k q^{n-k}\left(e^{\left({{6ek}}\right)}\right)
\end{split}
\end{equation*}

Recall that, by definition of the hypergeometric distribution, we have:

$$\Pr[\mathcal{X}=k]=\frac{\binom{B}{k}\binom{A - B}{n-k}}{\binom{A}{n}}$$

We can expand out the binomial terms into their factorial representations to see:

\begin{align*}
\Pr[\mathcal{X}=k]&=\frac{\frac{B!}{(B-k)!k!}\cdot\frac{(A - B)!}{(A - B-n+k)!(n-k)!}}{\frac{A!}{(A-n)!n!}}\\
&=\binom{n}{k} \prod_{i=1}^{k}(B-k+i)\prod_{i=1}^{n-k}(A-B-n+k+i)\prod_{i=1}^n \frac{1}{A-n+i}\\
&=\binom{n}{k} \prod_{i=1}^{k}\frac{B-k+i}{A-k+i}\prod_{i=1}^{n-k}\frac{A-B-n+k+i}{A-n+i}\\
&=\binom{n}{k} \prod_{i=1}^{k}\frac{B-k+i}{A-k+i}\prod_{i=1}^{n-k}\left(1-\frac{B}{A-n+i}+\frac{k}{A-n+i}\right)   \\
&\leq \binom{n}{k} \prod_{i=1}^{k}\frac{B-k+i}{A-k+i}\prod_{i=1}^{n-k}\left(1-\frac{B}{A}+\frac{k}{A-n}\right).
\end{align*}

By definition of the hypergeometric distribution, $k\leq B$. Thus, $k-i<B<A$ for all $i\in[k]$, so:

$$\frac{B-k+i}{A-k+i}\leq \frac{B}{A}=(1-q).$$

This gives us the first inequality of the lemma:

$$P[\mathcal{X}=k]\leq \binom{n}{k}\prod_{i=1}^k (1-q). \prod_{i=1}^{n-k} \left(q+\frac{k}{A-n}\right)=\binom{n}{k} (1-q)^k \left(q+\frac{k}{A-n}\right)^{n-k}.$$

We will now proceed under the assumption that $n\leq \frac{3}{2}qA$ to achieve the second bound. We write:

\begin{align*}
\left(q+\frac{k}{A-n}\right)^{n-k}&\leq \left(q+\frac{k}{(1-\frac{3}{2}q)A}\right)^{n-k}
=\sum_{i=0}^{n-k} \binom{n-k}{i}q^{n-k-i}\left(\frac{k}{(1-\frac{3}{2}q)A}\right)^{i}\\
&\leq q^{n-k}\sum_{i=0}^{n-k} \left(\frac{\frac{3}{2}eqA}{i}\right)^i\left(\frac{1}{q}\right)^i\left(\frac{k}{(1-\frac{3}{2}q)A}\right)^{i}
\leq q^{n-k}\sum_{i=0}^{n-k}\left(\frac{\frac{3}{2}ek}{i(1-\frac{3}{2}q)}\right)^{i}\\
&\leq q^{n-k}\sum_{i=0}^{n-k} \left(\frac{1}{i!}\right)\left(\frac{\frac{3}{2}ek}{1-\frac{3}{2}q}\right)^{i}
\leq q^{n-k}\left(e^{\left(\frac{\frac{3}{2}ek}{1-\frac{3}{2}q}\right)}\right)
\leq q^{n-k}\left(e^{\left({6ek}\right)}\right).
\end{align*}

Applying this to the first inequality gives:

We are now ready to prove Claim <ref>.

Since $2\ell\left(\frac{2\ell}{N} \right) \leq \frac{4qK\ell}{N} \leq
\frac{4q\ell}{18eq^2} \leq \frac{\ell}{2}$ for $q$ large enough, by Lemma <ref>, we have

\begin{equation}\label{eq:tail_app}
\begin{split}
\Pr\left[\Bin\left(\ell, \frac{2\ell}{n}\right)\geq j\right] \leq 2\left(\frac{4e\ell}{n}\right)^{j}.
\end{split}
\end{equation}

Using $K\leq \frac{3}{2}N$, we employ the second bound of Lemma <ref> to find that for sufficiently large $q$,

\begin{align*}
\Pr&\left[\Bin\left(\ell, \frac{2\ell}{N}\right)\geq j\right]\cdot \Pr[\textnormal{HyperGeom}(qN,q(1-p)N,qK)=\ell]\\
&\leq 2\left(\frac{4e\ell}{N}\right)^{j}\left(\binom{qK}{\ell}(1-p)^{\ell}p^{qK-\ell}e^{6e\ell}\right)
\leq 2\left(\frac{8eK}{N}\right)^{j}\binom{qK}{2K}p^{qK-2K}e^{12eK} \\
&\leq 2\left(8e\right)^{2K}\left(\frac{K}{ N}\right)^{j}\left(\frac{eq}{2}\right)^{2K}p^{(q-2)K}e^{12eK}
= 2\left(16e^{12e+4}q^2\right)^{K} \left(\frac{K}{N}\right)^{j} p^{(q-2)K}
\leq\left(p^{q-c\log_p(q)} \right)^K\left(\frac{K}{N}\right)^{j}.
\end{align*}

for some universal constant $c$.

For the second statement, we combine eq. <ref> and the second bound of Lemma <ref>, achieving

\begin{align*}
&\sum_{\ell=2K+1}^{qK}\Pr\left[\Bin\left(\ell, 1-\frac{2\ell}{N}\right)\geq \frac{\ell}{2}\right]\cdot\Pr[\textnormal{HyperGeom}(qN,q(1-p)N,qK)=\ell]\\
&\leq \sum_{\ell=2K+1}^{qK}2\left(\frac{4e\ell}{N}\right)^{\frac{\ell}{2}}\left(\binom{qK}{\ell}(1-p)^K\left(p+\frac{\ell}{q(N-K)}\right)^{qK-\ell}\right)\\
&\leq \sum_{\ell=2K+1}^{qK}2\left(\frac{4e\ell}{N}\right)^{\frac{\ell}{2}}\left(\frac{1}{2}+\frac{K}{(N-K)}\right)^{qK - \ell} \left(\frac{eqK}{\ell}\right)^\ell\\
&\leq \sum_{\ell=2K+1}^{qK}2\left(\frac{4e\ell}{N}\right)^{\frac{\ell}{2}}\left(0.625\right)^{qK - \ell} \left(\frac{eqK}{\ell}\right)^\ell\\
&\leq 2(0.625)^{qK} \sum_{\ell=2K+1}^{qK}\left(\frac{4e^{3}q^2K^2}{\ell N}\right)^{\ell/2}\\
&\leq 2qK(0.625)^{qK}\max_{\ell\in\{2K+1,...,qK\}}\left(\frac{4e^{3}q^2K^2}{\ell N}\right)^{\ell/2}.
\end{align*}

To show the function in the expression above is maximized at $\ell = 2K+1$ when $K\leq \frac{N}{18eq^2}$, note that the maximum over $x$ of $f(x) = \left(\frac{y}{x}\right)^x$ is achieved at $x = y/e$, and above this value of $x$, $f(x)$ is decreasing. Let $C=\frac{4e^{3}q^2K^2}{N}$, and consider the function $f(x) = \left(\frac{C/2}{x}\right)^x$, such that $f(\ell/2) = \left(\frac{4e^{3}q^2K^2}{\ell N}\right)^{\ell/2}$. Thus $f$ is decreasing for $\ell/2 \geq \frac{C}{e} = \frac{4e^{2}q^2K^2}{N}$. Observe that $\frac{8e^2q^2K^2}{N} \leq 2K$, since $K \leq \frac{N}{18eq^2} \leq \frac{N}{4e^2q^2}$, and so $\max_{\ell\in\{2K+1,...,qK\}}\left(\frac{4e^{3}q^2K^2}{\ell N}\right)^{\ell/2} \leq \left(\frac{4e^{3}q^2K^2}{(2K + 1)N}\right)^{(2K + 1)/2}$. It follows that

\begin{align*}
\sum_{\ell=2K+1}^{qK}&\Pr\left[\Bin\left(\ell, 1-\frac{2\ell}{N}\right)\geq \frac{\ell}{2}\right]\cdot\Pr[\textnormal{HyperGeom}(qN,q(1-p)N,qK)=\ell]\\
&\leq 2qK(0.625)^{qK}\left(\frac{4e^3q^2K^2}{(2K+1)N}\right)^{K+1/2}
\leq 2qK(0.625)^{qK}(2e^3q^2)^{K+1/2}\left(\frac{K}{N}\right)^{K+1/2}\\
&\leq e^{-K}\left(\frac{K}{N}\right)^{K+1/2}.
\end{align*}