Improved Lower Bounds for Submodular Function Minimization

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 poly $(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 $\tilde{\Omega}(n^{1/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].

Authors

• Deeparnab Chakrabarty
• Andrei Graur
• Haotian Jiang
• Aaron Sidford

Keywords

• Computer science
• Minimization
• Complexity theory
• Lower Bound
• Submodular Function
• Submodular Function Minimization
• Deterministic
• Family Functioning
• High Probability
• Range Of Functions
• Previous Paragraph
• Set Of Elements
• Base Case
• Random Function
• Divisible
• Parallel Algorithm
• Main Insights
• Unique Minimizer
• Main Building Blocks
• Unweighted Graph
• Collection Of Functions
• Parallel Optimization
• query complexity
• parallel complexity