Errorcorrecting codes that admit {\em local} decoding and correcting algorithms have been the focus of much recent research due to their numerous theoretical and practical applications. An important goal is to obtain the best possible tradeoffs between the number of queries the algorithm makes to its oracle (the {\em locality} of the task), and the amount of redundancy in the encoding (the {\em information rate}).
In Hamming's classical adversarial channel model, the current tradeoffs are dramatic, allowing either small locality, but superpolynomial blocklength, or small blocklength, but high locality. However, in the computationally bounded, adversarial channel model, proposed by Lipton (STACS 1994), constructions of locally decodable codes suddenly exhibit small locality and small blocklength, but these constructions require strong trusted setup assumptions e.g., Ostrovsky, Pandey and Sahai (ICALP 2007) construct private locally decodable codes in the setting where the sender and receiver already share a symmetric key.
We study variants of locally decodable and locally correctable codes in computationally bounded, adversarial channels, in a setting with no publickey or privatekey cryptographic setup. The only setup assumption we require is the selection of the {\em public} parameters (seed) for a collisionresistant hash function. Specifically, we provide constructions of {\em relaxed locally correctable} and {\em relaxed locally decodable codes} over the binary alphabet, with constant information rate, and polylogarithmic locality.
Our constructions, which compare favorably with their classical analogues in the computationally unbounded Hamming channel, crucially employ {\em collisionresistant hash functions} and {\em local expander graphs}, extending ideas from recent cryptographic constructions of memoryhard functions.
more »
« less
Robustly SelfOrdered Graphs: Constructions and Applications to Property Testing
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.
The second construction proceeds in three steps: It boosts the mere existence of robustly selfordered graphs,
which provides explicit graphs of sublogarithmic size, to an efficient construction of polynomialsize graphs,
and then, repeating it again, to exponentialsize(robustly selfordered) graphs that are locally constructible. This construction can yield robustly selfordered graphs that are either expanders or highly disconnected,
having logarithmic size connected components.
We also consider graphs of unbounded degree, seeking correspondingly unbounded robustness parameters.
We again demonstrate that such graphs (of linear degree)exist (in abundance), and that they can be constructed efficiently, in a strong sense. This turns out to require very different tools. Specifically, we show that the construction of such graphs reduces to the construction of nonmalleable twosource extractors with very weak parameters but with some additional natural features. We actually show two reductions, one simpler than the other but yielding a less efficient construction when combined with the known constructions of extractors.
We demonstrate that robustly selfordered boundeddegree graphs are useful towards obtaining lower bounds on the query complexity of testing graph properties both in the boundeddegree and the dense graph models. Indeed, their robustness offers efficient, local and distance preserving reductions from testing problems
on ordered structures (like sequences) to the unordered (effectively unlabeled) graphs.
One of the results that we obtain, via such a reduction, is a subexponential separation between the query complexities of testing and tolerant testing of graph properties in the boundeddegree graph model.
Changes to previous version:
We retract the claims made in our initial posting regarding the construction of nonmalleable twosource extractors
(which are quasiorthogonal) as well as the claims about the construction of relocationdetecting codes (see Theorems 1.5 and 1.6 in the original version). The source of trouble is a fundamental flaw in the proof of Lemma 9.7 (in the original version), which may as well be wrong.
Hence, the original Section 9 was omitted, except that the original Section 9.3 was retained as a new Section 8.3.
The original Section 8 appears as Section 8.0 and 8.1, and Section 8.2 is new.
more »
« less
 Award ID(s):
 1900460
 NSFPAR ID:
 10273422
 Date Published:
 Journal Name:
 Electronic colloquium on computational complexity
 Volume:
 ECCC TR20149
 ISSN:
 14338092
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


