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>