Export Reviews, Discussions, Author Feedback and Meta-Reviews

This paper presents an efficient algorithm for learning sparse polynomial functions over boolean domain. The polynomial functions are represented by a linear combination of parity functions so that the learning is essentially finding all the non-zero coefficients. Given a set of observations, the sparse polynomial learning is formulated into a compressive sensing problem over a large scale linear system. Different from [12][13], this paper presents theoretical results on finding the active set (the indices of non-zero coefficients) efficiently by using the unique sign pattern property, and also an application to graph sketching in social network data.