{'fraction_non_alphanumeric': 0.05748731149019094, 'fraction_numerical': 0.01240492706833617, 'mean_word_length': 3.738096878660511, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 15, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 32, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Near-Optimal Cayley Expanders for Abelian Groups

We give an efficient deterministic algorithm that outputs an expanding generating set for any finite abelian group. The size of the generating set is close to the randomized construction of Alon and Roichman (1994), improving upon various deterministic constructions in both the dependence on the dimension and the spectral gap. By obtaining optimal dependence on the dimension we resolve a conjecture of Azar, Motwani, and Naor (1998) in the affirmative. Our technique is an extension of the bias amplification technique of Ta-Shma (2017), who used random walks on expanders to obtain expanding generating sets over the additive group of n-bit strings. As a consequence, we obtain (i) randomness-efficient constructions of almost k-wise independent variables, (ii) a faster deterministic algorithm for the Remote Point Problem, (iii) randomness-efficient low-degree tests, and (iv) randomness-efficient verification of matrix multiplication.


Main Result
A graph is an expander if there exists α > 0 such that the spectral gap of its adjacency matrix (namely, the difference between its top eigenvalue and its second eigenvalue) is at least α. Such graphs are very well-connected in the sense that they lack sparse cuts. Expanders that are additionally sparse are immensely important in computer science and mathematics (see, e.g. the survey [HLW06]).
Cayley graphs are an important class of graphs built from groups. Given a group G and a generating set S ⊂ G, the graph Cay(G, S) has vertex set G and edges (g, g · s) for all g ∈ G, s ∈ S. In addition to describing various well-known graphs such as the hypercube and the torus, Cayley graphs of (non-abelian) groups gave the first explicit constructions of near-optimal expander graphs [LPS88]. Moreover, their algebraic structure makes Cayley graphs easier to analyze. In particular, the eigenvectors and eigenvalues of a Cayley graph are well-understood through the Fourier transform on the group.
Theorem 1.1. There is a deterministic, polynomial-time algorithm which, given a generating set of an abelian group G, integer n ≥ 1, and ǫ > 0, outputs a generating set S ⊂ G n of size O( n log(|G|) O(1) ǫ 2+o (1) ) such that Cay(G n , S) has spectral gap 1 − ǫ.
Expanding Cayley graphs are equivalent to pseudorandom objects called ǫ-biased sets. These were originally defined over F n 2 by Naor and Naor [NN93]. A set S ⊆ F n 2 is said to be ǫ-biased if for every non-empty T ⊆ [n], we have E x∈S [ i∈T x i ] = 1/2 ± ǫ.
Naor and Naor initiated a long line of work culminating in a recent breakthrough result by Ta-Shma, that achieves |S| = O( n ǫ 2+o(1) ) [TS17]. This construction approaches the Alon-Roichman bound as ǫ → 0.
Ta-Shma's construction follows previous work in using a 2-step "bias amplification" approach. First, identify an explicit set S 0 ⊂ F n 2 with constant bias, usually through algebraic methods. Second, amplify the bias of S 0 to any ǫ > 0 by performing a random walk on an expander graph. While this general method was already known, it could only achieve |S| = O( n ǫ 4+o(1) ). To break this barrier, Ta-Shma identified a graph structure obtained from a "wide replacement product", which was more effective for the bias amplification step and resulted in |S| = O( n ǫ 2+o(1) ).

Wide Replacement Walks are Optimal Character Samplers
Random walks on expander graphs are useful for a variety of algorithmic purposes. A classical fact is that expander walks are good approximate samplers, in the sense that a sufficiently long random walk on an expander will visit sets of density δ for approximately a δ fraction of the steps. This is called the "expander Chernoff bound" and one can characterize this as the property that expander walks fool a suitable test function. Ta-Shma observed that expander walks fool the much more sensitive class of parity functions on {0, 1} n as well. Parity functions are sensitive to input perturbations -flipping a single bit in the input can change the output. The classical expander Chernoff bound is not fine-grained enough to prove that t-step expander walks fool parity functions. The fact that they nevertheless do fool parity functions is therefore surprising, and Ta-Shma referred to this fact as "expanders are good parity samplers" [TS17].
Since parity functions are just the characters of F n 2 , we can ask: do expander walks also fool the characters of more general classes of groups? We show that this is indeed true, and therefore "expander walks are good character samplers." Moreover, just as in the F 2 case, a random walk on a wide replacement product of expander graphs is an optimal type of character sampler.
Therefore, wide replacement walks obtain precisely the same bias amplification parameters for small-bias sets over abelian groups as they do in the G = F 2 case.
Character sampling explained: Let us precisely explain what we mean by "character sampling." A character of an abelian group is a homomorphism χ : G → C * , where C * is the multiplicative group of complex numbers. The eigenvalues of an abelian Cayley graph Cay(G, S) are given by | Ex∼S χ(x)| for all characters χ. Note that the constant function that maps all values to 1 is a character, and the eigenvalue associated with it is the top eigenvalue. Therefore, we are interested in generating sets S such that | Ex∼S χ(x)| ≤ ǫ for all non-constant χ.
For simplicity, consider the case G = Z d for some d ≥ 2. Let ω d := exp( 2πi d ) denote the primitive d th root of unity. In this case the characters are just the maps x → ω x·j d for j = 0, 1, ..., d − 1. Now, suppose we have some ǫ 0 -biased set G 0 ⊂ G, where ǫ 0 < 1 is a constant. First, observe that taking t independent samples from G 0 and outputting their sum obtains a distribution with bias (ǫ 0 ) t . However, since independent sampling also results in a distribution of size |G 0 | t , there is no improvement in size as a function of bias.
The idea of the random walk approach is to derandomize independent sampling by taking correlated samples. Specifically, identify G 0 with the vertices of some degree-regular expander graph Γ. We need to show that taking a random walk of length t on Γ and then summing the elements in the path gives a distribution with less bias than G 0 .
A t-step walk on Γ gives a sequence of group elements (x 0 , ..., x t ) ∈ G t+1 0 . We are interested in the bias of the random group element i x i . In general, we cannot hope that ( i x i ) is close to the uniform distribution in statistical distance. However, for every non-constant character χ, it turns out that the quantity | E [χ( i x i )]| is at most ǫ, where the expectation is over paths (x 0 , ..., x t ) in the graph. Notice that Ex∈G [χ(x)] = 0, so the random element ( i x i ) is close to uniform in the weaker sense of fooling characters. Therefore, the expander walk is a good "character sampler." As in the F 2 case, character functions are sensitive to input perturbations. Therefore, the character sampling property of expanders is a much finer-grained property than the expander Chernoff bound.
Why expanders are character samplers: We express the bias of the random walk distribution algebraically in terms of matrix norms corresponding to the random walk.
Abusing notation, let Γ denote the random walk matrix of the graph Γ. Let the character χ * : Z d → C be the worst-case character for the random-walk distribution. Partition G 0 into S 0 , ..., S d−1 depending on their values with respect to χ * , so that x ∈ S k ⇐⇒ χ * (x) = ω k d . We need to track how often the walk enters S 0 , S 1 , ..., S d−1 ⊂ V (Γ). Identify each S i with an be the projection onto this subspace. Finally, let Π = y∈Z d ω y d Π y be the weighted projection matrix. Given some initial distribution u on the vertices, the vector Γ t u tracks the distribution after taking a t-step walk on the graph. The matrix Π tracks how often the walk enters the sets S 0 , ..., S d−1 , and so the bias of the random walk distribution can be bounded by the norm of (ΠΓ) t .
Let V denote the subspace spanned by the all-ones vector 1, and V ⊥ = (V ) ⊥ . For a vector v ∈ V ⊕ V ⊥ , let v and v ⊥ denote the projections onto V , V ⊥ respectively.
To see this, notice that if v ∈ V ⊥ is a unit vector, then ΠΓΠΓ v ≤ ΠΓΠ λ(Γ) v ≤ λ(Γ). Therefore, the "bad" case is when v ∈ V . Let u = 1 √ |V (Γ)| 1. Using the fact that Π = 1, It remains to show that Π(Πu) ≤ bias(G 0 ). To see this, notice that Π is a diagonal matrix and u is just 1 scaled by a constant. Further, Π is a block-diagonal matrix of the form Note that we have reordered the vertices of the graph in order of S 0 , S 1 and so on. If the blocks are exactly the same size, then Πu ∈ V ⊥ , because y∈Z d ω y d = 0. In general the blocks have different dimensions, but they are the same size up to the bias of G 0 . Therefore (Πu) ≤ bias(G 0 ).
It follows that a random walk on Γ is a good character sampler. However, this approach can never amplify bias fast enough to achieve a generating set smaller than O( |G 0 | ǫ 4+o(1) ). The reason is because while we can bound (ΠΓ) 2 , we cannot bound ΠΓ below 1. Therefore, we effectively only gain from one in every two steps.
Wide Replacement Walks are Optimal Character Samplers: To circumvent the "2-step barrier" of expander walks outlined above, Ta-Shma used the wide replacement walk on a product of two expander graphs. The idea of the wide replacement walk is to take the product of a D 1regular graph Γ as before with an "inner graph" H on D s 1 vertices, for some s ≥ 2. The product graph replaces every vertex of Γ with a copy of H (called a "cloud") and then connects clouds to other clouds according to the edge structure of Γ.
Analyzing the bias of the walk involves bounding the matrix norm ofΠΓḢ, whereΓ andḢ are random walk matrices on the product corresponding to Γ, H.
Let V denote the subspace of vectors which are constant on the H-component of the product, and let V ⊥ = (V ) ⊥ . Similar to the above case, one can show thatΠΓḢ shrinks the norm of any v ∈ V ⊥ by a factor of λ(H). The difficult case is when v ∈ V . Here we arrive at the core idea of the replacement product: if the inner graph H is pseudorandom with respect to Γ, then when the walk is in V , the next s steps approximate the ordinary random walk on Γ.
This is enough to circumvent the "2-step barrier" since in even the "bad case" where the walk is stuck in V , we can shrink the bias as though it were taking an ordinary walk on Γ. As we showed above, this shrinks the bias from some ǫ 0 to (ǫ 0 + 2λ(Γ)) ⌊s/2⌋ every s steps. If we select Γ, H such that ǫ 0 + 2λ(Γ) ≤ λ(H) 2 , then we conclude that we shrink the bias by a factor of λ(H) s−Os(1) every s steps. So we gain from s − O(1) out of every s steps.
Going from the F 2 -case to the case of general abelian groups simply requires a more careful analysis of characters. Morally speaking, the only difference in the analysis is that the projection matrix Π which tracks how often the walk enters each S i is different. This does not change the overall argument much; in particular, we can use almost identical graphs Γ, H as in [TS17].
We conclude that a wide replacement walk allows us to amplify bias of a constant-biased subset G 0 ⊂ G n of size O(n log(|G|) O(1) ) (e.g. the construction of [AMNV18]) to an ǫ-biased set of size (1) ), nearly matching the Alon-Roichman bound.

