From rote@inf.fu-berlin.de Mon Jan 06 12:39:31 2020 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 <1ioQjK-0049td-QH>; Mon, 06 Jan 2020 12:39:30 +0100 Received: from inpost2.zedat.fu-berlin.de ([130.133.4.69]) by outpost.zedat.fu-berlin.de (Exim 4.85) with esmtps (TLSv1.2:ECDHE-RSA-AES256-GCM-SHA384:256) (envelope-from ) id <1ioQjK-003Ie8-Nq>; Mon, 06 Jan 2020 12:39:30 +0100 Received: from strecke.imp.fu-berlin.de ([160.45.40.209]) by inpost2.zedat.fu-berlin.de (Exim 4.85) with esmtpsa (TLSv1.2:ECDHE-RSA-AES128-GCM-SHA256:128) (envelope-from ) id <1ioQjK-003W8k-IU>; Mon, 06 Jan 2020 12:39:30 +0100 To: Ita Brunke , facets-of-complexity@lists.fu-berlin.de References: <8d2e94c3-d657-27d1-8292-a9edefd2c5d9@inf.fu-berlin.de> From: =?UTF-8?Q?G=c3=bcnter_Rote?= Message-ID: <91e60edf-00ca-cf4f-8d46-4419dc31625b@inf.fu-berlin.de> Date: Mon, 6 Jan 2020 12:39:30 +0100 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101 Thunderbird/60.9.0 MIME-Version: 1.0 In-Reply-To: <8d2e94c3-d657-27d1-8292-a9edefd2c5d9@inf.fu-berlin.de> Content-Type: text/plain; charset=utf-8 Content-Language: en-US Content-Transfer-Encoding: 8bit X-Originating-IP: 160.45.40.209 X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1578310770-000BAB21-2474BAF3/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.000153, version=1.2.4 X-Spam-Flag: NO X-Spam-Status: No, score=-50.0 required=5.0 tests=ALL_TRUSTED X-Spam-Checker-Version: SpamAssassin 3.4.3 on Tuvalu.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Invitation to Monday Lecture & Colloquium - TODAY January 6 2020 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: Mon, 06 Jan 2020 11:39:31 -0000 Location: Room 005 - Ground Floor Freie Universität Berlin Institut für Informatik, Takustr. 9 14195 Berlin Time: Monday, Jan 6 - 14:15 h Lecturer: Frank Sottile (Texas University) Title: *Irrational toric varieties and the secondary polytope* Abstract: The secondary fan of a point configuration A in R^n encodes all regular subdivisions of A. These subdivisions also record all limiting objects obtained by weight degenerations of the irrational toric variety X_A parameterized by A. The secondary fan is the normal fan of the secondary polytope. We explain a functorial construction of R^n-equivariant cell complexes from fans that, when applied to the secondary fan, realizes the secondary polytope as the moduli space of translations and degenerations of X_A. This extends the work of Kapranov, Sturmfels and Zelevinsky (who established this for complex toric varieties when A is integral) to all real configurations A. Coffee & Tea Break: Room 134 Time: Monday, Jan 6 - 16:00 h s.t.* Colloquium: Lukas Kühne (Hebrew University of Jerusalem) Title: *Matroid representations by c-arrangements are undecidable* Abstract: A matroid is a combinatorial object based on an abstraction of linear independence in vector spaces and forests in graphs. It is a classical question to determine whether a given matroid is representable as a vector configuration over a field. Such a matroid is called linear. This talk is about a generalization of that question from vector configurations to c-arrangements. A c-arrangement for a fixed c is an arrangement of dimension c subspaces such that the dimensions of their sums are multiples of c. Matroids representable as c-arrangements are called multilinear matroids. We prove that it is algorithmically undecidable whether there exists a c such that a given matroid has a c-arrangement representation. In the proof, we introduce a non-commutative von Staudt construction to encode an instance of the uniform word problem for finite groups in matroids of rank three. The talk is based on joint work with Geva Yashfe. -- G"unter Rote (Germany=49)30-838-75150 (office) Freie Universit"at Berlin -75103 (secretary) Institut f"ur Informatik FAX (49)30-838-4-75150 Takustrase 9, D-14195 Berlin, GERMANY From rote@inf.fu-berlin.de Wed Jan 08 18:24:37 2020 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 <1ipF4P-001VSi-1y>; Wed, 08 Jan 2020 18:24:37 +0100 Received: from inpost2.zedat.fu-berlin.de ([130.133.4.69]) by outpost.zedat.fu-berlin.de (Exim 4.85) with esmtps (TLSv1.2:ECDHE-RSA-AES256-GCM-SHA384:256) (envelope-from ) id <1ipF4O-0020f3-VX>; Wed, 08 Jan 2020 18:24:36 +0100 Received: from strecke.imp.fu-berlin.de ([160.45.40.209]) by inpost2.zedat.fu-berlin.de (Exim 4.85) with esmtpsa (TLSv1.2:ECDHE-RSA-AES128-GCM-SHA256:128) (envelope-from ) id <1ipF4O-000Ht7-Os>; Wed, 08 Jan 2020 18:24:36 +0100 From: =?UTF-8?Q?G=c3=bcnter_Rote?= References: <4b6987b1-9099-380d-b3c0-9a1cd494d4e3@inf.fu-berlin.de> To: facets-of-complexity@lists.fu-berlin.de Message-ID: Date: Wed, 8 Jan 2020 18:24:36 +0100 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101 Thunderbird/60.9.0 MIME-Version: 1.0 In-Reply-To: <4b6987b1-9099-380d-b3c0-9a1cd494d4e3@inf.fu-berlin.de> Content-Type: text/plain; charset=utf-8 Content-Language: en-US Content-Transfer-Encoding: 8bit X-Originating-IP: 160.45.40.209 X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1578504277-000A6214-5A306B8E/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.270077, version=1.2.4 X-Spam-Flag: NO X-Spam-Status: No, score=-50.0 required=5.0 tests=ALL_TRUSTED X-Spam-Checker-Version: SpamAssassin 3.4.3 on Kiribati.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Monday Lecture & Colloquia - Jan 13, 2020 at TU Berlin 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, 08 Jan 2020 17:24:37 -0000 You are invited to our Monday Lecture & Colloquium on January 13, 2020 at 14:15 h & 16:00 h & 17:00 h at FU Berlin. Exceptionally, there will be *ANOTHER COLLOQUIUM* at 17:00. Lecture: Monday, April 15th - 14:15 h =============================================================== Eric Fusy (École Polytechnique Paris): Bijections between families of walks using oriented planar maps =============================================================== Abstract: When counting walks (with a given step-set), an equi-enumeration phenomenom is often observed between a stronger constraint on the domain and a stronger constraint on the position of the endpoint (a classical 1d example is the fact that positive walks of length 2n are in bijection with walks of length 2n ending at 0, both being counted by the central binomial coefficient). I will show examples of such relations for 2d walks where the equi-enumeration can be bijectively explained using planar maps endowed with certain orientations (Schnyder woods, bipolar orientations). Coffee & Tea Break: Room MA 316 - Third Floor First Colloquium: 16:00 h ========================================================= Andrei Asinowski (Universität Klagenfurt): The vectorial kernel method and patterns in lattice paths ========================================================= Abstract: A directed lattice path is a polygonal line which starts at the origin and consists of several vectors of the form (1, y) (where y belongs to a fixed set of integers) appended to each other. Enumeration of different kinds of lattice paths (walks/bridges/meanders /excursions) was accomplished by Banderier and Flajolet in 2002. We refine and generalize their results by studying lattice paths that avoid a fixed pattern (or several patterns). To this end, we develop a "vectorial kernel method" – a unified framework for enumeration of words generated by a counter automaton. Another improtant tool is the "autocorrelation polynomial" that encodes self-overlappings of a pattern, and its generalization: the "mutual correlation matrix" for several patterns. This talk is based on joint work with Cyril Banderier, Axel Bacher, Bernhard Gittenberger and Valerie Rointer. Second Colloquium: 17:00 h ============================================== Shahrzad Haddadan (MPI Informatik Saarbrücken): Algorithms for top-k lists and social networks ============================================== Abstract: Today’s massive and dynamic data sets have motivated many computer scientists and mathematicians to study classical problems in combinatorics and graph theory in various settings. In certain settings the algorithms’ access to the data is restricted while in others the resources are limited. In this talk we explore such settings in three directions: ranking of objects, property testing in social networks and finding communities in dynamic graphs. In the first part, we discuss algorithms on permutations as well as prefixes of permutations also known as top-k lists. The study of later particularly arises in big data scenarios when analysis of the entire permutation is costly or not interesting. We start by discussing random walks on the set of full rankings or permutations of n objects, a set whose size is n!. Since the 1990s to today, various versions of this problem have been studied, each for a different motivation. The second part of the talk is devoted to property testing in social networks: Given a graph, an algorithm seeks to approximate several parameters of a graph just by accessing the graph by means of oracles and while querying these oracles as few times as possible. We introduce a new oracle access model which is applicable to social networks, and assess the complexity of estimating parameters such as the number of users (vertices) in this model. In the third part of the talk, we introduce a new dynamic graph model which is based on triadic closure: a friendship is more likely to be formed between a pair of users with a larger number of mutual friends. We find upper bounds for the rate of graph evolution in this model and using such bounds we devise algorithms discovering communities. I will finish this talk by proposing new directions and presenting related open problems. ========================================================================================= Location: Room MA 041 (Ground Floor) Technische Universität Berlin Institut für Mathematik Straße des 17. Juni 136 10623 Berlin From rote@inf.fu-berlin.de Fri Jan 17 20:13:35 2020 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 <1isX3n-0030O8-7X>; Fri, 17 Jan 2020 20:13:35 +0100 Received: from inpost2.zedat.fu-berlin.de ([130.133.4.69]) by outpost.zedat.fu-berlin.de (Exim 4.85) with esmtps (TLSv1.2:ECDHE-RSA-AES256-GCM-SHA384:256) (envelope-from ) id <1isX3m-000Y0y-Cu>; Fri, 17 Jan 2020 20:13:34 +0100 Received: from strecke.imp.fu-berlin.de ([160.45.40.209]) by inpost2.zedat.fu-berlin.de (Exim 4.85) with esmtpsa (TLSv1.2:ECDHE-RSA-AES128-GCM-SHA256:128) (envelope-from ) id <1isX3m-001p0G-7X>; Fri, 17 Jan 2020 20:13:34 +0100 References: From: =?UTF-8?Q?G=c3=bcnter_Rote?= To: facets-of-complexity@lists.fu-berlin.de X-Forwarded-Message-Id: Message-ID: <7a930d6e-5671-053c-6708-e0a08d84f10f@inf.fu-berlin.de> Date: Fri, 17 Jan 2020 20:13:34 +0100 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101 Thunderbird/60.9.0 MIME-Version: 1.0 In-Reply-To: Content-Type: text/plain; charset=utf-8 Content-Language: en-US Content-Transfer-Encoding: 8bit X-Originating-IP: 160.45.40.209 X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1579288415-000525D6-FE1B5E7D/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.000416, version=1.2.4 X-Spam-Flag: NO X-Spam-Status: No, score=-50.0 required=5.0 tests=ALL_TRUSTED X-Spam-Checker-Version: SpamAssassin 3.4.3 on Palau.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Monday Lecture & Colloquia - Jan 20, 2020 at FU Berlin 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, 17 Jan 2020 19:13:35 -0000 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 From i.brunke@inf.fu-berlin.de Wed Jan 22 15:46:43 2020 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 <1iuHHG-004ArB-Vu>; Wed, 22 Jan 2020 15:46:43 +0100 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 <1iuHHG-00205W-TB>; Wed, 22 Jan 2020 15:46:42 +0100 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 <1iuHHG-001R4F-KG>; Wed, 22 Jan 2020 15:46:42 +0100 From: Ita Brunke To: facets-of-complexity@lists.fu-berlin.de Message-ID: Date: Wed, 22 Jan 2020 15:46:42 +0100 User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:68.0) Gecko/20100101 Thunderbird/68.4.1 MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="------------14F45A133C9C2900F1D8E40D" 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::1579704402-00099802-810CBC7A/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.000042, version=1.2.4 X-Spam-Flag: NO X-Spam-Status: No, score=-50.0 required=5.0 tests=ALL_TRUSTED,HTML_MESSAGE X-Spam-Checker-Version: SpamAssassin 3.4.3 on Vanuatu.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Invitation to Monday Lecture & Colloquium - January 27th 2020 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, 22 Jan 2020 14:46:43 -0000 This is a multi-part message in MIME format. --------------14F45A133C9C2900F1D8E40D Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit You are cordially invited to our next Monday Lecture & Colloquium on January 27th at *14:15 h*, *16:00 h* & *17:00 h* at FU Berlin. *Exceptionally*, there will be a*second Colloquium* at *17:00.* *_Location_**: ** * *Room 005 - Ground Floor* Freie Universität Berlin Takustr. 9 14195 Berlin *_Time_: **Monday, January 27th - 14:15 h* *_Lecture_: Haim Kaplan (Tel Aviv University**)* *_Title_: Privately Learning Thresholds * *_Abstract_:* We study the problem of computing a point in the convex hull, and the related problem of computing a separating hyperplane, under the constraint of differential privacy . Intuitively, differential privacy means that our output should be robust to small changes in the input (for example to adding or deleting a point). We study the minimum size of the input needed to achieve such a private computation (sample complexity) and its time complexity. Even in one dimension the problem is non-trivial and we will first focus on this case. Several interesting open problems will be presented as well. No previous background on differential privacy will be assumed. _*Coffee & Tea Break*_*:* *Room 134* ** *_Time_: **Monday, ***January* 27th**- 16:00 h s.t.* *_Colloquium_: Gweneth Anne McKinley (MIT, Cambridge, USA**)* *_Title_: Super-logarithmic cliques in dense inhomogeneous random graphs * *_Abstract_:* In the theory of dense graph limits, a graphon is a symmetric measurable function W from [0,1] ^2 to [0,1]. Each graphon gives rise naturally to a random graph distribution, denoted G ( n , W ), that can be viewed as a generalization of the Erdös-Rényi random graph. Recently, Dolezal, Hladky, and Mathe gave an asymptotic formula of order  log n   for the size of the largest clique in G ( n , W ) when W is bounded away from 0 and 1. We show that if W is allowed to approach 1 at a finite number of points, and displays a moderate rate of growth near these points, then the clique number of G ( n , W ) will be of order √ n almost surely. We also give a family of examples with clique number of order n ^ c for any c in (0,1), and some conditions under which the clique number of  G ( n , W ) will be o (√ n ) or ω(√ n ). This talk assumes no previous knowledge of graphons. *_Time_: **Monday, ***January* 27th**- 17:00 h s.t.* *_Colloquium_: Michał Włodar**czyk (Universität Eindhoven**)* *_Title_: Losing treewidth by separating subsets: on approximation of vertex/edge deletion problems * *_Abstract_:* Consider the problem of deleting the smallest set S of vertices (resp. edges) from a given graph G such that the induced subgraph (resp. subgraph) G \ S belongs to some class H . I will cover the case where graphs in H have treewidth bounded by t , and give a general framework to obtain approximation algorithms basing on two ingredients: 1) approximation algorithms for the k -Subset Separator problem, 2) FPT algorithms parameterized by the solution size. For the vertex deletion setting, this new framework combined with the current best result for k -Subset Vertex Separator, improves approximation ratios for basic problems such as k -Treewidth Vertex Deletion and Planar F Vertex Deletion. Our algorithms are simpler than previous works and give the first deterministic and uniform approximation algorithms under the natural parameterization. I will talk about what it means for several important graph classes and how the bounded treewidth property is exploited. I will present a sketch of the proof for the H Vertex Deletion algorithm and explain the differences between deleting vertices or edges. --------------14F45A133C9C2900F1D8E40D Content-Type: text/html; charset=utf-8 Content-Transfer-Encoding: 8bit

