On the Hardness of Learning Sparse Parities
Arnab Bhattacharyya∗

Ameet Gadekar∗

Suprovat Ghoshal∗

Rishi Saket†

arXiv:1511.08270v1 [cs.CC] 26 Nov 2015

November 30, 2015

Abstract
This work investigates the hardness of computing sparse solutions to systems of linear equations over
F2 . Consider the k-EvenSet problem: given a homogeneous system of linear equations over F2 on n
variables, decide if there exists a nonzero solution of Hamming weight at most k (i.e. a k-sparse solution).
While there is a simple O(nk/2 )-time algorithm for it, establishing fixed parameter intractability for kEvenSet has been a notorious open problem. Towards
this goal, we show that unless k-Clique can be
√
solved in no(k) time, k-EvenSet has no poly(n) · 2o( k) time algorithm for all k and no polynomial time
algorithm when k = ω(log2 n).
Our work also shows that the non-homogeneous generalization of the problem – which we call kVectorSum – is W[1]-hard on instances where the number of equations is O(k log n), improving on
previous reductions which produced Ω(n) equations. We use the hardness of k-VectorSum as a starting
point to prove the result for k-EvenSet, and additionally strengthen the former to show the hardness
of approximately learning k-juntas. In particular, we prove that given a system of O(exp(O(k)) · log n)
linear equations, it is W[1]-hard to decide if there is a k-sparse linear form satisfying all the equations
or any function on at most k-variables (a k-junta) satisfies at most (1/2 + ε)-fraction of the equations,
for any constant ε > 0. In the setting of computational learning, this shows hardness of approximate
non-proper learning of k-parities. In a similar vein, we use the hardness of k-EvenSet to show
that
√
that for any constant d, unless k-Clique can be solved in no(k) time, there is no poly(m, n) · 2o( k) time
algorithm to decide whether a given set of m points in Fn
2 satisfies: (i) there exists a non-trivial k-sparse
homogeneous linear form evaluating to 0 on all the points, or (ii) any non-trivial degree d polynomial P
supported on at most k variables evaluates to zero on ≈ PrFn2 [P (z) = 0] fraction of the points i.e., P is
fooled by the set of points.
Lastly, we study the approximation in the sparsity of the solution. Let the Gap-k-VectorSum
problem be: given an instance of k-VectorSum of size n, decide if there exist a k-sparse solution, or
every solution is of sparsity at least k′ = (1 + δ0 )k. Assuming ETH, we show that for some constants c0 ,
δ0 > 0 there is no poly(n) time algorithm for Gap-k-VectorSum when k = ω((log log n)c0 ).

∗ Department of Computer Science and Automation, Indian Institute of Science, Bangalore, India. Emails: {arnabb,
ameet.gadekar, suprovat.ghoshal}@csa.iisc.ernet.in. AB supported in part by DST Ramanujan Fellowship.
† IBM Research, Bangalore, India. Email: rissaket@in.ibm.com.

1

Introduction

Given a system of linear equations over F2 , does there exist a sparse non-trivial solution? This question is
studied in diﬀerent guises in several areas of mathematics and computer science. For instance, in coding
theory, if the system of linear equations is Mx = 0 where M is the parity check matrix of a binary code,
then the minimum (Hamming) weight of a nonzero solution is the distance of the code. This also captures
the problem of determining whether a binary matroid has a short cycle, as the latter reduces to deciding
whether there is a sparse nonzero x such that Mx = 0. In learning theory, the well known sparse parity
problem is: given a binary matrix M and a vector b decide whether there is a small weight nonzero vector
x satisfying Mx = b. The version where Mx is required to equal b in most coordinates, but not necessarily
all, is also well studied as the problem of learning noisy parities.
Let a vector x ∈ Fn2 be called k-sparse if it is nonzero in at most k positions, i.e. it has Hamming weight
at most k. In this work, we show that learning a k-sparse solution to a system of linear equations is ﬁxed
parameter intractable, even when (i) the number of equations is only logarithmic in the number of variables,
(ii) the learning is allowed to be approximate, i.e. satisfy only 51% of the equations and, (iii) is allowed
to output as hypothesis any function (junta) supported on at most k variables. We also prove variants
of these results for the case when the system of equations is homogeneous, which correspond to hardness
of the well known k-EvenSet problem. Note that it is always possible to recover a k-sparse solution in
O(nk ) time simply by enumerating over all k-sparse vectors. Our results show that for many settings of
k, no substantially faster algorithm is possible for k-EvenSet unless widely believed conjectures are false.
Assuming similar conjectures, we also rule out fast algorithms for learning γk-sparse solutions to a linear
system promising the existence of a k sparse solutions, for some γ > 1.
In the next few paragraphs we recall previous related work and place our results in their context. Let us
ﬁrst formally deﬁne the basic objects of our study:
Definition 1.1. k-VectorSum: Given a matrix M ∈ Fm×n
and a vector b ∈ Fm
2 , and a positive integer k
2
as parameter, decide if there exists a k-sparse vector x such that Mx = b.
Definition 1.2. k-EvenSet: Given a matrix M ∈ Fm×n
, and a positive integer k as parameter, decide if
2
there exists a k-sparse vector x such that Mx = 0.
Remark: In the language of coding theory, k-VectorSum is also known as the MaximumLikelihoodDecoding problem and k-EvenSet as the MinimumDistance problem.
Clearly, k-VectorSum is as hard as k-EvenSet1 . The k-VectorSum problem was shown to be W[1]hard2 by Downey, Fellows, Vardy and Whittle [DFVW99], even in the special case of the vector b consisting of
all 1’s. More recently, Bhattacharyya, Indyk, Woodruﬀ and Xie [BIWX11] showed that the time complexity
of k-VectorSum is min(2Θ(m) , nΘ(k) ), assuming 3-SAT has no 2o(n) time algorithm.
In contrast, the complexity of k-EvenSet remains unresolved, other than its containment in W[2] shown
in [DFVW99]. Proving W[1]-hardness for k-EvenSet was listed as an open problem in Downey and Fellows’
1999 monograph [DF99] and has been reiterated more recently in lists of open problems [FM12, FGMS12].
Note that if we ask for a vector x whose weight is exactly k instead of at most k, the problem is known to
be W[1]-hard [DFVW99]. Our work gives evidence ruling out eﬃcient algorithms for k-EvenSet for a wide
range of settings of k.
In the non-parameterized setting, where k is part of the input, these problems are very well-studied.
Vardy showed that EvenSet (or MinimumDistance) is NP-hard [Var97]. The question of approximating
k, the minimum distance of the associated code, has also received attention. Dumer, Micciancio and Sudan
[DMS03] showed that if RP 6= NP, then k is hard to approximate within some constant factor γ > 1.
Their reduction was derandomized by Cheng and Wan [CW08, CW09], and subsequently Austrin and Khot
[AK14] gave a simpler deterministic reduction for this problem. The results of [CW08, CW09] and [AK14]
were further strengthened by Micciancio [Mic14].
1 The name k-EvenSet is from the following interpretation of the problem: given a set system F over a universe U and a
parameter k, find a nonempty subset S ⊆ U of size at most k such that the intersection of S with every set in F has even size.
2 Standard definitions in parameterized complexity appear in Section 2.

1

From a computational learning perspective, the k-VectorSum problem can be restated as: given an
m-sized set of n-dimensional point and value pairs over F2 , decide if there exists a parity supported on at
most k variables (i.e. a k-parity) that is consistent with all the pairs. This has been extensively studied
as a promise problem when the points are uniformly generated. Note that in this case, if m = Ω(n), there
is a unique solution w.h.p and can be found eﬃciently by Gaussian elimination. On the other hand, for
m = O(k log n), the best known running time of O(nk/2 ) is given in [KS06] (credited to Dan Spielman).
Obtaining a polynomial time algorithm for m = poly(k log n) would imply attribute-efficient learning of
k-parities and is a long-standing open problem in the area [Blu96]. The best known dependence between
m and the running time for this problem is described in [BGM10, BGR15]. Our work proves the hardness
of k-VectorSum when m = O(k log n), showing evidence which rules out polynomial time algorithms for
learning k-parity when the input is generated adversarially.
A natural question studied in this work is whether one can do better if the learning algorithm is allowed
to be non-proper (i.e., output a hypothesis that is not a k-parity) and is allowed to not satisfy all the pointvalue pairs. To further motivate this problem, let us look at the case when k is not ﬁxed. In the absence
of noise, Gaussian elimination can eﬃciently recover a consistent parity. The harder case is the agnostic
(noisy) setting which promises that there is a parity consistent with at least 1 − ε fraction of the point-value
pairs. When the points are generated uniformly at random, one can learn the parity in time 2O(n/ log n)
[FGKP09, BKW03].
On the other hand, when the points are adversarially drawn, there is a non-proper algorithm due to Kalai,
that runs in time 2O(n/ log n) and outputs a circuit C which is consistent with
Mansour and Verbin [KMV08]

0.99
of the point value pairs. Håstad’s inapproximability for Max-3LIN [Hås01] implies
at least 1 − ε − 2−n

