Abstract: We study the problem of minimizing a submodular function, defined on subsets of a ground set of n elements, that is known to have a k-sparse minimizer. We provide a deterministic algorithm which computes an additive \epsilon-approximate minimizer in \otilde(poly(k) log |f| / \epsilon) rounds of (poly(n)) queries to the value oracle, where |f| = max_{S \subseteq [n]} |f(S)|. We also provide an algorithm that finds an exact minimizer in \otilde(n poly(k)) queries. When the sparsity parameter is small, namely k = \otilde(1), the first algorithm is nearly-constant depth, and the second is a nearly-linear-query algorithm (in the size of the ground set). To obtain our results, we introduce the novel concept of sparse dual certificates, which capture the structure of function f over k-sparse subsets and provide first-order methods to efficiently compute them. By contrast, previous state-of-the-art works on SFM use cutting plane methods, which fail to leverage the sparsity assumption, while our first-order methods are tailored to the geometry of sparse subsets and are arguably more "combinatorial'' in nature. Based on joint work with Haotian Jiang and Aaron Sidford.