You are cordially invited to our next Monday Lecture & Colloquium on January 27th at 14:15 h, 16:00 h & 17:00 h at FU Berlin.

Exceptionally, there will be a second Colloquium at 17:00.


Location:

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

Time: Monday, January 27th - 14:15 h

Lecture: Haim Kaplan (Tel Aviv University)

Title: Privately Learning Thresholds

Abstract:

We study the problem of computing a point in the convex hull, and the related problem of computing a separating hyperplane, under the constraint of differential privacy . Intuitively, differential privacy means that our output should be robust to small changes in the input (for example to adding or deleting a point). We study the minimum size of the input needed to achieve such a private computation (sample complexity) and its time complexity. Even in one dimension the problem is non-trivial and we will first focus on this case. Several interesting open problems will be presented as well. No previous background on differential privacy will be assumed.


Coffee & Tea Break:
Room 134

Time: Monday, January 27th - 16:00 h s.t.

Colloquium: Gweneth Anne McKinley (MIT, Cambridge, USA)

Title: Super-logarithmic cliques in dense inhomogeneous random graphs

Abstract:

In the theory of dense graph limits, a graphon is a symmetric measurable function W from [0,1] ^2 to [0,1]. Each graphon gives rise naturally to a random graph distribution, denoted G ( n , W ), that can be viewed as a generalization of the Erdös-Rényi random graph. Recently, Dolezal, Hladky, and Mathe gave an asymptotic formula of order  log n   for the size of the largest clique in G ( n , W ) when W is bounded away from 0 and 1. We show that if W is allowed to approach 1 at a finite number of points, and displays a moderate rate of growth near these points, then the clique number of G ( n , W ) will be of order √ n almost surely. We also give a family of examples with clique number of order n ^ c for any c in (0,1), and some conditions under which the clique number of  G ( n , W ) will be o (√ n ) or ω(√ n ). This talk assumes no previous knowledge of graphons.


Time: Monday, January 27th - 17:00 h s.t.

Colloquium: Michał Włodarczyk (Universität Eindhoven)

Title: Losing treewidth by separating subsets: on approximation of vertex/edge deletion problems

Abstract:

Consider the problem of deleting the smallest set S of vertices (resp. edges) from a given graph G such that the induced subgraph (resp. subgraph) G \ S belongs to some class H . I will cover the case where graphs in H have treewidth bounded by t , and give a general framework to obtain approximation algorithms basing on two ingredients: 1) approximation algorithms for the k -Subset Separator problem, 2) FPT algorithms parameterized by the solution size. For the vertex deletion setting, this new framework combined with the current best result for k -Subset Vertex Separator, improves approximation ratios for basic problems such as k -Treewidth Vertex Deletion and Planar F Vertex Deletion. Our algorithms are simpler than previous works and give the first deterministic and uniform approximation algorithms under the natural parameterization. I will talk about what it means for several important graph classes and how the bounded treewidth property is exploited. I will present a sketch of the proof for the H Vertex Deletion algorithm and explain the differences between deleting vertices or edges.

--------------14F45A133C9C2900F1D8E40D-- From i.brunke@inf.fu-berlin.de Tue Jan 28 17:18:34 2020 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 <1iwTZR-003tMZ-Oa>; Tue, 28 Jan 2020 17:18:33 +0100 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 <1iwTZR-0009UJ-Lp>; Tue, 28 Jan 2020 17:18:33 +0100 Received: from ip5f5af303.dynamic.kabel-deutschland.de ([95.90.243.3] helo=[192.168.0.2]) 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 <1iwTZR-003Bkv-CK>; Tue, 28 Jan 2020 17:18:33 +0100 From: Ita Brunke To: facets-of-complexity@lists.fu-berlin.de Message-ID: <85823375-9dcf-a37f-6685-c73d636cb650@inf.fu-berlin.de> Date: Tue, 28 Jan 2020 17:18:33 +0100 User-Agent: Mozilla/5.0 (Windows NT 6.1; Win64; x64; rv:52.0) Gecko/20100101 Firefox/52.0 SeaMonkey/2.49.5 MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="------------72A0FC8B908A22A5498EF19E" X-Originating-IP: 95.90.243.3 X-ZEDAT-Hint: A X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1580228313-0008DDA6-BBBEFFA4/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.000103, version=1.2.4 X-Spam-Flag: NO X-Spam-Status: No, score=-50.0 required=5.0 tests=ALL_TRUSTED,HTML_MESSAGE X-Spam-Checker-Version: SpamAssassin 3.4.3 on Kiribati.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Invitation to Monday Lecture & Colloquium - February 3rd 2020 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: Tue, 28 Jan 2020 16:18:34 -0000 This is a multi-part message in MIME format. --------------72A0FC8B908A22A5498EF19E Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit You are cordially invited to our next Monday Lecture & Colloquium on February 3rd - again at regular times - at *14:15 h* & *16:00 h* at FU Berlin. *_Location_**: ** * *Room 005 - Ground Floor* Freie Universität Berlin Takustr. 9 14195 Berlin *_Time_: **Monday, February 3rd - 14:15 h* *_Lecture_: Sándor Kisfaludi-Bak (MPI Saarbrücken**)* *_Title_: Separators and exact algorithms for geometric intersection graphs * *_Abstract_:* Given n ball-like objects in some metric space, one can define a geometric intersection graph where the vertices correspond to objects, and edges are added for pairs of objects with a non-empty intersection. A separator of a graph is a small or otherwise "nice" vertex set whose removal disconnects the graph into two roughly equal parts. In this talk, we will see some separator theorems for intersection graphs in Euclidean and hyperbolic space. One can use these separators to design simple divide and conquer algorithms for several classical NP-hard problems. It turns out that well-designed separators often lead to subexponential algorithms with optimal running times (up to constant factors in the exponent) under the Exponential Time Hypothesis (ETH). _*Coffee & Tea Break*_*:* *Room 134* *_Time_: **Monday, ***February* 3rd**- 16:00 h s.t.* *_Colloquium_: Yanitsa Pehova (University of Warwick**)* *_Title_: Characterisation of quasirandom permutations by a pattern sum * *_Abstract_:* We say that a sequence {π__/i/ } of permutations is quasirandom if, for each k>1 and each σ∈/S/__/k/ , the probability that a uniformly chosen /k-set of entries of π/__/i/ induces σ tends to 1//k/! as /i/ tends to infinity. It is known that a much weaker condition already forces π__/i/ to be quasirandom; namely, if the above property holds for all σ∈/S/_4 . We further weaken this condition by exhibiting sets S⊆/S/_4 , such that if randomly chosen four entries of π__/i/ induce an element of /S/ with probability tending to |/S/|/24, then {π__/i/ } is quasirandom. Moreover, we are able to completely characterise the sets /S/ with this property. In particular, there are exactly ten such sets, the smallest of which has cardinality eight. This is joint work with Timothy Chan, Daniel Král', Jon Noel, Maryam Sharifzadeh and Jan Volec. --------------72A0FC8B908A22A5498EF19E Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: 8bit

You are cordially invited to our next Monday Lecture & Colloquium on February 3rd - again at regular times - at 14:15 h & 16:00 h at FU Berlin.


Location:

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

Time: Monday, February 3rd - 14:15 h

Lecture: Sándor Kisfaludi-Bak (MPI Saarbrücken)

Title: Separators and exact algorithms for geometric intersection graphs

Abstract:

Given n ball-like objects in some metric space, one can define a geometric intersection graph where the vertices correspond to objects, and edges are added for pairs of objects with a non-empty intersection. A separator of a graph is a small or otherwise "nice" vertex set whose removal disconnects the graph into two roughly equal parts. In this talk, we will see some separator theorems for intersection graphs in Euclidean and hyperbolic space. One can use these separators to design simple divide and conquer algorithms for several classical NP-hard problems. It turns out that well-designed separators often lead to subexponential algorithms with optimal running times (up to constant factors in the exponent) under the Exponential Time Hypothesis (ETH).


Coffee & Tea Break:
Room 134

Time: Monday, February 3rd - 16:00 h s.t.

Colloquium: Yanitsa Pehova (University of Warwick)

Title: Characterisation of quasirandom permutations by a pattern sum

Abstract:

We say that a sequence {π_i} of permutations is quasirandom if, for each k>1 and each σ∈S_k, the probability that a uniformly chosen k-set of entries of π_i induces σ tends to 1/k! as i tends to infinity. It is known that a much weaker condition already forces π_i to be quasirandom; namely, if the above property holds for all σ∈S4. We further weaken this condition by exhibiting sets S⊆S4, such that if randomly chosen four entries of π_i induce an element of S with probability tending to |S|/24, then {π_i} is quasirandom. Moreover, we are able to completely characterise the sets S with this property. In particular, there are exactly ten such sets, the smallest of which has cardinality eight. This is joint work with Timothy Chan, Daniel Král', Jon Noel, Maryam Sharifzadeh and Jan Volec.

--------------72A0FC8B908A22A5498EF19E-- From i.brunke@inf.fu-berlin.de Mon Feb 03 17:58:59 2020 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 <1iyf3r-003ZRL-3l>; Mon, 03 Feb 2020 17:58:59 +0100 Received: from inpost2.zedat.fu-berlin.de ([130.133.4.69]) by outpost.zedat.fu-berlin.de (Exim 4.85) with esmtps (TLSv1.2:ECDHE-RSA-AES256-GCM-SHA384:256) (envelope-from ) id <1iyf3q-002zYi-54>; Mon, 03 Feb 2020 17:58:58 +0100 Received: from punkt.imp.fu-berlin.de ([160.45.40.245]) by inpost2.zedat.fu-berlin.de (Exim 4.85) with esmtpsa (TLSv1.2:ECDHE-RSA-AES128-GCM-SHA256:128) (envelope-from ) id <1iyf3p-0011wW-VR>; Mon, 03 Feb 2020 17:58:58 +0100 From: Ita Brunke To: facets-of-complexity@lists.fu-berlin.de Message-ID: Date: Mon, 3 Feb 2020 17:58:57 +0100 User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:68.0) Gecko/20100101 Thunderbird/68.4.1 MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="------------D1E5514C014F33239D926721" 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::1580749139-0006DFFB-6757D2F9/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 X-Spam-Flag: NO X-Spam-Status: No, score=-50.0 required=5.0 tests=ALL_TRUSTED,HTML_MESSAGE X-Spam-Checker-Version: SpamAssassin 3.4.4 on Palau.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Invitation to Monday Lecture & Colloquium - February 10th 2020 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: Mon, 03 Feb 2020 16:58:59 -0000 This is a multi-part message in MIME format. --------------D1E5514C014F33239D926721 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit You are cordially invited to our last Monday Lecture & Colloquium for this term on February 10th at 14:15 h, 16:00 h & 17:00 h at FU Berlin. *Exceptionally*, there will be once again a*second Colloquium* at *17:00. * *The Faculty will meet *after the second Colloquium.* * * * *_Location_**: ** * *Room 005 - Ground Floor* Freie Universität Berlin Takustr. 9 14195 Berlin *_Time_: **Monday, February 10th - 14:15 h* *_Lecture_: Lionel Pournin (Université Paris 13**)* *_Title_: Recent results on the diameter of lattice polytopes * *_Abstract_:* Several new results about the largest possible diameter of a lattice polytope contained in the hypercube [0,k]^d, a quantity related to the complexity of the simplex algorithm, will be presented. Upper bounds on this quantity have been known for a couple of decades and have been improved recently. In this lecture, conjecturally sharp lower bounds on this quantity will be presented for all d and k, as well as exact asymptotic estimates when d is fixed and k grows large. These lower bounds are obtained by computing the largest diameter a lattice zonotope contained in the hypercube [0,k]^d can have, answering a question by Günter Rote. This talk is based on joint work with Antoine Deza and Noriyoshi Sukegawa. _*Coffee & Tea Break*_*:* *Room 134* *_Time_: **Monday, **February 10th**- 16:00 h s.t.* *_Colloquium_: José Samper (Max Planck Institute Leipzig**)* *_Title_: Dual matroid polytopes and the independence complex of a matroid * *_Abstract_:* A shelling order of a simplicial/polytopal complex is an ordering of the top dimensional faces that allows us to understand various properties of the underlying complex (when it exists). Empirically, some shelling orders are better than others in the sense that they are easier to analyze or come equipped with . This is especially notable for complexes that admit many shelling orders, like polytopes and and matroid independence complexes. We propose a strange connection, linking shelling orders of dual matroid polytopes to shelling orders of independence complexes. In particular, we show that several classical theorems about shellability of matroids have geometric interpretations. We use this to address to propose a new strategy for a 1977 conjecture of R. Stanley about face numbers of independence complexes: that the h-vector is a pure O-sequence. The talk is based on joint work with Alex Heaton. *_Time_: **Monday, **February 10th**- 17:00 h s.t.* *_Colloquium_: Zslot Ádám Wagner (ETH Zürich**)* *_Title_: Recent developments in the container method * *_Abstract_:* The container algorithm is a recently-developed technique for establishing subtle clustering phenomena of independent sets in graphs and hypergraphs. This method has found numerous applications in extremal graph theory, Ramsey theory, additive combinatorics, and discrete geometry. In this talk, I will give a brief overview of this method and survey some recent developments. --------------D1E5514C014F33239D926721 Content-Type: text/html; charset=utf-8 Content-Transfer-Encoding: 8bit

