{'fraction_non_alphanumeric': 0.04907720799540201, 'fraction_numerical': 0.01871128424548183, 'mean_word_length': 3.687771291722796, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 6, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 39, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Subsampled Power Iteration: a Unified Algorithm for Block Models and Planted CSP's

We present an algorithm for recovering planted solutions in two well-known models, the stochastic block model and planted constraint satisfaction problems, via a common generalization in terms of random bipartite graphs. Our algorithm matches up to a constant factor the best-known bounds for the number of edges (or constraints) needed for perfect recovery and its running time is linear in the number of edges used. The time complexity is significantly better than both spectral and SDP-based approaches. The main contribution of the algorithm is in the case of unequal sizes in the bipartition (corresponding to odd uniformity in the CSP). Here our algorithm succeeds at a significantly lower density than the spectral approaches, surpassing a barrier based on the spectral norm of a random matrix. Other significant features of the algorithm and analysis include (i) the critical use of power iteration with subsampling, which might be of independent interest; its analysis requires keeping track of multiple norms of an evolving solution (ii) it can be implemented statistically, i.e., with very limited access to the input distribution (iii) the algorithm is extremely simple to implement and runs in linear time, and thus is practical even for very large instances.


Introduction
Partitioning a graph into parts based on the density of the edges within and between the parts is a fundamental algorithmic task both in its own right as a method of clustering data into similar pieces, and as a powerful subroutine of divide-and-conquer algorithms. There are many choices for number of parts required and the measure of the quality of a partition, and different choices give rise to algorithmic problems such as Max Clique, Max Cut, Uniform Sparsest Cut, and Min Bisection.
Finding an optimal graph partition is often an NP-hard problem in the worst case, and so the focus of research has turned to two directions beyond worst-case analysis, designing approximation algorithms and analyzing the average-case complexity of graph partitioning. In this paper we focus on the second direction.
Average-case complexity is the study of probability distributions over instances of computational problems. An efficient algorithm for such a distribution is one that runs in polynomial time in expectation or one that runs in polynomial time and outputs a correct solution with high probability over the distribution of instances.
The average-case study of graph partitioning problems is particularly rich, as the underlying distributions come from natural and widely studied models of random graphs. Such study was initiated in [12,23] in which several graph partitioning problems were found to have efficient average-case algorithms.

Planted partitioning
One way to formulate a clean algorithmic problem and to model a data clustering problem in which an underlying truth is revealed through noisy data is to plant a partition in a random graph and draw edges at random according to a distribution biased towards the planted partition. A particularly simple model of random graph partitioning with a planted solution is the stochastic block or planted bisection model: a graph on n vertices is split into an equal bipartition, and edges within a part are added independently with probability p, and edges crossing the partition added with probability q. Boppana [10] gave an eigenvector-based algorithm for this model, and Jerrum and Sorkin [34] gave a Metropolis approach. Another example of planted partitioning is the planted k-coloring model [8] in which the vertex set is partitioned into k equal parts and then edges crossing the partition are added independently at random while edges within the partition are forbidden. Alon and Kahale [3] gave a spectral algorithm for this problem.
Later algorithms [21,41,25,14,11,20] improved either the running time or the density at which the algorithms succeed, and in particular, Coja-Oghlan [15] showed that the planted partition in the stochastic block model can be partially recovered when the average degree is just a constant. Based on ideas from statistical physics, Decelle et al. [22] conjectured that in fact there is a sharp threshold for efficient recovery: if p = a/n, q = b/n, and (a − b) 2 < 2(a + b) then any non-trivial recovery of the planted partition is impossible, while if (a − b) 2 > 2(a + b) then there is an efficient algorithm (polynomial in the size of the graph) that gives a partition with significant correlation to the planting. Mossel, Sly, and Neeman proved the lower bound [42], and then Massoulie [40] and Mossel, Sly, Neeman [43] independently analyzed algorithms proving the upper bound. See also [44,38] for more on algorithms for this model.
Planted k-CSP's A broad and fundamental class of algorithmic problems is the class of boolean Constraint Satisfaction Problems (CSP's). A width-k CSP is defined by a set of m predicates denoted by P 1 , . . . , P m

