From i.brunke@inf.fu-berlin.de Thu Jan 10 14:01:15 2019 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 <1ghZxT-003ZOV-0R>; Thu, 10 Jan 2019 14:01:15 +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 <1ghZxS-000mAS-UD>; Thu, 10 Jan 2019 14:01:14 +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:AES128-SHA:128) (envelope-from ) id <1ghZxS-003EtB-NE>; Thu, 10 Jan 2019 14:01:14 +0100 From: Ita Brunke To: facets-of-complexity@lists.fu-berlin.de Message-ID: Date: Thu, 10 Jan 2019 14:01:14 +0100 User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:60.0) Gecko/20100101 Thunderbird/60.3.2 MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="------------A613DC86E2A4D1F5C56584B8" 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::1547125275-0003A0C8-945C47CC/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.183195, 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.2 on Tokelau.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Invitation to Monday Lecture & Colloquium - January 14th 2019 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, 10 Jan 2019 13:01:15 -0000 This is a multi-part message in MIME format. --------------A613DC86E2A4D1F5C56584B8 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 14th 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, January 14th - 14:15 h* *_Lecture_: Penny Haxell (University**of Waterloo)* *_Title_: Algorithms for independent transversals vs. small dominating sets * *_Abstract_:* An independent transversal (IT) in a vertex-partitioned graph G is an independent set in G consisting of one vertex in each partition class. There are several known criteria that guarantee the existence of an IT, of the following general form: the graph G has an IT unless the subgraph GS of G, induced by the union of some subset S of vertex classes, has a small dominating set. These criteria have been used over the years to solve many combinatorial problems. The known proofs of these IT theorems do not give efficient algorithms for actually finding an IT or a subset S of classes such that GS has a small dominating set. Here we present appropriate weakenings of such results that do have effective proofs. These result in algorithmic versions of many of the original applications of IT theorems. We will discuss a few of these here, including hitting sets for maximum cliques, circular edge colouring of bridgeless cubic graphs, and hypergraph matching problems. _*Coffee & Tea Break*_ *Room 134* *_Time_: **Monday, ***January 14th* - 16:00 h s.t.* *_Colloquium_: Carlos Amendola (Technische Universität München**)* *_Title_: Max-Linear Graphical Models via Tropical Geometry * *_Abstract_:* Motivated by extreme value theory, max-linear graphical models have been recently introduced and studied as an alternative to the classical Gaussian or discrete distributions used in graphical modeling. We present max-linear models naturally in the framework of tropical geometry. This perspective allows us to shed light on some known results and to prove others with algebraic techniques. In particular, we rephrase parameter estimation for max-linear models in terms of cones in the tropical eigenspace fan. This is joint work with Claudia Klüppelberg, Steffen Lauritzen and Ngoc Tran. --------------A613DC86E2A4D1F5C56584B8 Content-Type: text/html; charset=utf-8 Content-Transfer-Encoding: 8bit

You are cordially invited to our next Monday Lecture & Colloquium on January 14th 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, January 14th - 14:15 h

Lecture: Penny Haxell (University of Waterloo)

Title: Algorithms for independent transversals vs. small dominating sets

Abstract:

An independent transversal (IT) in a vertex-partitioned graph G is an independent set in G consisting of one vertex in each partition class. There are several known criteria that guarantee the existence of an IT, of the following general form: the graph G has an IT unless the subgraph GS of G, induced by the union of some subset S of vertex classes, has a small dominating set. These criteria have been used over the years to solve many combinatorial problems. The known proofs of these IT theorems do not give efficient algorithms for actually finding an IT or a subset S of classes such that GS has a small dominating set. Here we present appropriate weakenings of such results that do have effective proofs. These result in algorithmic versions of many of the original applications of IT theorems. We will discuss a few of these here, including hitting sets for maximum cliques, circular edge colouring of bridgeless cubic graphs, and hypergraph matching problems.


Coffee & Tea Break
Room 134

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

Colloquium: Carlos Amendola (Technische Universität München)

Title: Max-Linear Graphical Models via Tropical Geometry

