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: 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 How many dregular 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.
Special Lecture on Friday, 12th of July, at TU Berlin: Location: 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 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 visavis
clever relaxations of the class NC. In this vein, Goldwasser and
Grossman (2015) gave a pseudodeterministic 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
selfcontained. Based on the following joint paper with Nima
Anari: https://arxiv.org/pdf/1901.10387.pdf
