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 »
Local Testing for Membership in Lattices
Testing membership in lattices is of practical relevance, with applications to integer programming, error detection in latticebased communication and cryptography.
In this work, we initiate a systematic study of {\em local testing} for membership in lattices, complementing and building upon the extensive body of work on locally testable codes.
In particular, we formally define the notion of local tests
for lattices and present the following:
\begin{enumerate}
\item We show that in order to achieve low query complexity, it is sufficient to design onesided nonadaptive {\em canonical} tests. This result is akin to, and based on an
analogous result for errorcorrecting codes due to BenSasson \etal\ (SIAM J. Computing 35(1) pp121).
\item We demonstrate
upper and lower bounds on the query complexity of local testing for membership in
{\em code formula} lattices.
We instantiate our results for code formula lattices constructed from ReedMuller codes to obtain nearlymatching upper and lower bounds on the query complexity of testing such lattices.
\item We contrast lattice testing from code testing by showing lower bounds on the query complexity of testing lowdimensional lattices.
This illustrates large lower bounds on the query complexity of testing membership in {\em knapsack lattices}. On the other hand, we show that knapsack lattices more »
 Award ID(s):
 1649515
 Publication Date:
 NSFPAR ID:
 10033550
 Journal Name:
 FSTTCS
 Sponsoring Org:
 National Science Foundation
More Like this


The approximate degree of a Boolean function f is the least degree of a real polynomial that approximates f pointwise to error at most 1/3. The approximate degree of f is known to be a lower bound on the quantum query complexity of f (Beals et al., FOCS 1998 and J. ACM 2001). We find tight or nearly tight bounds on the approximate degree and quantum query complexities of several basic functions. Specifically, we show the following. kDistinctness: For any constant k, the approximate degree and quantum query complexity of the kdistinctness function is Ω(n3/4−1/(2k)). This is nearly tight for large k, as Belovs (FOCS 2012) has shown that for any constant k, the approximate degree and quantum query complexity of kdistinctness is O(n3/4−1/(2k+2−4)). Image size testing: The approximate degree and quantum query complexity of testing the size of the image of a function [n]→[n] is Ω~(n1/2). This proves a conjecture of Ambainis et al. (SODA 2016), and it implies tight lower bounds on the approximate degree and quantum query complexity of the following natural problems. kJunta testing: A tight Ω~(k1/2) lower bound for kjunta testing, answering the main open question of Ambainis et al. (SODA 2016). Statistical distance frommore »

Locally Decodable Codes (LDCs) are errorcorrecting codes for which individual message symbols can be quickly recovered despite errors in the codeword. LDCs for Hamming errors have been studied extensively in the past few decades, where a major goal is to understand the amount of redundancy that is necessary and sufficient to decode from large amounts of error, with small query complexity. Despite exciting progress, we still don't have satisfactory answers in several important parameter regimes. For example, in the case of 3query LDCs, the gap between existing constructions and lower bounds is superpolynomial in the message length. In this work we study LDCs for insertion and deletion errors, called Insdel LDCs. Their study was initiated by Ostrovsky and PaskinCherniavsky (Information Theoretic Security, 2015), who gave a reduction from Hamming LDCs to Insdel LDCs with a small blowup in the code parameters. On the other hand, the only known lower bounds for Insdel LDCs come from those for Hamming LDCs, thus there is no separation between them. Here we prove new, strong lower bounds for the existence of Insdel LDCs. In particular, we show that 2query linear Insdel LDCs do not exist, and give an exponential lower bound for the lengthmore »

Locally testable codes (LTC) are errorcorrecting codes that have a local tester which can distinguish valid codewords from words that are far from all codewords, by probing a given word only at a very small (sublinear, typically constant) number of locations. Such codes form the combinatorial backbone of PCPs. A major open problem is whether there exist LTCs with positive rate, constant relative distance and testable with a constant number of queries. In this paper, we present a new approach towards constructing such LTCs using the machinery of highdimensional expanders. To this end, we consider the Tanner representation of a code, which is specified by a graph and a base code. Informally, our result states that if this graph is part of an {\em agreement expander} then the local testability of the code follows from the local testability of the base code. Agreement expanders allow one to stitch together many mostlyconsistent local functions into a single global function. Highdimensional expanders are known to yield agreement expanders with constant degree. This work unifies and generalizes the known results on testability of the Hadamard, ReedMuller and lifted codes, all of which are proved via a single round of local selfcorrection: the correctedmore »

Generalized bicycle (GB) codes is a class of quantum errorcorrecting codes constructed from a pair of binary circulant matrices. Unlike for other simple quantum code ansätze, unrestricted GB codes may have linear distance scaling. In addition, lowdensity paritycheck GB codes have a naturally overcomplete set of lowweight stabilizer generators, which is expected to improve their performance in the presence of syndrome measurement errors. For such GB codes with a given maximum generator weight w, we constructed upper distance bounds by mapping them to codes local in D≤w−1 dimensions, and lower existence bounds which give d≥O(n1/2). We have also conducted an exhaustive enumeration of GB codes for certain prime circulant sizes in a family of twoqubit encoding codes with row weights 4, 6, and 8; the observed distance scaling is consistent with A(w)n1/2+B(w), where n is the code length and A(w) is increasing with w.