that learning a noisy parity in the adversarial setting is NP-hard, even for 1/2 + ε accuracy, for any constant
ε > 0. Gopalan, Khot and Saket [GKS10] showed that achieving an accuracy of 1 − 1/2d + ε using degree-d
polynomials as hypotheses is NP-hard. Subsequently, Khot [Kho09] proved an optimal bound of 1/2 + ε for
learning by constant degree polynomials3 . Our work studies the intractability of approximate non-proper
learning of k-parity, and extends the hardness result for k-VectorSum to learning by juntas of k variables,
and for k-EvenSet to learning using constant degree polynomials on k variables.
Another interesting question in the parameterized setting is related to a gap in the sparsity parameter k,
i.e. how tractable it is to learn a γk-sparse solution when the existence of a k-sparse solution is guaranteed,
for some constant γ > 1 (or γ < 1 in case of a maximization problem). Previously, Bonnet et al. [BEKP15]
and Khot and Shinkar [KS15] studied this problem for k-Clique, and both these works show conditional
hardness results. In our work we prove a “gap in k” hardness result for k-VectorSum similar to that
obtained in [BEKP15] for k-Clique.
In the rest of this section we formally describe our results for k-VectorSum and k-EvenSet, and give
a brief description of the techniques used to obtain them.

1.1

Our Results

Hardness of exact problems
We begin by giving a reduction from k-Clique showing the W[1]-hardness of k-VectorSum on instances
which have a small number of rows.
Theorem 1.3 (W[1]-hardness of k-VectorSum). The k-VectorSum problem is W[1]-hard on instances
(M, b) where M ∈ Fm×n
and b ∈ Fm
such that m = O(k log n). Our reduction implies, in particular, that
2 √
2
o( k)
k-VectorSum does not admit an n
time algorithm on such instances, unless k-Clique on r-vertex
graphs has an ro(k) time algorithm.
As far as we know, in previous proofs of the W[1]-hardness of k-VectorSum [DFVW99, CFK+ 15], the
number of rows in the matrix output by the reduction was linear in n. Our proof is inspired by a recent proof
3 As far as we know, this result is unpublished although it was communicated to the fourth author of this paper. We include
with his permission a proof of Khot’s result to illustrate some of the techniques which inspire part of this work.

2

of the W[1]-hardness of k-Sum [ALW14]. Also, in Appendix A, we give a simple O(n · 2m ) time algorithm
for k-VectorSum, which suggests that m cannot be made sublogarithmic in n for hard instances.
Next, we give a hardness reduction from k-VectorSum to the k-EvenSet problem.
Theorem 1.4 (Hardness of k-EvenSet). There is an FPT reduction from an instance (M, b) of k′
2
′
VectorSum, where M ∈ Fm×n
and b ∈ Fm
2 , to an instance M of O((k log n) )-EvenSet, where M ∈
2
m′ ×n′
′
′
F2
such that both m and n are bounded by fixed polynomials in m and n.
Using Theorem 1.3, the above yields the following corollary.
Corollary 1.5. There does not exist a poly(n) time algorithm for k-EvenSet when k = ω(log2 n), assuming
that k-Clique does not have a polynomial time algorithm
for any k = ω(1). More generally, under the same
√
o( k)
assumption, k-EvenSet does not admit a poly(n) · 2
time algorithm for unrestricted k.
Proof. Suppose there is a T (n, k) algorithm for k-EvenSet. Chaining together the reductions in Theorem 1.3
and Theorem 1.4, we get a T (poly(n), k 4 log2 n) algorithm for k-Clique.√ Choosing k = ω(1) implies the
ﬁrst part of the corollary. For the second part, observe that if f (x) = 2o( x) , then f (k 4 log2 n) = no(1) for
some k = ωn (1).

To the best of our knowledge, Corollary 1.5 gives the ﬁrst nontrivial hardness results for parameterized
k-EvenSet. Theorem 1.4 is obtained by adapting the hardness reduction for the inapproximability of
MinimumDistance by Austrin and Khot [AK14] to the parameterized setting.
Hardness of non-proper and approximately learning sparse parities
The hardness for k-VectorSum proved in Theorem 1.3 can be restated in terms of W[1]-hardness of learning
k-parity, i.e., linear forms depending on at most k variables4 .
Theorem 1.6 (Theorem 1.3 restated). The following is W[1]-hard: given m = O(k log n) point-value pairs
n
{(yi , ai )}m
i=1 ⊆ F2 × F2 , decide whether there exists a k-parity L which satisfies all the point-value pairs, i.e.,
L(yi ) = ai for all i = 1, . . . , m.
Next, we strengthen the above theorem in two ways. We show that the W[1]-hardness holds for learning
a k-parity using a k-junta, and additionally for any desired accuracy exceeding 50%. Here, a k-junta is any
function depending on at most k variables.
Theorem 1.7. The following is W[1]-hard: for any constant δ > 0, given m = O(k · 23k · (log n)/δ 3 )
n
point-value pairs {(zi , bi )}m
i=1 ⊆ F2 × F2 , decide whether:
YES Case: There exists a k-parity which satisfies all the point-value pairs.
NO Case. Any function f : Fn2 7→ F2 depending on at most k variables satisfies at most 1/2 + δ fraction of
the point value pairs.
Theorem 1.7 also implies hardness for approximately learning k-juntas, in comparison to previous W[2]hardness of exactly learning k-juntas shown by Arvind, Köbler and Lindner [AKL09]. Note that the current
best algorithm for learning k-junta, even over the uniform distribution, takes nΩ(k) time [Val12, MOS04].
We similarly strengthen Corollary 1.5 to rule out eﬃcient algorithms for approximately learning a ksparse solution to a homogeneous linear system using constant degree polynomials supported on at most k
variables.
4 Note that Theorem 1.3 as stated shows hardness of learning homogeneous k-parity i.e., homogeneous k-sparse linear forms
(without the constant term). The result can easily be made to hold for any general k-parities by adding a point-value pair
which is (0, 0).

3

Theorem 1.8. Assume that k-Clique does not have a poly(n) time√algorithm for any k = ω(1). Then for
any constant δ > 0 and positive integer d, there is no poly(m, n) · 2o( k) time algorithm to decide whether a
n
given set of m points {zi }m
i=1 ⊆ F2 satisfy:
YES Case: There exists a nonzero k-parity L such that L(zi ) = 0 for all i = 1, . . . , m.
n
NO Case. Any non-trivial degree d polynomial
 P : F2 7→ F2 depending on at most k variables satisfies
P (zi ) = 0 for at most Prz∈Fn2 [P (z) = 0] + δ fraction of the points.

The proof of the above theorem relies on an application of Viola’s [Vio09] pseudorandom generator for
constant degree polynomials, and is inspired by Khot’s [Kho09] NP-hardness of learning linear forms using
constant degree polynomials.
Gap in sparsity parameter
Using techniques similar to those employed in [BEKP15], we prove the following gap in k hardness for
k-VectorSum, i.e., hardness of Gap-k-VectorSum.
Theorem 1.9. Assuming the Exponential Time Hypothesis, there are universal constants δ0 > 0 and c0 such
that there is no poly(N ) time algorithm to determine whether an instance of Gap-k-VectorSum of size N
admits a solution of sparsity k or all solutions are of sparsity at least (1 + δ0 )k, for any k = ω((log log N )c0 ).
c0
More generally, under the same assumption, this problem does not admit an N O(k/ω((log log N ) )) time algorithm for unrestricted k.

1.2

Our Techniques

Our ﬁrst result, Theorem 1.3, is based on a gadget reduction from an n-vertex instance of k-Clique creating
columns of M corresponding to the vertices and edges of the graph along with a target vector b. Unlike
previous reductions which used dimension linear in the number of vertices, we reuse the same set of coordinates for the vertices and edges by assigning
unique logarithmic length patterns to each vertex. In total we

create k columns for each vertex and k2 columns for each edge, using O(k 2 log n) coordinates. The target