Abstract:
Motivated by extreme value theory, max-linear graphical models have been recently introduced and studied as an alternative to the classical Gaussian or discrete distributions used in graphical modeling. We present max-linear models naturally in the framework of tropical geometry. This perspective allows us to shed light on some known results and to prove others with algebraic techniques. In particular, we rephrase parameter estimation for max-linear models in terms of cones in the tropical eigenspace fan. This is joint work with Claudia Klüppelberg, Steffen Lauritzen and Ngoc Tran. --------------A613DC86E2A4D1F5C56584B8-- From i.brunke@inf.fu-berlin.de Fri Jan 18 16:50:31 2019 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 <1gkWPe-0038st-GW>; Fri, 18 Jan 2019 16:50:30 +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 <1gkWPe-0005f7-E5>; Fri, 18 Jan 2019 16:50:30 +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:AES128-SHA:128) (envelope-from ) id <1gkWPe-002NNs-8h>; Fri, 18 Jan 2019 16:50:30 +0100 From: Ita Brunke To: facets-of-complexity@lists.fu-berlin.de Message-ID: Date: Fri, 18 Jan 2019 16:50:30 +0100 User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:60.0) Gecko/20100101 Thunderbird/60.3.2 MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="------------A2691DB552492A7944CFA1F7" 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::1547826630-00035AB4-07070826/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.000132, version=1.2.4 X-Spam-Flag: NO X-Spam-Status: No, score=-48.8 required=5.0 tests=ALL_TRUSTED,HTML_MESSAGE, HTML_OBFUSCATE_10_20 X-Spam-Checker-Version: SpamAssassin 3.4.2 on Tokelau.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Invitation to Monday Lecture & Colloquium - January 21st 2019 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, 18 Jan 2019 15:50:31 -0000 This is a multi-part message in MIME format. --------------A2691DB552492A7944CFA1F7 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 21st at 14:15 h & 16:00 h at TU Berlin. *_Location_**: ** * *Room MA 041 - Ground Floor* Technische Universität Berlin Straße des 17. Juni 136 10623 Berlin *_Time_: **Monday, January 21st - 14:15 h* *_Lecture_: Maria Bras Amorós (Universitat Rovira i Virgili Tarragona**)* *_Title_: On numerical semigroups * *_Abstract_:* A numerical semigroup is a subset of the positive integers (*N*) together with 0, closed under addition, and with a finite complement in *N*∪{0}. The number of gaps is its genus. Numerical semigroups arise in algebraic geometry, coding theory, privacy models, and in musical analysis. It has been shown that the sequence counting the number of semigroups of each given genus /g/, denoted (/n_g /)_/g/≥ _0 , has a Fibonacci-like asymptotic behavior. It is still not proved that, for each /g/, /n//_g /_+2 ≥ /n//_g /_+1 + /n_g / or, even more simple, /n/_/g/+1 ≥ /n_g /. We will explain some classical problems on numerical semigroups as well as some of their applications to other fields and we will explain the approach of counting semigroups by means of trees. _*Coffee & Tea Break*_*:* *R**oom MA 316 - Third Floor***[British Reading]* * *_Time_: **Monday, ***January 21st* - 16:00 h s.t.* *_Colloquium_: Torsten Mütze (Technische Universität Berlin**)* *_Title_: On symmetric chains and Hamilton cycles * *_Abstract_:* The /n/-cube is the poset obtained by ordering all subsets of {1,2,...,/n/} by inclusion. A symmetric chain is a sequence of subsets /A_k /⊆/A/_/k/+1 ⊆…⊆/A_n-k / with |/A_i /|=/i/ for all /i=k/,…,/n-k/, and a symmetric chain decomposition, or SCD for short, of the /n/-cube is a partition of all its elements into symmetric chains. There are several known descriptions of SCDs in the/n/-cube for any /n/≥1, going back to works by De Bruijn, Aigner, Kleitman and several others. All those constructions, however, yield the very same SCD. In this talk I will present several new constructions of SCDs in the /n/-cube. Specifically, we construct five pairwise edge-disjoint SCDs in the /n/-cube for all /n/≥90, and four pairwise orthogonal SCDs for all /n/≥60, where orthogonality is a slightly stronger requirement than edge-disjointness. Specifically, two SCDs are called orthogonal if any two chains intersect in at most a single element, except the two longest chains, which may only intersect in the unique minimal and maximal element (the empty set and the full set). This improves the previous best lower bound of three orthogonal SCDs due to Spink, and is another step towards an old problem of Shearer and Kleitman from the 1970s, who conjectured that the /n/-cube has ⌊/n//2⌋+1 pairwise orthogonal SCDs. We also use our constructions to prove some new results on the central levels problem, a far-ranging generalization of the well-known middle two levels conjecture (now theorem), on Hamilton cycles in subgraphs of the (2/n/+1)-cube induced by an even number of levels around the middle. Specifically, we prove that there is a Hamilton cycle through the middle four levels of the (2/n/+1)-cube, and a cycle factor through any even number of levels around the middle of the (2/n/+1)-cube. This talk is based on two papers, jointly with Sven Jäger, Petr Gregor, Joe Sawada, and Kaja Wille (ICALP 2018), and with Karl Däubel, Sven Jäger, and Manfred Scheucher, respectively. --------------A2691DB552492A7944CFA1F7 Content-Type: text/html; charset=utf-8 Content-Transfer-Encoding: 8bit