You are cordially invited to our last Monday Lecture & Colloquium for this term on February 10th at 14:15 h, 16:00 h & 17:00 h at FU Berlin.

Exceptionally, there will be once again a second Colloquium at 17:00.

The Faculty will meet after the second Colloquium.


Location:

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

Time: Monday, February 10th - 14:15 h

Lecture: Lionel Pournin (Université Paris 13)

Title: Recent results on the diameter of lattice polytopes

Abstract:

Several new results about the largest possible diameter of a lattice polytope contained in the hypercube [0,k]^d, a quantity related to the complexity of the simplex algorithm, will be presented. Upper bounds on this quantity have been known for a couple of decades and have been improved recently. In this lecture, conjecturally sharp lower bounds on this quantity will be presented for all d and k, as well as exact asymptotic estimates when d is fixed and k grows large. These lower bounds are obtained by computing the largest diameter a lattice zonotope contained in the hypercube [0,k]^d can have, answering a question by Günter Rote. This talk is based on joint work with Antoine Deza and Noriyoshi Sukegawa.


Coffee & Tea Break:
Room 134

Time: Monday, February 10th - 16:00 h s.t.

Colloquium: José Samper (Max Planck Institute Leipzig)

Title: Dual matroid polytopes and the independence complex of a matroid

Abstract:

A shelling order of a simplicial/polytopal complex is an ordering of the top dimensional faces that allows us to understand various properties of the underlying complex (when it exists). Empirically, some shelling orders are better than others in the sense that they are easier to analyze or come equipped with . This is especially notable for complexes that admit many shelling orders, like polytopes and and matroid independence complexes. We propose a strange connection, linking shelling orders of dual matroid polytopes to shelling orders of independence complexes. In particular, we show that several classical theorems about shellability of matroids have geometric interpretations. We use this to address to propose a new strategy for a 1977 conjecture of R. Stanley about face numbers of independence complexes: that the h-vector is a pure O-sequence. The talk is based on joint work with Alex Heaton.


Time: Monday, February 10th - 17:00 h s.t.

Colloquium: Zslot Ádám Wagner (ETH Zürich)

Title: Recent developments in the container method

Abstract:

The container algorithm is a recently-developed technique for establishing subtle clustering phenomena of independent sets in graphs and hypergraphs. This method has found numerous applications in extremal graph theory, Ramsey theory, additive combinatorics, and discrete geometry. In this talk, I will give a brief overview of this method and survey some recent developments.

--------------D1E5514C014F33239D926721-- From rote@inf.fu-berlin.de Thu Feb 06 18:51:53 2020 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 <1izlJh-003Ix3-E2>; Thu, 06 Feb 2020 18:51:53 +0100 Received: from inpost2.zedat.fu-berlin.de ([130.133.4.69]) by outpost.zedat.fu-berlin.de (Exim 4.85) with esmtps (TLSv1.2:ECDHE-RSA-AES256-GCM-SHA384:256) (envelope-from ) id <1izlJh-0022g8-BV>; Thu, 06 Feb 2020 18:51:53 +0100 Received: from [64.210.41.235] (helo=[192.168.1.214]) by inpost2.zedat.fu-berlin.de (Exim 4.85) with esmtpsa (TLSv1.2:ECDHE-RSA-AES128-GCM-SHA256:128) (envelope-from ) id <1izlJf-0035kA-0B>; Thu, 06 Feb 2020 18:51:53 +0100 References: To: facets-of-complexity@lists.fu-berlin.de Cc: Ita Brunke From: =?UTF-8?Q?G=c3=bcnter_Rote?= X-Forwarded-Message-Id: Message-ID: <0b168244-15b5-3f74-8742-4c40e1833885@inf.fu-berlin.de> Date: Thu, 6 Feb 2020 18:56:50 +0100 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101 Thunderbird/60.7.2 MIME-Version: 1.0 In-Reply-To: Content-Type: text/plain; charset=utf-8; format=flowed Content-Language: en-US Content-Transfer-Encoding: 8bit X-Originating-IP: 64.210.41.235 X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1581011513-0005ECF0-6184E939/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.018729, version=1.2.4 X-Spam-Flag: NO X-Spam-Status: No, score=-50.0 required=5.0 tests=ALL_TRUSTED X-Spam-Checker-Version: SpamAssassin 3.4.4 on Tokelau.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Invitation to Monday Lecture & Colloquium - February 10th 2020 / Third 17:00 talk canceled 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: Thu, 06 Feb 2020 17:51:53 -0000 You are invited to our last Monday Lecture & Colloquium for this term next Monday at 14:15 h and 16:00 h at FU Berlin. The *second Colloquium* that was planned for *17:00* is CANCELED. Location: Room 005 - Ground Floor Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin Time: Monday, February 10th - 14:15 h Lecture: Lionel Pournin (Université Paris 13) Title: Recent results on the diameter of lattice polytopes Abstract: Several new results about the largest possible diameter of a lattice polytope contained in the hypercube [0,k]^d, a quantity related to the complexity of the simplex algorithm, will be presented. Upper bounds on this quantity have been known for a couple of decades and have been improved recently. In this lecture, conjecturally sharp lower bounds on this quantity will be presented for all d and k, as well as exact asymptotic estimates when d is fixed and k grows large. These lower bounds are obtained by computing the largest diameter a lattice zonotope contained in the hypercube [0,k]^d can have, answering a question by Günter Rote. This talk is based on joint work with Antoine Deza and Noriyoshi Sukegawa. Coffee & Tea Break: Room 134 Time: 16:00 h s.t. Colloquium: José Samper (Max-Planck-Institut Leipzig) Title: Dual matroid polytopes and the independence complex of a matroid Abstract: A shelling order of a simplicial/polytopal complex is an ordering of the top dimensional faces that allows us to understand various properties of the underlying complex (when it exists). Empirically, some shelling orders are better than others in the sense that they are easier to analyze or come equipped with . This is especially notable for complexes that admit many shelling orders, like polytopes and and matroid independence complexes. We propose a strange connection, linking shelling orders of dual matroid polytopes to shelling orders of independence complexes. In particular, we show that several classical theorems about shellability of matroids have geometric interpretations. We use this to address to propose a new strategy for a 1977 conjecture of R. Stanley about face numbers of independence complexes: that the h-vector is a pure O-sequence. The talk is based on joint work with Alex Heaton. The second colloquium that was planned at 17:00 h (by Zsolt Ádám Wagner from ETH Zürich, about recent developments in the container method) is CANCELED. From i.brunke@inf.fu-berlin.de Mon Feb 10 14:23:28 2020 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 <1j1928-002Nn3-5A>; Mon, 10 Feb 2020 14:23:28 +0100 Received: from inpost2.zedat.fu-berlin.de ([130.133.4.69]) by outpost.zedat.fu-berlin.de (Exim 4.85) with esmtps (TLSv1.2:ECDHE-RSA-AES256-GCM-SHA384:256) (envelope-from ) id <1j1927-001EWi-5S>; Mon, 10 Feb 2020 14:23:27 +0100 Received: from punkt.imp.fu-berlin.de ([160.45.40.245]) by inpost2.zedat.fu-berlin.de (Exim 4.85) with esmtpsa (TLSv1.2:ECDHE-RSA-AES128-GCM-SHA256:128) (envelope-from ) id <1j1926-002ju2-T8>; Mon, 10 Feb 2020 14:23:27 +0100 From: Ita Brunke To: facets-of-complexity@lists.fu-berlin.de References: Message-ID: Date: Mon, 10 Feb 2020 14:23:26 +0100 User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:68.0) Gecko/20100101 Thunderbird/68.4.1 MIME-Version: 1.0 In-Reply-To: Content-Type: multipart/alternative; boundary="------------452046647D1A24B345B1F3BB" 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::1581341008-00046016-79E042EF/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.003378, version=1.2.4 X-Spam-Flag: NO X-Spam-Status: No, score=-50.0 required=5.0 tests=ALL_TRUSTED,HTML_MESSAGE X-Spam-Checker-Version: SpamAssassin 3.4.4 on Niue.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] CHANGE of program - Monday Lecture & Colloquium - February 10th 2020 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: Mon, 10 Feb 2020 13:23:28 -0000 This is a multi-part message in MIME format. --------------452046647D1A24B345B1F3BB Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit Due to the storm 'Sabine' the second talk of today can not be given. Today there will only be the Lecture and the coffee after. On 03.02.2020 17:58, Ita Brunke wrote: > > You are cordially invited to our last Monday Lecture & Colloquium for > this term on February 10th at 14:15 h, 16:00 h & 17:00 h at FU Berlin. > > *Exceptionally*, there will be once again a*second Colloquium* at *17:00. > * > > *The Faculty will meet *after the second Colloquium.* > * > > * > * > > *_Location_**: ** > * > > *Room 005 - Ground Floor* > Freie Universität Berlin > Takustr. 9 > 14195 Berlin > > *_Time_: **Monday, February 10th - 14:15 h* > > *_Lecture_: Lionel Pournin (Université Paris 13**)* > > *_Title_: Recent results on the diameter of lattice polytopes > * > > *_Abstract_:* > > Several new results about the largest possible diameter of a lattice > polytope contained in the hypercube [0,k]^d, a quantity related to the > complexity of the simplex algorithm, will be presented. Upper bounds > on this quantity have been known for a couple of decades and have been > improved recently. In this lecture, conjecturally sharp lower bounds > on this quantity will be presented for all d and k, as well as exact > asymptotic estimates when d is fixed and k grows large. These lower > bounds are obtained by computing the largest diameter a lattice > zonotope contained in the hypercube [0,k]^d can have, answering a > question by Günter Rote. This talk is based on joint work with Antoine > Deza and Noriyoshi Sukegawa. > > > _*Coffee & Tea Break*_*:* > *Room 134* > > *_Time_: **Monday, **February 10th**- 16:00 h s.t.* > > *_Colloquium_: José Samper (Max Planck Institute Leipzig**)* > > *_Title_: Dual matroid polytopes and the independence complex of a > matroid > * > > *_Abstract_:* > > A shelling order of a simplicial/polytopal complex is an ordering of > the top dimensional faces that allows us to understand various > properties of the underlying complex (when it exists). Empirically, > some shelling orders are better than others in the sense that they are > easier to analyze or come equipped with . This is especially notable > for complexes that admit many shelling orders, like polytopes and and > matroid independence complexes. We propose a strange connection, > linking shelling orders of dual matroid polytopes to shelling orders > of independence complexes. In particular, we show that several > classical theorems about shellability of matroids have geometric > interpretations. We use this to address to propose a new strategy for > a 1977 conjecture of R. Stanley about face numbers of independence > complexes: that the h-vector is a pure O-sequence. The talk is based > on joint work with Alex Heaton: > --------------452046647D1A24B345B1F3BB Content-Type: text/html; charset=utf-8 Content-Transfer-Encoding: 8bit

Due to the storm 'Sabine' the second talk of today can not be given.

Today there will only be the Lecture and the coffee after.


    
On 03.02.2020 17:58, Ita Brunke wrote:

    

    

      
      
You are cordially invited to our last Monday Lecture &
        Colloquium for this term on February 10th at 14:15 h, 16:00 h
        & 17:00 h at FU Berlin. 

      

      
Exceptionally, there will be once again a second
          Colloquium at 17:00. 

        

      
The Faculty will meet after the second Colloquium.

        

      


        

      
 

      
Location: 

        

      Room 005 - Ground Floor

      Freie Universität Berlin

      Takustr. 9

      14195 Berlin 

      
Time: Monday, February 10th - 14:15 h 

      
Lecture: Lionel Pournin (Université Paris 13)

      
Title: Recent results on the diameter of lattice
          polytopes

        

      Abstract:

      

        
Several new results about the largest possible diameter of a
          lattice polytope contained in the hypercube [0,k]^d, a
          quantity related to the complexity of the simplex algorithm,
          will be presented. Upper bounds on this quantity have been
          known for a couple of decades and have been improved recently.
          In this lecture, conjecturally sharp lower bounds on this
          quantity will be presented for all d and k, as well as exact
          asymptotic estimates when d is fixed and k grows large. These
          lower bounds are obtained by computing the largest diameter a
          lattice zonotope contained in the hypercube [0,k]^d can have,
          answering a question by Günter Rote. This talk is based on
          joint work with Antoine Deza and Noriyoshi Sukegawa.

        

      

      

      Coffee & Tea Break:

      Room 134

      
Time: Monday, February 10th -
          16:00 h s.t. 

      
Colloquium: José Samper (Max Planck Institute Leipzig)

      
Title: Dual matroid polytopes and the independence
          complex of a matroid 

        

      Abstract:

      
A shelling order of a simplicial/polytopal complex is an
        ordering of the top dimensional faces that allows us to
        understand various properties of the underlying complex (when it
        exists). Empirically, some shelling orders are better than
        others in the sense that they are easier to analyze or come
        equipped with . This is especially notable for complexes that
        admit many shelling orders, like polytopes and and matroid
        independence complexes. We propose a strange connection, linking
        shelling orders of dual matroid polytopes to shelling orders of
        independence complexes. In particular, we show that several
        classical theorems about shellability of matroids have geometric
        interpretations. We use this to address to propose a new
        strategy for a 1977 conjecture of R. Stanley about face numbers
        of independence complexes: that the h-vector is a pure
        O-sequence. The talk is based on joint work with Alex Heaton: 

    

  


--------------452046647D1A24B345B1F3BB--



From itabrunke@zedat.fu-berlin.de Mon Oct 12 16:13:04 2020
Received: from outpost1.zedat.fu-berlin.de ([130.133.4.66])
 by list1.zedat.fu-berlin.de (Exim 4.94)
 for facets-of-complexity@lists.fu-berlin.de with esmtps (TLS1.2)
 tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384
 (envelope-from )
 id 1kRyZT-002tZ9-Mk; Mon, 12 Oct 2020 16:13:03 +0200
Received: from inpost2.zedat.fu-berlin.de ([130.133.4.69])
 by outpost.zedat.fu-berlin.de (Exim 4.94)
 for facets-of-complexity@lists.fu-berlin.de with esmtps (TLS1.2)
 tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384
 (envelope-from )
 id 1kRyZT-003x50-K7; Mon, 12 Oct 2020 16:13:03 +0200
Received: from ip5f5af231.dynamic.kabel-deutschland.de ([95.90.242.49]
 helo=[192.168.0.2]) by inpost2.zedat.fu-berlin.de (Exim 4.94)
 for facets-of-complexity@lists.fu-berlin.de with esmtpsa (TLS1.2)
 tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256
 (envelope-from )
 id 1kRyZT-002KgD-6j; Mon, 12 Oct 2020 16:13:03 +0200
