[Theory] 1/26 Talks at TTIC: Yu Chen, University of Pennsylvania

[Mary Marre]

*When:*      Wednesday, January 26th at* 11:30 am CT*



*Where:*     Zoom Virtual Talk (*register in advance here
<https://uchicagogroup.zoom.us/webinar/register/WN_Qul2Aq7PRMa6sNkbPEmTSQ>*)


*Who: *       Yu Chen, University of Pennsylvania


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

*Abstract: *Submodular function minimization (SFM) and matroid intersection
are fundamental discrete optimization problems with applications in many
fields. It is well known that both of these can be solved by making
\textsf{Poly}(N) queries to a relevant oracle (evaluation oracle for SFM
and rank oracle for matroid intersection), where N denotes the universe
size. However, all known polynomial query algorithms are highly adaptive,
requiring at least N rounds of querying the oracle. A natural question is
whether these can be efficiently solved in a highly parallel manner,
namely, with \textsf{Poly}(N) queries using only poly-logarithmic rounds of
adaptivity.

An important step towards understanding the adaptivity needed for efficient
parallel SFM was taken recently in the work of Balkanski and Singer who
showed that any SFM algorithm making \textsf{Poly}(N) queries necessarily
requires \Omega(\log N/\log \log N) rounds. This left open the possibility
of efficient SFM algorithms in poly-logarithmic rounds. For matroid
intersection, even the possibility of a constant round, \textsf{Poly}(N)
query algorithm was not hitherto ruled out.

In this work, we prove that any, possibly randomized, algorithm for
submodular function minimization or matroid intersection making
\textsf{Poly}(N) queries requires \tilde{\Omega}\left(N^{1/3}\right) rounds
of adaptivity. In fact, we show a polynomial lower bound on the number of
rounds of adaptivity even for algorithms that make at most 2^{N^{1-\delta}}
queries, for any constant \delta> 0. Therefore, even though SFM and matroid
intersection are efficiently solvable, they are not highly parallelizable
in the oracle model.

This is joint work with Deeparnab Chakrabarty (Dartmouth) and Sanjeev
Khanna (Penn).

*Host:* *Julia Chuzhoy <cjulia at ttic.edu>*



Mary C. Marre
Faculty Administrative Support
*Toyota Technological Institute*
*6045 S. Kenwood Avenue*
*Chicago, IL  60637*
*mmarre at ttic.edu <mmarre at ttic.edu>*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20220119/ef51eb2d/attachment.html>