[Theory] NOW: 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>*


On Wed, Jan 26, 2022 at 10:30 AM Mary Marre <mmarre at ttic.edu> wrote:

> *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>*
>
>
> On Tue, Jan 25, 2022 at 12:49 PM Mary Marre <mmarre at ttic.edu> wrote:
>
>> *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>*
>>
>>
>> On Wed, Jan 19, 2022 at 6:11 PM Mary Marre <mmarre at ttic.edu> wrote:
>>
>>> *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/20220126/2590fe69/attachment-0001.html>