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 locallymore »
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 more »
 Award ID(s):
 1900460
 Publication Date:
 NSFPAR ID:
 10273422
 Journal Name:
 Electronic colloquium on computational complexity
 Volume:
 ECCC TR20149
 ISSN:
 14338092
 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 thismore »

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, formore »

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.

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)).