TL;DR
This paper proves that submodular function minimization (SFM) and matroid intersection, despite having efficient polynomial-time algorithms, are inherently sequential. The authors establish a polynomial lower bound on the number of "rounds" of adaptivity required for these problems, demonstrating that they cannot be efficiently parallelized in the oracle model.
What Problem Does This Paper Address?
Submodular function minimization (SFM) and matroid intersection are fundamental problems in discrete optimization with wide-ranging applications. While polynomial-time algorithms exist for both, they typically require a large number of sequential "rounds" of querying an oracle (e.g., an evaluation oracle for SFM, a rank oracle for matroid intersection). The key question is whether these problems can be solved efficiently in a highly parallel manner, meaning with a polynomial number of queries but only a polylogarithmic number of rounds. Previous work showed a lower bound of $\Omega(\log N / \log \log N)$ rounds for SFM, leaving open the possibility of polylogarithmic round algorithms. For matroid intersection, no such lower bound was previously established. This paper aims to close this gap by proving a polynomial lower bound on the number of rounds for both problems.
Methods
The authors construct specific "partition submodular functions" and "nested matroids" that are designed to be hard for parallel algorithms. These functions are built using "suffix functions" and leverage a "masking" technique inspired by prior work. The core idea is to create scenarios where an algorithm, even with many queries, cannot distinguish between different hard instances of the problem within a limited number of rounds. This indistinguishability is achieved by carefully designing the functions such that their marginal values behave similarly for certain types of queries, even when the underlying structure (the partition or matroid) is different. The proof relies on Yao's minimax lemma, which allows them to show that any deterministic algorithm will err with high probability on a randomly chosen hard instance.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Inherent Sequentiality: The paper demonstrates that SFM and matroid intersection are fundamentally sequential problems, meaning they cannot be easily parallelized beyond a certain depth.
- Partition Submodular Functions as Hard Instances: The authors introduce a specific class of submodular functions based on partitions of the universe. These functions are crucial for constructing the lower bounds.
- Suffix Indistinguishability: A key technical tool is the concept of "suffix indistinguishability," which ensures that certain parts of the problem remain hidden from the algorithm for a number of rounds. This is achieved by carefully designing the marginal behavior of the functions.
- Connection Between SFM and Matroid Intersection: The paper highlights a deep connection between SFM and matroid intersection, showing that lower bounds for one can be translated to the other. This is achieved by constructing submodular functions that are closely related to the rank functions of nested matroids.
- Bottleneck at $N^{1/3}$: The construction of the hard instances leads to a lower bound of $\Omega(N^{1/3})$ rounds, suggesting that a significant number of sequential steps are unavoidable.
Key Results
- Polynomial Lower Bound for SFM: Any algorithm for submodular function minimization making poly(N) queries requires $\Omega(N^{1/3})$ rounds of adaptivity. This holds even for algorithms making up to $2N^{1-\delta}$ queries per round.
- Polynomial Lower Bound for Matroid Intersection: Similarly, any algorithm for matroid intersection using rank oracles requires $\Omega(N^{1/3})$ rounds of adaptivity.
- Lower Bound for Approximate SFM: The paper also shows an $\Omega(1/\epsilon)$-lower bound on the number of rounds for $\epsilon$-additive approximations of SFM.
Limitations and Future Work
- Lower Bound Tightness: The authors acknowledge that their construction leads to a lower bound of $\Omega(N^{1/3})$, and a new approach might be needed to prove stronger lower bounds, potentially up to $\Omega(N)$.
- Query Complexity: While the paper focuses on rounds of adaptivity, the general query complexity of SFM and matroid intersection remains an active area of research.
- Partition Submodular Functions: The paper suggests that partition submodular functions are an interesting class of functions worth further study, particularly regarding their complexity and minimization in different settings.
- Parallel SFM/Matroid Intersection: The authors pose open questions about whether efficient parallel algorithms exist for specific cases of SFM and matroid intersection, or if polylogarithmic rounds can be achieved in certain scenarios.
Summary updated