[Facets-of-complexity] Monday Lecture & Colloquia - Jan 20, 2020 at FU Berlin

[Günter Rote <rote@inf.fu-berlin.de>]

You are invited to our Monday Lecture & Colloquiums on January 20, 2020
at 14:15 h & 16:00 h & 17:00 h at FU Berlin.
Exceptionally, there will be *ANOTHER COLLOQUIUM TALK* at 17:00.

Lecture: Monday, January 20, 14:15 h
   ==========================================
   Holger Dell (IT University of Copenhagen):

   Counting and sampling small subgraphs
   ==========================================

Abstract:
We discuss various algorithmic techniques used for counting and sampling subgraphs
in a large input graph. The focus of the talk is on the mathematical foundations.
We start with the beautiful technique of color-coding (Alon, Yuster, Zwick 1995),
and we discuss various generalizations based on group algebras (Koutis 2008) and
on the exterior algebra (Brand, Dell, Husfeldt 2018). These techniques are most
useful for sampling, which is equivalent to approximate counting. On the other
hand, the fastest known algorithm to exactly count subgraphs that are isomorphic
to a graph H (Curticapean, Dell, Marx 2017) is based on the foundations of
Lovász' theory of graph limits.


Coffee & Tea Break: Room 134 - First Floor

First Colloquium: 16:00 h
   ==========================================================
   Alan Arroyo (Institute of Science and Technology Austria):

   Obstructions in graph drawings
   =========================================================?

Abstract:
Many nice results in graph theory involve the characterization of a graph class in
terms of a set of forbidden obstructions. In this talk I will consider the problem of
understanding whether a class of graph drawings can be characterized by a set of
forbidden obstructions. I will do an overview on interesting recent results that fall
under this theme, but I will emphasize more on those related to geometric arrangements.

Second Colloquium: 17:00 h
   ==========================================
   Gorav Jindal (Aalto University, Helsinki):

   On the Complexity of Symmetric Polynomials
   ==========================================

Abstract:
The fundamental theorem of symmetric polynomials states that for a symmetric polynomial
f_Sym in C[x1,x2,...,x_n], there exists a unique "witness" f in C[y1,y2,...,y_n] such
that f_Sym=f(e1,e2,...,e_n), where the e_i's are the elementary symmetric polynomials.
In this work, we study the arithmetic complexity L(f) of the witness f as a function of
the arithmetic complexity L(f_Sym) of f_Sym. We show that the arithmetic complexity L(f)
of f is bounded by poly(L(f_Sym),deg(f),n). Prior to this work, only exponential upper
bounds were known for L(f). The main ingredient in our result is an algebraic analogue of
Newton’s iteration on power series.
As a corollary of this result, we show that if VP is not equal to VNP then there are
symmetric polynomial families which have super-polynomial arithmetic complexity.
This is joint work with Markus Bläser.

=========================================================================================
Location:
Seminar room 005 (Ground Floor)
Freie Universität Berlin
Institut für Informatik
Takustr. 9, 14195 Berlin
<https://www.mi.fu-berlin.de/en/fb/contact/location.html>