vector b ensures that a solution always has at least k + k2 columns, which suﬃces in the YES case while
the NO case requires strictly more columns to sum to b.
For proving Theorem 1.4, we homogenize the instance of Theorem 1.3 by including b as a column of M.
To force the solution to always choose b we use the approach of Austrin and Khot [AK14] who face the
same issue when reducing to the MinimumDistance problem. Since we need to retain the bound on the
sparsity of the solution, we cannot use their techniques directly. Instead, we construct a small length sketch
of a purported sparse solution and use it as an input to a tensor code based ampliﬁcation gadget used in
[AK14]. Our construction however inﬂates the parameter k to O((k log n)2 ).
The hardness of approximately learning k-parities with k-juntas given in Theorem 1.7 is obtained by
transforming the instance of Theorem 1.3 using an ε-balanced code, along with an analysis of the Fourier
spectrum of any k-junta on the resulting distribution. In contrast, Theorem 1.8 is obtained by using the
instance of Theorem 1.4 (appropriately transformed using an ε-balanced code) as an input to Viola’s construction [Vio09] of pseudorandom generators for degree d polynomials. Note that the exp(k) blowup in the
reduction for Theorem 1.7 rules out its use for proving Theorem 1.8 due to the presence of a (log2 n) factor
in the sparsity parameter of the instance obtained in Theorem 1.4. On the other hand, the non-homogeneity
of the k-VectorSum problem hinders the use of Viola’s pseudorandom generator for proving a version (for
degree d polynomials on k variables instead of k-juntas) of Theorem 1.7 which avoids the exp(k) blowup.
For Theorem 1.9, we use the improved sparsification lemma of Calabro, Impagliazzo and Paturi [CIP06]
followed by Dinur’s almost linear PCP construction [Din07] to reduce an n-variable 3-SAT instance to 2εn
Gap-3-SAT instances with almost linear in n clauses and variables. For each instance a corresponding
k-VectorSum instance is created by partitioning the clauses into k blocks and adding F2 -valued variables
for partial assignments to each block along with non-triviality and consistency equations. In the YES case
setting one variable from each block to 1 (i.e. a k-sparse solution) suﬃces, whereas in the NO case at least γk
4

variables need to be set to 1, for some constant γ > 1. The parameters are such that an eﬃcient algorithm
to decide the YES and NO cases would violate the Exponential Time Hypothesis for 3-SAT.
Organization of the paper. Theorem 1.3 is proved in Section 3, and using it as the starting point Theorem
1.4 is proved in Section 4. The reduction proving Theorem 1.7 is given in 5, and starts with a restatement
of Theorem 1.3. The proofs of Theorems 1.8 and 1.9 are provided in Section 6 and Section 7 respectively.
We also include in Appendix B a proof of Khot’s [Kho09] result on NP-hardness of approximately learning
linear forms using constant degree polynomials to illustrate the use of Viola’s pseudorandom generator [Vio09]
which is also used in the proof of Theorem 1.8.
In the next section we give some deﬁnitions and results which shall prove useful for the subsequent
proofs.

2
2.1

Preliminaries
Parameterized Complexity

A parameterization of a problem is a poly(n)-time computable function that assigns an integer k > 0 to each
problem instance x of length n (bits). The pair (x, k) is an instance of the corresponding parameterized
problem. The parameterized problem is said to be fixed parameter tractable (FPT) if it admits an algorithm
that runs in time f (k) · poly(n) where k is the parameter of the input, n is the size of the input, and f is
an arbitrary computable function. The W-hierarchy, introduced by Downey and Fellows [DF95, DF99], is a
sequence of parameterized complexity classes with FPT = W[0] ⊆ W[1] ⊆ W[2] ⊆ · · · . It is widely believed
that FPT 6= W[1].
These hierarchical classes admit notions of completeness and hardness under FPT reductions i.e., f (k) ·
poly(n)-time transformations from a problem A instance (x, k) where |x| = n, to an instance (x′ , k ′ ) of
problem B where |x′ | = poly(n) and k ′ is bounded by f (k). For example, consider the k-Clique problem:
given a graph G on n vertices and an integer parameter k, decide if G has a clique of size k. The kClique problem is W[1]-complete, and serves as a canonical hard problem for many W[1]-hardness reductions
including those in this work.
For a precise deﬁnition of the W-hierarchy, and a general background on parameterized algorithms and
complexity, see [DF99, FG06, CFK+ 15].

2.2

Coding Theoretic Tools

Our hardness reductions use some basic results from coding theory. For our purposes, we shall be restricting
our attention to linear codes over F2 i.e., those which form linear subspaces. A code C ⊆ Fn2 is said to
be a [n, k, d]-binary linear code if C forms a k-dimensional subspace of Fn2 such that all nonzero elements
(codewords) in C are of Hamming weight at least d. We use weight wt(x) of a codeword x to denote its
Hamming weight, distance of a code to denote the minimum weight of any nonzero codeword, and rate to
denote the fraction k/n. A generator matrix G ∈ F2n×k for C is such that C = {Gx | x ∈ Fk2 }. Also
(n−k)×n
satisfying: G⊥ y = 0 iff y ∈ C. We shall use the
associated with C is a parity check matrix G⊥ ∈ F2
generator and parity check matrices of well studied code constructions whose properties we state below.
Theorem 2.1 (BCH Codes, Theorem 3 [BR60]). The dimension of the BCH code of block length n = (2m −1)
and distance d is at least n − ⌈ d−1
2 ⌉m .

While the above theorem restricts the block length to be of the form (2m − 1), for general n we can use
as the parity check matrix any n columns of the parity check matrix of a BCH code of the minimum length
(2m − 1) greater than or equal to n. In particular, we have the following corollary tailored for our purpose.

Corollary 2.2. For all lengths n and positive integers k < n, there exists a parity check matrix R ∈
F220k log n×n such that Rx =
6 0 whenever 0 < wt(x) < 18k. Moreover, this matrix can be computed in time
poly(n, k).
5

The following explicit family of ε-balanced binary linear codes of constant rate was given by Alon et
al. [ABN+ 92].
Theorem 2.3 (ε-balanced codes [ABN+ 92]). There exists an explicit family of codes C ⊆ Fn2 such that every
codeword in C has normalized weight in the range [1/2 − ε, 1/2 + ε], and rate Ω(ε3 ), which can be constructed
in time poly(n, 1ε ), where ε > 0 is an arbitrarily small constant.
Given a linear code C ⊆ Fn2 , the product code C ⊗2 consists of n × n matrices where each row and each
column belongs to C; equivalently, C ⊗2 = {GXGT : X ∈ F2k×k } where G ∈ F2n×k is the generator matrix
for the code C. If the distance d(C) = d, then it is easy to verify that d(C ⊗2 ) > d2 . However, we shall use
the following lemma from [AK14] for a tighter lower bound on the Hamming weight when the code word
satisﬁes certain properties.
Lemma 2.4 (Density of Product Codes [AK14]). Let C ⊆ Fn2 be a binary linear code of distance d = d(C),
and let Y ∈ C ⊗2 be a nonzero codeword with the additional properties that diag(Y) = 0, and Y = YT . Then,
the Hamming weight of Y is at least 23 d2 .

2.3

Some Useful Tools

The proof of Theorem 1.8 in Section 6 and Khot’s [Kho09] result given in Appendix B use Viola’s [Vio09]
construction of pseudorandom generators which we describe below.
Definition 2.5. A distribution D over Fn2 is said to ε-fool degree d polynomials in n-variables over F2 if
for any degree d polynomial P :
E [e(P (z))] − E [e(P (z))] 6 ε,
z←D

z←U

where U is the uniform distribution over Fn2 and e(x) := (−1)x for x ∈ {0, 1}.
Theorem 2.6. Let Y1 , . . . , Yd be d independent distributions on Fn2 that each ε-fool linear polynomials. Then
d−1
the distribution W = Y1 + · · · + Yd εd -fools degree-d polynomials where εd := 16 · ε1/2 .
Our proof of Theorem 1.9 in Section 7 uses the following improved sparsification lemma of Calabro,
Impagliazzo, and Paturi [CIP06].
Lemma 2.7. There is a deterministic algorithm which, for any ε > 0, transforms an n-variable 3-CNF
formula F to F1 , . . . , Fs ∈ 3-CNF, each on at most n variables s.t.
1. s 6 2εn .
2. F is satisfiable if and only if at least one of F1 , . . . , Fs is satisfiable.
3. The number of clauses in each F1 , . . . , Fs is at most O((1/ε)9 · n).
4. The algorithm runs in time 2εn · poly(n), where the degree of the polynomial may depend on ε.
We shall also use in Section 7 the following reduction to Gap-3-SAT implied by the construction of almost
linear sized PCPs given by Dinur [Din07].
Theorem 2.8. There exist universal constants γ0 > 0 and c0 , and a polynomial time reduction from a 3-CNF
formula F on m clauses to a 3-CNF formula F ′ on at most m(log m)c0 clauses such that: (i) (YES Case) if
F is satisfiable then F ′ is satisfiable, and (ii) (NO Case) if F is unsatisfiable then at most (1 − γ0 ) fraction
of the clauses of F ′ are satisfied by any assignment.

6

3

W[1]-hardness of k-VectorSum on O(k log n) Equations

The following theorem implies Theorem 1.3.
Theorem 3.1. There is an FPT reduction from an instance G(V, E) of k-Clique, over n vertices and m
′
edges, to an instance (M, b) of k ′ -VectorSum, where M ∈ F2d×n such that k ′ = O(k 2 ), d = O(k 2 log n)
and n′ is polynomial in n and k.
The rest of this section is devoted to proving the above theorem. We start by observing
that a k-clique

in a graph G(V, E) can be certiﬁed by the pair of mappings f : [k] 7→ V and g : [k]
→
7
E , such that
2