Applications
Explicit constructions of expander graphs are an essential component of algorithms, especially for derandomization. Here we are interested in the setting of constructing an expanding Cayley graph from a given abelian group G. Our construction achieves a near-optimal degree, which improves parameters in various applications.
Almost k-wise independence: A distribution D ∼ G n is (ǫ, k)-wise independent if for every index set I ⊂ [n] of size k, the restriction of D to I is ǫ-close to uniform in statistical distance. Almost k-wise independent distributions are a fundamental object in and of themselves. They also have a variety of applications in derandomization, including load balancing [CP14], derandomization of Monte-Carlo simulations [CP14], derandomization of CSP approximation algorithms [CMM09], and pseudorandom generators [CHHL19]. We note that certain applications (e.g. quantum tdesigns [AE07]) really require almost k-wise independent distributions over arbitrary alphabet size rather than just the binary alphabet, which motivates our study of ǫ-biased sets over arbitrary abelian groups.
Vazirani's XOR Lemma asserts that an ǫ-biased distribution D is also (ǫ |G| k , k)-wise indepdent for all k ≤ n. Therefore, by constructing an ǫ ′ -biased distribution where ǫ ′ = ǫ √ |G| k , we also obtain explicit constructions of (ǫ, k)-wise independent random variables on G n . Proposition 1.2 (Almost k-wise independent sets over abelian groups). Let G be a finite abelian group given by some generating set. For any ǫ > 0 and n ≥ k ≥ 1 there exists a deterministic, polynomial-time algorithm whose output is an (ǫ, k)-wise independent distribution over G n . The support size is O( n·|G| k+o(1) ǫ 2+o(1) ).
Remote Point Problem: A matrix A ∈ F m×n 2 is (k, d)-rigid iff for all rank-k matrices R ∈ F m×n 2 , the matrix A−R has a row with at least d nonzero entries. Valiant initiated the study of rigid matrices in circuit complexity, proving that an explicit construction of an (Ω(n), n Ω(1) )-rigid matrix for m = O(n) would imply superlinear circuit lower bounds [Val77]. After more than four decades of research, state of the art constructions have yet to meet this goal [BHPT20].
The Remote Point Problem was introduced by Alon, Panigrahy, and Yekhamin as an intermediate problem in the overall program of rigid matrix constructions [APY09]. Arvind and Srinivasan generalized the problem to any group [AS10].
Let G be a group, n ≥ 1, and H ≤ G n a subgroup given by some generating set. For a given G, H and integer r > 0, the Remote Point Problem is to find a point x ∈ G n such that x has Hamming distance greater than r from all h ∈ H, or else reject. In the case of G n = F n 2 , this is a relaxation of the matrix rigidity problem, since rather than finding m vectors x 1 , ..., x m ∈ F n 2 whose linear span is far from all low-dimensional subspaces, we are given a single subspace and must find just a single point far from it.
To find a remote point, existing algorithms first construct a collection of subgroups H 1 , ..., H m ≤ G m whose union covers all points of distance at most r from H. In the F 2 case, [APY09] find a point x ∈ i H i by the method of pessimistic estimators. In the general case, [AS10] instead prove that any generating set S ⊂ G n such that Cay(G n , S) has sufficiently good expansion must contain a point outside of i H i . They find this remote point by first constructing an expanding generating set S, and then exhaustively searching it. Their argument implicitly uses the fact that small-bias sets correspond to rigid matrices, albeit with weak parameters -this connection was developed further in [AC13].
The construction of [AS10] for small-bias sets over abelian groups has size O((log(|G|) + n 2 ǫ 2 ) 5 ) in general, and for log(|G|) ≤ log( n 2 ǫ 2 ) O(1) this is improved to O( n 2 ǫ 2 ). Our algorithm improves the dependence on n from n 2 to n.
Randomness-Efficient Low-Degree Testing: Let F q be the finite field on q elements. Lowdegree testing is a property testing problem in which, when given query access to a function f : F n q → F q and d ≥ 1, one must decide whether f is a degree d polynomial or far (in Hamming distance) from all degree d polynomials. These tests are a key ingredient in constructions of Locally Testable Codes (LTCs) and Probabilistically Checkable Proofs (PCPs) [BSSVW03].
To test whether f is a degree-d polynomial, a natural test is to sample x, y ∼ F n and check whether f (x) agrees with the unique (degree-d, univariate) polynomial obtained by Lagrange interpolation along d + 1 points on the line {x + ty : t ∈ F q }.
Rubinfeld and Sudan introduced a low-degree test using this idea [RS96]. It is given query access to the function f , along with a line oracle function g. Let L denote all lines { a + t b : t ∈ F q } ⊂ F n q , where a, b ∈ F n . Given a description of a line, the line oracle g returns a univariate polynomial of degree d defined on that line. Hence we write g : L → F q [t], where the image of g is understood to only contain degree-d polynomials.
If f is indeed a degree-d polynomial, then one can set g(ℓ) = f | ℓ for all ℓ ∈ L, and the following two-query test clearly accepts.
(i) Select x, y ∈ F n independently, uniformly at random.
They also showed this test is sound: when f is far from degree-d polynomials, the test rejects with high probability.
Ben-Sasson et al derandomized this test by replacing the second uniform sample y with a sample from an ǫ-biased set [BSSVW03]. This modification improves the randomness efficiency of the tests, and therefore the length of the resulting LTC and PCP constructions. Moreover, they showed that the soundness guarantees of low-degree tests are almost unchanged due to the expansion properties of the Cayley graph on F n q . Our constructions of small-bias sets immediately imply improved randomness-efficiency of this low-degree test. Proposition 1.3 (Improved [BSSVW03] Theorem 4.1). Let F q be the finite field of q elements, n ≥ 1, f : F n q → F q a function, and g : L → F q [t] a line oracle. There exists a degree-d test which has sample space size O(q n · n log(q) O(1) ǫ 2+o(1) ). For d ≤ q/3 and sufficiently small δ > 0, if the test accepts with probability ≥ 1 − δ then f has Hamming distance at most 4δ from a degree d polynomial.
Randomness-Efficient Verification of Matrix Multiplication: Let R denote some finite field F q or cyclic group Z q for q ≥ 2. Given A, B, C ∈ R n×n , the matrix multiplication verification problem asks whether AB = C.
Naively, one could multiply A, B and then check whether AB = C entry-wise in O(n ω ) time, where ω ≈ 2.373 [AW21]. A classical result of Freivalds suggests the following much simpler quadratic-time randomized algorithm: Sample x ∈ R n and check whether ABx = Cx [Fre77].
Observe that the entries of ABx and Cx are linear functions of x. Therefore, sampling x from a small-bias set gives a randomness-efficient version of Freivalds' algorithm, at the cost of slightly higher error. Our construction therefore gives the following randomness efficient algorithm for verification of matrix multiplication.
Proposition 1.4. Let R denote a finite field F q or cyclic group Z/qZ. Given matrices A, B, C ∈ R n×n and ǫ-biased set S ⊂ R n , there exists randomized algorithm to decide whether AB = C with one-sided error ( 1 q + ǫ). Its runtime is O(n 2 ) and it uses log( n log(q) O(1) ǫ 2+o(1) ) random bits.
We note that if R = Z, there exists a deterministic O(n 2 ) time algorithm to verify matrix multiplication [KW14]. However, this result relies on the fact that Z has characteristic zero. For the analysis to hold in the case of Z q , we would need a very strong bound on the entries of A, B, C -namely, that max