You are cordially invited to our next Monday Lecture & Colloquium on January 21st at 14:15 h & 16:00 h at TU Berlin.

Location:

Room MA 041 - Ground Floor
Technische Universität Berlin
Straße des 17. Juni 136
10623 Berlin 

Time: Monday, January 21st - 14:15 h

Lecture: Maria Bras Amorós (Universitat Rovira i Virgili Tarragona)

Title: On numerical semigroups

Abstract:

A numerical semigroup is a subset of the positive integers (N) together with 0, closed under addition, and with a finite complement in N∪{0}.

The number of gaps is its genus. Numerical semigroups arise in algebraic geometry, coding theory, privacy models, and in musical analysis. It has been shown that the sequence counting the number of semigroups of each given genus g, denoted (ng)g≥0, has a Fibonacci-like asymptotic behavior. It is still not proved that, for each g, ng+2 ≥ ng+1 + ng or, even more simple, ng+1 ≥ ng.

We will explain some classical problems on numerical semigroups as well as some of their applications to other fields and we will explain the approach of counting semigroups by means of trees.


Coffee & Tea Break :

Room MA 316 - Third Floor [British Reading]


Time: Monday, January 21st - 16:00 h s.t.

Colloquium: Torsten Mütze (Technische Universität Berlin)

Title: On symmetric chains and Hamilton cycles

Abstract:
The n-cube is the poset obtained by ordering all subsets of {1,2,...,n} by inclusion. A symmetric chain is a sequence of subsets Ak⊆Ak+1⊆…⊆An-k with |Ai|=i for all i=k,…,n-k, and a symmetric chain decomposition, or SCD for short, of the n-cube is a partition of all its elements into symmetric chains. There are several known descriptions of SCDs in the n-cube for any n≥1, going back to works by De Bruijn, Aigner, Kleitman and several others. All those constructions, however, yield the very same SCD.

In this talk I will present several new constructions of SCDs in the n-cube. Specifically, we construct five pairwise edge-disjoint SCDs in the n-cube for all n≥90, and four pairwise orthogonal SCDs for all n≥60, where orthogonality is a slightly stronger requirement than edge-disjointness. Specifically, two SCDs are called orthogonal if any two chains intersect in at most a single element, except the two longest chains, which may only intersect in the unique minimal and maximal element (the empty set and the full set). This improves the previous best lower bound of three orthogonal SCDs due to Spink, and is another step towards an old problem of Shearer and Kleitman from the 1970s, who conjectured that the n-cube has ⌊n/2⌋+1 pairwise orthogonal SCDs.

We also use our constructions to prove some new results on the central levels problem, a far-ranging generalization of the well-known middle two levels conjecture (now theorem), on Hamilton cycles in subgraphs of the (2n+1)-cube induced by an even number of levels around the middle. Specifically, we prove that there is a Hamilton cycle through the middle four levels of the (2n+1)-cube, and a cycle factor through any even number of levels around the middle of the (2n+1)-cube.

This talk is based on two papers, jointly with Sven Jäger, Petr Gregor, Joe Sawada, and Kaja Wille (ICALP 2018), and with Karl Däubel, Sven Jäger, and Manfred Scheucher, respectively.