[k]
g(i, j) = (f (i), f (j)) ∈ E ∀i, j ∈ [k], i < j. Here, we use 2 to represent {(i, j) | 1 6 i < j 6 k}. The
underlying idea behind the reduction is to construct M and b such that f and g exist iff there is a sparse
set of columns of M that sums up to b.
Construction of M and b. Let G(V, E) be a k-Clique instance on n = |V | vertices and m = |E| edges,
where V = {v1 , v2 , . . . , vn }. For each vertex vi ∈ V , assign a distinct N = ⌈log(n + 1)⌉ bit nonzero binary
pattern denoted by qi ∈ FN
2 . We ﬁrst construct a set of vectors – which shall be the columns of M –
corresponding to the vertices and edges. The dimension over which the vectors are deﬁned is partitioned
into three sets of coordinates:
Edge-Vertex Incidence Coordinates: These consist of k slots, where each slot consists of (k − 1) subslots,
and each subslot in turn consists of N coordinates. In any column of M, a subslot may either contain the
N -length pattern of a vertex, or it might be all zeros.

Edge Indicator Coordinates: These are a set of k2 coordinates corresponding to {(i, j) | 1 6 i < j 6 k},
indicating whether the vector represents an edge mapped from (i, j). Any column of M may have at most
one of these coordinates set to 1.
Vertex Indicator Coordinates: These are a set of k coordinates corresponding to indices i ∈ {1, . . . , k}, which
indicate whether the vector represents a vertex mapped from i. Any column of M may have at most one of
these coordinates set to 1.

Thus, each vector is a concatenation of k(k − 1)N edge-vertex incidence bits, followed by k2 edge

indicator bits and k vertex indicator bits, so that d = k(k − 1)N + k2 + k = O(k 2 log n). For ease of
notation, let Slj represent the N -sized subset of coordinates belonging to the subslot l of slot j where j ∈ [k]
and l ∈ [k − 1]. We deﬁne qi (Slj ) ∈ Fd2 to be the vector which contains the pattern of vertex vi in Slj , and
is zero everywhere else. For 1 6 i < j 6 k, let δi,j ∈ Fd2 be the vector which has a 1 at the edge indicator
coordinate corresponding to (i, j), and is 0 everywhere else. Similarly, δi ∈ Fd2 is the indicator vector which
has its ith vertex indicator coordinate set to 1, everything else being 0. Use these components we construct
the vertex and edge vectors as follows.
Vertex Vectors: For each vertex vi ∈ V and j ∈ [k], we introduce a vector η(vi , j) ∈ Fd2 which indicates that
vertex vi is mapped from index (slot) j i.e., f (j) = vi . The vector is constructed as follows: populate each of
the (k − 1) subslots of the jth slot with the pattern of vertex vi (which is qi ), and set its jth vertex indicator
Pk−1
coordinate to 1. Formally, η(vi , j) := l=1
qi (Slj ) + δj . For each vertex there are k vertex vectors resulting
in a total of nk vertex vectors.
Edge Vectors: For each edge e = (vi1 , vi2 ) ∈ E where i1 < i2 , and 1 6 j1 < j2 6 k, we introduce a vector
that indicates that the pair of indices (slots) (j1 , j2 ) is mapped to (vi1 , vi2 ) i.e., g(j1 , j2 ) = (vi1 , vi2 ) . We
construct the vector η(e, j1 , j2 ) ∈ Fd2 as follows: populate Sjj21−1 with the pattern of vertex vi1 , and Sjj12 with
the pattern of vertex vi2 . Additionally, we set the edge indicator coordinate corresponding to (j1 , j2 ) to 1.
The vector is formally expressed as, η(e, j1 , j2 ) := qi1 (Sjj21−1 ) + qi2 (Sjj12 ) + δj1 ,j2 . Intuitively, for the lower
ordered vertex vi1 , η(e, j1 , j2 ) cancels out the (j2 − 1)th subslot of slot j1 , and for the higher ordered vertex
vi2 , it cancels out the j1 th subslot of its j2 th slot. Note that we are treating (vi1 , vi2 ) as an unordered pair
since i1 < i2 . Therefore, for each edge e ∈
 E, and for each choice of 1 6 j1 < j2 6 k, we introduce one edge
vector. Hence, there are a total of m · k2 edge vectors in the set.
7

The vertex and edge vectors constructed above constitute the columns
of M. The target vector b ensures

that (i) every solution must have at least k vertex vectors, and k2 edge vectorsP
and (ii) thePvectors must
cancel each other out in the Edge-Vertex Incidence coordinates. Formally, b = i∈[k] δi + 16i<j<k δi,j .
In other words, all the edge and vertex indicator coordinates of b are set to 1, and everything else to 0.

3.1

YES case


We show that if G(V, E) has a k-Clique, then there exists a set of k+ k2 columns of M that sum to b. Assume
that vi1 , vi2 , . . . , vik form a k-clique where i1 < i2 < · · · < ik . We select k vertex vectors {η(vij , j)}j∈[k] , and

k
2 edge vectors {η(e, j1 , j2 ) | e = (vij1 , vij2 ), 1 6 j1 < j2 6 k}. Since the k vertices form a clique, these
vectors always exists. Observe that for any ﬁxed j ∈ [k], (i) for ℓ = 1, . . . , j − 1, η(vij , j) and η(e, ℓ, j) have
the same pattern qij in subslot ℓ of slot j, where e = (viℓ , vij ), and (ii) for ℓ = j + 1, . . . , k, η(vij , j) and

η(e, j, ℓ) have the same pattern qij in subslot (ℓ − 1) of slot j, where e = (vij , viℓ ). Thus, the k + k2 selected
vectors sum to zero on all but the vertex and edge indicator coordinates and thus sum up to b.

3.2

NO Case

Suppose for a contradiction that S is a subset of columns of M that sum to b and that |S| 6 k +

k
2


.

Proposition 3.2. There are exactly k vertex vectors corresponding to indices (slots) i ∈ [k] in S. Also,
there are exactly k2 edge vectors, one for each pair (i, j) (1 6 i < j 6 k) of slots, in S.

Proof. This follows from the observation that there are k + k2 nonzero indicator coordinates in the target
b, and each (edge or vertex) vector contributes exactly one nonzero (edge or vertex) indicator coordinate.
Therefore, by a counting argument, k vertex vectors, one each for the indices (slots) i ∈ [k], must contribute
to the k vertex indicator bits. Similarly, k2 edge vectors, one for each pair of slots (i, j) (1 6 i < j 6 k),

must contribute to the k2 edge indicator bits.


The above proposition implies that for each pair of vertex vectors there is exactly one edge vector which
has a common populated subslot with each of them. So there are exactly (k − 1) edge vectors which share
a populated subslot with any given vertex vector in S.
Since the k vertex vectors in S populate distinct slots, in total k(k − 1) subslots are populated
 by the sum
of the k vertex vectors. Note that any edge vector populates exactly 2 subslots. Thus, for the k2 = k(k−1)/2
edge vectors in S to sum up to the values in k(k − 1) subslots, it must be that no two edge vectors overlap
in the same slot-subslot combination.
Thus, for each vertex vector there are exactly (k − 1) edge vectors which share distinct populated subslots
with it, and these edge vectors must cancel out the corresponding subslots i.e., have the same pattern in the
shared subslot as that of the vertex vector. In other words, for any two vertex vectors corresponding to slots
i and j respectively (i < j), the edge vector corresponding to the pair (i, j) must cancel one subslot from
each one of the two vertex vectors. This is possible only if (i) the k vertex vectors correspond to distinct
vertices in G, and (ii) each pair of these vertices have an edge between them for the corresponding edge
vector to exist. This implies that G has a k-clique which is a contradiction.

4

Parameterized Reduction for the k-EvenSet problem

The following is a restatement of Theorem 1.4.
Theorem 4.1 (Hardness of k-EvenSet). Given an instance (M, t) of k-VectorSum, where M ∈ Fm×n
2
2
′
2
′
and t ∈ Fm
2 , there is a poly(m, n) time reduction to an instance M of O(k log n)-EvenSet, where M ∈
m′ ×n′
′
′
F2
such that m and n are polynomial in n and m.
The rest of this section is devoted to proving the above theorem. The next few paragraphs give an informal
description of the reduction. We then deﬁne the variables and equations of the k-EvenSet instance, and
analyze the completeness and soundness of the reduction.
8

4.1

Reduction Overview

