<div dir="ltr"><div dir="ltr"><div class="gmail_default" style="font-size:small"><div class="gmail_default"><p style="font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;line-height:normal;color:rgb(80,0,80);margin:0px"><font face="arial, sans-serif" color="#000000"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b>When:</b>    </font></font><font style="vertical-align:inherit"><font style="vertical-align:inherit">  Wednesday, January 26th at<b> <span style="background-color:rgb(255,255,0)">11:30 am CT</span></b></font></font><br></font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif" color="#000000"> </font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font style="color:rgb(0,0,0);vertical-align:inherit"><font style="vertical-align:inherit"><b>Where:</b>     </font></font><font color="#000000">Zoom Virtual Talk (</font><font color="#0000ff"><b><a href="https://uchicagogroup.zoom.us/webinar/register/WN_Qul2Aq7PRMa6sNkbPEmTSQ" target="_blank">register in advance here</a></b></font><font color="#000000">)</font></font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><br></font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><font color="#000000"><b>Who: </b> </font><font color="#500050">    </font><font color="#000000">  Yu Chen, University of Pennsylvania </font></font></font></font></p></div><div class="gmail_default"><b style="color:rgb(0,0,0)"><font face="arial, sans-serif"><br></font></b></div><div class="gmail_default"><b style="color:rgb(0,0,0)"><font face="arial, sans-serif"><br></font></b></div><div class="gmail_default"><font face="arial, sans-serif"><b style="color:rgb(60,64,67)">Title:</b><span style="color:rgb(60,64,67)">        A Polynomial Lower Bound on the Number of Rounds for Parallel Submodular Function Minimization and Matroid Intersection</span><br style="color:rgb(60,64,67)"><br style="color:rgb(60,64,67)"><b style="color:rgb(60,64,67)">Abstract: </b><span style="color:rgb(60,64,67)">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.</span><br style="color:rgb(60,64,67)"></font><p style="color:rgb(60,64,67)"><font face="arial, sans-serif">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.</font></p><p style="color:rgb(60,64,67)"><font face="arial, sans-serif">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}\<u></u>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.</font></p><p style="color:rgb(60,64,67)"><font face="arial, sans-serif">This is joint work with Deeparnab Chakrabarty (Dartmouth) and Sanjeev Khanna (Penn).<br></font></p><font face="arial, sans-serif"><br></font></div><div class="gmail_default"><font face="arial, sans-serif"><b>Host:</b> <b><font color="#0000ff"><a href="mailto:cjulia@ttic.edu" target="_blank">Julia Chuzhoy</a></font></b></font></div><div class="gmail_default"><br></div><div class="gmail_default"><br></div><div class="gmail_default"><br></div><div class="gmail_default"><br></div></div><div><div dir="ltr" class="gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><div><span style="font-family:arial,helvetica,sans-serif;font-size:x-small">Mary C. Marre</span><br></div><div><div><font face="arial, helvetica, sans-serif" size="1">Faculty Administrative Support</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1">6045 S. Kenwood Avenue</font></i></div><div><font size="1"><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL  60637</font></i><br></font></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif" size="1">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Wed, Jan 19, 2022 at 6:11 PM Mary Marre <<a href="mailto:mmarre@ttic.edu">mmarre@ttic.edu</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div><div><p style="font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;line-height:normal;color:rgb(80,0,80);margin:0px"><font face="arial, sans-serif" color="#000000"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b>When:</b>    </font></font><font style="vertical-align:inherit"><font style="vertical-align:inherit">  Wednesday, January 26th at<b> <span style="background-color:rgb(255,255,0)">11:30 am CT</span></b></font></font><br></font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif" color="#000000"> </font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font style="color:rgb(0,0,0);vertical-align:inherit"><font style="vertical-align:inherit"><b>Where:</b>     </font></font><font color="#000000">Zoom Virtual Talk (</font><font color="#0000ff"><b><a href="https://uchicagogroup.zoom.us/webinar/register/WN_Qul2Aq7PRMa6sNkbPEmTSQ" target="_blank">register in advance here</a></b></font><font color="#000000">)</font></font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><br></font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><font color="#000000"><b>Who: </b> </font><font color="#500050">    </font><font color="#000000">  Yu Chen, University of Pennsylvania </font></font></font></font></p></div><div><b style="color:rgb(0,0,0)"><font face="arial, sans-serif"><br></font></b></div><div><b style="color:rgb(0,0,0)"><font face="arial, sans-serif"><br></font></b></div><div><span style="background-color:rgb(255,255,255)"><font face="arial, sans-serif"><b style="color:rgb(60,64,67)">Title:</b><span style="color:rgb(60,64,67)">        A Polynomial Lower Bound on the Number of Rounds for Parallel Submodular Function Minimization and Matroid Intersection</span><br style="color:rgb(60,64,67)"><br style="color:rgb(60,64,67)"><b style="color:rgb(60,64,67)">Abstract: </b><span style="color:rgb(60,64,67)">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.</span><br style="color:rgb(60,64,67)"></font></span><p style="color:rgb(60,64,67)"><span style="background-color:rgb(255,255,255)"><font face="arial, sans-serif">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.</font></span></p><p style="color:rgb(60,64,67)"><span style="background-color:rgb(255,255,255)"><font face="arial, sans-serif">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}\<u></u>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.</font></span></p><p style="color:rgb(60,64,67)"><span style="background-color:rgb(255,255,255)"><font face="arial, sans-serif">This is joint work with Deeparnab Chakrabarty (Dartmouth) and Sanjeev Khanna (Penn).<br></font></span></p><font face="arial, sans-serif"><br></font></div><div><font face="arial, sans-serif"><b>Host:</b> <b><font color="#0000ff"><a href="mailto:cjulia@ttic.edu" target="_blank">Julia Chuzhoy</a></font></b></font></div><div style="font-size:small"><br></div><div style="font-size:small"><br></div><div style="font-size:small"><br></div></div><div><div dir="ltr"><div dir="ltr"><div><span style="font-family:arial,helvetica,sans-serif;font-size:x-small">Mary C. Marre</span><br></div><div><div><font face="arial, helvetica, sans-serif" size="1">Faculty Administrative Support</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1">6045 S. Kenwood Avenue</font></i></div><div><font size="1"><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL  60637</font></i><br></font></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif" size="1">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div></div>
</blockquote></div></div>