WorksMathematics
Shotgun Assembly of the Non-Uniform Labeled Lattice Model
Abstract
In this paper, we study the graph shotgun assembly problem in the labeled lattice model, as introduced by Mossel and Ross (2019). We start with a -dimensional lattice of length , where the color of each vertex is sampled i.i.d. from a distribution . Then, we ask whether it is possible to reconstruct the coloring of the lattice given the coloring of each subgrid of length . While previous work by Ding and Liu (2023) and Demidovich, Panichkin, and Zhukovskii (2023) identified the reconstruction threshold when is uniform, we examine the non-uniform case. This paper establishes a sufficient condition for the impossibility of reconstruction for using information-theoretic arguments. Our negative result matches the known threshold in the uniform case.
Introduction
The graph shotgun assembly problem aims to infer a graph when given collections of local neighborhoods of the graph. One motivating application is the reconstruction of neural connections in neuroscience: given sub-networks of neurons collected from experiments, the goal is to reconstruct the entire neural network of the brain [19]. The term shotgun assembly is inspired by the problem of DNA shotgun assembly, in which an entire DNA sequence is reconstructed from fragments of DNA subsequences that overlap each other. In this setting, we have a long 1-dimensional lattice of nodes, each labeled with one of four values (adenine, cytosine, guanine, or thymine), and we would like to recover the label of each node based on observations of smaller, overlapping fragments.
The labeled lattice model, proposed by Mossel and Ross [15], generalizes DNA shotgun assembly for any arbitrary dimension and number of labels. Let be the probability mass function of a discrete distribution on values. Then, the labeled lattice model is defined as the -dimensional lattice of length , denoted , with i.i.d. vertex labels (also called colors) from a fixed . For the rest of this paper, we will use “lattice” to refer to the labeled lattice model.
The shotgun assembly problem on the labeled lattice model asks when it is possible to recover the coloring of the whole lattice, given that we can observe the coloring of small subgrids (but not their location within the lattice). To formalize this, we define a -card of the lattice as a subgrid of length where the coloring and orientation are observed, but the location is not. Then, we define the -deck of the lattice as the collection of all -cards. Note that each -card has vertices, and that the -deck contains total cards. Then, we call a lattice identifiable from its -deck if no other lattice shares the same -deck, and non-identifiable otherwise. The shotgun assembly problem aims to 1) determine the values of for which the lattice is identifiable and non-identifiable, and 2) if the lattice is identifiable, find an efficient algorithm to recover the lattice coloring from the -deck.
Prior work has largely focused on the case where is a uniform discrete distribution. The threshold for was found by Dyer, Frieze, and Suen [8], who showed that as , the lattice is identifiable with a constant nontrivial probability if where is a constant. Consequently, the lattice coloring is identifiable with high probability when while it is non-identifiable with high probability when .
The threshold for was first found by Ding and Liu [7], who showed that if , then the lattice is identifiable with high probability, while if , the lattice is non-identifiable with high probability. We note that Ding and Liu also developed an efficient algorithm to recover the lattice coloring above the threshold. Later, Narayanan and Yap [16] improved the threshold to two-point concentration in the case where and using an alternative algorithm, which was later generalized to all and by Demidovich, Panichkin, and Zhukovskii [5]. The latter showed that if , then the lattice is identifiable with high probability, while if , then the lattice is non-identifiable with high probability. Thus, the threshold for identifiability is well-understood in the uniform case.
Moving to the case where is non-uniform, the threshold for was also identified by Dyer, Frieze, and Suen [8]; the authors showed that as , the lattice can be recovered with a constant nontrivial probability when where and is a constant. Thus, the lattice coloring is identifiable with high probability when , and non-identifiable with high probability when .
However, much less is known for since the analysis becomes substantially more difficult. Mossel and Ross [15] identified a sufficient condition for identifiability in which all -cards are unique, which is . Under this condition, we can recover the lattice by starting with an arbitrary initial -card, and then looking for other cards with a shared subgrid of length ; since all subgrids with length are unique in the lattice, cards with shared subgrids must necessarily be adjacent. We note that their sufficient condition does not match the threshold in the uniform case. To the best of our knowledge, this was the only known result in the non-uniform case.
Our main contribution is establishing a sufficient condition for non-identifiability in the non-uniform case, which matches the known threshold in the uniform case for . We conjecture that our sufficient condition for non-identifiability is the true threshold in the non-uniform case. In addition, we also provide an alternative proof of non-identifiability for the case, which could help with understanding the lattice’s properties better.
Related Work
There is also a large body of work on related shotgun assembly problems that were first introduced by Mossel and Ross [15], and we discuss some of them here.
Dense Erdős–Rényi. One of the most well-studied such problems is shotgun assembly of unlabeled Erdős–Rényi graphs, which asks whether we can reconstruct a graph (up to isomorphism) from the local -neighborhood of each vertex. In the dense setting, the focus has largely been on finding the edge probabilities such that reconstruction is possible for a fixed . There are two phase transitions—reconstruction is possible when the probability is very small or very large, and impossible in between. Intuitively, when is very small, all components fit within a single -neighborhood, while if is very large, all -neighborhoods are unique [13].
For , work by Gaudio and Mossel [9], Huang and Tikhomirov [11], and Johnston, Kronenberg, Roberts, and Scott [13] have identified the phase transitions at and , where denotes equality up to polylog factors.
For , Johnston et al. [13] identified one phase transition at . The other phase transition is still unknown; Gaudio and Mossel [9] showed that if then reconstruction is impossible, while Johnston et al. [13] showed that if then reconstruction is possible.
For , the phase transitions are known from Johnston et al. [13], expanding on the initial work of Mossel and Ross [15]. One transition occurs at , while the other transition occurs at .
Finally, for , Johnston et al. [13] identified the phase transitions at and . A more precise result is known for : Gaudio, Rácz, and Sridhar [10] showed that reconstruction is possible when .
Sparse Erdős–Rényi. The sparse setting considers whether reconstruction is possible in , which depends on the value of . Initial work by Mossel and Ross [15] showed that the threshold occurs at . Later, Ding, Jiang, and Ma [6] identified a sharp threshold at , where is the probability that two independent Galton-Watson trees with parameter are isomorphic. In particular, they showed that if then reconstruction is impossible, while if then reconstruction is possible via a polynomial time algorithm.
Random Jigsaw Puzzles Another related problem introduced by Mossel and Ross [15] is reconstructing random “jigsaw puzzles”. In this problem, we consider a grid of squares, where each border between adjacent squares has one of configurations drawn uniformly at random. Then, we want to know the values of for which we can reassemble the squares back together.
Bordenave, Feige, and Mossel [3] and Nenadov, Pfister, and Steger [17] initially showed that if , then the puzzle has a unique solution, while if , then the puzzle does not have a unique solution. Follow-up work by Balister, Bollobás, and Narayanan [2] showed that there exist constants such that implies that the puzzle is unique, while implies that the puzzle is not unique. Then, Martinsson [14] identified specific constants, showing that if then the puzzle is unique, while if then the puzzle is not unique. The true threshold remains an open problem.
The remainder of the paper is organized as follows. In Section 2, we present our main result, a sufficient condition for non-identifiability when . We subsequently prove our main result in Section 3. In Section 4, we provide an alternative proof of non-identifiability for . In Section 5, we discuss potential candidates for the true threshold for . Finally, we conclude with some future research directions in Section 6.
Main Result
In this section, we present a sufficient condition for the lattice to be non-identifiable, which matches the known threshold in the uniform case [7].
Theorem 2.1. Let and fix . Then, the lattice is non-identifiable with high probability if
where denotes the entropy of .
Remark. Observe that if is uniform, then . Thus, our condition for non-identifiability becomes , which is indeed the threshold in the uniform case.
We use techniques from information theory to prove Theorem 2.1. In particular, we use Fano’s inequality to lower bound the probability that the MAP estimator fails to recover the lattice from the deck, which shows that the error probability is . Intuitively, under Condition (1), the entropy of the lattice exceeds the entropy of the -deck, so there is not enough information in the -deck to recover the lattice.
Proof of Non-identifiability for
In this section, we show that the lattice is non-identifiable with high probability when .
Preliminaries
We first state several lemmas that will be used in the proof.
Lemma 3.1 (Fano’s Inequality (Theorem 2.11.1 in [4])). Let be correlated random variables. Suppose that we observe , and we want to estimate from the observed value of , which we denote . Define the error probability
Then, for any estimator
where denotes the conditional entropy of conditioned on , and is the support of .
Lemma 3.2 (Fannes-Audenaert Inequality [1]). Let and be discrete random variables on the same support of elements with total variation distance . Then
where is the binary entropy of $\epsilon.
Lemma 3.3 (Hoeffding’s Inequality). Let . Then,
Lemma 3.4 (Binomial Chernoff Bound). Let and . Then,
Let be a lattice drawn from the labeled lattice model, and let be the corresponding -deck. To show that the lattice is non-identifiable, we can show that any estimator fails to recover with high probability, meaning that . Rather than analyzing an estimator over all possible lattices, we instead consider a simpler set of lattices whose probability goes to as , and show that any estimator fails to recover such lattices with high probability.
Fix a sequence , which implies that and that as . We define as the event that the -lattice has a “typical” coloring , in the sense that for all ,
That is, the number of vertices of each color is close to their expectation. Thus, we call a lattice -typical if holds. It turns out that the lattice coloring is typical with high probability.
Lemma 3.5. The event holds with high probability.
Proof. Let . Observe that the number of vertices of color follows a distribution. By Hoeffding’s inequality and the union bound,
which shows that holds with high probability.
Since the lattice coloring is typical with high probability, it suffices to show that typical lattices are not identifiable with high probability. To this end, we define as a lattice coloring with the same distribution as conditioned on , and as a -deck with the same distribution as conditioned on . Let be the MAP estimator for estimating from . Then, showing that typical lattices are non-identifiable with high probability is equivalent to showing that .
In addition, we define as the set of lattice colorings that satisfy , and denote , which is the number of -typical -lattices.
Proposition 3.6. Suppose that the following three properties hold.
,
, and
.
Then, , which shows that the lattice is non-identifiable with high probability.
Proof. From Fano’s inequality, we have that
where because is completely determined by . Then, using Properties 1-3 above, we obtain
In the sequel, we prove that the three properties in Proposition 3.6 hold when , which allows us to conclude Theorem 2.1.
Proof of Property 1
Lemma 3.7 (Property 1). We have that .
Proof. Observe that we can represent the lattice as i.i.d. random variables which encode the color of each vertex in the lattice. Since the joint entropy of i.i.d. random variables equals the sum of their individual entropies, we obtain that . Hence, it is sufficient to show that .
To accomplish this, we first compute the total variation distance between and , denoted . By the coupling inequality (Lemma 4.1.11 in [18]), we have that
for all couplings of and . Thus, we consider the following coupling: If then we let . If , then we sample separately so that the marginal distribution of is preserved. In this case, we have
from (3). Now, we apply the Fannes-Audenaert inequality, which yields
To analyze the first term, recall that as . Therefore, we have that , which implies that as well. For the second term, we use the fact that to obtain
Therefore, , which shows that .
Proof of Property 2
Lemma 3.8 (Property 2). We have that .
Proof. Observe that the probability of any given -typical lattice is at least
since there are at most vertices with color . Therefore, the number of typical lattices is at most
which implies that
Since , we have that , which completes the proof. □
Proof of Property 3
We prove Property 3 using a similar strategy as Property 1. First, we show that by finding an explicit encoding for and showing that the expected encoding length is ; since is less than the expected encoding length of any encoding [4], it follows that as well. Then, we use the coupling inequality to compute the total variation distance between and , and apply the Fannes-Audenaert inequality to show that .
Lemma 3.9. If , then .
Proof. We construct an explicit encoding of the deck and show that the expected encoding length is . Consider the following encoding: For every type of card that appears in the deck, we will encode the type of card using a unique identifier of length , then encode the number of times that type of card appears using a string of length .
Observe that there are at most types of cards because there are vertices in each card and choices for the color of each vertex. Thus, we can give each type of card a unique identifier using bits. Meanwhile, there are less than cards in the deck (which is also the maximum number of times any given type of card can appear), so we can encode the count of each card type using bits.
Now, we compute the expected encoding length of the deck from the point of view of a fixed, unrevealed card. Its contribution to the encoding length is given by
where is the number of times that card appears in the deck—this is an overcounting factor, since all cards of the same type have a collective encoding length of . Thus, the expected encoding length of the deck is
It remains to bound . First, observe that for any ,
To upper-bound , we let and focus on upper-bounding . Rather than examine directly, we define a new random variable as follows: Partition the lattice into non-overlapping regions of vertices, which we call the cards of the partitioned lattice; there are a total of cards in the partitioned lattice. Then, consider a random card from the partitioned lattice, which we call the top card, and let be the number of times the top card appears in the partitioned lattice. We note that stochastically, which yields .
We now upper-bound . Let , where is the number of vertices of color in the top card. For any fixed , define as the event
meaning that the number of vertices of each color is close to its expectation. We call the top card -typical if holds. Note that the top card is -typical with high probability, which can be shown using a similar argument to Lemma 3.5.
To compute , we fix and use the law of total probability, conditioning on . Furthermore, we divide the sum into two parts depending on whether the card is -typical, which yields
Conditioned on , the probability that any given card equals the top card is . Therefore, the number of cards matching the top card is distributed according to .
Now, define , and since , we have that for all . Hence, stochastically for any , which implies that for any . In light of (7), we obtain that , which also implies that
Now, we compute an upper bound for using the Chernoff bound. We first compute , which yields
Under the condition , we have that
where is a constant. Under this condition, we also have that
where the last inequality follows from . Therefore,
Now, we use the Chernoff bound to upper-bound where , which yields
From (8), we see that as well. Substituting this into (5), we obtain that
Consequently, the expected encoding length of the deck is at most
which shows that .
Using Lemma 3.9, we can now prove Property 3.
Lemma 3.10 (Property 3). If , then .
Proof. We first use the coupling inequality (Lemma 4.1.11 in [18]) to bound the total variation distance between and , which yields
for any coupling of , . Consider the coupling between , described in Lemma 3.7; since , are determined by , respectively, this also induces a coupling between , . Furthermore, we note that if , then as well. Therefore, we obtain
where the last inequality follows from (4). Then, applying the Fannes-Audenaert inequality and repeating the argument used in Lemma 3.7 shows that . Since from Lemma 3.9, we obtain that as well.
Proof of Non-identifiability for
In this section, we provide an alternative proof of non-identifiability in the 1-dimensional case. We first state the threshold established by Dyer, Frieze, and Suen [8] and Mossel and Ross [15].
Theorem 4.1. Let and fix . Then, the lattice is identifiable with high probability if
and non-identifiable with high probability if
where is the probability that two vertices have the same color.
We note that this threshold corresponds to all -cards being unique. Above this threshold, all -cards are unique with high probability; this allows us to identify adjacent -cards by looking for subgrids of length which appear in both cards, and then reconstruct the lattice by piecing together adjacent cards. Meanwhile, below that threshold, many -cards are not unique, which allows us to produce multiple distinct lattices with the same -deck through a swapping procedure.
To prove non-identifiability under Condition (10), we extend a technique from Ding and Liu [7] that showed non-identifiability in the uniform case. Let be disjoint, consecutive intervals in the 1-dimensional lattice with vertices each. For each , let be a collection of disjoint -cards within . We claim the following proposition holds.
Proposition 4.2. Suppose that . With high probability, there exist for such that
and that
where is the interval strictly between and and is the interval strictly between and , and is the first vertices in and is the first vertices in .
Proposition 4.2 is sufficient to show non-identifiability because and can be swapped to produce different lattices while keeping the same deck; we refer the reader to Section 2.1 in [7] for full details. Therefore, we obtain the non-identifiability result in Theorem 4.1 as a corollary.
Proof of Proposition 4.2. We first show (11) using the second moment method. Let be the number of pairs such that . Formally,
We will show that as using Chebyshev’s inequality. Observe that for any disjoint cards and ,
because the probability that any two given vertices match is . Hence,
Now we compute the second moment. First, observe that
We will explain where each term in the second equality comes from. The first term comes from the case where and . There are ways to choose such . To obtain and , we need one subinterval of vertices to have the same coloring as another subinterval of vertices, which occurs with probability .
The second term comes from the case where either or , but not both. Assume for now that and . There are ways to choose such (the factor comes from choosing and the factor comes from choosing ). To obtain and , we need three subintervals of vertices to all have the same coloring (since must have the same coloring as both and ), which occurs with probability . The same logic holds for when and .
The third term comes from the case where both and . There are ways to choose such . Then, occurs with probability and also occurs with probability ; since these events are independent, the probability of and is .
Now, we apply Chebyshev’s inequality, which yields
We will show that both terms go to zero. For the first term, recall that and observe that implies . Hence, we obtain
For the second term, we use the monotonicity of -norms [12] to obtain that , which implies that . In addition, observe that implies . Thus,
Therefore, with high probability, there exist such that . Identical reasoning shows that with high probability, there exist such that . Hence, (11) holds with high probability.
Now, we show (12) using a straightforward calculation and the union bound, following the same reasoning as [7]. For any given , we have that
which is exponentially decreasing in . The number of possible choices for and is (coming from choices for each of ), which is polynomially increasing in . By the union bound, (12) holds with high probability.
Discussion on the Threshold
In this section, we propose two possible values for the threshold and discuss why each might be the true threshold. One possible value for the threshold is . There are a couple of reasons for this: First, this value coincides with the threshold in the uniform case, as in the uniform case. In addition, we have already proven non-identifiability below this value, and despite our attempts, we were unable to extend our proof to larger values of .
However, we do not rule out this possibility. Our proof depends on finding an encoding of the deck such that to prove Property 3 in Proposition 3.6, and the threshold is used to show that such an encoding is possible. We think that it may be possible to find a better encoding of the deck such that even when , which would prove non-identifiability of the lattice for a higher value (and disqualify as a possibility for the true threshold).
Another possible value for the threshold is , where . This value also coincides with the threshold in the uniform case, as , so . Furthermore, in the uniform case, the threshold for is exactly half of the threshold for , which are and respectively. From [8], we know that the threshold for the non-uniform case with is ; taking half of this value suggests that the threshold for could be .
To compare these two possible thresholds, we observe that with equality holding if and only if is uniform. This can be shown using Jensen’s inequality: Let be the random variable which equals with probability . Using the fact that is convex, we obtain
Consequently, we see that
where equality holds if and only if is uniform. Note that since in the uniform case, the difference between these two possible thresholds only appears in the non-uniform case.
There is a qualitative transition in the behavior of the lattice at each of these values for . If , then the expected number of times a randomly chosen -card repeats goes to 0.
Lemma 5.1. If , then the expected number of cards with the same coloring as a randomly chosen -card is .
Proof. We will consider cards which overlap with the chosen card separately from the cards which do not overlap with the chosen card.
Observe that the probability that two fixed, non-overlapping cards have the same coloring is , since the probability two vertices have the same color is , and each card has vertices. Thus, the expected number of non-overlapping cards with the same coloring as a randomly chosen card is at most . This is when because .
Meanwhile, there are less than cards which overlap the chosen card. Since each card does not overlap with the chosen card on a region of size at least vertices, the probability that two fixed, overlapping cards have the same coloring is at most . Thus, the contribution of overlapping cards to the expectation is at most .
On the other hand, if (i.e., in between the two proposed values), then a randomly chosen card is unique with high probability, but the expected number of repeats diverges to infinity, as established by the following two lemmas.
Lemma 5.2. If , then the expected number of cards with the same coloring as a randomly chosen card is .
Proof. The probability that any two fixed cards have the same coloring is at least (including cards which overlap). Therefore, the expected number of repeats is at least , which tends to infinity when .
Lemma 5.3. If , then a randomly chosen card is unique with high probability.
Proof. Fix . Let , where is the number of vertices of color . We use the law of total probability, conditioning on . Furthermore, we divide the sum into two parts depending on whether the card is -typical, in the sense of the event defined in (6). Let be the event that a randomly chosen card is unique. Then,
because occurs with high probability. Therefore, it is sufficient to show that when (i.e. that a random typical card is unique with high probability).
Recall that the probability that any given card has color count equals . Under the event , we have
Then, taking a union bound over all cards in the deck, we obtain
We want to show this probability goes to 1. Therefore, it is sufficient to show that
Observe that when , we have
as desired, where the second inequality follows from .
We know that in the uniform case, if the expected number of times a randomly chosen -card appears goes to zero (as in Lemma 5.1) then the lattice is identifiable. We expect the same to hold in the non-uniform case as well, so we believe that the lattice should be identifiable when .
Meanwhile, when , a randomly chosen card is unique with high probability, while the expected number of repeats goes to infinity. Consequently, we have a small number of cards which repeat many times throughout the lattice. This potentially creates a barrier for reconstruction because we might have many regions, centered around these repeated cards, that look similar. This could provide opportunities to swap two cards to create a different lattice but keep the same deck. Therefore, whether the true threshold is or depends on whether this barrier can be overcome to reconstruct the lattice.
Conclusion and Future Work
In this paper, we studied the problem of shotgun assembly on the non-uniform labeled lattice model. Our main contribution is establishing a sufficient condition for non-identifiability which matches the known threshold in the uniform case. This work gives rise to some natural open questions.
What is the true threshold for identifiability? Is it one of the two candidates proposed in § 5?
When the lattice is identifiable, what algorithm can be used to reconstruct the lattice?
References
- [1]Koenraad M R Audenaert. A sharp continuity estimate for the von Neumann entropy. Journal of Physics A: Mathematical and Theoretical, 40(28):8127–8136, 2007.DOI
- [2]Paul Balister, Béla Bollobás, and Bhargav Narayanan. Reconstructing random jigsaws. In Multiplex and Multilevel Networks. Oxford University Press, 2017.
- [3]Charles Bordenave, Uriel Feige, and Elchanan Mossel. Shotgun assembly of random jigsaw puzzles. Random Structures & Algorithms, 56(4):998–1015, 2020.arxiv.org/abs/1605.03086
- [4]Thomas M. Cover and Joy A. Thomas. Elements of Information Theory. John Wiley & Sons, Hoboken, N.J, 2nd edition, 2006.
- [5]Yury Demidovich, Yaroslav Panichkin, and Maksim Zhukovskii. Reconstruction of graph colourings. arXiv preprint arXiv:2308.01671, 2023.arxiv.org/abs/2308.01671
- [6]Jian Ding, Yiyang Jiang, and Heng Ma. Shotgun Threshold for Sparse Erdős–Rényi Graphs. IEEE Transactions on Information Theory, 69(11):7373–7391, 2023.DOI
- [7]Jian Ding and Haoyu Liu. Shotgun assembly threshold for lattice labeling model. Probability Theory and Related Fields, 187:423–442, 2023.arxiv.org/abs/2205.01327
- [8]Martin Dyer, Alan Frieze, and Stephen Suen. The Probability of Unique Solutions of Sequencing by Hybridization. Journal of Computational Biology, 1(2):105–110, 1994.pubmed.ncbi.nlm.nih.gov/8790457
- [9]Julia Gaudio and Elchanan Mossel. Shotgun assembly of Erdős-Rényi random graphs. Electronic Communications in Probability, 27:1–14, 2022.DOI
- [10]Julia Gaudio, Miklós Z. Rácz, and Anirudh Sridhar. Average-case and smoothed analysis of graph isomorphism. The Annals of Applied Probability, 35(2):1373–1406, 2025.arxiv.org/abs/2211.16454
- [11]Han Huang and Konstantin Tikhomirov. Shotgun assembly of unlabeled Erdős-Rényi graphs. Probability Theory and Related Fields, 2025.DOI
- [12]Nathaniel Johnston. Advanced Linear and Matrix Algebra. Springer, 2021.DOI
- [13]Tom Johnston, Gal Kronenberg, Alexander Roberts, and Alex Scott. Shotgun assembly of random graphs. Probability Theory and Related Fields, 2025.DOI
- [14]Anders Martinsson. A Linear Threshold for Uniqueness of Solutions to Random Jigsaw Puzzles. Combinatorics, Probability and Computing, 28(2):287–302, 2019.
- [15]Elchanan Mossel and Nathan Ross. Shotgun Assembly of Labeled Graphs. IEEE Transactions on Network Science and Engineering, 6(2):145–157, 2019.
- [16]Bhargav Narayanan and Corrine Yap. Reconstructing Random Pictures. Random Structures & Algorithms, 66(1), 2025.DOI
- [17]Rajko Nenadov, Pascal Pfister, and Angelika Steger. Unique reconstruction threshold for random jigsaw puzzles. Chicago Journal of Theoretical Computer Science, 2017.arxiv.org/abs/1605.03043
- [18]Sébastien Roch. Modern Discrete Probability: An Essential Toolkit. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2024.
- [19]Daniel Soudry, Suraj Keshri, Patrick Stinson, Min-hwan Oh, Garud Iyengar, and Liam Paninski. Efficient “Shotgun” Inference of Neural Connectivity from Highly Sub-sampled Activity Data. PLOS Computational Biology, 11(10):1–30, 2015.DOI