Our results and techniques
We propose a natural bipartite stochastic block model that generalizes the classic stochastic block model defined above. The key motivation for the study of this model is that the two types of planted k-CSP's described above can be reduced to our block model. We then give a new algorithm for solving the random instances of the model.
The algorithm is based on applying power iteration with a sequence of matrices subsampled from the original adjacency matrix. This is in contrast to previous algorithms that compute the eigenvectors (or singular vectors) of the full adjacency matrix. The new algorithm has several advantages.
• The algorithm matches the best-known (and in some cases the best-possible) performance with respect to the edge or constraint density needed for complete recovery of the planted partition or assignment. The algorithm for planted CSP's nearly matches computational lower bounds for SDP hierarchies [45] and the class of statistical algorithms [26].
• The algorithm is fast, running in time linear in the number of edges or constraints used, unlike other approaches that require computing eigenvalues or solving semi-definite programs.
• The algorithm is conceptually simple and easy to describe and implement. In fact it can be implemented in the statistical model, with very limited access to the input graph.
• It is based on the idea of iteration with subsampling which may have further applications in the design and analysis of algorithms.
We now define the models and state our main theorems.
Bipartite stochastic block model Definition 1. For δ ∈ [0, 2] \ {1}, n 1 , n 2 even, and P 1 = A 1 ∪ B 1 , P 2 = A 2 ∪ B 2 bipartitions of vertex sets V 1 , V 2 of size n 1 , n 2 respectively, we define the bipartite stochastic block model B(n 1 , n 2 , P 1 , P 2 , δ, p) to be the random graph in which edges between vertices in A 1 and A 2 and B 1 and B 2 are added independently with probability δp and edges between vertices in A 1 and B 2 and B 1 and A 2 with probability (2 − δ)p.
The algorithmic task for the bipartite block model is to recover one or both partitions (completely or partially) using as few edges and as little computational time as possible. In this work we will assume that n 1 ≤ n 2 , and we will be concerned with the algorithmic task of recovering the partition P 1 completely, as this will allow us to solve the planted k-CSP problems described below. We define complete recovery of P 1 as finding the exact partition with high probability over the randomness in the graph and in the algorithm. We define partial ( )-recovery as finding any partition that agrees with P 1 on at least 1/2 + fraction of vertices whp.
Note that setting n 1 = n 2 = n, and identifying A 1 and B 1 and A 2 and B 2 gives the usual stochastic block model (with loops allowed). Theorem 1. Assume n 1 ≤ n 2 . There is an algorithm that completely recovers the partition P 1 in the bipartite stochastic block model B(n 1 , n 2 , P 1 , P 2 , δ, p) with probability 1 − o(1) as n 1 → ∞ using O Note that for the usual stochastic block model this gives an algorithm using O(n log n) edges and O(n log n) time, which is optimal for complete recovery since that many edges are needed for Figure 1: Bipartite stochastic block model. every vertex to appear at least once. For any n 1 , n 2 , at least √ n 1 n 2 edges are necessary for even non-trivial partial recovery, as below that threshold the graph consists of small components. For very lopsided graphs, with n 2 n 1 log 2 n 1 , the running time is sublinear in the size of V 2 ; this requires careful implementation and is essential to achieving the running time bounds for planted CSP's described below.
Planted k-CSP's We now describe a general model for planted satisfiability problems. For an integer k, let C k be the set of all ordered k-tuples of literals from x 1 , . . . , x n , x 1 , . . . , x n with no repetition of variables. For a k-tuple of literals C and an assignment σ, σ(C) denotes the vector of values that σ assigns to the literals in C. A planting distribution Q : Definition 2. Given a planting distribution Q : {±1} k → [0, 1], and an assignment σ ∈ {±1} n , we define the random constraint satisfaction problem F Q,σ (n, m) by drawing m k-clauses from C k independently according to the distribution where σ(C) is the vector of values that σ assigns to the k-tuple of literals comprising C.
Definition 3. The distribution complexity r(Q) of the planting distribution Q is the smallest r > 0 so that there is some S ⊆ [k], |S| = r, so that the discrete Fourier coefficientQ(S) is non-zero.
In other words, the distribution complexity of Q is r if Q is an (r − 1)-wise independent distribution on {±1} k but not r-wise independent. For any Q that is not the uniform distribution over all clauses, we have 1 ≤ r(Q) ≤ k (the uniform distribution over all clauses does not reveal any information about σ and we can define its complexity to be ∞).
Theorem 2. For any planting distribution Q, there exists an algorithm that for any assignment σ, given an instance of F Q,σ (n, m) completely recovers the planted assignment σ for m = O(n r/2 log n) and using O(n r/2 log n) time, where r ≥ 2 is the distribution complexity of Q. For distribution complexity r = 1, the algorithm gives non-trivial partial recovery with O(n 1/2 log n) constraints and complete recovery with O(n log n) constraints.
We also show that the same result applies to recovering the planted assignment in Goldreich's PRG defined above.
Theorem 3. For any predicate P : {±1} k → {±1}, there exists an algorithm that for any assignment σ, given m random P -constraints completely recovers the planted assignment σ for m = O(n r/2 log n) and using O(n r/2 log n) time, where r ≥ 2 is the degree of the highest-degree non-zero Fourier coefficient of P . For r = 1, the algorithm gives non-trivial partial recovery with O(n 1/2 log n) constraints and complete recovery with O(n log n) constraints.

