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--