The GilbertVarshamov bound (nonconstructively) establishes the existence of binary codes of distance 1/2ε and rate Ω(ε 2 ) (where an upper bound of O(ε 2 log(1/ε)) is known). TaShma [STOC 2017] gave an explicit construction of εbalanced binary codes, where any two distinct codewords are at a distance between 1/2ε/2 and 1/2+ε/2, achieving a near optimal rate of Ω(ε 2+β ), where β→ 0 as ε→ 0. We develop unique and list decoding algorithms for (a slight modification of) the family of codes constructed by TaShma, in the adversarial error model. We prove the following results for εbalanced codes with block length N and rate Ω(ε 2+β ) in this family: For all , there are explicit codes which can be uniquely decoded up to an error of half the minimum distance in time N Oε,β(1) . For any fixed constant β independent of ε, there is an explicit construction of codes which can be uniquely decoded up to an error of half the minimum distance in time (log(1/ε)) O(1) ·N Oβ(1) . For any , there are explicit εbalanced codes with rate Ω(ε 2+β ) which can be list decoded up to error 1/2ε ' in time N Oε,ε'more »
Explicit Abelian Lifts and Quantum LDPC Codes
For an abelian group H acting on the set [𝓁], an (H,𝓁)lift of a graph G₀ is a graph obtained by replacing each vertex by 𝓁 copies, and each edge by a matching corresponding to the action of an element of H.
Expanding graphs obtained via abelian lifts, form a key ingredient in the recent breakthrough constructions of quantum LDPC codes, (implicitly) in the fiber bundle codes by Hastings, Haah and O'Donnell [STOC 2021] achieving distance Ω̃(N^{3/5}), and in those by Panteleev and Kalachev [IEEE Trans. Inf. Theory 2021] of distance Ω(N/log(N)). However, both these constructions are nonexplicit. In particular, the latter relies on a randomized construction of expander graphs via abelian lifts by Agarwal et al. [SIAM J. Discrete Math 2019].
In this work, we show the following explicit constructions of expanders obtained via abelian lifts. For every (transitive) abelian group H ⩽ Sym(𝓁), constant degree d ≥ 3 and ε > 0, we construct explicit dregular expander graphs G obtained from an (H,𝓁)lift of a (suitable) base nvertex expander G₀ with the following parameters:
ii) λ(G) ≤ 2√{d1} + ε, for any lift size 𝓁 ≤ 2^{n^{δ}} where δ = δ(d,ε),
iii) λ(G) ≤ ε ⋅ d, for any lift size 𝓁 more »
 Editors:
 Braverman, Mark
 Publication Date:
 NSFPAR ID:
 10339909
 Journal Name:
 Leibniz international proceedings in informatics
 Volume:
 215
 ISSN:
 18688969
 Sponsoring Org:
 National Science Foundation
More Like this


Berenbrink, Petra and (Ed.)A directed acyclic graph G = (V,E) is said to be (e,d)depth robust if for every subset S ⊆ V of S ≤ e nodes the graph GS still contains a directed path of length d. If the graph is (e,d)depthrobust for any e,d such that e+d ≤ (1ε)V then the graph is said to be εextreme depthrobust. In the field of cryptography, (extremely) depthrobust graphs with low indegree have found numerous applications including the design of sidechannel resistant MemoryHard Functions, Proofs of Space and Replication and in the design of Computationally Relaxed Locally Correctable Codes. In these applications, it is desirable to ensure the graphs are locally navigable, i.e., there is an efficient algorithm GetParents running in time polylogV which takes as input a node v ∈ V and returns the set of v’s parents. We give the first explicit construction of locally navigable εextreme depthrobust graphs with indegree O(log V). Previous constructions of εextreme depthrobust graphs either had indegree ω̃(log² V) or were not explicit.

A graph G is called {\em selfordered} (a.k.a asymmetric) if the identity permutation is its only automorphism. Equivalently, there is a unique isomorphism from G to any graph that is isomorphic to G. We say that G=(VE) is {\em robustly selfordered}if the size of the symmetric difference between E and the edgeset of the graph obtained by permuting V using any permutation :VV is proportional to the number of nonfixedpoints of . In this work, we initiate the study of the structure, construction and utility of robustly selfordered graphs. We show that robustly selfordered boundeddegree graphs exist (in abundance), and that they can be constructed efficiently, in a strong sense. Specifically, given the index of a vertex in such a graph, it is possible to find all its neighbors in polynomialtime (i.e., in time that is polylogarithmic in the size of the graph). We provide two very different constructions, in tools and structure. The first, a direct construction, is based on proving a sufficient condition for robust selfordering, which requires that an auxiliary graph, on {\em pairs} of vertices of the original graph, is expanding. In this case the original graph is (not only robustly selfordered but) also expanding. Themore »

For a graph G on n vertices, naively sampling the position of a random walk of at time t requires work Ω(t). We desire local access algorithms supporting positionG(t) queries, which return the position of a random walk from some fixed start vertex s at time t, where the joint distribution of returned positions is 1/ poly(n) close to those of a uniformly random walk in ℓ1 distance. We first give an algorithm for local access to random walks on a given undirected dregular graph with eO( 1 1−λ √ n) runtime per query, where λ is the secondlargest eigenvalue of the random walk matrix of the graph in absolute value. Since random dregular graphs G(n, d) are expanders with high probability, this gives an eO(√ n) algorithm for a graph drawn from G(n, d) whp, which improves on the naive method for small numbers of queries. We then prove that no algorithm with subconstant error given probe access to an input dregular graph can have runtime better than Ω(√ n/ log(n)) per query in expectation when the input graph is drawn from G(n, d), obtaining a nearly matching lower bound. We further show an Ω(n1/4) runtime per query lowermore »

The Sparsest Cut is a fundamental optimization problem that have been extensively studied. For planar inputs the problem is in P and can be solved in Õ(n 3 ) time if all vertex weights are 1. Despite a significant amount of effort, the best algorithms date back to the early 90’s and can only achieve O(log n)approximation in Õ(n) time or 3.5approximation in Õ(n 2 ) time [Rao, STOC92]. Our main result is an Ω(n 2−ε ) lower bound for Sparsest Cut even in planar graphs with unit vertex weights, under the (min, +)Convolution conjecture, showing that approxima tions are inevitable in the nearlinear time regime. To complement the lower bound, we provide a 3.3approximation in nearlinear time, improving upon the 25year old result of Rao in both time and accuracy. We also show that our lower bound is not far from optimal by observing an exact algorithm with running time Õ(n 5/2 ) improving upon the Õ(n 3 ) algorithm of Park and Phillips [STOC93]. Our lower bound accomplishes a repeatedly raised challenge by being the first finegrained lower bound for a natural planar graph problem in P. Building on our construction we prove nearquadratic lower bounds under SETHmore »