Comparison with previous work:
The algorithm of Mossel, Neeman, and Sly [43] for the case n 1 = n 2 also runs in near linear time, while other known algorithmic approaches for planted partitioning that succeed near the optimal edge density [41,15,40] perform eigenvector or singular vector computations and thus require superlinear time.
For planted satisfiability, the algorithm of Flaxman for planted 3-SAT works for distributions with complexity r ≤ 2 using O(n) constraints, while the algorithm of Coja-Oghlan, Cooper, and Frieze [16] works for all planted 3-SAT distributions that exclude unsatisfied clauses and uses O(n 3/2 ln 10 n) constraints.
The only previous algorithm that finds the planted assignment in Goldreich's PRG for all predicates is the SDP-based algorithm of Bogdanov and Qiao [9] with the folklore generalization to r-wise independent predicates (cf. [45]). Similar to our algorithm, it usesÕ(n r/2 ) constraints. This algorithm effectively solves the noisy r-XOR-SAT instance and therefore can be also used to solve our general version of planted satisfiability usingÕ(n r/2 ) clauses (via the reduction in Section 3). Notably for both this algorithm and ours, having a completely satisfying planted assignment plays no special role: the number of constraints required depends only on the distribution complexity.
Our algorithm is arguably simpler than the approach in [9] and substantially improves the running time even for small k. Another advantage of our approach is that it can be implemented using restricted access to the distribution of constraints referred to as statistical queries. Roughly speaking, for the planted SAT problem this access allows an algorithm to evaluate multi-valued functions of a single clause on randomly drawn clauses or to estimate expectations of such functions, without direct access to the clauses themselves. Recently, in [26], lower bounds on the number of clauses necessary for a polynomial-time statistical algorithm to solve planted k-CSPs were proved. It is therefore important to understand the power of such algorithms for solving planted k-CSPs. A statistical implementation of our algorithm gives an upper bound that nearly matches the lower bound for the problem. See [26] for the formal details of the model and statistical implementation.
In Section 2 we describe the algorithm and analyze its performance. In Section 3 we present the reduction of the planted k-CSP problems to the bipartite stochastic block model. The appendix contains full details of the analysis.