To: facets-of-complexity@lists.fu-berlin.de
From: Ita Brunke 
Message-ID: 
Date: Mon, 12 Oct 2020 16:13:02 +0200
User-Agent: Mozilla/5.0 (Windows NT 6.1; Win64; x64; rv:52.0) Gecko/20100101
 Firefox/52.0 SeaMonkey/2.49.5
MIME-Version: 1.0
Content-Type: multipart/alternative;
 boundary="------------2F8D89064CC755CA711106D4"
X-Original-Sender: i.brunke@inf.fu-berlin.de
X-Originating-IP: 95.90.242.49
X-ZEDAT-Hint: A
X-purgate: suspect
X-purgate-type: suspect
X-purgate-ID: 151147::1602511983-00067A41-77D4F8AA/19/6968933386
X-Bogosity: Ham, tests=bogofilter, spamicity=0.012001, 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
X-Spam-Checker-Version: SpamAssassin 3.4.4 on Tokelau.ZEDAT.FU-Berlin.DE
X-Spam-Level: 
Subject: [Facets-of-complexity] Invitation to Monday Lecture & Colloquium -
 October 19th 2020 - online via zoom
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: Mon, 12 Oct 2020 14:13:04 -0000

This is a multi-part message in MIME format.
--------------2F8D89064CC755CA711106D4
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit

You are cordially invited to our first Monday Lecture & Colloquium since 
Corona crisis stopped our curriculum.
Monday Lecture & Colloquium will be held online. Invitation for Zoom 
will follow by Invitor.
First Monday Lecture & Colloquium will start on October 19th 2020 at 
14:15 h & 16:00 h.

*_Online via_:
Zoom - Invitation will follow*

*_Time_: **Monday, October 19th - 14:15 h*

*_Lecture_: Mikkel Abrahamsen (University of Copenhagen)
*

*_Title_: A framework for ∃R-completeness of two-dimensional packing 
problems*

*_Abstract_:*

We show that many natural two-dimensional packing problems are 
algorithmically equivalent to finding real roots of multivariate 
polynomials. A two-dimensional packing problem is defined by the type of 
pieces, containers, and motions that are allowed. The aim is to decide 
if a given set of pieces can be placed inside a given container. The 
pieces must be placed so that they are pairwise interior-disjoint, and 
only motions of the allowed type can be used to move them there. We 
establish a framework which enables us to show that for many 
combinations of allowed pieces, containers, and motions, the resulting 
problem is ∃R-complete. This means that the problem is equivalent (under 
polynomial time reductions) to deciding whether a given system of 
polynomial equations and inequalities with integer coefficients has a 
real solution. We consider packing problems where only translations are 
allowed as the motions, and problems where arbitrary rigid motions are 
allowed, i.e., both translations and rotations. When rotations are 
allowed, we show that the following combinations of allowed pieces and 
containers are ∃R-complete: - simple polygons, each of which has at most 
8 corners, into a square, - convex objects bounded by line segments and 
hyperbolic curves into a square, - convex polygons into a container 
bounded by line segments and hyperbolic curves. Restricted to 
translations, we show that the following combinations are ∃R-complete: - 
objects bounded by segments and hyperbolic curves into a square, - 
convex polygons into a container bounded by segments and hyperbolic 
curves. Joint work by Mikkel Abrahamsen, Tillmann Miltzow, and Nadja 
Seiferth. The paper has been accepted for FOCS.

_*Break*_*:*

*Wherever you are.***


*_Time_: **Monday, ***October 19th* - 16:00 h s.t.*

*_Colloquium_: Tillmann Miltzow (Utrecht University**)*

*_Title_: A practical algorithm with performance guarantees for the 
art-gallery problem*

*_Abstract_:*

Given a closed simple polygon P, we say two points p,q see each other if 
the segment pq is fully contained in P. The art gallery problem seeks a 
minimum size set G⊂P of guards that sees P completely. The only known 
algorithm to solve the art gallery problem exactly is attributed to 
Sharir and uses algebraic methods. As the art gallery problem is 
∃R-complete, it seems impossible to avoid algebraic methods without 
additional assumptions.

To circumvent this problem, we introduce the notion of vision stability.
In order to describe vision stability, consider an enhanced guard that 
can see "around the corner" by an angle of δ or a diminished guard whose 
vision is "blocked" by an angle δ by reflex vertices. A polygon P has 
vision stability δ if the optimal number of enhanced guards to guard P 
is the same as the optimal number of diminished guards to guard P. We 
will argue that most relevant polygons are vision-stable. We describe a 
one-shot algorithm that computes an optimal guard set for vision-stable 
polygons using polynomial time besides solving one integer program.

We implemented an iterative version of the vision-stable algorithm. Its 
practical performance is slower, but comparable to other
state-of-the-art algorithms. Our iterative algorithm is a variation of 
the one-shot algorithm. It delays some steps and only computes them only 
when deemed necessary. Given a chord c of a polygon, we denote by n(c) 
the number of vertices visible from c. The chord-width of a polygon is 
the maximum n(c) over all possible chords c. The set of vision-stable 
polygons admits an FPT algorithm when parametrized by the chord-width. 
Furthermore, the one-shot algorithm runs in FPT time when parameterized 
by the number of reflex vertices.

Joint work by Simon Hengeveld & Tillmann Miltzow.


--------------2F8D89064CC755CA711106D4
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: 8bit


  

    
  
  
    

      

        
You are cordially invited to our first Monday Lecture &
          Colloquium since Corona crisis stopped our curriculum.

          Monday Lecture & Colloquium will be held online.
          Invitation for Zoom will follow by Invitor.

          First Monday Lecture & Colloquium will start on October
          19th 2020 at 14:15 h & 16:00 h. 

        

        Online via:

          Zoom - Invitation will follow 
        
Time: Monday, October 19th - 14:15 h 

        
Lecture: Mikkel Abrahamsen (University of
            Copenhagen)

          

        
Title: A framework for ∃R-completeness of
            two-dimensional packing problems

        Abstract:

        


        

        
We show that
          many natural two-dimensional packing problems are
          algorithmically equivalent to finding real roots of
          multivariate polynomials. A two-dimensional packing problem is
          defined by the type of pieces, containers, and motions that
          are allowed. The aim is to decide if a given set of pieces can
          be placed inside a given container. The pieces must be placed
          so that they are pairwise interior-disjoint, and only motions
          of the allowed type can be used to move them there. We
          establish a framework which enables us to show that for many
          combinations of allowed pieces, containers, and motions, the
          resulting problem is ∃R-complete. This means that the problem
          is equivalent (under polynomial time reductions) to deciding
          whether a given system of polynomial equations and
          inequalities with integer coefficients has a real solution. We
          consider packing problems where only translations are allowed
          as the motions, and problems where arbitrary rigid motions are
          allowed, i.e., both translations and rotations. When rotations
          are allowed, we show that the following combinations of
          allowed pieces and containers are ∃R-complete: - simple
          polygons, each of which has at most 8 corners, into a square,
          - convex objects bounded by line segments and hyperbolic
          curves into a square, - convex polygons into a container
          bounded by line segments and hyperbolic curves. Restricted to
          translations, we show that the following combinations are
          ∃R-complete: - objects bounded by segments and hyperbolic
          curves into a square, - convex polygons into a container
          bounded by segments and hyperbolic curves. Joint work by
          Mikkel Abrahamsen, Tillmann Miltzow, and Nadja Seiferth. The
          paper has been accepted for FOCS.

        

        Break :

        
Wherever you are. 

        

        Time: Monday, October 19th -
          16:00 h s.t. 

        
Colloquium: Tillmann Miltzow (Utrecht University)

        
Title: A practical algorithm with performance
            guarantees for the art-gallery problem

        Abstract:

        
Given a closed simple polygon P, we
          say two points p,q see each other if the segment pq is fully
          contained in P. The art gallery problem seeks a minimum size
          set G⊂P of guards that sees P completely. The only known
          algorithm to solve the art gallery problem exactly is
          attributed to Sharir and uses algebraic methods. As the art
          gallery problem is ∃R-complete, it seems impossible to avoid
          algebraic methods without additional assumptions. 

          

          To circumvent this problem, we introduce the notion of vision
          stability. 

          In order to describe vision stability, consider an enhanced
          guard that can see "around the corner" by an angle of δ or a
          diminished guard whose vision is "blocked" by an angle δ by
          reflex vertices. A polygon P has vision stability δ if the
          optimal number of enhanced guards to guard P is the same as
          the optimal number of diminished guards to guard P. We will
          argue that most relevant polygons are vision-stable. We
          describe a one-shot algorithm that computes an optimal guard
          set for vision-stable polygons using polynomial time besides
          solving one integer program. 

          

          We implemented an iterative version of the vision-stable
          algorithm. Its practical performance is slower, but comparable
          to other 

          state-of-the-art algorithms. Our iterative algorithm is a
          variation of the one-shot algorithm. It delays some steps and
          only computes them only when deemed necessary. Given a chord c
          of a polygon, we denote by n(c) the number of vertices visible
          from c. The chord-width of a polygon is the maximum n(c) over
          all possible chords c. The set of vision-stable polygons
          admits an FPT algorithm when parametrized by the chord-width.
          Furthermore, the one-shot algorithm runs in FPT time when
          parameterized by the number of reflex vertices.

        

          
Joint work by Simon Hengeveld & Tillmann Miltzow.

        

      

    

  


--------------2F8D89064CC755CA711106D4--



From itabrunke@zedat.fu-berlin.de Sun Oct 18 18:00:01 2020
Received: from outpost1.zedat.fu-berlin.de ([130.133.4.66])
 by list1.zedat.fu-berlin.de (Exim 4.94)
 for facets-of-complexity@lists.fu-berlin.de with esmtps (TLS1.2)
 tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384
 (envelope-from )
 id 1kUB6G-000N8n-8G; Sun, 18 Oct 2020 18:00:00 +0200
Received: from inpost2.zedat.fu-berlin.de ([130.133.4.69])
 by outpost.zedat.fu-berlin.de (Exim 4.94) with esmtps (TLS1.2)
 tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384
 (envelope-from )
 id 1kUB6G-001ZKc-56; Sun, 18 Oct 2020 18:00:00 +0200
