Random walks in expander graphs and their various derandomizations ( e.g ., replacement=zig-zag product) are invaluable tools from pseudorandomness. Recently, Ta-Shma used s -wide replacement walks ...in his breakthrough construction of a binary linear code almost matching the Gilbert-Varshamov bound (STOC 2017). Ta-Shma's original analysis was entirely linear algebraic, and subsequent developments have inherited this viewpoint. In this work, we rederive Ta-Shma's analysis from a combinatorial point of view using repeated application of the expander mixing lemma . We hope that this alternate perspective will yield a better understanding of Ta-Shma's construction. As an additional application of our techniques, we give an alternate proof of the expander hitting set lemma .
Ramanujan coverings of graphs Hall, Chris; Puder, Doron; Sawin, William F.
Advances in mathematics (New York. 1965),
01/2018, Volume:
323
Journal Article
Recent developments have shown the existence of quantum low-density parity check (qLDPC) codes with constant rate and linear distance. A natural question concerns the efficient decodability of these ...codes. In this paper, we present a linear time decoder for the recent quantum Tanner codes construction of asymptotically good qLDPC codes, which can correct all errors of weight up to a constant fraction of the blocklength. Our decoder is an iterative algorithm which searches for corrections within constant-sized regions. At each step, the corrections are found by reducing a locally defined and efficiently computable cost function which serves as a proxy for the weight of the remaining error.
We prove an optimal mixing time bound for the single-site update Markov chain known as the Glauber dynamics or Gibbs sampling in a variety of settings. Our work presents an improved version of the ...spectral independence approach of Anari et al. (2020) and shows O(nlogn) mixing time on any n-vertex graph of bounded degree when the maximum eigenvalue of an associated influence matrix is bounded. As an application of our results, for the hard-core model on independent sets weighted by a fugacity λ, we establish O(nlogn) mixing time for the Glauber dynamics on any n-vertex graph of constant maximum degree Δ when λ<λc(Δ) where λc(Δ) is the critical point for the uniqueness/non-uniqueness phase transition on the Δ-regular tree. More generally, for any antiferromagnetic 2-spin system we prove O(nlogn) mixing time of the Glauber dynamics on any bounded degree graph in the corresponding tree uniqueness region. Our results apply more broadly; for example, we also obtain O(nlogn) mixing for q-colorings of triangle-free graphs of maximum degree Δ when the number of colors satisfies q > α Δ where α ≈ 1.763, and O(mlogn) mixing for generating random matchings of any graph with bounded degree and m edges.
Our approach is based on two steps. First, we show that the approximate tensorization of entropy (i.e., factorizing entropy into single vertices), which is a key step for establishing the modified log-Sobolev inequality in many previous works, can be deduced from entropy factorization into blocks of fixed linear size. Second, we adapt the local-to-global scheme of Alev and Lau (2020) to establish such block factorization of entropy in a more general setting of pure weighted simplicial complexes satisfying local spectral expansion; this also substantially generalizes the result of Cryan et al. (2019).
We prove that the sum of t boolean-valued random variables sampled by a random walk on a regular expander converges in total variation distance to a discrete normal distribution at a rate of ...O(λ/t1/2−o(1)), where λ is the second largest eigenvalue of the random walk matrix in absolute value. To the best of our knowledge, among known Berry-Esseen bounds for Markov chains, our result is the first to show convergence in total variation distance, and is also the first to incorporate a linear dependence on expansion λ. In contrast, prior Markov chain Berry-Esseen bounds showed a convergence rate of O(1/√t) in weaker metrics such as Kolmogorov distance.
Our result also improves upon prior work in the pseudorandomness literature, which showed that the total variation distance is O(λ) when the approximating distribution is taken to be a binomial distribution. We achieve the faster O(λ/t1/2−o(1)) convergence rate by generalizing the binomial distribution to discrete normals of arbitrary variance. We specifically construct discrete normals using a random walk on an appropriate 2-state Markov chain. Our bound can therefore be viewed as a regularity lemma that reduces the study of arbitrary expanders to a small class of particularly simple expanders.
Random Walks on Rotating Expanders Cohen, Gil; Maor, Gal
Proceedings of the 55th Annual ACM Symposium on Theory of Computing,
06/2023
Conference Proceeding
Peer reviewed
Open access
Random walks on expanders are a powerful tool which found applications in many areas of theoretical computer science, and beyond. However, they come with an inherent cost – the spectral expansion of ...the corresponding power graph deteriorates at a rate that is exponential in the length of the walk. As an example, when G is a d-regular Ramanujan graph, the power graph Gt has spectral expansion 2Ω(t) √D, where D = dt is the regularity of Gt, thus, Gt is 2Ω(t) away from being Ramanujan. This exponential blowup manifests itself in many applications.
In this work we bypass this barrier by permuting the vertices of the given graph after each random step. We prove that there exists a sequence of permutations for which the spectral expansion deteriorates by only a linear factor in t. In the Ramanujan case this yields an expansion of O(t √D). We stress that the permutations are tailor-made to the graph at hand and require no randomness to generate.
Our proof, which holds for all sufficiently high girth graphs, makes heavy use of the powerful framework of finite free probability and interlacing families that was developed in a seminal sequence of works by Marcus, Spielman and Srivastava.
Broadcasting on Random Directed Acyclic Graphs Makur, Anuran; Mossel, Elchanan; Polyanskiy, Yury
IEEE transactions on information theory,
2020-Feb., 2020-2-00, Volume:
66, Issue:
2
Journal Article
Peer reviewed
Open access
We study the following generalization of the wellknown model of broadcasting on trees. Consider an infinite directed acyclic graph (DAG) with a unique source vertex X. Let the collection of vertices ...at distance k from X be called the kth layer, and suppose every non-source vertex has indegree d ≥ 2. At layer 0, the source vertex is given a random bit. At layer k ≥ 1, each vertex receives d bits from its parents in the (k-1)th layer, which are transmitted along edges that are independent binary symmetric channels (BSCs) with crossover probability δ ∈ (0, 1/2). Each vertex combines its d noisy inputs using a 2 deterministic d-ary Boolean processing function that generates the value at the vertex. The goal is to be able to reconstruct the original bit X with probability of error bounded away from 1/2 using the values of all vertices at an arbitrarily deep layer k. This question is closely related to models of reliable computation and storage, and information flow in biological networks. In this paper, we treat the case of randomly constructed DAGs, for which we show that broadcasting is only possible if the BSC noise level δ is below a certain (degree and function dependent) critical threshold. For d ≥ 3, and random DAGs with layers of size Ω(log(k)) and majority processing functions, we identify the critical threshold. For d = 2, we establish a similar result for the NAND processing function. We also prove a partial converse result for odd d ≥ 3 illustrating that the identified thresholds are impossible to improve by selecting different processing functions if the decoder is restricted to using a single vertex's value. Finally, for any BSC noise level δ, we construct explicit DAGs (using regular bipartite lossless expander graphs) with bounded degree and layers of size Θ(log(k)) admitting reconstruction. In particular, we show that the first r layers of such DAGs can be generated in either deterministic quasipolynomial time or randomized polylogarithmic time in r. These results portray a doubly-exponential advantage for storing a bit in bounded degree DAGs compared to trees, where d = 1 but layer sizes need to grow exponentially with depth in order for broadcasting to be possible.
PDF