The algorithm
We now present our algorithm for the bipartite stochastic block model. We define vectors u and v of dimension n 1 and n 2 respectively, indexed by V 1 and V 2 , with u i = 1 for i ∈ A 1 , u i = −1 for i ∈ B 1 , and similarly for v. To recover the partition P 1 it suffices to find either u or −u.
We will find ±u by multiplying a random initial vector x 0 by a sequence of centered adjacency matrices and their transposes. We form these matrices as follows: let G p be the random bipartite graph drawn from the model B(n 1 , n 2 , P 1 , P 2 , δ, p), and T a positive integer. Then we form bipartite graphs G 1 , . . . , G T on the same vertex sets V 1 , V 2 by placing each edge of G p uniformly and independently at random in one of the T graphs. Thus G 1 , . . . , G T are i.i.d. with distribution G p/T . Next we form the n 1 × n 2 adjacency matrices A 1 , . . . , A T with rows indexed by V 1 and columns by V 2 with a 1 in entry (i, j) if vertex i ∈ V 1 is joined to vertex j ∈ V 2 . Finally we center the matrices by defining M i = A i − p T J where J is the n 1 × n 2 all ones matrix. We will denote by M (q) the distribution of these matrices, with q = p/T . In other words, for i ∈ A 1 , j ∈ A 2 or i ∈ B 1 , j ∈ B 2 , we have M (q) ij = 1 − q with probability δq and −q otherwise; for i ∈ A 1 , j ∈ B 2 or i ∈ B 1 , j ∈ A 2 , we have M (q) ij = 1 − q with probability (2 − δ)q and −q otherwise, with all entries in the matrix independent.
In the bipartite block model, the subsampled matrices are independent, leading to clean analysis and a strong bound on the number of iterations required to solve the problem. The subsampling also mitigates the influence of high-degree vertices leading to significant improvement over the spectral approach for a large subclass of planted CSP's.
The analysis of the algorithm proceeds by tracking a potential function, U i = x i ·u for a sequence of unit vectors x 0 , x 1 , . . . of dimension n 1 . We must bound various norms of the x i 's as well as norms of a sequence of auxiliary vectors y 1 , y 2 , . . . of dimension n 2 . We use superscripts to denote the current step of the iteration and subscripts for the components of the vectors, so x i j is the jth coordinate of the vector after the ith iteration.
The basic iterative steps are the multiplications y = M T x and x = M y. 2. Sample x ∈ {±1} n 1 uniformly at random and let x 0 = x √ n 1 .
3. For i = 1 to T let 4. For each coordinate j of z i take the majority vote for all i ∈ {T /2, . . . , T } and call this vector v:

Return the partition indicated by v.
The analysis of the resampled power iteration algorithm proceeds in four phases, during which we track the progress of two vectors x i and y i , as measured by their inner product with u and v respectively. We define U i := u · x i and V i := v · y i . Here we give an overview of each phase; the complete analysis is in Appendix A.
• Phase 1. Within log n 1 iterations, |U i | reaches log log n 1 . We show that conditioned on the value of U i , there is at least a 1/2 chance that |U i+1 | ≥ 2|U i |; that U i never gets too small; and that in log n 1 steps, a run of log log n 1 doublings pushes the value of U i above log log n 1 .
• Phase 2. After reaching log log n 1 , U i , makes steady, predictable progress, doubling at each step whp until it reaches Θ( √ n 1 ), at which point we say x i has strong correlation with u.
• Phase 3. Once x i is strongly correlated with u, we show that z i+1 agrees with either u or −u on a large fraction of coordinates.
• Phase 4. We show that taking the majority vote of the coordinate-by-coordinate signs of z i over O(log n 1 ) additional iterations gives complete recovery whp.

Number of edges used and running time
To make progress at each step, each iteration uses a matrix drawn from M (q) with q = O((δ − 1) −2 (n 1 n 2 ) −1/2 ). All together there are O(log n 1 ) iterations, and so we can take p = O(log n 1 (δ − 1) −2 (n 1 n 2 ) −1/2 ). If n 2 = Θ(n 1 ), then a straightforward implementation of the algorithm runs in time linear in the number of edges used: each entry of x i = M y i (resp. y i = M T x i−1 ) can be computed as a sum over the edges in the graph associated with M . The rounding and majority vote are both linear in n 1 .
However, if n 2 n 1 , then simply initializing the vector y i will take too much time. In this case, we have to implement the algorithm more carefully. We still maintain the vectors x 0 , x 1 , . . . as before, but instead of computing the vectors y i at each step, we create a set S i ⊂ V 2 of all vertices with degree at least 1 in the current graph G i . The size of S i is bounded by the number of edges in G i , and checking membership can be done in constant time with a data structure of size O(|S i |) that requires expected time O(|S i |) to create [28]. Now instead of computing y i = M T 2i−1 x i−1 , we create the set S i . Then to compute x i = M 2i y i , we do the following computation: The quantity e = (j, k) ∈ G 2i : k / ∈ S i can be computed with the membership data structure in time linear in the number of edges of G 2i . Finally, e=(j,k)∈G 2i :k∈S i y i k can be computed in time linear in the number of edges too, by looking up the edges incident to vertex k ∈ V 2 in the previous graph to determine y i k .

