This work investigates the hardness of computing sparse solutions to systems of linear equations over F 2 . Consider the k -EvenSet problem: given a homogeneous system of linear equations over F 2 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 ( n k 2 ) -time algorithm for it, establishing fixed parameter intractability for k -EvenSet has been a notorious open problem. Towards this goal, we show that unless k -Clique can be solved in n o ( k ) time, k -EvenSet has no poly ( n ) 2 o ( k ) time algorithm for all k and no polynomial time algorithm when k = ( log 2 n ) .

Our work also shows that the non-homogeneous generalization of the problem -- which we call k -VectorSum -- 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 for any constant 0"> 0 , 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. 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 n o ( k ) time, there is no poly ( m n ) 2 o ( k ) time algorithm to decide whether a given set of m points in F 2 n 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 Pr F n 2 [ 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 c 0 , 0"> 0 0 there is no poly ( n ) time algorithm for Gap- k -VectorSum when k = (( log log n ) c 0 ) .