From i.brunke@inf.fu-berlin.de Fri Jul 05 14:37:02 2019 Received: from outpost1.zedat.fu-berlin.de ([130.133.4.66]) by list1.zedat.fu-berlin.de (Exim 4.85) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLSv1.2:ECDHE-RSA-AES256-GCM-SHA384:256) (envelope-from ) id <1hjNSX-002XJi-AM>; Fri, 05 Jul 2019 14:37:01 +0200 Received: from inpost2.zedat.fu-berlin.de ([130.133.4.69]) by outpost.zedat.fu-berlin.de (Exim 4.85) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLSv1.2:ECDHE-RSA-AES256-GCM-SHA384:256) (envelope-from ) id <1hjNSX-002pxw-87>; Fri, 05 Jul 2019 14:37:01 +0200 Received: from punkt.imp.fu-berlin.de ([160.45.40.245]) by inpost2.zedat.fu-berlin.de (Exim 4.85) for facets-of-complexity@lists.fu-berlin.de with esmtpsa (TLSv1.2:ECDHE-RSA-AES128-GCM-SHA256:128) (envelope-from ) id <1hjNSW-000LJa-VP>; Fri, 05 Jul 2019 14:37:01 +0200 From: Ita Brunke To: facets-of-complexity@lists.fu-berlin.de Message-ID: Date: Fri, 5 Jul 2019 14:37:00 +0200 User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:60.0) Gecko/20100101 Thunderbird/60.7.2 MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="------------A6DC5805FC9CBE74C8904568" Content-Language: en-US X-Originating-IP: 160.45.40.245 X-ZEDAT-Hint: A X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1562330221-000E1070-DEE20DDC/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.003667, version=1.2.4 X-Spam-Flag: NO X-Spam-Status: No, score=-50.0 required=5.0 tests=ALL_TRUSTED,HTML_MESSAGE, URIBL_BLOCKED X-Spam-Checker-Version: SpamAssassin 3.4.2 on Niue.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Invitation to Monday Lecture - July 8th 2019 & Special Talk - July 12th 2019 X-BeenThere: facets-of-complexity@lists.fu-berlin.de X-Mailman-Version: 2.1.29 Precedence: list List-Id: announcements of Monday lectures and other events List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 05 Jul 2019 12:37:02 -0000 This is a multi-part message in MIME format. --------------A6DC5805FC9CBE74C8904568 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit You are cordially invited to our next Monday Lecture on July 8th at 14:15 h at FU Berlin, and to the same week's special talk on Friday 12th of July at TU Berlin. This Monday there will be no Colloquium, but the Faculty Meeting after the lecture. *_Location_**: ** * *Room 005 - Ground Floor* Freie Universität Berlin Takustr. 9 14195 Berlin *_Time_: **Monday, July 8th - 14:15 h* *_Lecture_: Anita Liebenau (University of New South Wales**)* *_Title_: Enumerating graphs and other discrete structures by degree sequence * *_Abstract_:* How many d-regular graphs are there on n vertices? What is the probability that G(n,p) has a specific given degree sequence, where G(n,p) is the homogeneous random graph in which every edge is inserted with probability p? Asymptotic formulae for the first question are known when d=o(\sqrt(n)) and when d= \Omega(n). More generally, asymptotic formulae are known for the number of graphs with a given degree sequence, for a wide enough range of degree sequences. From these enumeration formulae one can then deduce asymptotic formulae for the second question. McKay and Wormald showed that the formulae for the sparse case and the dense case can be cast into a common form, and then conjectured in 1990 and 1997 that the same formulae should hold for the gap range. A particular consequence of both conjectures is that the degree sequence of the random graph G(n,p) can be approximated by a sequence of n independent binomial variables Bin(n − 1, p'). In 2017, Nick Wormald and I proved both conjectures. In this talk I will describe the problem and survey some of the earlier methods to showcase the  differences to our new methods. I shall also report on enumeration results of other discrete structures, such as bipartite graphs and hypergraphs, that are obtained by adjusting our methods to those settings. _*Coffee & Tea*_*:* *Room 134* *_Special Lecture on Friday, 12th of July, at TU Berlin_:* *_Location_**: ** * *Room MA 041 - Ground Floor* Technische Universität Berlin Straße des 17. Juni 136 10623 Berlin *_Time_: **_Friday_, **July 12th**- _10:15_ h* *_Lecture_: Vijay Vazirani (University of California**)* *_Title_: Matching is as Easy as the Decision Problem, in the NC Model * *_Abstract_:* Is matching in NC, i.e., is there a deterministic fast parallel algorithm for it? This has been an outstanding open question in TCS for over three decades, ever since the discovery of Random NC matching algorithms.  Over the last five years, the TCS community has launched a relentless attack on this question, leading to the discovery of numerous powerful ideas. We give what appears to be the culmination of this line of work: An NC algorithm for finding a minimum weight perfect matching in a general graph with polynomially bounded edge weights, provided it is given an oracle for the decision problem. Consequently, for settling the main open problem, it suffices to obtain an NC algorithm for the decision problem.  We believe this new fact has qualitatively changed the nature of this open problem.Our result builds on the work of Anari and Vazirani (2018), which used planarity of the input graph critically; in fact, in three different ways. Our main challenge was to adapt these steps to general graphs by appropriately trading planarity with the use of the decision oracle. The latter was made possible by the use of several of the ideadiscovered over the last five years. The difficulty of obtaining an NC perfect matching algorithm led researchers to study matching vis-a-vis clever relaxations of the class NC. In this vein, Goldwasser and Grossman (2015) gave a pseudo-deterministic RNC algorithm for finding a perfect matching in a bipartite graph, i.e., an RNC algorithm with the additional requirement that on the same graph, it should return the same (i.e., unique) perfect matching for almost all choices of random bits.  A corollary of our reduction is an analogous algorithm for general graphs. This talk is fully self-contained. Based on the following joint paper with Nima Anari: https://arxiv.org/pdf/1901.10387.pdf --------------A6DC5805FC9CBE74C8904568 Content-Type: text/html; charset=utf-8 Content-Transfer-Encoding: 8bit