Reduction of planted k-CSP's to the block model
Here we describe how solving the bipartite block model suffices to solve the planted k-CSP problems. First consider a planted k-SAT problem F Q,σ (n, m) with distribution complexity r. Let S ⊆ [k], |S| = r, be such thatQ(S) = η = 0. We will show that subsampling r literals with indices in the set S from each k-clause induces a distribution on r-constraints defined by Q δ : {±1} r → R + of the form Q δ (C) = δ/2 r for |C| even, Q δ (C) = (2 − δ)/2 r for |C| odd, for some δ ∈ [0, 2] , δ = 1, where |C| is the number of TRUE literals in C under σ. This reduction allows us to focus on algorithms for the specific case of a parity-based distribution on k-clauses with distribution complexity k. Recall that for a function f : {−1, 1} k → R, its Fourier coefficients are defined for each subset S ⊂ [k] aŝ where χ S are the Walsh basis functions of {±1} k with respect to the uniform probability measure, i.e., χ S (x) = i∈S x i . Lemma 1. If the function Q : {±1} k → R + defines a distribution Q σ on k-clauses with distribution complexity r and planted assignment σ, then for some S ⊆ [k], |S| = r and δ ∈ [0, 2] \ {1}, choosing r literals with indices in S from a clause drawn randomly from Q σ yields a random r-clause from Q δ σ . Proof. From Definition 3 we have that there exist S with |S| = r such thatQ(S) = 0. Note that by definition,Q measures the difference between the probability under Q that the number of true values in {x i } i∈S is even and the probability that the number of true values in {x i } i∈S is odd. By the definition of Q σ , this probability being different from 0 is equivalent to the existence of δ = 1 such that an r-clause generated by choosing the literals with indices in S from a k-clause chosen randomly from Q σ is distributed according to Q δ σ defined as above (over r-clauses).
Next we describe how the parity distribution on r-constraint induces a bipartite block model. Let V 1 be the collection of all ordered r/2 -tuples of literals of the given variable set, and V 2 the collection of all ordered r/2 -tuples. We have n 1 = |V 1 | = 2n r/2 and n 2 = |V 2 | = 2n r/2 . We partition each set into two parts based on the parity of the number of true literals in the tuples under the planted assignment σ: A 1 ⊂ V 1 , A 2 ⊂ V 2 are the sets of r/2 , r/2 tuples respectively with an even number of true literals, and B 1 , B 2 are the sets with an odd number of true literals.
For each r-constraint (l 1 , l 2 , . . . , l r ), we add an edge in the block model between the tuples (l 1 , . . . , l r/2 ) ∈ V 1 and (l r/2 +1 , . . . , l r ) ∈ V 2 . A constraint drawn according to Q δ σ induces a random edge between A 1 and A 2 or B 1 and B 2 with probability δ and between A 1 and B 2 or B 1 and A 2 with probability 2 − δ, exactly the distribution of a single edge in the bipartite block model.
Solving this bipartite block model completely for the partition P 1 = A 1 ∪ B 1 divides the r/2tuples of literals into even and odd parity sets, and then solving a set of linear equations mod 2 recovers the parity of each individual literal, reconstructing either σ or −σ.
The reduction from Goldreich's PRG to the bipartite block model is even simpler. By definition, the value of the predicate is correlated with the parity function of some r of the k inputs of the predicate (see for example [9]). Therefore the input can be seen as produced by the noisy r-XOR predicate on random and uniform r-tuples of variables. The r-tuples for which this predicate is equal to 1 give an instance of noisy r-XOR-SAT. A bipartite block model can now be formed on r/2 and r/2 tuples of variables (instead of literals) analogously to the construction above.