Let Mx = t be a hard instance of k-VectorSum i.e., in the YES case there exists a k-sparse solution,
whereas in the NO case all solutions have Hamming weight at least (k + 1). We homogenize this aﬃne
system by replacing the target vector t by a0 t for some F2 -variable a0 , where a0 t is a coordinate-wise
multiplication of t with the scalar a0 . Clearly, if all (k + 1)-sparse (including a0 as a variable) solutions
to Mx = a0 t have a0 = 1 then the hardness of k-VectorSum implies the desired hardness result for kEvenSet. However, this may not be true in general: there could exist a k-sparse x such that Mx = 0.
The objective of our reduction therefore, is to ensure that any solution to Mx = a0 t that has a0 = 0 with
a k-sparse x, must have signiﬁcantly large weight in other auxiliary variables which we shall add in the
construction.
Towards this end, we borrow some techniques from the proof of the inapproximability of MinimumDistance by Austrin and Khot [AK14]. Using transformations by suitable codes we ﬁrst obtain a K =
O(k log n)-length sketch y = (y1 , . . . , yK ) of x, such that y is of normalized weight nearly 1/2 when x is
k-sparse but nonzero. We then construct a codeword Y ∈ FK×K
, which is intended to be the product code2
word yyT . However, this relationship cannot be expressed explicitly in terms of linear equations. Instead,
for each pair of coordinates (i, j) ∈ [K] × [K], we introduce functions Zij : F2 × F2 7→ F2 indicating the value
taken by the pair (yi , yj ) along with constraints that relate the Zij variables to codewords y and Y. In fact,
the explicit variables {Zij } determine both y and Y which are implicit. The constraints also satisfy the key
property: if x is k-sparse, then the number of nonzero Zij variables is signiﬁcantly larger when a0 = 0 than
when a0 = 1. This forces all sparse solutions to set a0 = 1, which gives us the desired separation in sparsities
between the YES and NO cases.

4.2

Constraints

Let Mx = t be the instance of k-VectorSum over F2 , in n variables and m equations. We homogenize this
system by introducing a new F2 -variable a0 so that the new system of equations is then given by
Mx = a0 t,

(1)

where the a0 t is the coordinate wise product of t with the scalar a0 . We also add the following additional
constraints and variables.
′
Linear Sketch Constraints : Let R ∈ Fk ×n be the parity check matrix of a [n, n − k ′, 18k] linear code, where
′
k = 20k log n, as deﬁned in Corollary 2.2. Deﬁne η to be a k ′ -length sketch of x using R as,
η = Rx.

(2)

′

Mixing Constraints : Let C ∈ F2K×k be the generator matrix of a linear code C ⊆ FK
2 as deﬁned in
20k log n
k′
Theorem 2.3 where C has relative distance 12 −ε and rate Ω(ε3 ) for some small ε > 0 and K = Ω(ε
,
3) 6
cε3
for some constant c > 0. We add the constraint
y = Cη = CRx.

(3)
2

Product Code Constraints : Let C ⊗2 := C C be the product code with relative distance 12 − ε , constructed from C. Let Y = {Yij }16i,j6K ∈ FK×K
be such that Y = yyT . To represent this relation linearly,
2
we introduce variables {Zij (a, b)}a,b∈F2 for each 1 6 i, j 6 K, which are intended to indicate the value assigned to the pair (yi , yj ) i.e., Zij (a, b) = 1{yi = a, yj = b}. For each (i, j) ∈ [K] × [K] we add the following
equations,
N

Zij (0, 0) + Zij (0, 1) + Zij (1, 0) + Zij (1, 1) =

a0

(4)

Zij (1, 0) + Zij (1, 1) =
Zij (0, 1) + Zij (1, 1) =

yi
yj

(5)
(6)

Yij .

(7)

Zij (1, 1) =
9

Furthermore, we add the constraints
QY = 0,
where Q is the parity check matrix for the product code C

(8)
⊗2

, and

Yij

=

Yji

∀i 6= j,

Yii

=

yi

∀i ∈ [K],
T

(9)
(10)
1

2

r−1

so that Y preserves the diagonal entries and symmetry of yy . Finally, we introduce x , x , . . . , x
constraints
xi = x
∀i ∈ [r − 1],

and
(11)

2

2

25k(log n)
where r = K
. These r − 1 explicit copies of the vector x are used to balance the Hamming
16 6
c2 ε6
weight of the ﬁnal solution. Observe that all the variables described above are linear combinations of
a0 , {Zij (·, ·)}i,j∈[k] and the coordinates of the vectors x and {xi }i∈[r−1] . Hence, we analyze the sparsity of
the solution restricted to these explicit variables. The total number of variables considered is 4K 2 + r · n + 1.

Remark : The key diﬀerence between [AK14] and our reduction is in Equation (2) which constructs a small
(O(k log n))-length sketch of the n-length vector x. This helps us contain the blowup in the sparsity of the
solution to O(k 2 log2 n) instead of O(n).

4.3

Completeness

In the YES case, setting a0 = 1 we obtain a k-sparse x such that Mx = a0 t = t. Furthermore, for each
i, j ∈ [K], exactly one of the Zij variables would be nonzero. Hence, we have a solution of weight K 2 + rk + 1.

4.4

Soundness

Since the solution has to be non-trivial, at least one of a0 , x, y, Y must be nonzero. Note that when x = 0,
y = 0 since y is a homogeneous linear transformation of x. Moreover, we may assume that the weight of x
K 2 +1
+ k +1 < 18k by our setting of r, otherwise the total weight of the solution would be at
is at most
r

2

least r · K r+1 + k + 1 > K 2 + r(k + 1) + 1 due to the copies of x and we would be done. The construction
of y along with the upper bound of 18k on the weight of x constrains y to be nonzero when x is nonzero.
Thus, the only three cases we need to consider are:

Case (i): a0 = 1. In this case, any solution x to Mx = a0 t = t has weight at least k + 1. Furthermore,
for each i, j ∈ [K], at least one of the four Zij variables must be nonzero since a0 = 1. Hence, the total
Hamming weight of the solution is at least K 2 + r(k + 1) + 1.

Case (ii): a0 = 0, x 6= 0, y 6= 0. By construction, since y is nonzero it has weight > 12 − ε K. Therefore,

2
for at least 1 − 12 + ε > 43 − 2ε fraction of the pairs (i, j) ∈ [K] × [K], either yi = 1 or yj = 1 . Observe
that for each
two Zij variables are set to 1. Thus, the weight of any solution in this case
 such pair,
 at least

is at least 2

3
4

− 2ε K 2 =

3
2

− 4ε K 2 .

Case (iii): a0 = 0, x = 0, y = 0, Y 6= 0. We have that diag(Y) = y = 0, Y is symmetric and it belongs
to the product
C ⊗2 (as enforced by Equations (8) and (9)). Then by lemma 2.4, the weight of Y is at
 code
3
2
least 8 − 3ε K . Observe that for each i, j ∈ [K] such that Yij = 1, Equations (4)-(7) force all four Zij
variables to be set to 1. Hence, the number of nonzero Zij ’s are at least 32 − 12ε K 2 .

The above analysis yields that in contrast to the YES case which admits a (K 2 + rk + 1)-sparse solution,
in the NO case all solutions are of weight at least




 3
2
2
min K + r(k + 1) + 1 ,
> K 2 + r(k + 1) + 1
− 12ε K
2

by choice of the parameter r. Thus, solving the d-EvenSet problem with d = K 2 + rk + 1 = O(k 2 (log n)2 )
solves the k-VectorSum instance Mx = t.
10

5

Hardness of Learning k-Parities using k-Juntas

The hardness for k-VectorSum proved in Theorem 1.3 can be restated in terms of W[1]-hardness of learning
k-parities, i.e. linear forms depending on at most k-variables.
Theorem 5.1. The following is W[1]-hard: given r = O(k log n) point-value pairs {(yi , ai )}ri=1 ⊆ Fn2 × F2 ,
decide whether there exists a homogeneous linear form L supported on at most k variables which satisfies all
the point-value pairs, i.e. L(yi ) = ai for all i = 1, . . . , t.
Combining the above with a small bias linear code we induce an approximation gap for learning k-parities
along with extending the result to non-homogeneous linear forms.
Theorem 5.2. The following is W[1]-hard: for any ε > 0 depending only on k, given t = O(k log n/ε3 )
point-value pairs {(zi , bi )}ti=1 ⊆ Fn2 × F2 , decide whether:
YES Case: There exists a homogeneous linear form supported on at most k variables which satisfies all the
point-value pairs.
NO Case. Any linear form supported on at most k variables satisfies a fraction in the range [1/2 − ε, 1/2 + ε]
of the point value pairs.
Proof. Let W = {Wij } ∈ Ft×r
be the generator matrix of an ε-balanced linear code given by Theorem 2.3,
2
where t = O(r/ε3 ). Given an instance {(yj , aj )}rj=1 from Theorem 5.1, let
zi =

r
X

Wij yj ,

and

bi =

r
X

Wij aj ,

j=1

j=1

for i = 1, . . . , t.
In the YES case, there is a homogeneous linear form L∗ that satisﬁes all {(yj , aj )}rj=1 and thus satisﬁes
linear combinations of these point-value pairs, in particular {(zi , bi )}ti=1 .
For the NO case, consider any linear form L(x) + c. Since the homogeneous part L does not satisfy
all pairs {(yj , aj )}rj=1 , it will satisfy a fraction in the range [1/2 − ε, 1/2 + ε] of the pairs {(zi , bi )}ti=1 , due
the lower and upper bounds bound on the weight of the nonzero codewords in the column space of W.
Thus, the linear form L(x) + c also satisﬁes a fraction in the range [1/2 − ε, 1/2 + ε] of the point-value pairs
{(zi , bi )}ti=1 .