You are cordially invited to our next Monday Lecture on July 8th at 14:15 h at FU Berlin, and to the same week's special talk on Friday 12th of July at TU Berlin. This Monday there will be no Colloquium, but the Faculty Meeting after the lecture.

Location:

Room 005 - Ground Floor
Freie Universität Berlin
Takustr. 9
14195 Berlin

Time: Monday, July 8th - 14:15 h

Lecture: Anita Liebenau (University of New South Wales)

Title: Enumerating graphs and other discrete structures by degree sequence

Abstract:

How many d-regular graphs are there on n vertices? What is the probability that G(n,p) has a specific given degree sequence, where G(n,p) is the homogeneous random graph in which every edge is inserted with probability p? Asymptotic formulae for the first question are known when d=o(\sqrt(n)) and when d= \Omega(n). More generally, asymptotic formulae are known for the number of graphs with a given degree sequence, for a wide enough range of degree sequences. From these enumeration formulae one can then deduce asymptotic formulae for the second question. McKay and Wormald showed that the formulae for the sparse case and the dense case can be cast into a common form, and then conjectured in 1990 and 1997 that the same formulae should hold for the gap range. A particular consequence of both conjectures is that the degree sequence of the random graph G(n,p) can be approximated by a sequence of n independent binomial variables Bin(n − 1, p'). In 2017, Nick Wormald and I proved both conjectures. In this talk I will describe the problem and survey some of the earlier methods to showcase the  differences to our new methods. I shall also report on enumeration results of other discrete structures, such as bipartite graphs and hypergraphs, that are obtained by adjusting our methods to those settings.


Coffee & Tea:
Room 134


Special Lecture on Friday, 12th of July, at TU Berlin:

Location:

Room MA 041 - Ground Floor
Technische Universität Berlin
Straße des 17. Juni 136
10623 Berlin

Time: Friday, July 12th - 10:15 h

Lecture: Vijay Vazirani (University of California)

Title: Matching is as Easy as the Decision Problem, in the NC Model

Abstract:

Is matching in NC, i.e., is there a deterministic fast parallel algorithm for it? This has been an outstanding open question in TCS for over three decades, ever since the discovery of Random NC matching algorithms.  Over the last five years, the TCS community has launched a relentless attack on this question, leading to the discovery of numerous powerful ideas. We give what appears to be the culmination of this line of work: An NC algorithm for finding a minimum weight perfect matching in a general graph with polynomially bounded edge weights, provided it is given an oracle for the decision problem. Consequently, for settling the main open problem, it suffices to obtain an NC algorithm for the decision problem.  We believe this new fact has qualitatively changed the nature of this open problem.Our result builds on the work of Anari and Vazirani (2018), which used planarity of the input graph critically; in fact, in three different ways. Our main challenge was to adapt these steps to general graphs by appropriately trading planarity with the use of the decision oracle. The latter was made possible by the use of several of the ideadiscovered over the last five years. The difficulty of obtaining an NC perfect matching algorithm led researchers to study matching vis-a-vis clever relaxations of the class NC. In this vein, Goldwasser and Grossman (2015) gave a pseudo-deterministic RNC algorithm for finding a perfect matching in a bipartite graph, i.e., an RNC algorithm with the additional requirement that on the same graph, it should return the same (i.e., unique) perfect matching for almost all choices of random bits.  A corollary of our reduction is an analogous algorithm for general graphs. This talk is fully self-contained. Based on the following joint paper with Nima Anari: https://arxiv.org/pdf/1901.10387.pdf

--------------A6DC5805FC9CBE74C8904568-- From i.brunke@inf.fu-berlin.de Wed Jul 10 12:47:38 2019 Received: from outpost1.zedat.fu-berlin.de ([130.133.4.66]) by list1.zedat.fu-berlin.de (Exim 4.85) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLSv1.2:ECDHE-RSA-AES256-GCM-SHA384:256) (envelope-from ) id <1hlA8P-001f3D-Tp>; Wed, 10 Jul 2019 12:47:38 +0200 Received: from inpost2.zedat.fu-berlin.de ([130.133.4.69]) by outpost.zedat.fu-berlin.de (Exim 4.85) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLSv1.2:ECDHE-RSA-AES256-GCM-SHA384:256) (envelope-from ) id <1hlA8P-0043s3-RA>; Wed, 10 Jul 2019 12:47:37 +0200 Received: from punkt.imp.fu-berlin.de ([160.45.40.245]) by inpost2.zedat.fu-berlin.de (Exim 4.85) for facets-of-complexity@lists.fu-berlin.de with esmtpsa (TLSv1.2:ECDHE-RSA-AES128-GCM-SHA256:128) (envelope-from ) id <1hlA8P-000uQp-Hq>; Wed, 10 Jul 2019 12:47:37 +0200 To: facets-of-complexity@lists.fu-berlin.de From: Ita Brunke Message-ID: <35b4316f-862d-dc11-ae15-1ad9a0c6359f@inf.fu-berlin.de> Date: Wed, 10 Jul 2019 12:47:37 +0200 User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:60.0) Gecko/20100101 Thunderbird/60.7.2 MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="------------A4A296E171D55A9727FA92E3" Content-Language: en-US X-Originating-IP: 160.45.40.245 X-ZEDAT-Hint: A X-purgate: suspect X-purgate-type: suspect X-purgate-ID: 151147::1562755657-000252D6-4BC6896E/1/6397047249 X-Bogosity: Ham, tests=bogofilter, spamicity=0.061116, version=1.2.4 X-Spam-Flag: NO X-Spam-Status: No, score=-49.0 required=5.0 tests=ALL_TRUSTED, FU_XPURGATE_SUSP, HTML_MESSAGE,URIBL_BLOCKED X-Spam-Checker-Version: SpamAssassin 3.4.2 on Niue.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Invitation Special Talk Friday - changed Abstract X-BeenThere: facets-of-complexity@lists.fu-berlin.de X-Mailman-Version: 2.1.29 Precedence: list List-Id: announcements of Monday lectures and other events List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 10 Jul 2019 10:47:38 -0000 This is a multi-part message in MIME format. --------------A4A296E171D55A9727FA92E3 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit You are cordially invited to our special talk on Friday 12th of July at TU Berlin. *_Special Lecture on Friday, 12th of July, at TU Berlin_:* *_Location_**: ** * *Room MA 041 - Ground Floor* *Technische Universität Berlin** **Straße des 17. Juni 136** **10623 Berlin* *_Time_: **_Friday_, **July 12th**- _10:15_ h* *_Lecture_: Vijay Vazirani (University of California**)* *_Title_: Matching is as Easy as the Decision Problem, in the NC Model * *_Abstract_: * Is matching in NC, i.e., is there a deterministic fast parallel algorithm for it? This has been an outstanding open question in TCS for over three decades, ever since the discovery of Random NC matching algorithms. Over the last five years, the TCS community has launched a relentless attack on this question, leading to the discovery of numerous powerful ideas. We give what appears to be the culmination of this line of work: An NC algorithm for finding a minimum weight perfect matching in a general graph with polynomially bounded edge weights, provided it is given an oracle for the decision problem. Consequently, for settling the main open problem, it suffices to obtain an NC algorithm for the decision problem. We believe this new fact has qualitatively changed the nature of this open problem. All known efficient matching algorithms for general graphs follow one of two approaches: those initiated by Edmonds (1965) or Lovasz (1979). Our algorithm is based on a new approach which was inspired by the multitude of ideas discovered in the last five years. The difficulty of obtaining an NC perfect matching algorithm led researchers to study matching vis-a-vis clever relaxations of the class NC. In this vein, Goldwasser and Grossman (2015) gave a pseudo-deterministic RNC algorithm for finding a perfect matching in a bipartite graph, i.e., an RNC algorithm with the additional requirement that on the same graph, it should return the same (i.e., unique) perfect matching for almost all choices of random bits. A corollary of our reduction is an analogous algorithm for general graphs. This talk is fully self-contained. Based on the following joint paper with Nima Anari:https://arxiv.org/pdf/1901.10387.pdf --------------A4A296E171D55A9727FA92E3 Content-Type: text/html; charset=utf-8 Content-Transfer-Encoding: 8bit