Comparison with spectral approach
As noted above, many approaches to graph partitioning problems and planted satisfiability problems use eigenvalues or singular vectors. These algorithms are essentially based on the signs of the top eigenvector of the centered adjacency matrix being correlated with the planted vector. This is fairly straightforward to establish when the average degree of the random graph is large enough (as we sketch below). However, in the stochastic block model, for example, when the average degree is a constant, vertices of large degree dominate the spectrum: the eigenvectors of the largest eigenvalues are nearly basis vectors (see [38] for a discussion and references).
To surmount this barrier, Coja-Oghlan [15] regularized the graph by removed high-degree vertices and analyzed the resulting spectrum. The recent works of Massoulie [40] and Mossel, Neeman, and Sly [43] analyze the spectrum of a matrix that counts the number of non-backtracking, or self-avoiding, walks of length c log n between vertices i and j; this spectrum is less sensitive to high-degree vertices and so they are able to find correlation with the planted vector at an optimal density, proving the conjecture from [22].
Our approach of power iteration with resampled matrices can be viewed as an alternative approach to dealing with the challenge of high-degree vertices. As each matrix uses disjoint sets of edges, the iterated vectors do not converge to near-basis vectors localized around a particular vertex, and this in fact is the substance of our bounds on the various norms of x i and y i (see Lemma 2 in Appendix A).
In the case of the usual block model, n 1 = n 2 = n, while our approach has a fast running time, it does not save on the number of edges required as compared to the standard spectral approach: both require Ω(n log n) edges. However, when n 2 n 1 , eg. n 1 = n (k−1)/2 , n 2 = n (k+1)/2 as in the case of the planted k-CSP's for odd k, the problem of high-degree vertices is exacerbated considerably. In fact, previous spectral approaches to planted CSP's or random k-SAT refutation worked for k even with n k/2 constraints [30,18,25], while spectral-based algorithms for odd k only worked for k = 3 and used considerably more complicated constructions and techniques [24,29,16].
In constrast, our algorithm unifies the approach to planted k-CSP's for odd and even k, works for odd k > 3, and is particularly simple and fast.
Consider M from the distribution M (p). Let u be the n 1 dimensional vector indexed as the rows of M whose entries are 1 if the corresponding vertex is in A 1 and −1 otherwise. Define the n 2 dimensional vector v analogously. The next propositions summarize properties of M . Proposition 3. Let A be a random n 1 × n 2 matrix with independent entries in the range [−1, 1] with mean zero and variance at most σ 2 . Suppose n 1 ≤ n 2 . Then with probability 1 − o(1), The above lemmas suffice to show high correlation between the top singular vector and the vector u when n 2 = Θ(n 1 ) and p = Ω(log n 1 /n). This is because the norm of E (M ) is p √ n 1 n 2 ; this is higher than O( √ pn 2 ), the norm of M − E (M ). Therefore the top singular vector of M will be correlated with the top singular vector of E (M ). The latter is a rank-1 matrix with u as its right singular vector. However, when n 2 n 1 (eg. k odd), the norm of the zero-mean matrix M − E (M ) is in fact much larger than the norm of E (M ). (i.e., p √ n 1 n 2 vs √ pn 2 , the former is O(1), while the latter is Ω((n 2 /n 1 ) 1/4 )). In other words, the top singular value of M is much larger than the value obtained by the vector corresponding to the planted assignment! In spite of this, one can exploit correlations to recover the planted vector with our resampling algorithm.
A Analysis of the subsampled power iteration algorithm We abuse notation and let A 1 , B 1 , A 2 , B 2 denote the sets of coordinates of the corresponding vertex sets. Recall that u ∈ {±1} n 1 is 1 on A 1 and −1 on B 1 , and v ∈ {±1} n 2 is 1 on A 2 , −1 on B 2 . M (q) is a random n 1 × n 2 matrix where the entries are independent and the entry (i, j) takes value 1 − q with probability δq, −q otherwise if i ∈ A 1 , j ∈ A 2 or i ∈ B 1 , j ∈ B 2 , and value 1 − q with probability (2 − δ)q, −q otherwise if i ∈ A 1 , j ∈ B 2 or i ∈ B 1 , j ∈ A 2 . We assume WLOG that δ > 1. Set q = 100 (δ−1) 2 √ n 1 n 2 and T = 10 log n 2 . For convenience we denote d = 100/(δ − 1) 2 . We begin with some preliminary facts on the effect of multiplying a unit vector by M (q) or M (q) T . We use these estimates repeatedly in what follows.

