# Improved Lower Bounds for Submodular Function Minimization

arXiv: https://arxiv.org/abs/2207.04342 · HTML: https://mlsanity.com/paper/2207.04342/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Jul 2022.

## Built on by (most cited first, 1 of 1)

- [Parallel Sampling via Counting](https://mlsanity.com/paper/2408.09442/) (2024)

## Abstract (arXiv)

We provide a generic technique for constructing families of submodular functions to obtain lower bounds for submodular function minimization (SFM). Applying this technique, we prove that any deterministic SFM algorithm on a ground set of n elements requires at least Omega(n log n) queries to an evaluation oracle. This is the first super-linear query complexity lower bound for SFM and improves upon the previous best lower bound of 2n given by [Graur et al., ITCS 2020]. Using our construction, we also prove that any (possibly randomized) parallel SFM algorithm, which can make up to mathsfpoly(n) queries per round, requires at least Omega(n / log n) rounds to minimize a submodular function. This improves upon the previous best lower bound of tildeOmega(n1/3) rounds due to [Chakrabarty et al., FOCS 2021], and settles the parallel complexity of query-efficient SFM up to logarithmic factors due to a recent advance in [Jiang, SODA 2021].