As we show below, using a small enough bias ε in the above construction, one can strengthen the hardness
result to learning k-parities with k-juntas, i.e. functions depending only on a subset of at most k variables.
Theorem 5.3. (Theorem 1.7 restated) The following is W[1]-hard: for any constant δ > 0, given t =
O(k · 23k · log n/δ 3 ) point-value pairs {(zi , bi )}ti=1 ⊆ Fn2 × F2 , decide whether:
YES Case: There exists a homogeneous linear form supported on at most k variables which satisfies all the
point-value pairs.
NO Case. Any function f : Fn2 7→ F2 depending on at most k variables satisfies at most 1/2 + δ fraction of
the point value pairs.
Proof. The construction of Z = {(zi , bi )}ti=1 is exactly the same as in the proof of Theorem 5.2 taking
ε = δ · 2−k . The YES case follows directly as before.
For the NO case, let f : Fn2 7→ F2 be a function depending only a subset S ⊆ [n] of coordinates where
|S| 6 k. Deﬁne an extension g : Fn+1
7→ F2 as g(x1 , . . . , xn , xn+1 ) := f (x1 , . . . , xn ) + xn+1 . For convenience
2
we shall abuse notation to denote (z, b) = (z1 , . . . , zn , b) where z = (z1 , . . . , zn ) ∈ Fn2 and b ∈ F2 . To complete
the proof we need to show that,
E

(z,b)∈Z

[e(g(z, b))] 6 2δ,

11

(12)

where e(x) := (−1)x . For some real values Cα (α ⊆ [n + 1]), the Fourier expansion of e(g) is given by,
X
Cα χα .
e(g) =
α⊆[n+1]

Since e(g(x1 , . . . , xn+1 )) = e(f (x1 , . . . , xn ) + xn+1 ) and f depends only on coordinates in S, it is easy to see
that the Fourier spectrum of e(g) is supported only on characters χα such that α ⊆ S ∪ {n + 1}. Further,
since e(g(x1 , . . . , xn+1 )) changes sign on ﬂipping xn+1 , Cα 6= 0 ⇒ (n + 1) ∈ α. Thus,
X
Cα χα .
(13)
e(g) =
α⊆S∪{n+1}
(n+1)∈α

Observe that for any α in the sum above, χα (x1 , . . . , xn , b) = e(L(x1 , . . . , xn ) + b) where L is a homogeneous
linear form supported on at most k variables. For any such α, the NO case of Theorem 5.2 implies,
E

(z,b)∈Z

[χα (z, b)] 6 2ε

(14)

Using the above along with Equation (13) yields,
E

(z,b)∈Z

[e(g(z, b))]

6 (2ε) ·

X

|Cα |

α⊆S∪{n+1}
(n+1)∈α

6 (2ε) · 2k = 2δ,
where the last inequality is because there are at most 2k subsets α in the sum on the RHS of Equation (13)
and each |Cα | 6 1 since e(g) is a {−1, 1}-valued function.


6

Proof of Theorem 1.8

We ﬁrst prove the following strengthening of Theorem 1.4 along the same lines as Theorem 5.2 in Section 5.
Theorem 6.1 (Hardness of approximate k-EvenSet). For any constant ε > 0, given an instance (A, b) of
′
′
′
m×n
k ′ -VectorSum, where A ∈ F2m ×n and b ∈ Fm
of
2 , there is an FPT reduction to an instance B ∈ F2
′
′
′ 2
k -EvenSet for some k = O((k log n ) ), such that
YES Case: There is a nonzero k-sparse vector x which satisfies Bx = 0.
NO Case. For any nonzero k-sparse vector x the weight of Bx is in the range [1/2 − ε, 1/2 + ε].
Here both m and n are bounded by fixed polynomials in m′ and n′ .
Proof. Let M ∈ Fr×n
be the instance of k-EvenSet obtained by applying Theorem 1.4 to the instance
2
be the generator
(A, b) of k ′ -VectorSum we start with. As in the proof of Theorem 5.2 let W ∈ Fm×r
2
matrix of an ε-balanced linear code given by Theorem 2.3, where m = O(r/ε3 ). Taking B := WM completes
the proof.

It is easy to see that the uniform distribution on the rows of the matrix B fools all linear forms (with
error ε) over k variables. Viola’s result [Vio09] (Theorem 2.6) implies that for any constant d, taking d-wise
d−1
sums of the rows of M yields a distribution which fools all degree d polynomials with error 16 · ε1/2 .
Taking ε to be a small enough constant yields the following theorem which implies Theorem 1.8.
Theorem 6.2. For any constants δ > 0 and positive integer d, given an instance (A, b) of k ′ -VectorSum,
′
′
′
m
n
where A ∈ F2m ×n and b ∈ Fm
2 , there is an FPT reduction to a set of m points {zi }i=1 ⊆ F2 such that for
′
′ 2
some k = O((k log n ) ),
12

YES Case: There exists a k-parity L such that L(zi ) = 0 for all i = 1, . . . , m.
NO Case. Any degree d polynomial
P : Fn2 7→ F2 depending on at most k variables satisfies P (zi ) = 0 for at

n
most Prz∈F2 [P (z) = 0] + δ fraction of the points.

In the above m and n are bounded by fixed polynomials in m′ and n′ .

7

Hardness Reduction for Gap-k-VectorSum

In this section we ﬁrst prove the following theorem.
Theorem 7.1. For universal constants δ0 > 0 and c0 , and any arbitrarily small constant ε > 0, there is a
2O(εn) -time Turing reduction from an n-variable 3-CNF formula F to s 6 2εn instances I1 , . . . , Is of Gap′
k-VectorSum, each of size at most O(k 2 · 2O(n /k) ) where n′ = cε n(log n)c0 for some constant cε depending
on ε, such that
YES Case. If F is satisfiable, then at least one instance Ij (j ∈ [s]) admits a solution of sparsity k.
NO Case. If F is unsatisfiabe, then no instance Ij admits a solution of sparsity 6 (1 + δ0 )k.
Proof. Let F be a 3-CNF formula on n-variables. We use Lemma 2.7 to obtain 3-CNF fomulas H1 , . . . Hs
for s 6 2εn , each on at most n variables and O((1/ε)9 · n) clauses. Using Theorem 2.8, each Hj (j ∈ [s]) is
separately transformed into a Gap-3-SAT instance Fj with at most n′ = cε n(log n)c0 clauses (and variables),
for some cε = O((1/ε)9 ). Each Fj is now reduced to an instance Ij of Gap-k-VectorSum as follows.
Fix j ∈ [s] and let C(Fj ) denote the set of clauses of Fj . We may assume that |C(Fj )| is divisible by
k by adding up to k dummy clauses which are always satisﬁed. Let B1j , . . . , Bkj be any arbitrary partition
of C(Fj ) into k equal sized subsets, and let X(Bij ) be the set of variables contained in the clauses Bij . Let
j
SAT(Bij ) ⊆ {0, 1}X(Bi ) be the set of assignments to the variables X(Bij ) that satisfy all the clauses in Bij ,
for 1 6 i 6 k. For each α ∈ SAT(Bij ) we introduce an F2 -valued variable zα , and add the following equation,
X
zα = 1,
(15)
α∈SAT(Bij )

for each i = 1, . . . , k. We also add equations to ensure consistency of the solution across diﬀerent blocks
of variables. For each pair of distinct blocks Bij and Bij′ and each assignment to their common variables
j
j
σ ∈ {0, 1}X(Bi )∩X(Bi′ ) we add the following equation.
X
X
zα =
zβ .
(16)
α∈SAT(Bij )
σ=α|
j

β∈SAT(Bij′ )
σ=β|
j

j
X(B )∩X(B ′ )
i
i

j
X(B )∩X(B ′ )
i
i

It is easy to see that |X(Bij )| = O(n′ /k) and |SAT(Bij )| 6 2O(n /k) for 1 6 i 6 k. Thus, the above
′
′
construction of Ij has at most k · 2O(n /k) variables, and at most k 2 · 2O(n /k) equations. The constant c0 is
the same as in Theorem 2.8 and δ0 shall be chosen later.
′

7.1

YES Case

If F is satisﬁable, the for some j ∗ ∈ [s], Hj ∗ is satisﬁable and therefore Fj ∗ is satisﬁable. Let π be a satisfying
∗
assignment for Fj ∗ . In Ij ∗ , for each Bij (1 6 i 6 k) we set the variable zα corresponding to the projection
∗
∗
α ∈ SAT(Bij ) of π on to the variables X(Bij ) to 1, and the rest of the variables to 0. Clearly, this satisﬁes
Equations (15) and (16) since π is a satisfying assignment. As we set exactly one variable per block to 1,
Ij ∗ admits a solution of sparsity k.

13

7.2

NO Case