Received: from ip5f5af239.dynamic.kabel-deutschland.de ([95.90.242.57]
 helo=[192.168.0.2]) by inpost2.zedat.fu-berlin.de (Exim 4.94)
 with esmtpsa (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256
 (envelope-from )
 id 1kUB6F-000TDK-P4; Sun, 18 Oct 2020 18:00:00 +0200
From: Ita Brunke 
To: facets-of-complexity@lists.fu-berlin.de
Message-ID: 
Date: Sun, 18 Oct 2020 17:59:59 +0200
User-Agent: Mozilla/5.0 (Windows NT 6.1; Win64; x64; rv:52.0) Gecko/20100101
 Firefox/52.0 SeaMonkey/2.49.5
MIME-Version: 1.0
Content-Type: multipart/alternative;
 boundary="------------2E736698B774C1742279BD8F"
X-Original-Sender: i.brunke@inf.fu-berlin.de
X-Originating-IP: 95.90.242.57
X-ZEDAT-Hint: A
X-purgate: clean
X-purgate-type: clean
X-purgate-ID: 151147::1603036800-000C5F89-4BD067AE/0/0
X-Bogosity: Ham, tests=bogofilter, spamicity=0.003288, version=1.2.4
X-Spam-Flag: NO
X-Spam-Status: No, score=-50.0 required=5.0 tests=ALL_TRUSTED,HTML_MESSAGE
X-Spam-Checker-Version: SpamAssassin 3.4.4 on Tokelau.ZEDAT.FU-Berlin.DE
X-Spam-Level: 
Subject: [Facets-of-complexity] Invitation Link to Monday Lecture &
 Colloquium October 19th 2020 via zoom
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: Sun, 18 Oct 2020 16:00:01 -0000

This is a multi-part message in MIME format.
--------------2E736698B774C1742279BD8F
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit

Dear all,

please find invitation link for zoom here:

https://tu-berlin.zoom.us/j/69716124232?pwd=dzFlcTFHMmFXRTE5QmZLaEV5N0FRUT09 


You may also find the link on our homepage:

http://www.facetsofcomplexity.de/monday/WS-2020-21/index.html

Valid for all Monday Lectures to come for winter term 20/21.

You are cordially invited to our first Monday Lecture & Colloquium since 
Corona crisis stopped our curriculum.
Monday Lecture & Colloquium will be held online. Invitation for Zoom 
will follow by Invitor.
First Monday Lecture & Colloquium will start on October 19th 2020 at 
14:15 h & 16:00 h.

*_Online via_:
Zoom - Invitation will follow*

*_Time_: **Monday, October 19th - 14:15 h*

*_Lecture_: Mikkel Abrahamsen (University of Copenhagen)
*

*_Title_: A framework for ∃R-completeness of two-dimensional packing 
problems*

*_Abstract_:*

We show that many natural two-dimensional packing problems are 
algorithmically equivalent to finding real roots of multivariate 
polynomials. A two-dimensional packing problem is defined by the type of 
pieces, containers, and motions that are allowed. The aim is to decide 
if a given set of pieces can be placed inside a given container. The 
pieces must be placed so that they are pairwise interior-disjoint, and 
only motions of the allowed type can be used to move them there. We 
establish a framework which enables us to show that for many 
combinations of allowed pieces, containers, and motions, the resulting 
problem is ∃R-complete. This means that the problem is equivalent (under 
polynomial time reductions) to deciding whether a given system of 
polynomial equations and inequalities with integer coefficients has a 
real solution. We consider packing problems where only translations are 
allowed as the motions, and problems where arbitrary rigid motions are 
allowed, i.e., both translations and rotations. When rotations are 
allowed, we show that the following combinations of allowed pieces and 
containers are ∃R-complete: - simple polygons, each of which has at most 
8 corners, into a square, - convex objects bounded by line segments and 
hyperbolic curves into a square, - convex polygons into a container 
bounded by line segments and hyperbolic curves. Restricted to 
translations, we show that the following combinations are ∃R-complete: - 
objects bounded by segments and hyperbolic curves into a square, - 
convex polygons into a container bounded by segments and hyperbolic 
curves. Joint work by Mikkel Abrahamsen, Tillmann Miltzow, and Nadja 
Seiferth. The paper has been accepted for FOCS.

_*Break*_*:*

*Wherever you are.***


*_Time_: **Monday, ***October 19th* - 16:00 h s.t.*

*_Colloquium_: Tillmann Miltzow (Utrecht University**)*

*_Title_: A practical algorithm with performance guarantees for the 
art-gallery problem*

*_Abstract_:*

Given a closed simple polygon P, we say two points p,q see each other if 
the segment pq is fully contained in P. The art gallery problem seeks a 
minimum size set G⊂P of guards that sees P completely. The only known 
algorithm to solve the art gallery problem exactly is attributed to 
Sharir and uses algebraic methods. As the art gallery problem is 
∃R-complete, it seems impossible to avoid algebraic methods without 
additional assumptions.

To circumvent this problem, we introduce the notion of vision stability.
In order to describe vision stability, consider an enhanced guard that 
can see "around the corner" by an angle of δ or a diminished guard whose 
vision is "blocked" by an angle δ by reflex vertices. A polygon P has 
vision stability δ if the optimal number of enhanced guards to guard P 
is the same as the optimal number of diminished guards to guard P. We 
will argue that most relevant polygons are vision-stable. We describe a 
one-shot algorithm that computes an optimal guard set for vision-stable 
polygons using polynomial time besides solving one integer program.

We implemented an iterative version of the vision-stable algorithm. Its 
practical performance is slower, but comparable to other
state-of-the-art algorithms. Our iterative algorithm is a variation of 
the one-shot algorithm. It delays some steps and only computes them only 
when deemed necessary. Given a chord c of a polygon, we denote by n(c) 
the number of vertices visible from c. The chord-width of a polygon is 
the maximum n(c) over all possible chords c. The set of vision-stable 
polygons admits an FPT algorithm when parametrized by the chord-width. 
Furthermore, the one-shot algorithm runs in FPT time when parameterized 
by the number of reflex vertices.

Joint work by Simon Hengeveld & Tillmann Miltzow.


--------------2E736698B774C1742279BD8F
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: 8bit


  

    
  
  
    Dear all,

    

    please find invitation link for zoom here:

    

    https://tu-berlin.zoom.us/j/69716124232?pwd=dzFlcTFHMmFXRTE5QmZLaEV5N0FRUT09
    

    

    You may also find the link on our homepage:

    

    http://www.facetsofcomplexity.de/monday/WS-2020-21/index.html

    

    Valid for all Monday Lectures to come for winter term 20/21.

    

    

      

        

          
You are cordially invited to our first Monday Lecture &
            Colloquium since Corona crisis stopped our curriculum.

            Monday Lecture & Colloquium will be held online.
            Invitation for Zoom will follow by Invitor.

            First Monday Lecture & Colloquium will start on October
            19th 2020 at 14:15 h & 16:00 h. 

          

          Online via:

            Zoom - Invitation will follow 
          
Time: Monday, October 19th - 14:15 h
          

          
Lecture: Mikkel Abrahamsen (University of
              Copenhagen)

            

          
Title: A framework for ∃R-completeness of
              two-dimensional packing problems

          Abstract:

          


          

          
We show
            that many natural two-dimensional packing problems are
            algorithmically equivalent to finding real roots of
            multivariate polynomials. A two-dimensional packing problem
            is defined by the type of pieces, containers, and motions
            that are allowed. The aim is to decide if a given set of
            pieces can be placed inside a given container. The pieces
            must be placed so that they are pairwise interior-disjoint,
            and only motions of the allowed type can be used to move
            them there. We establish a framework which enables us to
            show that for many combinations of allowed pieces,
            containers, and motions, the resulting problem is
            ∃R-complete. This means that the problem is equivalent
            (under polynomial time reductions) to deciding whether a
            given system of polynomial equations and inequalities with
            integer coefficients has a real solution. We consider
            packing problems where only translations are allowed as the
            motions, and problems where arbitrary rigid motions are
            allowed, i.e., both translations and rotations. When
            rotations are allowed, we show that the following
            combinations of allowed pieces and containers are
            ∃R-complete: - simple polygons, each of which has at most 8
            corners, into a square, - convex objects bounded by line
            segments and hyperbolic curves into a square, - convex
            polygons into a container bounded by line segments and
            hyperbolic curves. Restricted to translations, we show that
            the following combinations are ∃R-complete: - objects
            bounded by segments and hyperbolic curves into a square, -
            convex polygons into a container bounded by segments and
            hyperbolic curves. Joint work by Mikkel Abrahamsen, Tillmann
            Miltzow, and Nadja Seiferth. The paper has been accepted for
            FOCS.

          

          Break :

          
Wherever you are. 

          

          Time: Monday, October 19th -
            16:00 h s.t. 

          
Colloquium: Tillmann Miltzow (Utrecht University)

          
Title: A practical algorithm with performance
              guarantees for the art-gallery problem

          Abstract:

          
Given a closed simple polygon P,
            we say two points p,q see each other if the segment pq is
            fully contained in P. The art gallery problem seeks a
            minimum size set G⊂P of guards that sees P completely. The
            only known algorithm to solve the art gallery problem
            exactly is attributed to Sharir and uses algebraic methods.
            As the art gallery problem is ∃R-complete, it seems
            impossible to avoid algebraic methods without additional
            assumptions. 

            

            To circumvent this problem, we introduce the notion of
            vision stability. 

            In order to describe vision stability, consider an enhanced
            guard that can see "around the corner" by an angle of δ or a
            diminished guard whose vision is "blocked" by an angle δ by
            reflex vertices. A polygon P has vision stability δ if the
            optimal number of enhanced guards to guard P is the same as
            the optimal number of diminished guards to guard P. We will
            argue that most relevant polygons are vision-stable. We
            describe a one-shot algorithm that computes an optimal guard
            set for vision-stable polygons using polynomial time besides
            solving one integer program. 

            

            We implemented an iterative version of the vision-stable
            algorithm. Its practical performance is slower, but
            comparable to other 

            state-of-the-art algorithms. Our iterative algorithm is a
            variation of the one-shot algorithm. It delays some steps
            and only computes them only when deemed necessary. Given a
            chord c of a polygon, we denote by n(c) the number of
            vertices visible from c. The chord-width of a polygon is the
            maximum n(c) over all possible chords c. The set of
            vision-stable polygons admits an FPT algorithm when
            parametrized by the chord-width. Furthermore, the one-shot
            algorithm runs in FPT time when parameterized by the number
            of reflex vertices.

          

            
Joint work by Simon Hengeveld & Tillmann Miltzow.

          

        

      

    

  


--------------2E736698B774C1742279BD8F--



From itabrunke@zedat.fu-berlin.de Wed Oct 21 17:39:51 2020
Received: from outpost1.zedat.fu-berlin.de ([130.133.4.66])
 by list1.zedat.fu-berlin.de (Exim 4.94)
 for facets-of-complexity@lists.fu-berlin.de with esmtps (TLS1.2)
 tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384
 (envelope-from )
 id 1kVGDL-001FhT-G8; Wed, 21 Oct 2020 17:39:47 +0200
Received: from inpost2.zedat.fu-berlin.de ([130.133.4.69])
 by outpost.zedat.fu-berlin.de (Exim 4.94) with esmtps (TLS1.2)
 tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384
 (envelope-from )
 id 1kVGDJ-001gXe-WA; Wed, 21 Oct 2020 17:39:46 +0200
Received: from ip5f5af206.dynamic.kabel-deutschland.de ([95.90.242.6]
 helo=[192.168.0.2]) by inpost2.zedat.fu-berlin.de (Exim 4.94)
 with esmtpsa (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256
 (envelope-from )
 id 1kVGDJ-003BG5-Kf; Wed, 21 Oct 2020 17:39:45 +0200
From: Ita Brunke 
To: facets-of-complexity@lists.fu-berlin.de
Message-ID: 
Date: Wed, 21 Oct 2020 17:39:46 +0200
User-Agent: Mozilla/5.0 (Windows NT 6.1; Win64; x64; rv:52.0) Gecko/20100101
 Firefox/52.0 SeaMonkey/2.49.5
MIME-Version: 1.0
Content-Type: multipart/alternative;
 boundary="------------A0B3404A94CD29A0FC28780D"
X-Original-Sender: i.brunke@inf.fu-berlin.de
X-Originating-IP: 95.90.242.6
X-ZEDAT-Hint: A
X-purgate: clean
X-purgate-type: clean
X-purgate-ID: 151147::1603294787-000F1E66-369EA45E/0/0
X-Bogosity: Ham, tests=bogofilter, spamicity=0.000009, version=1.2.4
X-Spam-Flag: NO
X-Spam-Status: No, score=-50.0 required=5.0 tests=ALL_TRUSTED,HTML_MESSAGE
X-Spam-Checker-Version: SpamAssassin 3.4.4 on Tuvalu.ZEDAT.FU-Berlin.DE
X-Spam-Level: 
Subject: [Facets-of-complexity] Invitation to Monday Lecture - October 26th
 2020 - online via zoom
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, 21 Oct 2020 15:39:51 -0000

This is a multi-part message in MIME format.
--------------A0B3404A94CD29A0FC28780D
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit

You are cordially invited to our second Monday Lecture since Corona 
crisis stopped our curriculum.
All Monday Lectures and Colloquia of winter term 20/21 will be held 
online via zoom.

You may find valid Invitation for zoom throughout all winter term here:
http://www.facetsofcomplexity.de/monday/WS-2020-21/index.html

Invitation link:
https://tu-berlin.zoom.us/j/69716124232?pwd=dzFlcTFHMmFXRTE5QmZLaEV5N0FRUT09

Second Monday Lecture will be on October 26th 2020 at 14:15 h.

*_Online via_:
Zoom - Invitation*

*_Time_: **Monday, October 26th - 14:15 h*

*_Lecture_: Sophie Spirkl (University of Waterloo)
*

*_Title_: k-coloring graphs with forbidden induced subgraphs*

*_Abstract_:*

A k-coloring of a graph G is a function c that assigns an integer 
between 1 and k to every vertex of G such that c(u) is not equal to c(v) 
for every edge uv of G. Deciding, given a graph G, whether G has a 
k-coloring, is NP-hard for all k at least 3.

In this talk, we will consider what happens when we restrict the input, 
that is: For a graph H and integer k, what is the complexity of deciding 
if a given graph G with no induced subgraph isomorphic to H has a 
k-coloring?

We know the answer for many pairs H and k. Possibly the most interesting 
open cases are those in which H is a path; I will talk about recent 
results and open questions related to this.


--------------A0B3404A94CD29A0FC28780D
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: 7bit


  
    
  
  
    

      
You are cordially invited to our second Monday Lecture since
        Corona crisis stopped our curriculum.

        All Monday Lectures and Colloquia of winter term 20/21 will be
        held online via zoom. 

      

      
You may find valid Invitation for zoom throughout all winter
        term here:

        http://www.facetsofcomplexity.de/monday/WS-2020-21/index.html

      

      
Invitation link:

        https://tu-berlin.zoom.us/j/69716124232?pwd=dzFlcTFHMmFXRTE5QmZLaEV5N0FRUT09

      
 Second Monday Lecture will be on October 26th 2020 at 14:15 h.
        

      

      Online via:

        Zoom - Invitation

      
Time: Monday, October 26th - 14:15 h 

      
Lecture: Sophie Spirkl (University of Waterloo)

        

      
Title: k-coloring graphs with forbidden induced
          subgraphs

      Abstract:

      


      

      
A k-coloring of
        a graph G is a function c that assigns an integer between 1 and
        k to every vertex of G such that c(u) is not equal to c(v) for
        every edge uv of G. Deciding, given a graph G, whether G has a
        k-coloring, is NP-hard for all k at least 3.
        

          
In this talk, we will consider what happens when we
            restrict the input, that is: For a graph H and integer k,
            what is the complexity of deciding if a given graph G with
            no induced subgraph isomorphic to H has a k-coloring?

          
We know the answer for many pairs H and k. Possibly the
            most interesting open cases are those in which H is a path;
            I will talk about recent results and open questions related
            to this.

        

      

    

  


--------------A0B3404A94CD29A0FC28780D--



From itabrunke@zedat.fu-berlin.de Wed Oct 28 16:10:12 2020
Received: from outpost1.zedat.fu-berlin.de ([130.133.4.66])
 by list1.zedat.fu-berlin.de (Exim 4.94)
 for facets-of-complexity@lists.fu-berlin.de with esmtps (TLS1.2)
 tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384
 (envelope-from )
 id 1kXn5X-000G7d-VH; Wed, 28 Oct 2020 16:10:12 +0100
Received: from inpost2.zedat.fu-berlin.de ([130.133.4.69])
 by outpost.zedat.fu-berlin.de (Exim 4.94) with esmtps (TLS1.2)
 tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384
 (envelope-from )
 id 1kXn5X-000FgH-7c; Wed, 28 Oct 2020 16:10:11 +0100
Received: from ip5f5af4be.dynamic.kabel-deutschland.de ([95.90.244.190]
 helo=[192.168.0.2]) by inpost2.zedat.fu-berlin.de (Exim 4.94)
 with esmtpsa (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256
 (envelope-from )
 id 1kXn5W-001JsM-Id; Wed, 28 Oct 2020 16:10:11 +0100
From: Ita Brunke 
To: facets-of-complexity@lists.fu-berlin.de
Message-ID: 
Date: Wed, 28 Oct 2020 16:10:10 +0100
User-Agent: Mozilla/5.0 (Windows NT 6.1; Win64; x64; rv:52.0) Gecko/20100101
 Firefox/52.0 SeaMonkey/2.49.5
MIME-Version: 1.0
Content-Type: multipart/alternative;
 boundary="------------AF05D139A74295C669577A1C"
X-Original-Sender: i.brunke@inf.fu-berlin.de
X-Originating-IP: 95.90.244.190
X-ZEDAT-Hint: A
X-purgate: clean
X-purgate-type: clean
X-purgate-ID: 151147::1603897811-000BAE25-BCEAA500/0/0
X-Bogosity: Ham, tests=bogofilter, spamicity=0.252889, version=1.2.4
X-Spam-Flag: NO
X-Spam-Status: No, score=-50.0 required=5.0 tests=ALL_TRUSTED,HTML_MESSAGE
X-Spam-Checker-Version: SpamAssassin 3.4.4 on Tokelau.ZEDAT.FU-Berlin.DE
X-Spam-Level: 
Subject: [Facets-of-complexity] Invitation and link to Monday Lecture -
 November 2nd 2020 - online via zoom
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, 28 Oct 2020 15:10:12 -0000

This is a multi-part message in MIME format.
--------------AF05D139A74295C669577A1C
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit

You are cordially invited to our next Monday Lecture.
All Monday Lectures and Colloquia of winter term 20/21 will be held 
online via zoom.

You may find valid Invitation for zoom throughout all winter term here:
http://www.facetsofcomplexity.de/monday/WS-2020-21/index.html

Invitation link:
https://tu-berlin.zoom.us/j/69716124232?pwd=dzFlcTFHMmFXRTE5QmZLaEV5N0FRUT09

Monday Lecture will be on November 2nd 2020 at 14:15 h.

*_Online via_:
Zoom - Invitation*

*_Time_: **Monday, November 2nd - 14:15 h*

*_Lecture_: Markus Bläser (Universität Saarbrücken)
*

*_Title_: Irreversibility of tensors of minimal border rank and barriers 
for fast matrix multiplication*

*_Abstract_:*

Determining the asymptotic algebraic complexity of matrix multiplication 
is a central problem in algebraic complexity theory. The best upper 
bounds on the so-called exponent of matrix multiplication if obtained by 
starting with an "efficient" tensor, taking a high power and 
degenerating a matrix multiplication out of it.In the recent years, 
several so-called barrier results have been established. A barrier 
result shows a lower bound on the best upper bound for the exponent of 
matrix multiplication that can be obtained by a certain restriction 
starting with a certain tensor. We prove the following barrier over the 
complex numbers: Starting with a tensor of minimal border rank 
satisfying a certain genericity condition, except for the diagonal 
tensor, it is impossible to prove ω = 2 using arbitrary restrictions. 
This is astonishing since the tensors of minimal border rank look like 
the most natural candidates for designing fast matrix multiplication 
algorithms. We prove this by showing that all of these tensors are 
irreversible, using a structural characterisation of these tensors. 
Joint work with Vladimir Lysikov.

--------------AF05D139A74295C669577A1C
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: 8bit


  
    
  
  
    

      

        
You are cordially invited to our next Monday Lecture. 

          All Monday Lectures and Colloquia of winter term 20/21 will be
          held online via zoom. 

        

        
You may find valid Invitation for zoom throughout all winter
          term here:

          http://www.facetsofcomplexity.de/monday/WS-2020-21/index.html

        

        
Invitation link:

          https://tu-berlin.zoom.us/j/69716124232?pwd=dzFlcTFHMmFXRTE5QmZLaEV5N0FRUT09

        
 Monday Lecture will be on November 2nd 2020 at 14:15 h. 

        

        Online via:

          Zoom - Invitation

        
Time: Monday, November 2nd - 14:15 h 

        
Lecture: Markus Bläser (Universität Saarbrücken)

          

        
Title: Irreversibility of tensors of minimal border
            rank and barriers for fast matrix multiplication

        Abstract:

        


        

        
Determining
          the asymptotic algebraic complexity of matrix multiplication
          is a central problem in algebraic complexity theory. The best
          upper bounds on the so-called exponent of matrix
          multiplication if obtained by starting with an "efficient"
          tensor, taking a high power and degenerating a matrix
          multiplication out of it. In the recent years,
              several so-called barrier results have been established. A
              barrier result shows a lower bound on the best upper bound
              for the exponent of matrix multiplication that can be
              obtained by a certain restriction starting with a certain
              tensor. We prove the following barrier over the complex
              numbers: Starting with a tensor of minimal border rank
              satisfying a certain genericity condition, except for the
              diagonal tensor, it is impossible to prove ω = 2 using
              arbitrary restrictions. This is astonishing since the
              tensors of minimal border rank look like the most natural
              candidates for designing fast matrix multiplication
              algorithms. We prove this by showing that all of these
              tensors are irreversible, using a structural
              characterisation of these tensors. Joint
          work with Vladimir Lysikov.
          
 

        

      

    

  


--------------AF05D139A74295C669577A1C--



From itabrunke@zedat.fu-berlin.de Wed Nov 04 14:36:33 2020
Received: from outpost1.zedat.fu-berlin.de ([130.133.4.66])
 by list1.zedat.fu-berlin.de (Exim 4.94)
 for facets-of-complexity@lists.fu-berlin.de with esmtps (TLS1.2)
 tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384
 (envelope-from )
 id 1kaIxj-001fld-75; Wed, 04 Nov 2020 14:36:33 +0100
Received: from inpost2.zedat.fu-berlin.de ([130.133.4.69])
 by outpost.zedat.fu-berlin.de (Exim 4.94) with esmtps (TLS1.2)
 tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384
 (envelope-from )
 id 1kaIxi-0008ph-A2; Wed, 04 Nov 2020 14:36:30 +0100
Received: from ip5f5af1c4.dynamic.kabel-deutschland.de ([95.90.241.196]
 helo=[192.168.0.2]) by inpost2.zedat.fu-berlin.de (Exim 4.94)
 with esmtpsa (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256
 (envelope-from )
 id 1kaIxi-000Ty1-2m; Wed, 04 Nov 2020 14:36:30 +0100
To: facets-of-complexity@lists.fu-berlin.de
From: Ita Brunke 
Message-ID: 
Date: Wed, 4 Nov 2020 14:36:30 +0100
User-Agent: Mozilla/5.0 (Windows NT 6.1; Win64; x64; rv:52.0) Gecko/20100101
 Firefox/52.0 SeaMonkey/2.49.5
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
X-Original-Sender: i.brunke@inf.fu-berlin.de
X-Originating-IP: 95.90.241.196
X-purgate: clean
X-purgate-type: clean
X-purgate-ID: 151147::1604496991-000DEF25-FEAEDA13/0/0
X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4
X-Spam-Flag: NO
X-Spam-Status: No, score=-50.0 required=5.0 tests=ALL_TRUSTED
X-Spam-Checker-Version: SpamAssassin 3.4.4 on Kiribati.ZEDAT.FU-Berlin.DE
X-Spam-Level: 
Subject: [Facets-of-complexity] No Monday's Lecture or Colloquium - next
 week - Nov. 9th
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, 04 Nov 2020 13:36:33 -0000

Dear all,

there will be no Monday's Lecture or Colloquium next week, Nov. 9th.
Next Monday's Lecture will be Nov. 16th.

All the best,
Ita

-- 
Graduiertenkolleg 'Facets of Complexity'
Koordinatorin: Ita Brunke  Raum 111  Tel.:838-52683
Freie Universität Berlin
Institut für Informatik
Takustr. 9
14195 Berlin (Dahlem)



From itabrunke@zedat.fu-berlin.de Tue Nov 10 16:59:25 2020
Received: from outpost1.zedat.fu-berlin.de ([130.133.4.66])
 by list1.zedat.fu-berlin.de (Exim 4.94)
 for facets-of-complexity@lists.fu-berlin.de with esmtps (TLS1.2)
 tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384
 (envelope-from )
 id 1kcW3I-00420y-VU; Tue, 10 Nov 2020 16:59:25 +0100
Received: from inpost2.zedat.fu-berlin.de ([130.133.4.69])
 by outpost.zedat.fu-berlin.de (Exim 4.94) with esmtps (TLS1.2)
 tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384
 (envelope-from )
 id 1kcW3I-00053E-1I; Tue, 10 Nov 2020 16:59:24 +0100
Received: from ip5f5af417.dynamic.kabel-deutschland.de ([95.90.244.23]
 helo=[192.168.0.2]) by inpost2.zedat.fu-berlin.de (Exim 4.94)
 with esmtpsa (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256
 (envelope-from )
 id 1kcW3H-002Gbw-Np; Tue, 10 Nov 2020 16:59:23 +0100
From: Ita Brunke 
To: facets-of-complexity@lists.fu-berlin.de
Message-ID: 
Date: Tue, 10 Nov 2020 16:59:23 +0100
User-Agent: Mozilla/5.0 (Windows NT 6.1; Win64; x64; rv:52.0) Gecko/20100101
 Firefox/52.0 SeaMonkey/2.49.5
MIME-Version: 1.0
Content-Type: multipart/alternative;
 boundary="------------B211201AE0439BACF98AC723"
X-Original-Sender: i.brunke@inf.fu-berlin.de
X-Originating-IP: 95.90.244.23
X-ZEDAT-Hint: A
X-purgate: clean
X-purgate-type: clean
X-purgate-ID: 151147::1605023964-0005B020-4E35B451/0/0
X-Bogosity: Ham, tests=bogofilter, spamicity=0.000057, version=1.2.4
X-Spam-Flag: NO
X-Spam-Status: No, score=-50.0 required=5.0 tests=ALL_TRUSTED,HTML_MESSAGE
X-Spam-Checker-Version: SpamAssassin 3.4.4 on Kiribati.ZEDAT.FU-Berlin.DE
X-Spam-Level: 
Subject: [Facets-of-complexity] Invitation and link to Monday Lecture -
 November 16th 2020 - online via zoom
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: Tue, 10 Nov 2020 15:59:25 -0000

This is a multi-part message in MIME format.
--------------B211201AE0439BACF98AC723
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit

You are cordially invited to our next Monday Lecture.
All Monday Lectures and Colloquia of winter term 20/21 will be held 
online via zoom.

You may find valid Invitation for zoom throughout all winter term here:
http://www.facetsofcomplexity.de/monday/WS-2020-21/index.html

Invitation link:
https://tu-berlin.zoom.us/j/69716124232?pwd=dzFlcTFHMmFXRTE5QmZLaEV5N0FRUT09

Monday Lecture will be on November 16th 2020 at 14:15 h.

*_Online via_:
Zoom - Invitation*

*_Time_: **Monday, November 16th - 14:15 h*

*_Lecture_: Lisa Sauermann (IAS, Princeton)
*

*_Title_: On the extension complexity of low-dimensional polytopes*

*_Abstract_:*

It is sometimes possible to represent a complicated polytope as a 
projection of a much simpler polytope. To quantify this phenomenon, the 
extension complexity of a polytope P is defined to be the minimum number 
of facets in a (possibly higher-dimensional) polytope from which P can 
be obtained as a (linear) projection. In this talk, we discuss some 
results on the extension complexity of random d-dimensional polytopes 
(obtained as convex hulls of random points on either on the unit sphere 
or in the unit ball), and on the extension complexity of polygons with 
all vertices on a common circle. Joint work with Matthew Kwan and Yufei 
Zhao.

--------------B211201AE0439BACF98AC723
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: 7bit


  

    
  
  
    
You are cordially invited to our next Monday Lecture. 

      All Monday Lectures and Colloquia of winter term 20/21 will be
      held online via zoom. 

    

    
You may find valid Invitation for zoom throughout all winter term
      here:

      http://www.facetsofcomplexity.de/monday/WS-2020-21/index.html

    

    
Invitation link:

      https://tu-berlin.zoom.us/j/69716124232?pwd=dzFlcTFHMmFXRTE5QmZLaEV5N0FRUT09

    
 Monday Lecture will be on November 16th 2020 at 14:15 h. 

    

    Online via:

      Zoom - Invitation

    
Time: Monday, November 16th - 14:15 h 

    
Lecture: Lisa Sauermann (IAS, Princeton)

      

    
Title: On the extension complexity of low-dimensional
        polytopes

    Abstract:

    


    

    It is sometimes possible to represent a complicated polytope as a
    projection of a much simpler polytope. To quantify this phenomenon,
    the extension complexity of a polytope P is defined to be the
    minimum number of facets in a (possibly higher-dimensional) polytope
    from which P can be obtained as a (linear) projection. In this talk,
    we discuss some results on the extension complexity of random
    d-dimensional polytopes (obtained as convex hulls of random points
    on either on the unit sphere or in the unit ball), and on the
    extension complexity of polygons with all vertices on a common
    circle. Joint work with Matthew Kwan and Yufei Zhao.
  


--------------B211201AE0439BACF98AC723--



From itabrunke@zedat.fu-berlin.de Tue Nov 17 17:35:09 2020
Received: from outpost1.zedat.fu-berlin.de ([130.133.4.66])
 by list1.zedat.fu-berlin.de (Exim 4.94)
 for facets-of-complexity@lists.fu-berlin.de with esmtps (TLS1.2)
 tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384
 (envelope-from )
 id 1kf3we-003vwa-RS; Tue, 17 Nov 2020 17:35:04 +0100
Received: from inpost2.zedat.fu-berlin.de ([130.133.4.69])
 by outpost.zedat.fu-berlin.de (Exim 4.94) with esmtps (TLS1.2)
 tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384
 (envelope-from )
 id 1kf3we-001gnm-2t; Tue, 17 Nov 2020 17:35:04 +0100
Received: from ip5f5af1e3.dynamic.kabel-deutschland.de ([95.90.241.227]
 helo=[192.168.0.2]) by inpost2.zedat.fu-berlin.de (Exim 4.94)
 with esmtpsa (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256
 (envelope-from )
 id 1kf3wd-002Pn2-Sb; Tue, 17 Nov 2020 17:35:04 +0100
From: Ita Brunke 
To: facets-of-complexity@lists.fu-berlin.de
Message-ID: 
Date: Tue, 17 Nov 2020 17:35:03 +0100
User-Agent: Mozilla/5.0 (Windows NT 6.1; Win64; x64; rv:52.0) Gecko/20100101
 Firefox/52.0 SeaMonkey/2.49.5
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
X-Original-Sender: i.brunke@inf.fu-berlin.de
X-Originating-IP: 95.90.241.227
X-purgate: clean
X-purgate-type: clean
X-purgate-ID: 151147::1605630904-0008DB70-C60B0273/0/0
X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4
X-Spam-Flag: NO
X-Spam-Status: No, score=-50.0 required=5.0 tests=ALL_TRUSTED
X-Spam-Checker-Version: SpamAssassin 3.4.4 on Tuvalu.ZEDAT.FU-Berlin.DE
X-Spam-Level: 
Subject: [Facets-of-complexity] No Monday's Lecture or Colloquium - next
 week - Nov. 23rd
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: Tue, 17 Nov 2020 16:35:09 -0000

Dear all,

there will be no Monday's Lecture or Colloquium next week, Nov. 23rd.
Next Monday's Lecture will be given the week after, Nov. 30th, by Stefan 
Mengel (CNRS).

Best regards,
Ita

-- 
Graduiertenkolleg 'Facets of Complexity'
Koordinatorin: Ita Brunke  Raum 111  Tel.:838-52683
Freie Universität Berlin
Institut für Informatik
Takustr. 9
14195 Berlin (Dahlem)



From itabrunke@zedat.fu-berlin.de Mon Nov 23 18:31:56 2020
Received: from outpost1.zedat.fu-berlin.de ([130.133.4.66])
 by list1.zedat.fu-berlin.de (Exim 4.94)
 for facets-of-complexity@lists.fu-berlin.de with esmtps (TLS1.2)
 tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384
 (envelope-from )
 id 1khFgt-003IGp-Nr; Mon, 23 Nov 2020 18:31:56 +0100
Received: from inpost2.zedat.fu-berlin.de ([130.133.4.69])
 by outpost.zedat.fu-berlin.de (Exim 4.94) with esmtps (TLS1.2)
 tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384
 (envelope-from )
 id 1khFgs-002BYt-QT; Mon, 23 Nov 2020 18:31:50 +0100
Received: from ip5f5af1d0.dynamic.kabel-deutschland.de ([95.90.241.208]
 helo=[192.168.0.2]) by inpost2.zedat.fu-berlin.de (Exim 4.94)
 with esmtpsa (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256
 (envelope-from )
 id 1khFgs-003nKY-IR; Mon, 23 Nov 2020 18:31:50 +0100
From: Ita Brunke 
To: facets-of-complexity@lists.fu-berlin.de
Message-ID: 
Date: Mon, 23 Nov 2020 18:31:50 +0100
User-Agent: Mozilla/5.0 (Windows NT 6.1; Win64; x64; rv:52.0) Gecko/20100101
 Firefox/52.0 SeaMonkey/2.49.5
MIME-Version: 1.0
Content-Type: multipart/alternative;
 boundary="------------A05D3B73ECAFDE788B55CD50"
X-Original-Sender: i.brunke@inf.fu-berlin.de
X-Originating-IP: 95.90.241.208
X-ZEDAT-Hint: A
X-purgate: clean
X-purgate-type: clean
X-purgate-ID: 151147::1606152711-00072536-D2229AAF/0/0
X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4
X-Spam-Flag: NO
X-Spam-Status: No, score=-50.0 required=5.0 tests=ALL_TRUSTED,HTML_MESSAGE
X-Spam-Checker-Version: SpamAssassin 3.4.4 on Kiribati.ZEDAT.FU-Berlin.DE
X-Spam-Level: 
Subject: [Facets-of-complexity] Invitation and link to Monday Lecture -
 November 30th 2020 - online via zoom
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: Mon, 23 Nov 2020 17:31:56 -0000

This is a multi-part message in MIME format.
--------------A05D3B73ECAFDE788B55CD50
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit

You are cordially invited to our next Monday Lecture.
All Monday Lectures and Colloquia of winter term 2020/21 will be given 
online via zoom.

You may find valid Invitation for zoom throughout all winter term here:
http://www.facetsofcomplexity.de/monday/WS-2020-21/index.html

Invitation link:
https://tu-berlin.zoom.us/j/69716124232?pwd=dzFlcTFHMmFXRTE5QmZLaEV5N0FRUT09

Monday Lecture will be on November 30th 2020 at 14:15 h.

*_Online via_:
Zoom - Invitation*

*_Time_: **Monday, November 30th - 14:15 h*

*_Lecture_: Stefan Mengel (CNRS)
*

*_Title_: A Biased Introduction to Decomposable Negation Normal Form**s*

*_Abstract_:*

Decomposable Negation Normal Forms (DNNF) are a class of Boolean 
circuits first introduced by Darwiche in 2001 in the context of 
artificial intelligence. Since then they have found applications as a 
flexible framework for encoding Boolean functions in other areas of 
computer science like theoretical computer science and database theory. 
In this talk, I will introduce DNNF, discuss some uses and sketch how 
one can show bounds on their size.

--------------A05D3B73ECAFDE788B55CD50
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: 7bit


  

    
  
  
    
You are cordially invited to our next Monday Lecture. 

      All Monday Lectures and Colloquia of winter term 2020/21 will be
      given online via zoom. 

    

    
You may find valid Invitation for zoom throughout all winter term
      here:

      http://www.facetsofcomplexity.de/monday/WS-2020-21/index.html

    

    
Invitation link:

      https://tu-berlin.zoom.us/j/69716124232?pwd=dzFlcTFHMmFXRTE5QmZLaEV5N0FRUT09

    
 Monday Lecture will be on November 30th 2020 at 14:15 h. 

    

    Online via:

      Zoom - Invitation

    
Time: Monday, November 30th - 14:15 h 

    
Lecture: Stefan Mengel (CNRS)

      

    
Title: A Biased Introduction to Decomposable Negation
        Normal Forms

    Abstract:

    


    

    Decomposable Negation Normal Forms (DNNF) are a class of Boolean
    circuits first introduced by Darwiche in 2001 in the context of
    artificial intelligence. Since then they have found applications as
    a flexible framework for encoding Boolean functions in other areas
    of computer science like theoretical computer science and database
    theory. In this talk, I will introduce DNNF, discuss some uses and
    sketch how one can show bounds on their size.

  


--------------A05D3B73ECAFDE788B55CD50--



From itabrunke@zedat.fu-berlin.de Wed Dec 02 18:30:20 2020
Received: from outpost1.zedat.fu-berlin.de ([130.133.4.66])
 by list1.zedat.fu-berlin.de (Exim 4.94)
 for facets-of-complexity@lists.fu-berlin.de with esmtps (TLS1.2)
 tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384
 (envelope-from )
 id 1kkVxH-003xXM-Vz; Wed, 02 Dec 2020 18:30:16 +0100
Received: from inpost2.zedat.fu-berlin.de ([130.133.4.69])
 by outpost.zedat.fu-berlin.de (Exim 4.94) with esmtps (TLS1.2)
 tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384
 (envelope-from )
 id 1kkVxG-001Cda-IP; Wed, 02 Dec 2020 18:30:14 +0100
Received: from ip5f5af16f.dynamic.kabel-deutschland.de ([95.90.241.111]
 helo=[192.168.0.2]) by inpost2.zedat.fu-berlin.de (Exim 4.94)
 with esmtpsa (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256
 (envelope-from )
 id 1kkVxF-000XHL-UB; Wed, 02 Dec 2020 18:30:14 +0100
From: Ita Brunke 
To: facets-of-complexity@lists.fu-berlin.de
Message-ID: <398e5baa-d39e-6f2a-8793-cf672ac704fa@inf.fu-berlin.de>
Date: Wed, 2 Dec 2020 18:30:13 +0100
User-Agent: Mozilla/5.0 (Windows NT 6.1; Win64; x64; rv:52.0) Gecko/20100101
 Firefox/52.0 SeaMonkey/2.49.5
MIME-Version: 1.0
Content-Type: multipart/alternative;
 boundary="------------EA1028161CC319B14347DCEF"
X-Original-Sender: i.brunke@inf.fu-berlin.de
X-Originating-IP: 95.90.241.111
X-ZEDAT-Hint: A
X-purgate: clean
X-purgate-type: clean
X-purgate-ID: 151147::1606930216-00099106-38DE0A3D/0/0
X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4
X-Spam-Flag: NO
X-Spam-Status: No, score=-50.0 required=5.0 tests=ALL_TRUSTED,HTML_MESSAGE
X-Spam-Checker-Version: SpamAssassin 3.4.4 on Tuvalu.ZEDAT.FU-Berlin.DE
X-Spam-Level: 
Subject: [Facets-of-complexity] Invitation and link to Monday Lecture -
 December 7th 2020 - online via zoom
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, 02 Dec 2020 17:30:20 -0000

This is a multi-part message in MIME format.
--------------EA1028161CC319B14347DCEF
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit

You are cordially invited to our next Monday Lecture. Next Monday, there 
will be the hearing of the PhD candidates.

We will have three talks. Talks will be 30 min. 15 min discussions, 15 
min break.
All Monday Lectures and Colloquia of winter term 2020/21 will be given 
online via zoom.

You may find valid Invitation for zoom throughout all winter term here:
http://www.facetsofcomplexity.de/monday/WS-2020-21/index.html

Invitation link:
https://tu-berlin.zoom.us/j/69716124232?pwd=dzFlcTFHMmFXRTE5QmZLaEV5N0FRUT09

Monday Lecture will be on December 7th 2020 at 14:00 h, 15:00, 16:00.

*_Online via_:
Zoom - Invitation*

*_Time_: **Monday, December 7th - 14:00 h*

*_Lecture_: Hussein Houdrouge
*

*_Title_: Subquadratic High-Dimensional Hierarchical Clustering*

*_Abstract_:*

We consider the widely-used Ward's method for computing hierarchical 
clusterings of high-dimensional Euclidean inputs. It is easy to show 
that there is no ecient implementation of these algorithms in high 
dimensional Euclidean space since it implicitly requires to solve the 
closest pair problem, a notoriously dicult problem. However, how fast 
can this algorithm be implemented if we allow approximation? More 
precisely: this algorithm successively merges the clusters that are at 
inducing the least sum-of-square error. We ask whether one could obtain 
a signicant running-time improvement if the algorithm can merge 
-approximate closest clusters (namely, clusters that are at distance 
sumof-square error at most times the distance of the closest clusters). 
We show that one can indeed take advantage of the relaxation and compute 
the approximate hierarchical clustering tree using -approximate nearest 
neighbor queries.
This leads to an algorithm running in time ~O (dn) + n1+O() for 
d-dimensional Euclidean space. We then provide experiments showing that 
this algorithm performs as well as the non-approximate version for 
classic classication tasks while achieving a signicant speed-up.


*_Time_: **Monday, December 7th - 15:00 h*

*_Lecture_: Kemal Rose
*

*_Title_: tba*

*_Abstract_:*

tba

*_Time_: **Monday, December 7th - 16:00 h*

*_Lecture_: Filippos Christodoulou
*

*_Title_: tba*

*_Abstract_:*

tba



--------------EA1028161CC319B14347DCEF
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: 7bit


  
    
  
  
    
You are cordially invited to our next Monday Lecture. Next
      Monday, there will be the hearing of the PhD candidates. 

    

    
We will have three talks. Talks will be 30 min. 15 min
      discussions, 15 min break.

      All Monday Lectures and Colloquia of winter term 2020/21 will be
      given online via zoom. 

    

    
You may find valid Invitation for zoom throughout all winter term
      here:

      http://www.facetsofcomplexity.de/monday/WS-2020-21/index.html

    

    
Invitation link:

      https://tu-berlin.zoom.us/j/69716124232?pwd=dzFlcTFHMmFXRTE5QmZLaEV5N0FRUT09

    
 Monday Lecture will be on December 7th 2020 at 14:00 h, 15:00,
      16:00. 

    

    Online via:

      Zoom - Invitation

    
Time: Monday, December 7th - 14:00 h 

    
Lecture: Hussein Houdrouge 

      

    
Title: Subquadratic High-Dimensional Hierarchical
        Clustering

    Abstract:

    


    

    We consider the widely-used Ward's method for computing hierarchical
    clusterings of high-dimensional Euclidean inputs. It is easy to show
    that there is no ecient implementation of these algorithms in high
    dimensional Euclidean space since it implicitly requires to solve
    the closest pair problem, a notoriously dicult problem. However,
    how fast can this algorithm be implemented if we allow
    approximation? More precisely: this algorithm successively merges
    the clusters that are at inducing the least sum-of-square error. We
    ask whether one could obtain a signicant running-time improvement
    if the algorithm can merge -approximate closest clusters (namely,
    clusters that are at distance sumof-square error at most times the
    distance of the closest clusters). We show that one can indeed take
    advantage of the relaxation and compute the approximate hierarchical
    clustering tree using -approximate nearest neighbor queries.

    This leads to an algorithm running in time ~O (dn) + n1+O() for
    d-dimensional Euclidean space. We then provide experiments showing
    that this algorithm performs as well as the non-approximate version
    for classic classication tasks while achieving a signicant
    speed-up.

    

    

    
Time: Monday, December 7th - 15:00 h 

    
Lecture: Kemal Rose 

      

    
Title: tba

    Abstract:

    


    

    tba

    

    
Time: Monday, December 7th - 16:00 h 

    
Lecture: Filippos Christodoulou 

      

    
Title: tba

    Abstract:

    


    

    tba

    

    

  


--------------EA1028161CC319B14347DCEF--



From itabrunke@zedat.fu-berlin.de Wed Dec 09 18:42:43 2020
Received: from outpost1.zedat.fu-berlin.de ([130.133.4.66])
 by list1.zedat.fu-berlin.de (Exim 4.94)
 for facets-of-complexity@lists.fu-berlin.de with esmtps (TLS1.2)
 tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384
 (envelope-from )
 id 1kn3U9-002xeU-VN; Wed, 09 Dec 2020 18:42:42 +0100
Received: from inpost2.zedat.fu-berlin.de ([130.133.4.69])
 by outpost.zedat.fu-berlin.de (Exim 4.94) with esmtps (TLS1.2)
 tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384
 (envelope-from )
 id 1kn3U8-001a82-CP; Wed, 09 Dec 2020 18:42:40 +0100
Received: from ip5f5af799.dynamic.kabel-deutschland.de ([95.90.247.153]
 helo=[192.168.0.2]) by inpost2.zedat.fu-berlin.de (Exim 4.94)
 with esmtpsa (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256
 (envelope-from )
 id 1kn3U7-002fGZ-R2; Wed, 09 Dec 2020 18:42:40 +0100
From: Ita Brunke 
To: facets-of-complexity@lists.fu-berlin.de, Matthias Beck
 , klimm@tu-berlin.de
Message-ID: <1adc8f01-d92b-e715-66a7-1f36513fb8d1@inf.fu-berlin.de>
Date: Wed, 9 Dec 2020 18:42:40 +0100
User-Agent: Mozilla/5.0 (Windows NT 6.1; Win64; x64; rv:52.0) Gecko/20100101
 Firefox/52.0 SeaMonkey/2.49.5
MIME-Version: 1.0
Content-Type: multipart/alternative;
 boundary="------------FC6008046FE7A8903CE2FB01"
X-Original-Sender: i.brunke@inf.fu-berlin.de
X-Originating-IP: 95.90.247.153
X-ZEDAT-Hint: A
X-purgate: clean
X-purgate-type: clean
X-purgate-ID: 151147::1607535762-0005C92C-916EAF55/0/0
X-Bogosity: Ham, tests=bogofilter, spamicity=0.000003, version=1.2.4
X-Spam-Flag: NO
X-Spam-Status: No, score=-50.0 required=5.0 tests=ALL_TRUSTED,HTML_MESSAGE
X-Spam-Checker-Version: SpamAssassin 3.4.4 on Tokelau.ZEDAT.FU-Berlin.DE
X-Spam-Level: 
Subject: [Facets-of-complexity] Invitation and link to Monday Lecture -
 December 14th 2020 - online via zoom
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, 09 Dec 2020 17:42:43 -0000

This is a multi-part message in MIME format.
--------------FC6008046FE7A8903CE2FB01
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit

You are cordially invited to our next Monday Lecture. Next Monday, there 
will be the hearing of the next PhD candidates.

We will have three talks. Talks will be 30 min. 15 min discussions, 15 
min break.
All Monday Lectures and Colloquia of winter term 2020/21 will be given 
online via zoom.

You may find valid Invitation for zoom throughout all winter term here:
http://www.facetsofcomplexity.de/monday/WS-2020-21/index.html

Invitation link:
https://tu-berlin.zoom.us/j/69716124232?pwd=dzFlcTFHMmFXRTE5QmZLaEV5N0FRUT09

Monday Lecture will be on December 14th 2020 at 14:00 h, 15:00, 16:00.

*_Online via_:
Zoom - Invitation*

*_Time_: **Monday, December 14th - 14:00 h*

*_Lecture_: Matthias Himmelmann
*

*_Title_: Generalized Principal Component Analysis for Algebraic Varieties**
*

*_Abstract_:*

The Buchberger-Möller algorithm is a famous symbolic method for finding 
all polynomials that vanish on a point cloud. It has even been extended 
to noisy samples. However, the resulting variety does not necessarily 
represent the topological or geometric structure of the data well. By 
making use of the Vandermonde matrix, it is possible to find polynomials 
of a prescribed degree vanishing on the samples. As this matrix is 
severely ill-conditioned, modifications are necessary. By making use of 
statistical and algebro-geometric techniques, an algorithm for learning 
a vanishing ideal that represents the data points‘ geometric properties 
well is presented. It is investigated that this method -- among various 
other desirable properties -- is more robust against perturbations in 
the data than the original algorithm.

*_Time_: **Monday, December 14th - 15:00 h*

*_Lecture_: Dante Luber
*

*_Title_: Boundary Complexes for Moduli Spaces of Curves*

*_Abstract_:*

In 2016, Noah Giansiracua showed that a collection of boundary divisors 
in the moduli space of genus-0 n-pointed curves has nonempty 
intersection if and only if all pairwise intersections are nonempty. 
This result is equivalent to showing that the boundary complex 
associated to such a moduli space is a flag complex. Kyla Quillin 
extended Giansiracusa's result to most moduli spaces of genus-g 
n-pointed curves. We give a complete classification of all (g,n) pairs 
for which the boundary complex is a flag complex.

*_Time_: **Monday, December 14th - 16:00 h*

*_Lecture_: Jannik Peters
*

*_Title_: Efficiency and Stability in Euclidean Network Design*

*_Abstract_:*

We study the recently proposed Euclidean Generalized Network Creation 
Game by Bilò et al.[SPAA 2019] and investigate the creation of 
(beta,gamma)-networks, which are in beta-approximate Nash equilibrium 
and have a total cost of at most gamma times the optimal cost. In our 
model we have n agents corresponding to points in Euclidean space create 
costly edges among themselves to optimize their centrality in the 
created network. Our main result is a simple O(n^2)-time algorithm that 
computes a (beta,beta)-network with low beta for any given set of 
points. Along the way, we significantly improve several results from 
Bilò et al. and we asymptotically resolve a conjecture about the Price 
of Anarchy.


--------------FC6008046FE7A8903CE2FB01
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: 8bit


  
    
  
  
    
You are cordially invited to our next Monday Lecture. Next
      Monday, there will be the hearing of the next PhD candidates. 

    

    
We will have three talks. Talks will be 30 min. 15 min
      discussions, 15 min break.

      All Monday Lectures and Colloquia of winter term 2020/21 will be
      given online via zoom. 

    

    
You may find valid Invitation for zoom throughout all winter term
      here:

      http://www.facetsofcomplexity.de/monday/WS-2020-21/index.html

    

    
Invitation link:

      https://tu-berlin.zoom.us/j/69716124232?pwd=dzFlcTFHMmFXRTE5QmZLaEV5N0FRUT09

    
 Monday Lecture will be on December 14th 2020 at 14:00 h, 15:00,
      16:00. 

    

    Online via:

      Zoom - Invitation

    
Time: Monday, December 14th - 14:00 h 

    
Lecture: Matthias Himmelmann 

      

    
Title: Generalized Principal Component Analysis for
        Algebraic Varieties

      

    Abstract:

    


    

    The Buchberger-Möller algorithm is a famous symbolic method for
    finding all polynomials that vanish on a point cloud. It has even
    been extended to noisy samples. However, the resulting variety does
    not necessarily represent the topological or geometric structure of
    the data well. By making use of the Vandermonde matrix, it is
    possible to find polynomials of a prescribed degree vanishing on the
    samples. As this matrix is severely ill-conditioned, modifications
    are necessary. By making use of statistical and algebro-geometric
    techniques, an algorithm for learning a vanishing ideal that
    represents the data points‘ geometric properties well is presented.
    It is investigated that this method -- among various other desirable
    properties -- is more robust against perturbations in the data than
    the original algorithm.

    

    
Time: Monday, December 14th - 15:00 h 

    
Lecture: Dante Luber 

      

    
Title: Boundary Complexes for Moduli Spaces of Curves

    Abstract:

    


    

    In 2016, Noah Giansiracua showed that a collection of boundary
    divisors in the moduli space of genus-0 n-pointed curves has
    nonempty intersection if and only if all pairwise intersections are
    nonempty. This result is equivalent to showing that the boundary
    complex associated to such a moduli space is a flag complex. Kyla
    Quillin extended Giansiracusa's result to most moduli spaces of
    genus-g n-pointed curves. We give a complete classification of all
    (g,n) pairs for which the boundary complex is a flag complex.

    

    
Time: Monday, December 14th - 16:00 h 

    
Lecture: Jannik Peters 

      

    
Title: Efficiency and Stability in Euclidean Network
        Design

    Abstract:

    


    

    We study the recently proposed Euclidean Generalized Network
    Creation Game by Bilò et al.[SPAA 2019] and investigate the creation
    of (beta,gamma)-networks, which are in beta-approximate Nash
    equilibrium and have a total cost of at most gamma times the optimal
    cost. In our model we have n agents corresponding to points in
    Euclidean space create costly edges among themselves to optimize
    their centrality in the created network. Our main result is a simple
    O(n^2)-time algorithm that computes a (beta,beta)-network with low
    beta for any given set of points. Along the way, we significantly
    improve several results from Bilò et al. and we asymptotically
    resolve a conjecture about the Price of Anarchy.

    

  


--------------FC6008046FE7A8903CE2FB01--



From itabrunke@zedat.fu-berlin.de Wed Dec 16 16:08:44 2020
Received: from outpost1.zedat.fu-berlin.de ([130.133.4.66])
 by list1.zedat.fu-berlin.de (Exim 4.94)
 for facets-of-complexity@lists.fu-berlin.de with esmtps (TLS1.2)
 tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384
 (envelope-from )
 id 1kpYPw-002OqM-Ju; Wed, 16 Dec 2020 16:08:41 +0100
Received: from inpost2.zedat.fu-berlin.de ([130.133.4.69])
 by outpost.zedat.fu-berlin.de (Exim 4.94) with esmtps (TLS1.2)
 tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384
 (envelope-from )
 id 1kpYPu-000xt8-W4; Wed, 16 Dec 2020 16:08:39 +0100
Received: from ip5f5af167.dynamic.kabel-deutschland.de ([95.90.241.103]
 helo=[192.168.0.2]) by inpost2.zedat.fu-berlin.de (Exim 4.94)
 with esmtpsa (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256
 (envelope-from )
 id 1kpYPt-002CEv-H5; Wed, 16 Dec 2020 16:08:38 +0100
From: Ita Brunke 
To: facets-of-complexity@lists.fu-berlin.de, Matthias Beck
 , klimm@tu-berlin.de
Message-ID: <6b9c8752-1041-3423-5c11-1efc230f9667@inf.fu-berlin.de>
Date: Wed, 16 Dec 2020 16:08:38 +0100
User-Agent: Mozilla/5.0 (Windows NT 6.1; Win64; x64; rv:52.0) Gecko/20100101
 Firefox/52.0 SeaMonkey/2.49.5
MIME-Version: 1.0
Content-Type: multipart/alternative;
 boundary="------------384EF14B8AABC9003B27361B"
X-Original-Sender: i.brunke@inf.fu-berlin.de
X-Originating-IP: 95.90.241.103
X-ZEDAT-Hint: A
X-purgate: clean
X-purgate-type: clean
X-purgate-ID: 151147::1608131321-000495BA-827DB4BD/0/0
X-Bogosity: Ham, tests=bogofilter, spamicity=0.496112, version=1.2.4
X-Spam-Flag: NO
X-Spam-Status: No, score=-50.0 required=5.0 tests=ALL_TRUSTED,HTML_MESSAGE,
 RCVD_IN_DNSWL_BLOCKED
X-Spam-Checker-Version: SpamAssassin 3.4.4 on Tuvalu.ZEDAT.FU-Berlin.DE
X-Spam-Level: 
Subject: [Facets-of-complexity] Invitation and link to Monday Lecture -
 January 4th 2021 - online via zoom
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, 16 Dec 2020 15:08:44 -0000

This is a multi-part message in MIME format.
--------------384EF14B8AABC9003B27361B
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit

You are cordially invited to our next Monday Lecture - in the New Year. 
Next Monday Lecture, there will be again the hearing of our PhD candidates.

We will have three talks. Talks will be 30 min. 15 min discussions, 15 
min break.
All Monday Lectures and Colloquia of winter term 2020/21 will be given 
online via zoom.

You may find valid Invitation for zoom throughout all winter term here:
http://www.facetsofcomplexity.de/monday/WS-2020-21/index.html

Invitation link:
https://tu-berlin.zoom.us/j/69716124232?pwd=dzFlcTFHMmFXRTE5QmZLaEV5N0FRUT09

Monday Lecture will be on *January 4th 2021* at 14:00 h, 15:00, 16:00.

*_Online via_:
Zoom - Invitation*

*_Time_: **Monday, January 4th - 14:00 h*

*_Lecture_: Sampada Kolhatkar
*

*_Title_: Bivariate chromatic polynomials of mixed graphs
*

*_Abstract_:*

For a graph G=(V,E), the chromatic polynomial X_G counts the number of 
vertex colourings as a function of number of colours. Stanley’s 
reciprocity theorem connects the chromatic polynomial with the 
enumeration of acyclic orientations of G. One way to prove the 
reciprocity result is via the decomposition of chromatic polynomials as 
the sum of order polynomials over all acyclic orientations. From the 
Discrete Geometry perspective, the decomposition is as the sum of 
Ehrhart polynomials through real braid arrangement. Beck, Bogart, and 
Pham proved the analogue of this reciprocity theorem for the strong 
chromatic polynomials for mixed graph. Dohmen–Pönitz–Tittmann provided 
a new two variable generalization of the chromatic polynomial for 
undirected graphs. We extend this bivariate chromatic polynomial to 
mixed graphs, provide a deletion-contraction like formula and study the 
colouring function geometrically via hyperplane arrangements.

*_Time_: **Monday, ***January 4th -* 15:00 h*

*_Lecture_: Alp Müyesser
*

*_Title_: Rainbow factors and trees*

*_Abstract_:*

Generalizing a conjecture of Aharoni, Joos and Kim asked the following 
intriguing question. Let H be a graph on m edges, and let G_i (1<=i<=m) 
be a sequence of m graphs on the common vertex set [n]. What is the 
weakest minimum degree restriction we can impose on each G_i to 
guarantee a rainbow copy of H? Joos and Kim answered this question when 
H is a Hamilton cycle or a perfect matching. We provide an asymptotic 
answer when H is an F-factor, or a spanning tree with maximum degree 
o(n/log n). This is joint work with Richard Montgomery and Yani Pehova.

*_Time_: **Monday, ***January 4th -* 16:00 h*

*_Lecture_: Shubhang Mittal
*

*_Title_: tba*

*_Abstract_:*

tba


--------------384EF14B8AABC9003B27361B
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: 8bit


  
    
  
  
    
You are cordially invited to our next Monday Lecture - in the New
      Year. Next Monday Lecture, there will be again the hearing of our
      PhD candidates. 

    

    
We will have three talks. Talks will be 30 min. 15 min
      discussions, 15 min break.

      All Monday Lectures and Colloquia of winter term 2020/21 will be
      given online via zoom. 

    

    
You may find valid Invitation for zoom throughout all winter term
      here:

      http://www.facetsofcomplexity.de/monday/WS-2020-21/index.html

    

    
Invitation link:

      https://tu-berlin.zoom.us/j/69716124232?pwd=dzFlcTFHMmFXRTE5QmZLaEV5N0FRUT09

    
 Monday Lecture will be on January 4th 2021 at 14:00 h,
      15:00, 16:00. 

    

    Online via:

      Zoom - Invitation

    
Time: Monday, January 4th - 14:00 h 

    
Lecture: Sampada Kolhatkar 

      

    
Title: Bivariate chromatic polynomials of mixed graphs

      

    Abstract:

    


    

    For a graph G=(V,E), the chromatic polynomial X_G counts the number
    of vertex colourings as a function of number of colours. Stanley’s
    reciprocity theorem connects the chromatic polynomial with the
    enumeration of acyclic orientations of G. One way to prove the
    reciprocity result is via the decomposition of chromatic polynomials
    as the sum of order polynomials over all acyclic orientations. From
    the Discrete Geometry perspective, the decomposition is as the sum
    of Ehrhart polynomials through real braid arrangement. Beck, Bogart,
    and Pham proved the analogue of this reciprocity theorem for the
    strong chromatic polynomials for mixed graph.
    Dohmen–Pönitz–Tittmann provided a new two variable generalization
    of the chromatic polynomial for undirected graphs. We extend this
    bivariate chromatic polynomial to mixed graphs, provide a
    deletion-contraction like formula and study the colouring function
    geometrically via hyperplane arrangements.

    

    
Time: Monday, January 4th -
        15:00 h 

    
Lecture: Alp Müyesser 

      

    
Title: Rainbow factors and trees

    Abstract:

    


    

    Generalizing a conjecture of Aharoni, Joos and Kim asked the
    following intriguing question. Let H be a graph on m edges, and let
    G_i (1<=i<=m) be a sequence of m graphs on the common vertex
    set [n]. What is the weakest minimum degree restriction we can
    impose on each G_i to guarantee a rainbow copy of H? Joos and Kim
    answered this question when H is a Hamilton cycle or a perfect
    matching. We provide an asymptotic answer when H is an F-factor, or
    a spanning tree with maximum degree o(n/log n). This is joint work
    with Richard Montgomery and Yani Pehova.

    

    
Time: Monday, January 4th -
        16:00 h 

    
Lecture: Shubhang Mittal 

      

    
Title: tba

    Abstract:

    


    

    tba

    

  


--------------384EF14B8AABC9003B27361B--