On the hardness of learning sparse parities

2015/11/26 by Arnab Bhattacharyya, Ameet Gadekar, Bhattacharyya, Arnab +5
Computer Science · #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #cs.CC #cs.DM #cs.DS

paper · pdf · doi:10.48550/arxiv.1511.08270

arxiv created 2015/11/26 · arxiv updated 2015/11/30

Abstract

This work investigates the hardness of computing sparse solutions to systems of linear equations over F₂. Consider the k-EvenSet problem: given a homogeneous system of linear equations over F₂ 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(sqrtk) time algorithm and no polynomial time algorithm when k = (log n)^2+eta for any eta > 0. 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 Omega(n) equations. We also show that for any constant eps > 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 if every function on at most k-variables (k-junta) satisfies at most (1/2 + eps)-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(sqrtk) time algorithm to decide whether a given set of m points in F₂ⁿ 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 approx. Pr_F2ⁿ[P(z) = 0] fraction of the points i.e., P is fooled by the set of points.

Related

• Approximating the Number of Relevant Variables in a Parity Implies Proper Learning
• Near-Optimal Time-Sparsity Trade-Offs for Solving Noisy Linear Equations
• On learning k-parities with and without noise
• The Fine-Grained Hardness of Sparse Linear Regression
• Sparse Solutions to Nonnegative Linear Systems and Applications