If F is not satisﬁable, then none of H1 , . . . , Hs are satisﬁable and thus, for each j = 1, . . . , s, at most (1 − γ0 )
fraction of the clauses of Fj are satisﬁable by any assignment. Fix any j ∈ [s]. Since B1j , . . . , Bkj is a balanced
partition of C(Fj ), any assignment to the variables of Fj can satisfy all the clauses of at most (1 − γ0 ) fraction
of Bij , 1 6 i 6 k.
Consider a solution to Ij of sparsity at most (1 + δ0 )k. By Equation (15), this solution must set an odd
number of variables in {zα | α ∈ SAT(Bij )} to 1, for 1 6 i 6 k. Let S ⊆ [k] consist of all indices i ∈ [k] such
that exactly one variable zαi for some αi ∈ SAT(Bij ) is set to 1. Thus, the sparsity is at least |S| + 3(k − |S|),
which is at most (1 + δ0 )k by our assumption. By rearranging we get |S| > (1 − δ0 /2)k. Further, Equation
′
(16) implies that for any i, i′ ∈ S, the assignments αi and αi are consistent on their common variables.
j
Thus, there is an assignment to the variables in ∪i∈S X(Bi ) that satisﬁes all the clauses of Bij for i ∈ S.
Choosing δ0 = γ0 yields a contradiction to our assumption, and therefore no Ij admits a solution of sparsity
at most (1 + δ0 )k.

Theorem 7.1 proved above implies the following restatement of Theorem 1.9.
Theorem 7.2. Assuming the Exponential Time Hypothesis, there are universal constants δ0 > 0 and c0 such
that there is no poly(N ) time algorithm to determine whether an instance of Gap-k-VectorSum of size N
admits a solution of sparsity k or all solutions are of sparsity at least (1 + δ0 )k, for any k = ω((log log N )c0 ).
c0
More generally, under the same assumption, this problem does not admit an N O(k/ω((log log N ) )) time algorithm for unrestricted k.
Proof. For the ﬁrst part of the theorem, assume for a contradiction that such an algorithm exists. In Theorem
7.1, the size of each Gap-k-VectorSum instance constructed is at most N , where log N = O(log k +n′ /k) =
O(log k)+ O(cε n(log n)c0 /k). Here n is the number of variables in the 3-CNF formula F . Thus, choosing k =
ω((log log N )c0 ) implies k = ω((log n)c0 ). Note that in the reduction k is bounded by poly(n). Our supposed
′
algorithm would decide each Gap-k-VectorSum instance in time poly(k, 2O(n /k) ) = 2o(n) . Applying this
to all the instances of Gap-k-VectorSum would decide the n-variable 3-CNF formula F in time 2(ε+o(1))n
for all constants ε > 0, which contradicts the ETH.
A similar analysis proves the second part (unrestricted k) of the theorem.


Acknowledgements
We thank Subhash Khot for his permission to include his proof for the hardness of learning parities using
polynomials. Also, thanks to Ryan Williams for encouraging and stimulating conversations and to Rocco
Servedio for bringing [AKL09] to our attention .

References
[ABN+ 92] Noga Alon, Jehoshua Bruck, Joseph Naor, Moni Naor, and Ron M Roth. Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs. IEEE Trans. Inform. Theory, 38(2):509–516, 1992. 6
[AK14]

Per Austrin and Subhash Khot. A simple deterministic reduction for the gap minimum distance
of code problem. IEEE Trans. Inform. Theory, 60(10):6636–6645, 2014. 1, 3, 4, 6, 9, 10, 17

[AKL09]

Vikraman Arvind, Johannes Köbler, and Wolfgang Lindner. Parameterized learnability of juntas.
Theor. Comp. Sci., 410(47-49):4928–4936, 2009. 3, 14

[ALW14]

Amir Abboud, Kevin Lewi, and Ryan Williams. Losing weight by gaining edges. In Proc. 22nd
Annual European Symposium on Algorithms, pages 1–12. Springer, 2014. 3

14

[BEKP15] Edouard Bonnet, Bruno Escoﬃer, Eun Jung Kim, and Vangelis Th. Paschos. On subexponential
and fpt-time inapproximability. Algorithmica, 71(3):541–565, 2015. 2, 4
[BGM10]

Harry Buhrman, David Garcı́a-Soriano, and Arie Matsliah. Learning parities in the mistakebound model. Inform. Process. Lett., 111(1):16–21, 2010. 2

[BGR15]

Arnab Bhattacharyya, Ameet Gadekar, and Ninad Rajgopal. On learning k-parities with and
without noise. arXiv preprint arXiv:1502.05375, 2015. 2

[BIWX11] Arnab Bhattacharyya, Piotr Indyk, David P Woodruﬀ, and Ning Xie. The complexity of linear
dependence problems in vector spaces. In Proc. 2nd Innovations in Computer Science, pages
496–508, 2011. 1
[BKW03]

Avrim Blum, Adam Kalai, and Hal Wasserman. Noise tolerant learning, the parity problem,
and the statistical query model. J. ACM, 50(4):506–519, 2003. 2

[Blu96]

Avrim Blum. On-line algorithms in machine learning. In Workshop on on-line algorithms,
Dagstuhl, pages 305–325. Springer, 1996. 2

[BR60]

R. C. Bose and Dwijendra K. Ray-Chaudhuri. On A class of error correcting binary group codes.
Information and Control, 3(1):68–79, 1960. 5

[CFK+ 15] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin
Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer International Publishing, 2015. 2, 5
[CIP06]

Chris Calabro, Russell Impagliazzo, and Ramamohan Paturi. A duality between clause width
and clause density for SAT. In 21st Annual IEEE Conference on Computational Complexity,
pages 252–260, 2006. 4, 6

[CW08]

Qi Cheng and Daqing Wan. Complexity of decoding positive-rate reed-solomon codes. In Proc.
35th Annual International Conference on Automata, Languages, and Programming, pages 283–
293. Springer, 2008. 1

[CW09]

Qi Cheng and Daqing Wan. A deterministic reduction for the gap minimum distance problem.
In Proc. 41st Annual ACM Symposium on the Theory of Computing, pages 33–38. ACM, 2009.
1

[DF95]

Rodney G. Downey and Michael R. Fellows. Fixed-parameter tractability and completeness I:
basic results. SIAM J. on Comput., 24(4):873–921, 1995. 5

[DF99]

Rodney G Downey and Michael Ralph Fellows. Parameterized complexity. Springer Science &
Business Media, 1999. 1, 5

[DFVW99] Rod G Downey, Michael R Fellows, Alexander Vardy, and Geoﬀ Whittle. The parametrized
complexity of some fundamental problems in coding theory. SIAM J. on Comput., 29(2):545–
570, 1999. 1, 2
[Din07]

Irit Dinur. The pcp theorem by gap ampliﬁcation. J. ACM, 54(3), 2007. 4, 6

[DMS03]

Ilya Dumer, Daniele Micciancio, and Madhu Sudan. Hardness of approximating the minimum
distance of a linear code. IEEE Trans. Inform. Theory, 49(1):22–37, 2003. 1

[FG06]

Jörg Flum and Martin Grohe. Parameterized Complexity Theory. Springer Verlag, 2006. 5

[FGKP09] Vitaly Feldman, Parikshit Gopalan, Subhash Khot, and Ashok Kumar Ponnuswami. On agnostic
learning of parities, monomials, and halfspaces. SIAM J. on Comput., 39(2):606–645, 2009. 2

15

[FGMS12] Michael R Fellows, Jiong Guo, Dániel Marx, and Saket Saurabh. Data reduction and problem
kernels (Dagstuhl Seminar 12241). Dagstuhl Reports, 2(6):26–50, 2012. 1
[FM12]

Fedor V Fomin and Dániel Marx. FPT suspects and tough customers: Open problems of Downey
and Fellows. In The Multivariate Algorithmic Revolution and Beyond, pages 457–468. Springer,
2012. 1

[GKS10]

Parikshit Gopalan, Subhash Khot, and Rishi Saket. Hardness of reconstructing multivariate
polynomials over ﬁnite ﬁelds. SIAM J. on Comput., 39(6):2598–2621, 2010. 2, 18

[Hås01]

Johan Håstad. Some optimal inapproximability results. Journal of the ACM (JACM), 48(4):798–
859, 2001. 2

[Kho06]

Subhash Khot. Ruling out PTAS for graph min-bisection, dense k-subgraph, and bipartite clique.
SIAM J. on Comput., 36(4):1025–1071, 2006. 17

[Kho09]

Subhash Khot. personal communication, 2009. 2, 4, 5, 6, 17

[KMV08]

Adam Tauman Kalai, Yishay Mansour, and Elad Verbin. On agnostic boosting and parity
learning. In Proc. 40th Annual ACM Symposium on the Theory of Computing, pages 629–638.
ACM, 2008. 2

[KS06]

Adam R Klivans and Rocco A Servedio. Toward attribute eﬃcient learning of decision lists and
parities. J. Mach. Learn. Res., 7:587–602, 2006. 2

[KS15]

Subhash Khot and Igor Shinkar. On hardness of approximating the parameterized clique problem. Electronic Colloquium on Computational Complexity (ECCC), 22:13, 2015. http://eccc.hpiweb.de/report/2015/013. 2

[LW05]

Michael Luby and Avi Wigderson. Pairwise independence and derandomization. Foundation
and Trends in Theoretical Computer Science, 1(4):237–301, 2005. 18

[Mic14]

