Theory of Computing
-------------------
Title     : Absolutely Sound Testing of Lifted Codes
Authors   : Elad Haramaty, Noga Ron-Zewi, and Madhu Sudan
Volume    : 11
Number    : 12
Pages     : 299-338
URL       : https://theoryofcomputing.org/articles/v011a012

Abstract
--------

In this paper we present a strong analysis of the testability of a
broad, and to date the most interesting known, class of "affine-
invariant" codes. Affine-invariant codes are codes whose coordinates
are associated with a vector space and in addition these codes are
invariant under affine transformations of the coordinate space.
Affine-invariant linear codes form a natural abstraction of algebraic
properties such as linearity and low-degree, which have been of
significant interest in theoretical computer science in the past. The
study of affine-invariance is motivated in part by its relationship to
property testing: affine-invariant linear codes tend to be locally
testable under fairly minimal and almost necessary conditions.

Recent work by Ben-Sasson et al. (CCC 2011) and Guo et al. (ITCS
2013) introduced a new class of affine-invariant linear codes
based on an operation called "lifting." Given a base code over a
$t$-dimensional space, its $m$-dimensional lift consists of all words
whose restriction to every $t$-dimensional affine subspace is a
codeword of the base code. Lifting not only captures the most familiar
codes, which can be expressed as lifts of low-degree polynomials, it
also yields new codes when applied to "medium-degree" polynomials
whose rate is better than that of the corresponding polynomial codes,
and all other combinatorial qualities are no worse.

In this paper we show that codes obtained by lifting are also testable
in an "absolutely sound" way. Specifically, we consider the natural
test: Pick a random affine subspace of base dimension and verify that
a given word is a codeword of the base code when restricted to the
chosen subspace. While this test accepts codewords with probability
one, we show that it rejects words at constant distance from the code
with constant probability (depending only on the alphabet size). This
work thus extends the results of Bhattacharyya et al. (FOCS 2010) and
Haramaty et al. (FOCS 2011), while giving concrete new codes of higher
rate that have absolutely sound testers. In particular, we show that
there exist codes satisfying the requirements of Barak et al. (FOCS
2012) for constructing small-set expanders with a large number of
eigenvalues close to the maximal one, with rate slightly higher than
that of the codes used in their work.

An extended abstract of this paper appeared in the "Proceedings of the
17th International Workshop on Randomization and Computation
(RANDOM'13)," pages 671-682, 2013,
http://link.springer.com/chapter/10.1007/978-3-642-40328-6_46