--------------A2691DB552492A7944CFA1F7-- From itabrunke@zedat.fu-berlin.de Fri Jan 25 13:35:02 2019 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 <1gn0hK-000fDK-Ji>; Fri, 25 Jan 2019 13:35:02 +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 <1gn0hK-001JSn-HH>; Fri, 25 Jan 2019 13:35:02 +0100 Received: from webmail1.zedat.fu-berlin.de ([130.133.4.91] helo=webmail.zedat.fu-berlin.de) by inpost2.zedat.fu-berlin.de (Exim 4.85) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLSv1.2:DHE-RSA-AES128-GCM-SHA256:128) (envelope-from ) id <1gn0hK-001zEA-8z>; Fri, 25 Jan 2019 13:35:02 +0100 Received: from 95.91.209.108 (ZEDAT-Webmail authenticated user itabrunke) by webmail.zedat.fu-berlin.de with HTTP; Fri, 25 Jan 2019 13:35:02 +0100 Message-ID: <53027.95.91.209.108.1548419702.webmail@webmail.zedat.fu-berlin.de> Date: Fri, 25 Jan 2019 13:35:02 +0100 From: "Ita Brunke" To: facets-of-complexity@lists.fu-berlin.de User-Agent: ZEDAT-Webmail MIME-Version: 1.0 Content-Type: text/plain;charset=utf-8 Content-Transfer-Encoding: 8bit X-Originating-IP: 130.133.4.91 X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1548419702-000C5AF8-F145EBD8/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.2 on Niue.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Invitation to Monday Lecture & Colloquium - January 28th 2019 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, 25 Jan 2019 12:35:03 -0000 You are cordially invited to our next Monday Lecture & Colloquium on January 28th at 14:15 h & 16:00 h at TU Berlin. Location: Room MA 041 - Ground Floor Technische Universität Berlin Straße des 17. Juni 136 10623 Berlin Time: Monday, January 28th - 14:15 h Lecture: Peter Gritzmann (Technische Universität München) Title: On dynamic discrete tomography: Constrained flow and multi assignment problemsfor plasma particle tracking Abstract: The talk deals with the problem of reconstructing the paths of a set of points over time, where, at each of a finite set of moments in time the current positions of the points in space are only accessible through a small number of their line X-rays. Such problems originate from the demand of particle tracking in plasma physics and can be viewed as constrained version of min-cost-flow and multi assignment problems. (Joint work with A. Alpers) Coffee & Tea Break : Room MA 316 - Third Floor [British Reading] Time: Monday, January 28th - 16:00 h s.t. Colloquium: Fei Xue (Technische Universität Berlin) Title: On successive minima-type inequalities for the polar of a convex body Abstract: The second theorem of Minkowski on successive minima provides optimal upper and lower bounds on the volume of a symmetric convex body in terms of its successive minima. Motivated by conjectures of Mahler and Makai Jr., we study bounds on the volume of a convex body in terms of the successive minima of its polar body. In this talk, we will show the lower bound in the planar case, and the upper bound in the general case. This talk is based on joint work with Martin Henk. From rolf.niedermeier@tu-berlin.de Tue Jan 29 20:08:55 2019 Received: from relay1.zedat.fu-berlin.de ([130.133.4.67]) 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 <1goYkh-003IoX-5J>; Tue, 29 Jan 2019 20:08:55 +0100 Received: from exchange.tu-berlin.de ([130.149.7.70]) by relay1.zedat.fu-berlin.de (Exim 4.85) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLSv1.2:DHE-RSA-AES256-GCM-SHA384:256) (envelope-from ) id <1goYkh-000ONb-2T>; Tue, 29 Jan 2019 20:08:55 +0100 Received: from SPMA-04.tubit.win.tu-berlin.de (localhost.localdomain [127.0.0.1]) by localhost (Email Security Appliance) with SMTP id C37299725F9_C50A4C5B for ; Tue, 29 Jan 2019 19:08:53 +0000 (GMT) Received: from exchange.tu-berlin.de (exchange.tu-berlin.de [130.149.7.70]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-SHA384 (256/256 bits)) (Client CN "exchange.tu-berlin.de", Issuer "DFN-Verein Global Issuing CA" (not verified)) by SPMA-04.tubit.win.tu-berlin.de (Sophos Email Appliance) with ESMTPS id 824879700CE_C50A4C5F for ; Tue, 29 Jan 2019 19:08:53 +0000 (GMT) Received: from [130.149.208.219] (130.149.208.219) by EX-MBX-04.tubit.win.tu-berlin.de (172.26.35.174) with Microsoft SMTP Server (TLS) id 15.0.1395.4; Tue, 29 Jan 2019 20:08:48 +0100 To: CC: Christlinde Thielcke , From: Rolf Niedermeier Date: Tue, 29 Jan 2019 20:08:48 +0100 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101 Thunderbird/60.4.0 MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Language: en-GB Content-Transfer-Encoding: 8bit X-ClientProxiedBy: EX-MBX05.tubit.win.tu-berlin.de (172.26.35.175) To EX-MBX-04.tubit.win.tu-berlin.de (172.26.35.174) X-PMWin-Version: 4.0.1, Antivirus-Engine: 3.73.0, Antivirus-Data: 5.59 X-PureMessage: [Scanned] Message-ID: <6933b6ac517f4283a341e1f2e0912a2e@EX-MBX-04.tubit.win.tu-berlin.de> X-SASI-RCODE: 200 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=tu-berlin.de; h=to:cc:from:subject:date:mime-version:content-type:content-transfer-encoding:message-id; s=dkim-tub; bh=JeLI+dxiHGq0d1HUqqEmzs2o588M1aZ3gMzK23y4Igc=; b=Gj61mM/Q/4qnsYVLvZffk5Ku8cesR2pAOe+e1FSQXTUVKTYjSdLce0ORjtubNyTjhgeZliI358xVfGQ2g81l6SZfypvqzlJrJrPLPXg+rC27/NPHDuOhFy0yjiQzBf2KhKxjmSy73ude4ZIuqVNj8i4QU2UnqtD+ksWKz3jwu58= X-Originating-IP: 130.149.7.70 X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1548788935-0003A427-1C0665DD/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.000092, version=1.2.4 X-Spam-Flag: NO X-Spam-Status: No, score=-0.3 required=5.0 tests=DKIM_SIGNED,DKIM_VALID, DKIM_VALID_AU,DKIM_VALID_EF,FORGED_MUA_MOZILLA,RCVD_IN_DNSWL_MED, SPF_NEUTRAL,URIBL_BLOCKED X-Spam-Checker-Version: SpamAssassin 3.4.2 on Niue.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] STACS 2019 conference 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: Tue, 29 Jan 2019 19:08:55 -0000 Dear Facets members, we invite you to participate in the subsequent conference held at TU Berlin, math building. If you want to take place in the full program (including a conference dinner in Aquarium Berlin), we ask you to fully register (and pay). If you just want to enjoy some of the talks, then you are free to participate; if you send your name and affiliation to our secretary Christlinde Thielcke (cc'ed), then we'll prepare a name tag for you. Best regards, Rolf Niedermeier www.akt.tu-berlin.de ======================================================================== STACS 2019 36th International Symposium on Theoretical Aspects of Computer Science March 13—16, 2019, TU Berlin, Berlin, Germany ======================================================================== The STACS deadline for early registration ends soon: February 5, 2019. Registration through https://stacs2019.akt.tu-berlin.de/ The scientific program consists of three invited talks * Leslie Ann Goldberg (Oxford): "Computational Complexity and Partition Functions" * Anca Muscholl (Bordeaux): "The Many Facets of String Transducers" * Petra Mutzel (Dortmund): "Algorithmic Data Analysis" and two invited tutorials * Karl Bringmann (Saarbruecken): "Fine-Grained Complexity Theory" * Tobias Friedrich (Potsdam): "Network Science". Moreover, the scientific program comprises 54 contributed papers (selected from 260 submitted papers). The program will start on March 13, 01:00 pm, with the two tutorials and it will end on March 16 around noon. More information and details concerning program arrangements can be found on the above-mentioned web page. From itabrunke@zedat.fu-berlin.de Fri Feb 01 19:05:42 2019 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 <1gpdC9-002qKD-Q0>; Fri, 01 Feb 2019 19:05:42 +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 <1gpdC9-00184M-Nd>; Fri, 01 Feb 2019 19:05:41 +0100 Received: from webmail1.zedat.fu-berlin.de ([130.133.4.91] helo=webmail.zedat.fu-berlin.de) by inpost2.zedat.fu-berlin.de (Exim 4.85) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLSv1.2:DHE-RSA-AES128-GCM-SHA256:128) (envelope-from ) id <1gpdC9-000u6T-Ht>; Fri, 01 Feb 2019 19:05:41 +0100 Received: from 95.91.242.189 (ZEDAT-Webmail authenticated user itabrunke) by webmail.zedat.fu-berlin.de with HTTP; Fri, 1 Feb 2019 19:05:41 +0100 Message-ID: <28452.95.91.242.189.1549044341.webmail@webmail.zedat.fu-berlin.de> Date: Fri, 1 Feb 2019 19:05:41 +0100 From: "Ita Brunke" To: facets-of-complexity@lists.fu-berlin.de User-Agent: ZEDAT-Webmail MIME-Version: 1.0 Content-Type: text/plain;charset=utf-8 Content-Transfer-Encoding: 8bit X-Originating-IP: 130.133.4.91 X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1549044341-00023A99-DCE252CD/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.2 on Kiribati.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Invitation to Monday Lecture & Colloquium - February 4th 2019 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, 01 Feb 2019 18:05:42 -0000 You are cordially invited to our next Monday Lecture & Colloquium on February 4th 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 4th - 14:15 h Lecture: Karim Adiprasito (Hebrew University of Jerusalem) Title: Triangulated manifolds, Lefschetz conjectures and the revenge of marriages Abstract: Stanley gave us necessary conditions that f-vectors of simplicial polytopes must satisfy by relating the problem to the hard Lefschetz theorem in algebraic geometry, an insurmountably deep and intimidating theorem in algebraic geometry. McMullen conjectured that these conditions are necessary in general, posing before us the problem of proving the hard Lefschetz theorem beyond what algebraic geometers would dream of. I will talk about the revenge of combinatorics, and in particular discuss how Hall's marriage theorem (or rather, one of its proofs) provides a way to this deep algebraic conjecture. Based on arxiv:1812.10454 Coffee & Tea Break: Room 134 Time: Monday, February 4th - 16:00 h s.t. Colloquium: Patrick Morris (Freie Universität Berlin) Title: Clique tilings in randomly perturbed graphs Abstract: A major theme in both extremal and probabilistic combinatorics is to find the appearance thresholds for certain spanning structures. Classical examples of such spanning structures include perfect matchings, Hamilton cycles and H-tilings, where we look for vertex disjoint copies of H covering all the vertices of some host graph G. In this talk we will focus on H-tilings in the case that H is a clique, a natural generalisation of a perfect matching. On the one hand there is the extremal question, how large does the minimum degree of an n-vertex graph G have to be to guarantee the existence of a clique factor in G? On the other hand, there is the probabilistic question. How large does p need to be to almost surely ensure the appearance of a clique factor in the Erdős-Rényi random graph G(n,p)? Optimal answers to these questions were given in two famous papers. The extremal question was answered by Hajnal and Szemerédi in 1970 and the probabilistic question by Johansson, Kahn and Vu in 2008. In this talk we bridge the gap between these two results by approaching the following question which contains the previous questions as special cases. Given an arbitrary graph of some fixed minimum degree, how many random edges need to be added on the same set of vertices to ensure the existence of a clique tiling? We give optimal answers to this question in all cases. Such results are part of a recent research trend studying properties of what is known as the randomly perturbed graph model, introduced by Bohman, Frieze and Martin in 2003. This is joint work with Jie Han and Andrew Treglown. From i.brunke@inf.fu-berlin.de Wed Feb 06 17:57:23 2019 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 <1grQVn-000T1t-Fk>; Wed, 06 Feb 2019 17:57:23 +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 <1grQVn-002g5L-Dc>; Wed, 06 Feb 2019 17:57:23 +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:AES128-SHA:128) (envelope-from ) id <1grQVn-001t0C-7s>; Wed, 06 Feb 2019 17:57:23 +0100 From: Ita Brunke To: facets-of-complexity@lists.fu-berlin.de Message-ID: <8b5d28a4-2c97-4256-4cfb-c4ef27eb1986@inf.fu-berlin.de> Date: Wed, 6 Feb 2019 17:57:23 +0100 User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:60.0) Gecko/20100101 Thunderbird/60.5.0 MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="------------7A8DED23764FBEF5A501C5C9" 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::1549472243-0008B614-2F13593D/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.2 on Palau.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Invitation to Monday Lecture & Colloquium - February 11th 2019 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, 06 Feb 2019 16:57:24 -0000 This is a multi-part message in MIME format. --------------7A8DED23764FBEF5A501C5C9 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 11th 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 11th - 14:15 h* *_Lecture_: Sergio Cabello (University**of Ljubljana)* *_Title_: Computational geometry, optimization and Shapley values * *_Abstract_:* I will discuss three unrelated sets of results combining geometry and algorithms. First we will see classes of graphs defined using the intersection of geometric objects in the plane, and discuss classical optimization problems for them. Then we will consider approximation algorithms for the potato peeling problem: find a maximum-area convex body inside a given polygon. The problem amounts to finding a maximum clique in the visibility graph of random samples of points inside the polygon, and results from stochastic geometry are used to bound the size of the samples. Finally, we will discuss the efficient computation of Shapley values for coalitional games defined by the area of usual geometric objects, such as the convex hull or the minimum axis-parallel bounding box. _*Coffee & Tea Break*_*:* *Room 134* *_Time_: **Monday, **February 11th**- 16:00 h s.t.* *_Colloquium_: Matías Bender (Sorbonne Université Paris**)* *_Title_: Solving sparse polynomial systems using Gröbner basis * *_Abstract_:* Solving systems of polynomial equations is one of the oldest and most important problems in computational mathematics and has many applications in several domains of science and engineering. It is an intrinsically hard problem with complexity at least single exponential in the number of variables. However, in most of the cases, the polynomial systems coming from applications have some kind of structure. For example, several problems in computer-aided design, robotics, computer vision, molecular biology and kinematics involve polynomial systems that are sparse that is, only a few monomials have non-zero coefficients. We focus on exploiting the sparsity of the Newton polytopes of the polynomials to solve the systems faster than the worst case estimates. In this talk, I will present a Gröbner basis approach to solve sparse 0-dimensional systems whose input polynomials have different Newton polytopes. Under regularity assumptions, we can have an explicit combinatorial bound for the complexity of the algorithm. This is joint work with Jean-Charles Faugère and Elias Tsigaridas. --------------7A8DED23764FBEF5A501C5C9 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 11th 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 11th - 14:15 h

Lecture: Sergio Cabello (University of Ljubljana)

Title: Computational geometry, optimization and Shapley values

Abstract:

I will discuss three unrelated sets of results combining geometry and algorithms. First we will see classes of graphs defined using the intersection of geometric objects in the plane, and discuss classical optimization problems for them. Then we will consider approximation algorithms for the potato peeling problem: find a maximum-area convex body inside a given polygon. The problem amounts to finding a maximum clique in the visibility graph of random samples of points inside the polygon, and results from stochastic geometry are used to bound the size of the samples. Finally, we will discuss the efficient computation of Shapley values for coalitional games defined by the area of usual geometric objects, such as the convex hull or the minimum axis-parallel bounding box.


Coffee & Tea Break:
Room 134

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

Colloquium: Matías Bender (Sorbonne Université Paris)

Title: Solving sparse polynomial systems using Gröbner basis

Abstract:
Solving systems of polynomial equations is one of the oldest and most important problems in computational mathematics and has many applications in several domains of science and engineering. It is an intrinsically hard problem with complexity at least single exponential in the number of variables. However, in most of the cases, the polynomial systems coming from applications have some kind of structure. For example, several problems in computer-aided design, robotics, computer vision, molecular biology and kinematics involve polynomial systems that are sparse that is, only a few monomials have non-zero coefficients.
We focus on exploiting the sparsity of the Newton polytopes of the polynomials to solve the systems faster than the worst case estimates. In this talk, I will present a Gröbner basis approach to solve sparse 0-dimensional systems whose input polynomials have different Newton polytopes. Under regularity assumptions, we can have an explicit combinatorial bound for the complexity of the algorithm.
This is joint work with Jean-Charles Faugère and Elias Tsigaridas. --------------7A8DED23764FBEF5A501C5C9--