You are cordially invited to our special talk on Friday 12th of July at TU Berlin.

Special Lecture on Friday, 12th of July, at TU Berlin:

Location:

Room MA 041 - Ground Floor
Technische Universität Berlin
 Straße des 17. Juni 136
 10623 Berlin

Time: Friday, July 12th - 10:15 h

Lecture: Vijay Vazirani (University of California)

Title: Matching is as Easy as the Decision Problem, in the NC Model

Abstract:

Is matching in NC, i.e., is there a deterministic fast parallel algorithm for it? This has been an outstanding open question in TCS for over three decades, ever since the discovery of Random NC matching algorithms. Over the last five years, the TCS community has launched a relentless attack on this question, leading to the discovery of numerous powerful ideas. We give what appears to be the culmination of this line of work: An NC algorithm for finding a minimum weight perfect matching in a general graph with polynomially bounded edge weights, provided it is given an oracle for the decision problem. Consequently, for settling the main open problem, it suffices to obtain an NC algorithm for the decision problem. We believe this new fact has qualitatively changed the nature of this open problem.


All known efficient matching algorithms for general graphs follow one of two approaches: those initiated by Edmonds (1965) or Lovasz (1979). Our algorithm is based on a new approach which was inspired by the multitude of ideas discovered in the last five years.

The difficulty of obtaining an NC perfect matching algorithm led researchers to study matching vis-a-vis clever relaxations of the class NC. In this vein, Goldwasser and Grossman (2015) gave a pseudo-deterministic RNC algorithm for finding a perfect matching in a bipartite graph, i.e., an RNC algorithm with the additional requirement that on the same graph, it should return the same (i.e., unique) perfect matching for almost all choices of random bits. A corollary of our reduction is an analogous algorithm for general graphs.
This talk is fully self-contained. Based on the following joint paper with Nima Anari: https://arxiv.org/pdf/1901.10387.pdf

--------------A4A296E171D55A9727FA92E3--