Constructing a spanning tree of a graph is one of the most basic tasks in graph theory. We consider a relaxed version of this problem in the setting of local algorithms. The relaxation is that the constructed subgraph is a sparse spanning subgraph containing at most (1+ϵ)n edges (where n is the number of vertices and ϵ is a given approximation/sparsity parameter). In the local setting, the goal is to quickly determine whether a given edge e belongs to such a subgraph, without constructing the whole subgraph, but rather by inspecting (querying) the local neighborhood of e. The challenge is to maintain consistency. That is, to provide answers concerning different edges according to the same spanning subgraph. We first show that for general boundeddegree graphs, the query complexity of any such algorithm must be Ω(n−−√). This lower bound holds for constantdegree graphs that have high expansion. Next we design an algorithm for (boundeddegree) graphs with high expansion, obtaining a result that roughly matches the lower bound. We then turn to study graphs that exclude a fixed minor (and are hence nonexpanding). We design an algorithm for such graphs, which may have an unbounded maximum degree. The query complexity of this algorithm is poly(1/ϵ,h) (independent of n and the maximum degree), where h is the number of vertices in the excluded minor. Though our two algorithms are designed for very different types of graphs (and have very different complexities), on a highlevel there are several similarities, and we highlight both the similarities and the differences.more » « less

Braverman, Mark (Ed.)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 𝓁 ≤ 2^{n^{δ₀}} for a fixed δ₀ > 0, when d ≥ d₀(ε), or iv) λ(G) ≤ Õ(√d), for lift size "exactly" 𝓁 = 2^{Θ(n)}. As corollaries, we obtain explicit quantum lifted product codes of Panteleev and Kalachev of almost linear distance (and also in a wide range of parameters) and explicit classical quasicyclic LDPC codes with wide range of circulant sizes. Items (i) and (ii) above are obtained by extending the techniques of Mohanty, O'Donnell and Paredes [STOC 2020] for 2lifts to much larger abelian lift sizes (as a byproduct simplifying their construction). This is done by providing a new encoding of special walks arising in the trace power method, carefully "compressing" depthfirst search traversals. Result (iii) is via a simpler proof of Agarwal et al. [SIAM J. Discrete Math 2019] at the expense of polylog factors in the expansion.more » « less

Micciancio, Daniele ; Ristenpart, Thomas. (Ed.)We present the first explicit construction of a nonmalleable code that can handle tampering functions that are boundeddegree polynomials. Prior to our work, this was only known for degree1 polynomials (affine tampering functions), due to Chattopad hyay and Li (STOC 2017). As a direct corollary, we obtain an explicit nonmalleable code that is secure against tampering by boundedsize arithmetic circuits. We show applications of our nonmalleable code in constructing nonmalleable se cret sharing schemes that are robust against boundeddegree polynomial tampering. In fact our result is stronger: we can handle adversaries that can adaptively choose the polynomial tampering function based on initial leakage of a bounded number of shares. Our results are derived from explicit constructions of seedless nonmalleable ex tractors that can handle boundeddegree polynomial tampering functions. Prior to our work, no such result was known even for degree2 (quadratic) polynomials.more » « less

A spanner of a graph G is a subgraph H that approximately preserves shortest path distances in G. Spanners are commonly applied to compress computation on metric spaces corresponding to weighted input graphs. Classic spanner constructions can seamlessly handle edge weights, so long as error is measured multiplicatively. In this work, we investigate whether one can similarly extend constructions of spanners with purely additive error to weighted graphs. These extensions are not immediate, due to a key lemma about the size of shortest path neighborhoods that fails for weighted graphs. Despite this, we recover a suitable amortized version, which lets us prove direct extensions of classic +2 and +4 unweighted spanners (both allpairs and pairwise) to +2W and +4W weighted spanners, where W is the maximum edge weight. Specifically, we show that a weighted graph G contains allpairs (pairwise) +2W and +4W weighted spanners of size O(n3/2) and O(n7/5) (O(np1/3) and O(np2/7)) respectively. For a technical reason, the +6 unweighted spanner becomes a +8W weighted spanner; closing this error gap is an interesting remaining open problem. That is, we show that G contains allpairs (pairwise) +8W weighted spanners of size O(n4/3) (O(np1/4)).more » « less