English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

Submodular function minimization (SFM) and matroid intersection arefundamental discrete optimization problems with applications in many fields. Itis well known that both of these can be solved making $\mathrm{poly}(N)$queries to a relevant oracle (evaluation oracle for SFM and rank oracle formatroid intersection), where $N$ denotes the universe size. However, all knownpolynomial query algorithms are highly adaptive, requiring at least $N$ roundsof querying the oracle. A natural question is whether these can be efficientlysolved in a highly parallel manner, namely, with $\mathrm{poly}(N)$ queriesusing only poly-logarithmic rounds of adaptivity.  An important step towards understanding the adaptivity needed for efficientparallel SFM was taken recently in the work of Balkanski and Singer who showedthat any SFM algorithm making $\mathrm{poly}(N)$ queries necessarily requires$\Omega(\log N/\log \log N)$ rounds. This left open the possibility ofefficient SFM algorithms in poly-logarithmic rounds. For matroid intersection,even the possibility of a constant round, $\mathrm{poly}(N)$ query algorithmwas not hitherto ruled out.  In this work, we prove that any, possibly randomized, algorithm forsubmodular function minimization or matroid intersection making$\mathrm{poly}(N)$ queries requires $\tilde{\Omega}\left(N^{1/3}\right)$ roundsof adaptivity. In fact, we show a polynomial lower bound on the number ofrounds of adaptivity even for algorithms that make at most $2^{N^{1-\delta}}$queries, for any constant $\delta> 0$. Therefore, even though SFM and matroidintersection are efficiently solvable, they are not highly parallelizable inthe oracle model.

A Polynomial Lower Bound on the Number of Rounds for Parallel Submodular Function Minimization and Matroid Intersection