Related Work
Explicit Constructions: Explicit constructions of expanding generating sets for Cayley graphs have been mostly studied in the pseudorandomness literature in the context of small-bias sets for derandomization. Naor and Naor gave a combinatorial construction over F n 2 of size O( n ǫ 3 ) [NN93]. Alon, Goldreich, Hastad, and Peralta used algebraic arguments to give constructions over finite fields F n of size O( n 2 ǫ 2 ), assuming the field size is bounded as log(|F|) < n log(n)+log(1/ǫ) [AGHP92]. Resarchers in various communities have obtained constructions that achieve size O(poly( n log(|G|) ǫ )), but suboptimal exponents. In number theory and additive combinatorics researchers studying the case of n = 1 gave constructions over Other constructions equivalent to small-bias sets include O( (n−1) 2 ǫ 2 )-sized ǫ-discrepancy sets over finite fields of prime order p when n ≤ p [AM95], and ǫ-balanced codes over finite fields, corresponding to small-bias sets over F n q of size O(n · q) with constant bias [Jus72]. Ta-Shma's tour de force gave the first explicit construction of expanding generating sets of size O( n log(|G|) ǫ 2+o(1) ), nearly attaining the Alon-Roichman bound, but only for the special case of G = F 2 [TS17]. Our work is an extension of Ta-Shma's bias amplification technique to the more general setting of arbitrary abelian groups.
Azar, Motwani, and Naor generalized the study of small-bias sets to finite abelian groups [AMN98]. Over Z n d they used character sum estimates to give a construction of size O((d + n 2 ǫ 2 ) C ), where C ≤ 5 is Linnik's constant [Xyl11]. Assuming the Extended Riemann Hypothesis, C ≤ 2 + o(1) [BS96]. When log(d) ≤ log( n 2 ǫ 2 ) O(C) they improve the size to O((1 + o(1)) n 2 ǫ 2 ). Arvind and Srinivasan proved that one can project small-bias sets over Z n d to any abelian group G n when d is the largest invariant factor of G. Therefore, using the construction from [AMN98] they obtain small-bias sets over G n with the same bias and size as [AMN98], with d = O(log(|G|)) [AS10].
The most general setting is to consider Cayley graphs over non-abelian groups. Wigderson and Xiao derandomized the Alon-Roichman construction using the method of pessimistic estimators [WX08]. Arvind, Mukhopadhyay, and Nimbhorkhar later gave a derandomization for both directed and undirected Cayley graphs using Erdos-Renyi sequences [AMN12]. However, both algorithms require the entire group table of G n as input, rather than just a generating set. Since generating sets are of size O(n log(|G|)), these algorithms are exponentially slower, running in time O(poly(|G| n )) rather than O(poly(n log(|G|)). Nevertheless, they have applications to settings such as homomorphism testing [SW06], which Wigderson and Xiao derandomized using their construction of expanding generating sets [WX08].
Chen, Moore, and Russell obtained generating sets of size O( n ǫ 11 ) over arbitrary groups G n where |G| is a constant [CMR13] . Like Ta-Shma, their technique is to use bias amplification via expander graphs; specifically, they amplify bias via an iterated application of a 1-step random walk on an expander graph. Rozenmann and Wigderson had already noted that this technique amplifies bias for G = F 2 [Bog12]. Chen, Moore, and Russell generalized this analysis to all groups, using techniques from harmonic analysis and random matrix theory [CMR13].
Existing work seems far from obtanining constructions for non-abelian groups near the Alon-Roichman bound. Known work tends to concentrate on special classes of non-abelian groups with some useful algebraic structure. Chen, Moore, and Russell constructed generating sets of size O( (n log(|G|)) 1+o(1) ) for smoothly solvable groups with constant-exponent abelian quotients [CMR13]. Their analysis exploits the structure of solvable groups via Clifford theory. It also hinges on the assumption that the quotients in the derived series have constant exponent.
Arvind et al later gave a construction of sizeÕ( log(|G|) 2−o(1) ǫ 8 ) for solvable subgroups G of permutation groups [AMNV18]. Their construction recursively generates expanding generating sets for quotients in the derived series of the group, and uses the thin sets construction of [AIK + 90] as a base set. Unlike [CMR13] they do not require successive quotients of the derived series to be small; however, their argument does rely on an O(log(n)) upper bound on the length of the derived series for any solvable G ≤ S n , which is not true for solvable groups in general.
Lower Bounds: Alon and Roichman gave a randomized upper bound of O( n log(|G|) ǫ 2 ) on the size of a generating set for any finite G n with spectral gap (1 − ǫ) [AR94]. In the same paper, they gave a nearly matching lower bound when G is abelian, of Ω(( n log(|G|) ). This is a sharper version of the folklore result that an abelian group G n requires O(n log(|G|)) generators for its Cayley graph to be connected.
For non-abelian groups, the existence of sparse expanders means the best lower bound in general is the Alon-Boppana bound. This removes the dependence on |G| and n, only requiring a generating set of size Ω( 1 ǫ 2 ) [Alo86] to achieve spectral gap of 1−ǫ. Indeed, explicit constructions of Ramanujan graphs can be built from Cayley graphs of non-abelian groups [LPS88], and therefore attain this bound.
Expander Walks: Random walks on expander graphs are an essential tool in computer science. Rather than surveying the vast literature, we refer the reader to the surveys [HLW06,Vad12]. Two remarks are in order.
First, our use of wide replacement walks is essentially a way of building expander graphs from other expander graphs. This is thematic of several previous works, such as the zig-zag product [RVW00]. Note that the zig-zag product is just a modification of the replacement product; indeed, the (wide) replacement product itself can be used to give explicit, combinatorial constructions of Ramanujan graphs [BATS11]. Ta-Shma used wide replacement walks to amplify spectral gaps of Cayley graphs on F n 2 [TS17]; this construction relied on previous constructions of expander graphs, although the expander graphs were not required to be Cayley graphs themselves.
Second, the fact that "expanders are good character samplers" is surprising given that characters are sensitive to input perturbations. A recent work of Cohen, Peri, and Ta-Shma uses Fourieranalytic techniques to classify a large class of Boolean functions which can be fooled by expander walks, including all symmetric Boolean functions [CPTS20].

Open Problems
Expanding generating sets of optimal size: The Alon-Roichman theorem proves that every group G n has an expanding generating set S ⊂ G n of size |S| = O( log(|G|) . This construction has not been fully derandomized for any group; even in the case of G n = F n 2 , Ta-Shma's construction only asympotically approaches a size of O( n ǫ 2 ) as ǫ → 0. The actual size of the generating set is O( n ǫ 2+o(1) ), and this o(1) term is seemingly unavoidable when using expander walks [TS17]. (1) ), for finite abelian G. The additional poly log(|G|) factor comes from the bounds on constant-bias subsets of abelian groups; any construction of a constant-bias set S ⊂ G n of size O(n log(|G|)) would immediately give expanding generating sets of size O( n log(|G|) ǫ 2+o(1) ). To our knowledge, not even a candidate construction exists which would give constant-bias subsets of size O(n log(|G|)) for abelian groups; this is an interesting and potentially easier open problem, since it requires none of the expander walks machinery that we need to get arbitrarily small ǫ.

Similarly, our algorithm gives an expanding generating
There is a candidate construction that could beat the Alon-Roichman bound for G = F 2 , based on algebraic-geometric codes [BATS13]. The code construction would give an ǫ-biased set S ⊂ F n 2 of size |S| = O( n ǫ 2 log(1/ǫ) ), assuming a conjecture in algebraic geometry. The authors themselves note that they have "no idea" whether this conjecture is valid [BATS13].
Expanding generating sets of non-abelian groups: While wide replacement walks amplify bias quite naturally for abelian groups, it is unclear whether they can do so for general groups. Dealing with matrix-valued irreducible representations, rather than scalar-valued characters, makes the analysis of bias amplification considerably more involved; hence even the analysis of the 1-step walk is nontrivial [CMR13]. It would be very interesting to see whether one can place algebraic conditions on a group that are weaker than commutativity, but still ensure that the wide replacement walk amplifies bias.
Existing works on expanding generating sets for non-abelian groups have studied solvable groups, which generalize abelian groups [CMR13,AMNV18]. However, if we restrict the algorithm to input instances which are all non-abelian groups, then existence results suggest that one should be able to beat the Alon-Roichman bound.
For example, it is known that for every finite simple non-abelian group G n , there exists a generating set S ⊂ G n such that Cay(G n , S) has spectral gap 1 − ǫ, and |S| is independent of n [BL18]. Therefore, restricting input instances to simple groups seems too easy, while an algorithm for all groups seems too hard. Is there some natural natural class of non-abelian, non-simple groups for which algorithms can efficiently find expanding generating sets near (or even below) the Alon-Roichman bound?
Decoding over any finite field: A recent work of Jeronimo et al gives a decoding algorithm for a modified version of Ta-Shma's codes [JQST20]. Since our work gives ǫ-balanced codes over any finite field, it would be interesting to extend both the modification of the codes and the decoding algorithm of [JQST20] to this general setting.
Classifying the power of expander walks on groups: So far we have discussed how random walks on expanders are good samplers in various ways, such as the expander Chernoff bound, parity sampling, and character sampling. Cohen, Peri, and Ta-Shma study the class of all Boolean functions that expander walks fool [CPTS20]. It would be very interesting to extend their results to functions on groups, perhaps using similar tools from harmonic analysis and representation theory. For example, for which groups G besides F 2 do expander walks fool all symmetric functions on G n ?

Cayley Graphs and Expanders
In this paper we are concerned with the expansion of a particular kind of graph called a Cayley graph. We begin with some preliminaries on graphs and group theory.
Let A ∈ C n×n be the (weighted) adjacency operator of G, and let M = 1 d A be the normalized adjacency operator, also known as the random walk matrix. Let the eigenvalues of M be denoted λ n ≤ ... ≤ λ 2 ≤ λ 1 = 1, counting multiplicity. Then G is a one-sided spectral expander if λ 2 < 1 − Ω(1), and G is a two-sided spectral expander if Throughout this paper, when speaking of expander graphs we will mean two-sided spectral expanders. We will commonly use λ(G) to denote the second eigenvalue in absolute value of a graph G.
Next, we define Cayley graphs, which are a type of graph whose vertices correspond to elements of some group, and whose edges are defined by the group operation.
Definition 2.2. (Symmetric generating set) Let G be a group and S ⊂ G. We say that S is symmetric if for all s ∈ S, s −1 ∈ S. Further, S is a generating set if for all g ∈ G there exist s 1 , ..., s k ∈ S (possibly repeated) such that s k · · · s 1 = g We write S = G. Definition 2.3. (Cayley Graph) Let G be a group and S ⊂ G be a symmetric generatring set, and w : S → R ≥0 a weight function. The Cayley graph Cay(G, S, w) is the graph with vertex set G and edge set {{g, g · s} : g ∈ G, s ∈ S}. The weight of an edge {g, g · s} is w(s).
We will require the total weight of S to be normalized to |S| by convention. Notice that since S is symmetric, we can consider the graph Cay(G, S) to be an undirected and weighted |S|-regular multigraph.
The eigenvectors of abelian Cayley graphs are described by their characters.
Definition 2.4. Let C * be the multiplicative group of nonzero complex numbers. For any finite abelian group G, the characters of G, denotedĜ, are the set of all homomorphisms χ : G → C * .
Proposition 2.5. Let G be a finite abelian group and S ⊂ G a symmetric generating set. Then the eigenvalues of Cay(G, S) are given by We remark that one can generalize this definition to non-abelian groups by replacing characters with equivalence classes of irreducible unitary representations -see, e.g. [CMR13]. For abelian groups the only such representations are character functions, so it suffices to discuss characters for our purposes.
Notice that any group has a trivial character χ : G → C * such that χ(g) = 1 for all g. The eigenvalue corresponding to the trivial character is always 1. Therefore, for a Cayley graph to be an expander we need bounds on all of its nontrivial characters. This leads to the definition of an expanding generating set for an abelian Cayley graph, which is also known as a small-bias set.
Definition 2.6 (Small-bias distributions for abelian groups). Let G be a finite abelian group and D ∼ G a random variable. For any character χ of G, the bias of D with respect to χ is Let χ 0 denote the trivial character. The bias of D is its maximum bias with respect to nontrivial characters.
If S ⊂ G, then bias(S) is the bias of the uniform distribution on S. If S is a symmetric generating set, λ(Cay(G, S)) = Bias(S).
Notice that if S is non-negatively weighted, we can normalize weights to sum to 1 and obtain a (not necessarily uniform) distribution on S. Then the bias of S is just the bias of this distribution.
In this language, the Alon-Roichman Theorem asserts that a random subset of G of size ) is ǫ-biased with high probability [AR94]. Finally, we will need a few more facts about characters of abelian groups. Definition 2.8. (Direct sum of groups) Let A, B be abelian groups. The direct sum A ⊕ B is the abelian group whose elements belong to the Cartesian product A × B. For (a 1 , b 1 ), (a 2 , b 2 ) ∈ A × B, the group operation is Notice that the direct sum is associative. For abelian groups A, B, C, (A⊕B)⊕C ∼ = A⊕(B ⊕C). So we can write A ⊕ B ⊕ C without ambiguity.
Proposition 2.9. (Fundamental theorem of finite abelian groups) Let G be a finite abelian group. Then G is isomorphic to a direct sum of cyclic groups. That is, there exist d 1 , ..., d k ≥ 2 such that We refer to Z d 1 ⊕ · · · ⊕ Z d k as the invariant factor decomposition of G. The integers d 1 , ..., d k are the invariant factors.
From the above propositions one can show that the characters of a finite abelian group are products of maps of the form x → ω j·x d i . This structure is crucial to our overall argument.
As a special case, consider G = F n 2 . The characters of F n 2 are precisely the elements of the Fourier basis for the vector space of functions {f : {−1, 1} n → C}. Fix any T ⊂ [n]. The character χ T : {−1, 1} n → C is given by the parity function on T .
The trivial character corresponds to T = ∅. From this it is easy to see that an ǫ-biased set S ⊂ F n 2 is also balanced, in the sense that its expected parity on any non-empty substring is close to

Wide Replacement Walks
Our algorithm performs a random walk on a wide replacement walk of expander graphs. In this section we define what it means to take a wide replacement walk.
Let G be a D 1 -regular graph on N 1 vertices and H be a D 2 -regular graph on D 1 vertices. The replacement product G r ○H is a (D 2 + 1)-regular graph on N 1 · D 1 vertices. Each vertex of G (the "outer graph") is replaced by a copy of H (the "inner graph"). We call these copies clouds.
The intra-cloud edges in each cloud of G r ○H are just the edges from H. However, G r ○H also has inter -cloud edges which arise by identifying the D 1 vertices of H with the D 1 incident edges of a vertex v ∈ V (G). This identification requires that we number the edges of every vertex in G. We formalize this with the concept of a rotation map.
Definition 2.10. (Rotation map) Let G be a D-reguluar graph such that the edges incident to every v ∈ V (G) are numbered 1, ..., D. Formally there is a function N : Then a rotation map is a function Rot : such that for all v, w ∈ V and i, j ∈ [D], Rot(v, i) = (w, j) iff the i th neighbor of v is w and the j th neighbor of w is v.
For technical reasons, we need a special kind of rotation map called a local inversion function. This is a rotation map where if (v, i) maps to (w, j) then j only depends on i.
Definition 2.11. (Local inversion function) Let G be a D-regular graph with a rotation map Rot : We are ready to define the wide replacement product walk. Instead of the usual inner graph H we use a "wide" inner graph on D s 1 vertices for some integer s ≥ 1. The vertices of H correspond to s-tuples that define s local inversion functions. The walk cycles through them.
To take a step in the usual replacement product walk, we start at some vertex v ∈ G r ○H then compose two steps: an intra-cloud step which changes the H-component, and an inter-cloud step which changes the G-component. Every vertex in G r ○H is incident to a unique inter-cloud edge; therefore, there is only one choice of neighboring cloud, and so the position after the intra-cloud step determines the entire step.
The s-wide replacement walk modifies the inter-cloud step so that there are s choices during inter-cloud step. If G is D 1 -regular, then a vertex of H corresponds to some vector (a 0 , ..., a s−1 ) ∈ [D 1 ] s . The wide replacement walk maintains a clock which tracks how many steps have been taken.
At time step t, the clock is set to ℓ = t mod s, and the inter-cloud step moves to a neighboring cloud according to the value of a ℓ ∈ [D 1 ].
After deciding which neighboring cloud to move to, the choice of which vertex in the cloud to land in is also determined by a ℓ . The walk updates the H-component by feeding the ℓ th coordinate to the local inversion function φ G : [D 1 ] → [D 1 ] of G, and leaving all other coordinates unchanged. So (a 0 , ..., a s−1 ) ∈ [D 1 ] s is mapped to (a 0 , ..., a ℓ−1 , φ G (a ℓ ), a ℓ+1 , ..., a s−1 ). This completes the intercloud step.
The utility of the wide replacement walk is that the H-component of a vertex now stores O(s log(D 1 )) bits of information, rather than just O(log(D 1 )) bits. As we discussed in the introduction, the barrier to bias amplification is when the walk distribution is uniform within clouds. Now, the values of the H-component are precisely the instructions for the inter-cloud steps of the walk; therefore, the fact that the H-component is uniform is no longer bad news, since it means that the inter-cloud steps of the replacement walk imitate the truly random walk on the outer graph for the next s steps.

Set
Step A few remarks are in order. First, notice that the number of random bits needed to specify a random step is only O(log(D 2 )), despite the fact that we are moving on a graph with V (G) × V (H) vertices. This will be crucial in the analysis of the tradeoff between bias amplification and size increase of the small-bias set.
Second, once a value of t is fixed, so the clock is set to ℓ = t mod s, the wide replacement walk can be regarded as taking a usual step in the usual replacement walk. The intra-cloud step is unchaged, and the inter-cloud step depends only on the ℓ th coordinate of the H-component.
Since we have specified what it means to take a random step, this is sufficient to describe the walk. We simply initialize at a uniform vertex of V (G) × V (H) and then take some number of steps, to be chosen later.

Expanding Generating Sets for Abelian Groups
Throughout this section, let G be a finite abelian group and n ≥ 1. In this section, we will describe an efficient deterministic algorithm to construct a generating set S ⊂ G n such that the Cayley graph Cay(G n , S) has second eigenvalue at most ǫ. The degree is |S| = O( n log(|G|) O(1) ǫ 2+o (1) ). The inputs to our algorithm are a generating set G ′ ⊂ G, integer n ≥ 1, and desired expansion ǫ > 0. The algorithm proceeds as follows: (i) Construct an ǫ 0 -biased set S 0 ⊂ G n with support size O(n log(|G|) O(1) ) for a constant ǫ 0 < 1.
(ii) Perform a wide replacement walk to amplify the bias of S 0 to ǫ. Specifically, we identify S 0 with the vertices of an outer graph Γ, and then choose an inner graph H in a manner described later. We emphasize that while Γ is an expander graph whose vertex set is S 0 , it is not required to be a Cayley graph on S 0 . For the purposes of this step, the group structure of G is irrelevant.
Let t ≥ 1 be the walk length, to be chosen later. The output ǫ-biased set S ⊂ G n corresponds to length-t walks on the wide replacement product of Γ and H. Given a sequence of vertices (x 0 , ..., x t ) ∈ V (Γ) × V (H), we add up the components corresponding to V (Γ), which are just elements of S 0 , to obtain some element of G n . This gives the elements of S.
Next, let us informally describe parameter choices (precise choices are in section 3.4). Let D 2 be the degree of H. At every step in the wide replacement walk we need to specify some i ∈ [D 2 ] to take a step. It follows that S ⊂ G n has a size of O(n log(|G|) O(1) · D t 2 ). We must choose t large enough to shrink the bias to ǫ. The choice t (walk length) and D 2 (degree of the inner graph) will determine the overall size of the output generating set.
These choices hinge on the bias amplification bound of the wide replacement walk. We show that the s-wide replacement walk shrinks the bias by a factor of O(s 2 · λ(H) s−3 ) every s steps. However, the size of the walk distribution grows by a factor of O(D s 2 ) every s steps. This imperfect bias amplification is why we cannot get optimal dependence on ǫ, as that would require that the bias shrinks by exactly O(λ(H) s ) every s steps.
This section is organized as follows. In section 3.1, we describe how one can identify the elements S 0 with the vertices of an expander graph, and then perform the ordinary random walk on the graph to amplify the bias of S 0 , albeit suboptimally. In section 3.2 we show how to express the bias of a wide replacement walk algebraically. In section 3.3 we prove an upper bound on this algebraic expression, therefore proving the bias amplification bound of the wide replacement walk. Finally, in section 3.4 we describe the details and exact parameters for the wide replacement walk, as well as the ǫ 0 -biased subset of G n .

The ordinary expander walk
Let G be a finite abelian group. For ease of notation, we will refer to G rather than G n until section 3.4, when we need to discuss parameters. Since H n is a finite abelian group for all abelian H, there is no loss of generality.
In this section we will show how to amplify the bias of a small-bias set in G by performing a random walk on an expander. This will be a lemma in the analysis of our actual construction, which involves a wide replacement walk.
To state the bias amplification theorem, we need some notation. Let G = Z d 1 ⊕ · · · ⊕ Z d k be the invariant factor decomposition of G. Notice that d i |d j for any i < j. In particular, all d i divide d k . For x ∈ G write x = (x 1 , ..., x k ), so that x i ∈ Z d i for each i.
Fix a nontrivial character χ : G → C * corresponding to a group element a ∈ G. Let a = (a 1 , ..., a k ). Then for a given x ∈ G, χ(g) = ω a 1 ·x d 1 · · · ω a k ·x d k . Since all d i divide d k , we can write this as Now, let S init ⊂ G have bias ǫ 0 . Identify S init with the vertices of some degree-regular expander graph Γ. We write V := V (Γ) = S init . In order to understand the bias of a random walk on Γ with respect to χ, we have to track how often the walk enters vertices which map to ω d k , ω 2 d k , and so on. We will partition S init as follows. For y ∈ Z d k , let S y be the elements of S init which are mapped to ω y d k by χ. Formally, Next, let t > 0 be the walk length. We will partition all length-(t + 1) sequences in S init according to their sum. For y The set S y corresponds to some subset of the vertices of Γ. Therefore we can identify S y with an |S y |-dimensional subspace of C V . Let Π y : C V → C V be the projection matrix onto this subspace. Let Π = y∈Z d k ω y d k Π y . We write Π = Π(χ) to indicate the dependence on choice of χ.
We can now state the bias amplification theorem for ordinary expander walks.
Theorem 3.1 (Ordinary t-step expander walk). Let S init ⊂ G have bias ǫ 0 and let Γ = (S init , E) be a d-regular expander graph with λ(Γ) = λ < 1. Suppose D ∼ G is the distribution induced by beginning at a uniform vertex and taking a t-step random walk (x (0) , ..., x (t) ) and then adding the results of the walk to get an element ( i x (i) ) ∈ G. Let χ * : G → C * be the nontrivial character which maximizes the bias of D. Let Π = Π(χ * ), and · be the matrix operator norm. Finally, abusing notation, let Γ be the random walk matrix of Γ. Then, 1 be the normalized all-ones vector. Let a * ∈ G be the element corresponding to χ * . Let (a * 1 , ..., a * k ) ∈ Z d 1 ⊕ · · · ⊕ Z d k denote a * written in the invariant factor decomposition. Let W ∼ V t+1 denote the distribution of all t-step walks on Γ. Let (x (0) , ..., x (t) ) ∼ W be some sequence of random walk steps. So x (0) ∼ S init (since the walk begins at a uniformly random vertex) x (i+1) is a uniformly random neighbor of Recall that we use subscripts to denote invariant factors, so x = (x 1 , ..., We have thus obtained an algebraic expression for the bias of the walk distribution, which we will now upper-bound. Theorem 3.2 (Matrix norm bounds). Let Π, Γ be as before.
Restricting to unit vectors v, it follows that Π = 1.
(ii) Let v ∈ C S be a unit vector. Let v be its projection onto 1 (the one-dimensional subspace of parallel vectors), and let v ⊥ be its projection onto the orthogonal complement 1 ⊥ . Then Let u = 1 √ |S| 1 be the normalized all-ones vector. Let λ := λ(Γ). Then observe that It remains to show that (Πu) ≤ ǫ 0 . Observe that We conclude that (ΠΓ) 2 v ≤ ǫ 0 + 2λ.
Combining the two propositions in this section, it follows that a t-step walk amplifies the bias to (ǫ 0 + 2λ) ⌊t/2⌋ .

The wide replacement walk
In this section and the subsequent one, we will show how the wide replacement walk amplifies bias more efficiently than an ordinary expander walk. We will proceed in a similar manner to the last section, by first obtaining an algebraic expression for the bias of the random walk distribution, and then upper-bounding the algebraic expression in section 3.3.

Setup
Let Γ = (S init , E) be a graph whose vertices are some constant-bias set S init ⊂ G as before. Suppose Γ is D 1 -regular. Let φ Γ : [D 1 ] → [D 1 ] be the local inversion function of Γ.
Let s > 0 be an integer, and let H be a D 2 -regular expander graph on [D 1 ] s vertices. We will abuse notation and use Γ, H to denote the random walk matrices of Γ, H respectively.
. We define three operators on V 1 ⊗ V 2 that we need to describe the bias of the wide replacement walk.
For i ∈ [s] define the projection matrix P i : . Then let P i : V 2 → C D 1 be the projection onto this subspace.
Given some v 1 ∈ V 1 and j ∈ [D 1 ], the vector v 1 [j] ∈ V 1 is a permutation of the coordinates of v 1 based on the mapping of each vertex to its j th neighbor in Γ 2 . This corresponds to taking a step in Γ, by moving along the edge numbered j incident to the current vertex. Γ . We are ready to define the three operators which describe the bias of the wide replacement walk.Ḣ Note that each of these operators is a tensor product of operators on V 1 , V 2 , and hence preserves tensor products.
Moreover, noticeḢ,Γ t mod s are precisely the transition matrices of the H-step and Γ-step in the wide replacement walk at time t.
For a character χ : G → C * letΠ(χ) = y∈Z d k ω y d kΠ y (χ).Π plays the role of Π from the analysis of the ordinary expander walk.

Algebraic Expression for the Bias
In this section we will express the bias of the wide replacement walk distribution in terms of the matrix norms ofL 0 , ...,L s−1 .
Proposition 3.3 (t-step s-wide replacement product walk). Let G be a finite abelian group. Let S init ⊂ G have bias ǫ 0 and let Γ = (S init , E) be a D 1 -regular expander graph. Let H be a D 2 regular expander on [D 1 ] s vertices for some integer s ≥ 1.
Let D walk ∼ G be the t-step s-wide replacement product walk distribution. It is defined by beginning at a uniform vertex and performing an t-step wide replacement wide on V (Γ) × V (H). Given a sequence of vertices ((a 0 , b 0 ), ..., (a t , b t )) ∈ V (Γ) × V (H) obtained from a walk, we output ( i a i ) ∈ G. Then D walk ∼ G is the distribution induced by taking all such t-step walks.
Let a * ∈ G be the element corresponding to the the character χ * . Recall that G ∼ = Z d 1 ⊕· · ·⊕Z d k and we write z ∈ G as z = (z 1 , ..., z k ), where z i ∈ Z d i . In particular a * = (a * 1 , ..., a * k ) where each a * i ∈ Z d i . For y ∈ Z d k let S y ⊂ S init be the elements mapped to ω y d k by χ * . Let T y ⊂ Z t+1 d k be sequences which sum to y.
Let W ∼ (V (Γ) × V (H)) t+1 be the distribution of all length-t wide replacement walks, starting at a uniform vertex.
Next, let u 1 ∈ V 1 , u 2 ∈ V 2 be the all-ones vectors scaled to be unit vectors in the 2-norm. Let u = u 1 ⊗ u 2 .
Let v (0) , ..., v (t) ∈ V 1 ⊗ V 2 be the distribution of steps corresponding to W . Note that v (0) is the all-ones vector scaled by 1 |V (Γ)×V (H)| (since the walk begins at a uniformly random vertex), and v (i+1) proceeds by taking a step in the wide replacement product graph from the distribution v (i) . In particular, v (i+1) ∈ V 1 ⊗ V 2 , since bothΓ,Ḣ tensorize and the walk begins at v (a, b) 1 = a and (a, b) The output of the random walk for some sample The bias of D walk is thus: We have shown how to express the bias of the replacement walk distribution algebraically. It remains to be shown that this matrix norm is indeed bounded. To show that the wide replacement walk gains from s − O(1) out of every s steps, we need to show that L s−1 · · ·L 0 ≤ λ(H) s−O(1) . We will do this in the next section.

Bounding the matrix norm
In the previous section we showed that the bound the bias of the wide-replacement walk distribution, it suffices to bound the operator norm of the following matrix, defined with respect to the worst-case character χ * of the walk distribution:L s−1 · · ·L 0 This is almost exactly the same matrix as the one analyzed in [TS17]. The difference is that the operatorΠ, instead of tracking how often the walk enters the sets in a bipartition of S init , now tracks how often the walk enters the sets in a d k -way partition of S init . Here d k = Ω(log(|G|)) is the largest invariant factor of G.
As a consequence, the diagonal entries ofΠ now come from the d k th roots of unity, rather than {±1}. The analysis of the matrix bound from [TS17] mostly carries through, although working over C V 1 ⊗ C V 2 rather than the reals will require some care.
As in [TS17], our argument will proceed by considering arbitrary vectors v, w and analyazing v,L s 1 · · ·L 0 w . We will repeatedly decompose the vectors into their parallel and perpendicular components. Let V = V 1 ⊗ 1 denote vectors whose H-component is a scalar multiple of 1 ("parallel vectors"), and V ⊥ = (V ) ⊥ ("perpendicular vectors").
Because of the spectral expansion of H, every time a vector is in V ⊥ we can show it shrinks by a factor of λ(H). The hard case is when vectors are in V . Here, we will prove a technical lemma which is a straightforward generalization of the core lemma in [TS17]. The lemma shows if the walk distribution is in V , then any sequence of s steps imitates a random walk of s steps on the outer graph Γ. This allows us to argue that the bias is amplified as though taking the ordinary random walk on Γ. If the bias so far is α, then this scales the bias by α → (α + 2λ(Γ)) s/2 after s steps. Notice that this step uses the bias amplification of the ordinary expander walk on Γ.
This turns out to be enough. Let ǫ 0 = bias(S init ) be the bias of the initial set S init ⊂ G. Since ǫ 0 is a constant, we can select graphs Γ, H such that ǫ 0 + 2λ(Γ) ≤ λ(H) 2 . Therefore, while we do not gain a factor of (λ(Γ)) s every s steps, we will gain according to a factor of (λ(H)) s−O(1) . Since λ 2 is bounded away from 1, the difference between gaining according to λ(Γ) or λ(H) does not matter asymptotically.
Therefore, whether in the V ⊥ or V case, we shrink the bias by a factor of λ(H) s−O(1) for every s steps.

Action on Parallel Vectors
In this section we will prove that any sequence of s steps imitates a random walk of s steps on the outer graph Γ. This allows us to avoid the issue of getting stuck in "parallel vectors" in our overall parallel-perpendicular decomposition argument.
We begin with an operator-averaging lemma.
Proposition 3.4 (Operator-Averaging, [TS17] Claim 14). Let Ω be a finite set and P, Q probability distributions on Ω. Let P − Q 1 denote the difference of the distributions in the 1-norm. Further, let {T x } x∈Ω be a family of linear operators on C n indexed by Ω, such that for all x ∈ Ω, T x ≤ 1.
If we unravel the definition, this is simply requiring that H is compatible with the edge labeling of Γ in precisely the way that we want. Pseudorandomness is a strong condition on H which, by definition, guarantees the wide-replacement walk imitates the ordinary walk on Γ in a suitable sense.
With this definition we can return to proving the lemma. We will begin by proving the pseudorandomness claim for the case where D 2 = 1. The case of general D 2 will follow by an application of operator averaging.
For any τ = τ 1 ⊗ 1 V (H) and υ = υ 1 ⊗ 1 V (H) , Proof. First, we consider the action of anL i on a general product vector when D 2 = 1. Let (u 1 ⊗ u 2 ) ∈ V 1 ⊗ V 2 . By the Birkhoff-von Neumann Theorem the random walk matrix Γ is an average of D 1 permutation matrices. Let Γ = 1 where each G r is a permutation matrix. At step i, the Γ-step in the replacement walk is chosen according to the i th coordinate of the H-vector. The H-vector itself is just the distribution a random step in H, starting from u 2 .
We need two new notations. First, let Ξ j i : C V 2 → C V 2 denote the permutation matrix corresponding to ξ j i , so thatΞ j i = I ⊗ Ξ j i .
Second, let ψ (i) Γ be the operator which applies the local inversion function φ Γ to the i th coordinate and leaves all else unchanged.
By assumption, since (j 0 , ..., j ℓ−1 ) is ζ-pseudorandom with respect to Γ, the distribution Z is ζ-close to the uniform distribution on [D 1 ] ℓ in the L 1 -norm. In other words, the inter-cloud steps taken in the replacement product walk are close to imitating an ordinary random walk on Γ. Explicitly, the expectations of each distribution are: Notice that Π ≤ 1, since it is just a sum of disjoint projections scaled by roots of unity. Moreover, G i ≤ 1 for all i, since G i is simply a permutation matrix. It follows that ΠG z ℓ−1 · · · ΠG z 0 ≤ 1 for all (z 0 , ..., z ℓ−1 ). Therefore, we conclude by operator averaging that Next, proving the general case where D 2 = 1 follows from another application of operator averaging. In particular, the matrix H is the average of D 2 permutation matrices. We will average over the choice of permutation in H.

A bound for the algebraic expression of bias
In the previous section we proved a technical lemma which allows us to circumvent the issue of getting stuck in parallel vectors. With this lemma, we are ready to prove our main theorem which bounds the matrix norm ofL s 1 · · ·L 0 . Our argument will proceed by considering the action of the matrixL s 1 · · ·L 0 on an arbitrary vector, and then repeatedly decomposing vectors into their V and V ⊥ components. Because of the spectral expansion of H, every time a vector is in V ⊥ we can show it shrinks by a factor of λ 2 = λ(H).
The hard case is when vectors are in V . Here, we will use the technical lemma from the previous section to argue that any sequence of s steps imitates a random walk on the outer graph Γ. This allows us to argue that the bias is amplified as though taking the ordinary random walk on Γ. This scales the bias by (ǫ 0 + 2λ 1 ) s/2 at every s steps.
This turns out to be enough, as we can assume that ǫ 0 + 2λ 1 ≤ λ 2 2 . Therefore, while we do not gain a factor of (λ 1 ) s every s steps, we will gain according to a factor of (λ 2 ) s . Since λ 2 < 1, the difference between gaining according to λ 2 or λ 1 does not matter asymptotically. Notice that the bias amplification of the ordinary expander walk turns out to be crucial for the wide replacement walk.
Therefore, whether in the V ⊥ or V case, we gain a factor of λ for every s steps.
Theorem 3.8 (Bounding algebraic expression for bias). Suppose that: Then we obtain the following bound for the bias of the walk after s steps.
Proof. For a (column) vector v, let v * denote its conjugate transpose. Let w s , x 0 ∈ C |V 1 |·|V 2 | be unit vectors which maximize the bilinear form w * sLs−1 · · ·L 0 x 0 , so that w * sL s−1 · · ·L 0 x 0 = L s−1 · · ·L 0 We will repeatedly apply the parallel-perpendicular decomposition from the left and right hand side of the expression. Let us define some additional notation. First, for any linear operator M let M * denote its adjoint (e.g. its conjugate transpose). We define the following "intermediate" vectors which will arise in the decomposition.
Next, we can decompose from the right side to obtain: Next, we decompose from the left side. Let 0 ≤ i ≤ s − 1. Then We can continue in this manner. Notice that since 1 is odd that w s−2 =Ḣ(Γ s−1Π w s−1 ) ⊥ , since (Π * ) * = Π. Further, notice that since w i ∈ V ⊥ , that w * i x i = 0. Therefore, we continue our decomposition to obtain Combining expressions, we obtain: Next, we bound each of the terms above in absolute value. We will separate the expression into three terms: First term: The above analysis of x s does not depend on the value of s, so we also obtain a corollary of Second term: Next, notice that for even values of i ≥ 0, The case for odd i attains the same bound, since Π * ≤ 1. Next, Therefore, since w s ≤ 1 we obtain w s−i ≤ λ(H) i . We are ready to bound the second term in the overall expression.
Third term: Finally, the third term in the expression collects all of the "leftover" terms which could not be simplified through parallel-perpendicular decomposition. These are precisely the parallel components of the vectors obtained at each step of the decomposition. To bound this term we will use the technical lemmas about the action of theL i operators on parallel vectors, which in turn use the pseudorandom machinery from the wide replacement product.
Consider some (i, j) such that 0 ≤ i < j ≤ s − 1. We wish to bound p * jL j−1 · · ·L i x i . Then p j = p 1 j ⊗ 1 V 2 and x i = (x i ) 1 ⊗ 1 V 2 . Since H is ζ-pseudorandom with respect to φ Γ , it follows that Therefore, up to an additive error factor, the action of the replacement walk on parallel vectors is the same as the action of a truly random walk on the outer graph Γ. We have already analyzed this walk, and as we argued, it amplifies bias by a factor of (ǫ 0 + 2λ(Γ)) every two steps. Therefore, We can therefore bound the third term by s−1 i=0 s−1 j=i+1 p * jL j−1 · · ·L i x i ≤ s 2 · (λ(H) s−2 + ζ). Putting it all together, we conclude

Parameters of the Construction
In this section we describe how to optimize parameters such that the wide replacement walk construction achieves our desired support size. Our construction and hence the parameters we choose are almost identical to those discussed in Section 5 of [TS17]. The algorithm is given integer n ≥ 1, desired second eigenvalue ǫ > 0, and an arbitrary generating set for a group G.
It first generates an ǫ 0 -biased set S init ⊂ G n of size O( n log(|G|) O(1) poly(ǫ 0 ) ) for a constant ǫ 0 . For concreteness we set ǫ 0 = 0.1. Proposition 3.9. There exists a deterministic, polynomial time algorithm which, given a generating set for an abelian group G and integer n ≥ 1, outputs a generating set S init ⊂ G n of size O(n(log(|G|)) O(1) ) such that the Cayley graph has second eigenvalue at most 0.1.
Proof. First, by Theorem 4 of [CMR13], we can construct a generating set S ⊂ G with second eigenvalue (1 − C log log(|G|) + β) for a parameter β and universal constant C. Its size will be |S| = O( n log(|G|) β O(1) ) = O(n log(|G|) 2 ). Setting β = C 2 log log(|G|) , we obtain second eigenvalue (1− C 2 log log(|G|) ). Next, we can amplify the bias of S to 0.1 by taking a t-step ordinary expander walk. By the results of section 3.1, if we take a walk on a D-regular expander graph with second eigenvalue λ and D = O(1), then the t-step walk will amplify the bias to ((1 − C 2 log log(|G|) ) + 2λ) ⌊t/2⌋ . For this quantity to be at most 0.1, it suffices to set t > log log(|G|)
We remark that for the constant-error regime, this construction obtains almost the same parameters as that of [AMNV18], who deal with the case of Z n d . Their construction can be easily extended to any arbitrary abelian group via the projection lemma of [AS10], although it will have additional low-order terms in the size of the generating set.
Next, the algorithm performs a wide replacement walk. We must specify the inner and outer graphs as well as the number of steps. Our parameters are almost identical to [TS17]. We include them here for completeness.
Proposition 3.10. The t-step wide replacement walk distribution is ǫ-biased.
Proof. The bias after t steps is given by (λ(H) s + sλ(H) s−1 + s 2 λ(H) s−2 ) ⌊t/s⌋ . Therefore, The last step follows by assumption on t.
Proposition 3.11. The support size of the wide replacement walk distribution is O(|S init |· 1 ǫ 2+O(α) ), where S init is the initial constant-bias set.

Applications
In this section, we will demonstrate the algorithmic applications of our construction of expanding generating sets for abelian Cayley graphs. As before let G denote a finite abelian group and n ≥ 1 an integer.

Almost k-wise independence
Let D ∼ G n and U denote the uniform distribution on G n . We say that D is (ǫ, k)-wise independent if for every I ⊂ [n] of size k, the restriction of D onto I-indices, denoted D I , is ǫ-close to U I in statistical distance. Let ∆ denote statistical distance. Vazirani's XOR Lemma asserts that if G = F 2 and D is ǫ-biased, then ∆(D, U ) ≤ ǫ · √ 2 n . In other words, if D is near-uniform in a weak sense (namely, if D is ǫ-biased), then D is also near-uniform in a strong sense (with respect to statistical distance), at the cost of a √ 2 n factor. From the proof of the lemma, it is easy to see that D is also (ǫ · √ 2 k , k)-wise independent for every k ≤ n.
Vazirani's XOR Lemma generalizes straightforwardly to the case of an arbitrary abelian group G. For the sake of completeness we include the proof here.
First, we need a lemma concerning Fourier coefficients of the uniform distribution. Proof. (i) By definition χ(g) = 1 for any g ∈ G n , so Ex∼D [χ(x)] = 1 for any D.
(ii) First, consider the special case G = Z d for some d ≥ 2. Then a nontrival χ : G n → C corresponds to some a ∈ Z n d \ { 0}. Observe that x, U is uniform on Z d , where the inner product is taken modulo d. Therefore Ex∼U [χ(x)] = Ex∼U [exp( 2πi d a, x )] = 0. Next, for arbitrary abelian G, observe that G = Z d 1 ⊕ · · · ⊕ Z d k . Any nontrivial character χ on G n is a product of characters on the factor groups Z d i . We have already shown each of these characters has expectation 0 on uniform inputs. The result follows from k = 1 case.
Next, we can prove our claim.
The last step is due to Plancherel's Theorem.
A special case of this fact is shown in [AMN98] Theorem 4.5, when G is replaced with a finite field of prime order.
As a corollary, an ǫ-biased distribution has statistical distance at most ǫ · |G| k from a k-wise independent distribution, since the latter is uniform on sets k indices, and a restriction of an ǫbiased set to any subset of indices is still ǫ-biased. Therefore, to obtain an (ǫ, k)-wise independent distribution we simply construct a distribution with bias ǫ √ |G| k . This requires a support size of O( n log |G| O(1) ·|G| k+o(1) ǫ 2+o(1) ) = O( n·|G| k+o(1) ǫ 2+o(1) ). The following proposition follows immediately. Proposition 4.3 (Almost k-wise independent sets over abelian groups). Let G be a finite abelian group, and k ≤ n be positive integers. For any input ǫ > 0 and generating set of G, there exists a deterministic, polynomial-time algorithm whose output is an (ǫ, k)-wise independent distribution over G n . The support size is O( n·|G| k+o(1) ǫ 2+o(1) )

Remote Point Problem
Let G be a group and H ≤ G n a subgroup given by some generating set H ′ ⊂ H. For a given G, H and integer r > 0, the Remote Point Problem is to find a point x ∈ G n such that x has Hamming distance > r from all h ∈ H, or else reject. Alon, Panigrahy, and Yekhamin introduced the Remote Point Problem over G = F 2 [APY09]. Later, Arvind and Srinivasan generalized the problem to any group, and extended the algorithm of Alon, Panigrahy, and Yekhamin to the generalized setting [AS10].
Their algorithm proceeds in essentially three steps. For a subgroup H ≤ G n , let its dimension be dim(H) := log |G| (H).
Upon an input H ≤ G n of dimesion k ≤ n/2, (1) Compute subgroups H 1 , ..., H m which cover H, each of which has dimension ≤ 2n/3. We obtain m = n O(c) for a constant c which controls how good our output distance is.
(2) Construct a symmetric multiset S ⊂ G n such that the Cayley graph Cay(G n , S) has λ(Cay(G n , S)) ≤ α. They require α ≤ 1 m 2 ≈ 1 n 20c . (3) Exhaustively search S for a point which is outside of i H i . Return that point s. Let d H denote Hamming distance on G n . From arguments in [AS10] it follows that d H (x, H) ≥ cn log(k) k for dimension k. The size of |S| is a bottleneck in the algorithm of [AS10]. In general they obtain expanding generating sets of size O((log(|G|) + n 2 ǫ 2 ) 5 ), and for log(|G|) ≤ log( n 2 ǫ 2 ) O(1) this is improved to O( n 2 ǫ 2 ). Therefore, we shrink the support size of S by a factor of at leastÕ(n) and hence speed up the exhaustive search step (3).

Randomness-Efficient Low-Degree Testing
Let F q be a finite field of q elements, n, d ≥ 1, and f : F n q → F q . The low-degree testing problem is to determine whether f is a degree-d polynomial or far from all such polynomials in Hamming distnace.
In the line oracle model, a tester is given query access to the function f , along with a line function g. Let L denote all lines { a + t b : t ∈ F} ⊂ F n , where a, b ∈ F n . In general there are multiple distinct choices of a, b which may describe the same line, so we implicitly fix some parametrization of L.
Given a description of a line, the line oracle g returns a univariate polynomial of degree d defined on that line. Hence we write g : L → F[t], where the image of g is understood to only contain degree-d polynomials.
The Rubinfeld-Sudan test now proceeds as follows [RS96]. If f is indeed a degree-d polynomial, then one can set g(ℓ) = f | ℓ for all ℓ ∈ L, and the following two-query test clearly accepts.
(i) Select x, y ∈ F n independently, uniformly at random.
(ii) Let ℓ be the line determined by {x + ty : t ∈ F q }. Accept iff f (x) agrees with g(ℓ)(x).
Ben-Sasson et al derandomized the line-point test as follows. Their algorithm flips a fair coin. If heads, it samples y from an ǫ-biased set S ⊂ F n q rather than from the entire space F n q . If tails, it checks whether f (x) agrees with g(ℓ)(x), where ℓ = {0 + tx : t ∈ F q }. We call this the "derandomized line-point test." Our construction improves the randomness-efficiency of the test since the ǫ-biased space S is smaller. The soundness parameters of the test are the same.
Proposition 4.4 (Improved [BSSVW03] Theorem 4.1). Let F q be a finite field of q elements, n ≥ 1, f : F n q → F q , g : L → F q [t]. The derandomized line-point point test has sample space size O(q n · n log(q) O(1) ǫ 2+o(1) ). Further, there exists a universal constant α > 0 such that for d ≤ q/3, n ≤ αq log(q) , ǫ < α n log(q) , δ ≤ α, if the derandomized line-point test accepts with probability ≥ 1 − δ then f has Hamming distance at most 4δ from a degree d polynomial.

Randomness-Efficient Verification of Matrix Multiplication
Suppose A, B, C are (n × n) matrices whose entries belong to some finite field F q or cyclic group Z q for q ≥ 2. Let R denote either F q or Z q . We wish to verify whether AB = C over R.
Naively we can multiply A, B and check entry-wise, but this takes O(n ω ) time, where ω ≈ 2.37 is the exponent of matrix multiplication [AW21].
A simple randomized algorithm is to sample vectors x ∈ R n uniformly, and then check whether ABx = Cx [Fre77]. This requires three matrix-vector multiplications, which takes O(n 2 ) time 4 .
Our algorithm replaces these uniform samples with samples from a small-bias set. Observe that if AB = C, then the probability that Px∼R n [ABx = Cx] = Px∼R n [(AB − C)x = 0] = 1 q . If S ⊂ R n is α-biased then Px∼S [ABx = Cx|AB = C] ≤ 1 q + α.
Proposition 4.5. Let R denote a finite field F q or cyclic group Z/qZ. Given matrices A, B, C ∈ R n×n and α-biased set S ⊂ R n , there exists an O(n 2 ) time randomized algorithm to decide whether AB = C with one-sided error 1 q + α. It uses O(log( n log(q) O(1) α 2+o(1) )) random bits.