var( M y
Proof. If j ∈ A 1 , and similarly for j ∈ B 1 . This gives and similarly for j ∈ B 2 . This gives Finally we have = n 2 x 4 ∞ · O n 1 q + n 2 1 q 2 + n 3 1 q 3 + n 4 1 q 4 = O n 2 n 1 q x 4 ∞ Next we show the normalizing factors M y 2 and M T x 2 are concentrated at each step; the l ∞ norms of the x i 's are bounded over all iterations, and the l ∞ and l 1 norms of the y i 's are bounded. This proposition is critical in ensuring steady progress of our potential functions.
The remaining entries have value −q. If the jth row of M i−1 has only −q entries, then using (2) inductively. This proves (1).
To prove (5), partition the coordinates of y i into two sets ∆ and ∆, with ∆ corresponding to rows of M i−1 with every entry −q, and ∆ the rest. Then Using Chebyshev and part (3), Similarly, using Chebyshev and part (4), To prove (3), note that ). Therefore it suffices to show that for every j = 1, . . . n 1 , To this end we will show that for any j, Again partition the coordinates of y i , with ∆ being the set of j so that |y i j | ≤ 2qn 1 n 2 and ∆ the rest. The contribution to |(M T i y i ) j | from ∆ is bounded by where m j is the number of 1 − q entries in the jth row of M T i . This number m j is dominated by a Binom(n 2 , 2q) random variable and so with probability 1 − exp(−n 2 q), m j ≤ 3n 2 q. Therefore, the contribution from ∆ is bounded by The contribution to |(M T i y i ) j | from ∆ is bounded by where we have used (4) and (1)), and m j is the number of 1 − q entries in the jth row of M T i whose column has index in ∆. m j is dominated by a Binom(3n 2 n 1 q, q) random variable, and so with probability 1 − O(exp(−Ω(3n 2 n 1 13/12q 2 ))), m j ≤ 3n 2 n 1 q 2 · n 1/12 1 in which case we have that the contribution from ∆ is bounded by proving inequality (2). (We remark that for this part, the loose bounds we have above suffice, as it is the next part that controls parameter settings).
To prove (4), set λ = n ). Therefore it suffices to show that for every j = 1, . . . n 2 , We will show that for any j, We partition the coordinates of x i according to their magnitude, in bins B 1 , . . . B L , defined for l < L as Taking a union bound over all L bins, we have (3).
Next we show that the vector y i reaches high correlation with v after T /2 steps. Recall the definitions V i := v · y i and U i := u · x i .

4,5. Chebyshev again.
Proof of Proposition 5. In the first phase, we show that it takes ln ln n 2 iterations for |U i | to reach ln ln n 1 whp. Next, it takes a further ln n 1 iterations to reach √ n 1 /2. Finally, |U i | will remain above √ n 1 /2 whp for an additional 2 ln n 1 iterations.
Step 1: We call a step from U i to U i+1 'good' if |U i+1 | ≥ 2|U i |, or if |U i+1 | ≥ 1/4 following a bad step. A run of ln ln ln n 1 good steps must end with |U i | ≥ ln ln n 1 . As long as |U i | < ln ln n 1 , the proposition above shows that the probability of a good step is at least 1/2, so in ln ln n 1 steps, with probability 1 − o(1) we will either have such a run or reach ln ln n 1 even earlier.
Step 2: Once we have |U i | ≥ ln ln n 1 , the value will double whp in successive steps until |U i | ≥ √ n 1 /4. This takes at most ln n 1 steps. The total error probability, by part 3) of Proposition 6 is a geometric series that sums to O(1/(ln ln n 1 ) 2 ).
Step 4: Finally we use part 5) of Proposition 6 to conclude that y i has high correlation with v.
We now use Proposition 5 to prove the main theorem.
Proof of Theorem 1. Now that we know whp y T /2 , y T /2+1 , . . . all have large correlation with v, we show that taking the majority vote for each coordinate of z T /2+1 , z T /2+2 , . . . recovers ±u whp. Take the first case from Proposition 5, with V i ≥ Now an application of Azuma's inequality shows that with probability at least 1−o(n −2 1 ), T i=T /2 z i j > 0. Similarly, for j ∈ B 1 , we have T i=T /2 z i j > 0 with probability at least 1 − o(n −2 1 ), and so whp the majority vote recovers u exactly. The same argument shows that if the second case of Proposition 5 holds, then −u is recovered whp.