Daniele Micciancio. Locally dense codes. In Proc. 29th Annual IEEE Conference on Computational Complexity, pages 90–97. IEEE, 2014. 1

[MOS04]

Elchanan Mossel, Ryan O’Donnell, and Rocco A. Servedio. Learning functions of k relevant
variables. J. Comp. Sys. Sci., 69(3):421–434, November 2004. 3

[Val12]

Gregory Valiant. Finding correlations in subquadratic time, with applications to learning parities
and juntas. In Proc. 53rd Annual IEEE Symposium on Foundations of Computer Science, pages
11–20. IEEE, 2012. 3

[Var97]

Alexander Vardy. The intractability of computing the minimum distance of a code. IEEE Trans.
Inform. Theory, 43(6):1757–1766, 1997. 1

[Vio09]

Emanuele Viola. The sum of D small-bias generators fools polynomials of degree D. Computational Complexity, 18(2):209–217, 2009. 4, 5, 6, 12, 18

A

A simple O(n · 2m)-time algorithm for k-VectorSum

Let (M, b) be an instance of k-VectorSum where M ∈ Fm×n
and b ∈ Fm
2 . Construct a graph G on vertex
2
m
set V = F2 and edge set given by,

 

V
E = {u, v} ∈
| u + v is a column of M .
2

16

We say that an edge {u, v} ∈ E is labeled by the column u + v of M. Clearly, if there is a vector x of
Hamming weight at most k such that Mx = b then there is a path of length at most k in G from 0 to
b given by choosing the edges labeled by the columns corresponding to the non-zero entries of x in any
sequence. On the other hand, if there is a path in G from 0 to b of length at most k, then there is a sequence
of at most k columns (with possible repetitions) of M which sum up to b. Cancelling out even number
of repetitions of any column yields a subset of at most k distinct columns of M that sum up to b. Thus,
deciding k-VectorSum reduces to determining whether there is a path of length at most k from 0 to b.
The size of V is 2r and of E is at most n · 2m , and the graph can be constructed in time O(n · 2m ). Doing
a Breadth First Search yields a running time of O(n · 2m ).

B

Optimal hardness of learning parities using degree d polynomials

The hardness reduction in this section is due to Khot [Kho09].
The starting point of the reduction is the MinimumDistance problem over F2 : given a matrix A ∈ Fm×n
,
2
ﬁnd a nonzero vector z ∈ Fn2 to minimize wt(Az) where wt(a) is the normalized hamming weight of a. The
latter quantity denotes the distance of the code given by the linear span of the columns of A.
Below we restate the hardness of MinimumDistance as proved by Austrin and Khot [AK14] along
with an additional guarantee satisﬁed by their reduction in the YES case which shall prove useful for the
subsequent application.
, it
Theorem B.1. [[AK14]] There is a universal constant ζ ∈ (0, 1/5) such that given a matrix A ∈ Fm×n
2
is NP-hard to distinguish between the following:
YES Case. There is a vector z = (z1 , . . . , zn ) ∈ Fn2 such that z1 = 1 and wt(Az) 6 ζ.
NO Case. For any nonzero vector z ∈ Fn2 , wt(Az) > 5ζ.
The following is an easy consequence of above obtained by tensoring the instance of the above theorem.
Theorem B.2. There is a universal constant ζ ∈ (0, 1/5) such that for any constant positive integer K,
given a matrix A ∈ Fm×n
, it is NP-hard to distinguish between the following:
2
YES Case. There is a vector z = (z1 , . . . , zn ) ∈ Fn2 such that z1 = 1 and wt(Az) 6 ζ K .
NO Case. For any nonzero vector z ∈ Fn2 , wt(Az) > 5K ζ K .
From the above we obtain – using techniques similar to those used in [Kho06] – the following hardness
of distinguishing between an MinimumDistance instance of distance ε vs. 1/2 − ε.
, it is NP-hard to distinguish
Theorem B.3. For any positive constant ε > 0, given a matrix B ∈ Fm×n
2
between the following:
YES Case. There is a vector z = (z1 , . . . , zn ) ∈ Fn2 such that z1 = 1 and wt(Bz) 6 ε.
NO Case. For any nonzero vector z ∈ Fn2 , 1/2 − ε 6 wt(Bz) 6 1/2 + ε.
Proof. Let A ∈ Fm×n
be an instance of MinimumDistance from Theorem B.2 for a large value of K. Let
2
Ai , i = 1, . . . , m be the rows of A. Let G be a regular expander on m vertices labeled from [m], with degree

10
D = 5K4ζ K
and second largest eigenvalue λ 6 D0.9 , which can be constructed eﬃciently. Note that
λ/D 6 (5K ζ K )/4.
Let t = 1/(2K ζ K ) and consider all t length random walks [i1 , i2 , . . . , it ] in G. There are m · Dt of such
walks. For each such walk we add 2t rows in B given by


t

X
sj Aij | s1 , . . . , st ∈ F2 .


j=1

17

In total, there are m′ = m · (2D)t rows in B and n columns.
YES Case
Let z be the vector given in the YES case of Theorem B.2, such that there are at most ζ K fraction of rows
Ai satisfying hAi , zi = 1. For a random walk in G, the probability that it contains an index corresponding
to any such row is at most tζ 6 1/2K . Thus, wt(Bz) 6 1/2K .
NO Case
Consider any z ∈ Fn2 . From the NO case of Theorem B.2, we have that at least 5k ζ K fraction of the rows
Ai satisfy hAi , zi = 1. Let I be the set of the indices corresponding to these rows. Using the analysis in
Section 4.7 of [LW05] we can bound the probability that a t length random walk [i1 , . . . , it ] in G does not
contain an index from I as follows.
t
p
λ
K
K
Pr [i1 6∈ I, i2 6∈ I, . . . , it 6∈ I] 6
1−5 ζ +
D
p
t
5K ζ K
6
1 − 5K ζ K +
4
K K


1/(ζ
2
)
5K ζ K
6
1−
4
6 e−(5/2)

K

/4

K

6 2−2 .

K

Thus, at least 1 − 2−2 fraction of the random walks contain an index from I. For any such walk, exactly
half of the 2t linear combinations of the corresponding rows result in a row Br of B such that hBr , zi = 0.
K
K
Thus, (1/2)(1 − 2−2 ) 6 wt(Bz) 6 (1/2)(1 + 2−2 ). Choosing K to be large enough completes the proof.


B.1

Main Theorem

The following theorem shows optimal hardness of learning linear forms by degree d polynomials and subsumes
the weaker results in [GKS10].
Theorem B.4. For any constants δ > 0 and positive integer d, given a set of point-value pairs {(xi , yi )}M
i=1 ⊆
FM
×
F
,
it
is
NP-hard
to
distinguish
whether
2
2
YES Case. There is a linear form ℓ∗ : FN
2 7→ F2 such that for at least (1 − δ) fraction of the pairs (x, y),
ℓ∗ (x) = y.
NO Case. Any degree d polynomial p : FN
2 7→ F2 satisfies p(x) = y for at most (1/2 + δ) fraction of the
point-value pairs.
Proof. Let B ∈ Fm×n
be the matrix given by Theorem B.3 for a parameter ε > 0 to be chosen small
2
enough. For each combination of d rows of B we add a point-value pair in our instance as follows. For
r = (r1 , . . . , rn ) obtained by summing some d rows of B we add ((r2 , . . . , rn ), r1 ) to our instance. Thus,
M = md and N = n − 1.
YES Case
Let z = (z1 , . . . , zn ) with z1 = 1 be the vector from the YES case of Theorem B.3 satisfying hz, bi = 0 for at
Pn−1
least (1 − ε) fraction of the rows b of B. Deﬁning ℓ∗ (x) = j=1 zj+1 xj , we obtain that for (1 − ε) fraction
of the rows (b1 , . . . , bn ) of B, ℓ∗ (b2 , . . . , bn ) = b1 . Thus, for at least (1 − εd) fraction of the point-value pairs
(x, y) of the instance constructed above, ℓ∗ (x) = y.
NO Case
In the NO case, the uniformly random distribution over the rows of B fools every linear form ℓ : Fn2 7→ F2
with bias ε. By the result of Viola [Vio09] (Theorem 2.6), the distribution given by uniformly random
18

d−1

d-wise sums of of the rows of B fools all degree d polynomials q : Fn2 7→ F2 with bias εd = 16 · ε1/2 .
Let (r1 , . . . , rn ) be a random element from the latter distribution, and let q(r1 , . . . , rn ) = r1 + p(r2 , . . . , rn )
where p is a degree d polynomial. Since q is linear in the ﬁrst coordinate, the bias of q under the uniform
distribution is 0, and p(r2 , . . . , rn ) 6= r1 for at least 1/2 − εd fraction of (r1 , . . . , rn ).
Thus, for any degree d polynomial p, for at least 1/2−εd fraction of the point-value pairs (x, y) constructed
in our instance p(x) 6= y.
d−1
To complete the reduction we choose ε to be small enough so that max{εd, 16 · ε1/2 } 6 δ.


19

