From rote@zedat.fu-berlin.de Mon Jan 08 13:10:45 2024 Received: from outpost1.zedat.fu-berlin.de ([130.133.4.66]) by list1.zedat.fu-berlin.de (Exim 4.95) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLS1.3) tls TLS_AES_256_GCM_SHA384 (envelope-from ) id 1rMoSq-003RSL-PJ; Mon, 08 Jan 2024 13:10:44 +0100 Received: from inpost2.zedat.fu-berlin.de ([130.133.4.69]) by outpost.zedat.fu-berlin.de (Exim 4.95) with esmtps (TLS1.3) tls TLS_AES_256_GCM_SHA384 (envelope-from ) id 1rMoSq-0018rL-Lc; Mon, 08 Jan 2024 13:10:44 +0100 Received: from strecke.imp.fu-berlin.de ([160.45.40.209]) by inpost2.zedat.fu-berlin.de (Exim 4.95) with esmtpsa (TLS1.3) tls TLS_AES_128_GCM_SHA256 (envelope-from ) id 1rMoSq-0001t4-G7; Mon, 08 Jan 2024 13:10:44 +0100 Message-ID: <54d2fbdb-2a12-4423-8b05-3386e7f1ed51@inf.fu-berlin.de> Date: Mon, 8 Jan 2024 13:10:50 +0100 MIME-Version: 1.0 User-Agent: Mozilla Thunderbird From: =?UTF-8?Q?G=C3=BCnter_Rote?= To: facets-of-complexity@lists.fu-berlin.de References: <3f3d536a-1120-0bb9-b2a0-a8ebb171a849@inf.fu-berlin.de> Content-Language: en-US In-Reply-To: <3f3d536a-1120-0bb9-b2a0-a8ebb171a849@inf.fu-berlin.de> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Original-Sender: rote@inf.fu-berlin.de X-Originating-IP: 160.45.40.209 X-ZEDAT-Hint: PO X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1704715844-9E26B5D5-5989DA6F/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.005501, version=1.2.4 X-Spam-Flag: NO X-Spam-Status: No, score=-50.0 required=5.0 tests=ALL_TRUSTED, T_SCC_BODY_TEXT_LINE X-Spam-Checker-Version: SpamAssassin 3.4.6 on Tuvalu.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] =?utf-8?q?Invitation_to_Monday_LectureTOD?= =?utf-8?q?AY=2C_14=3A15=3A_Raphael_Steiner_=28Z=C3=BCrich=29_-_Shortest_p?= =?utf-8?q?aths_on_combinatorial_polytopes=3A_Hardness_and_approximation?= 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, 08 Jan 2024 12:10:45 -0000 Our next Monday Lecture takes place today, on January 8 at FU Berlin. *_Location_* *Seminar room 053* - Ground Floor Freie Universität Berlin, Institut für Informatik Takustr. 9 14195 Berlin *_Time_: *Monday, January 8, 2024, 14:15* *_Lecture_: Raphael Steiner (ETH Zürich) *_Title_: Shortest paths on combinatorial polytopes: Hardness and approximation *_Abstract_:* I will present some of my joint work with Jean Cardinal on the complexity of computing and approximating shortest paths in the skeleton of a combinatorially defined polytope. In particular, I will discuss proofs for the inapproximability of finding shortest paths on the skeleton of perfect matching polytopes, and of polymatroids, and discuss various related context and problems in which our work is embedded. (Sorry for the late invitation! I just realized that I had sent it to the wrong list) From rote@zedat.fu-berlin.de Tue Jan 16 11:50:39 2024 Received: from outpost1.zedat.fu-berlin.de ([130.133.4.66]) by list1.zedat.fu-berlin.de (Exim 4.95) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLS1.3) tls TLS_AES_256_GCM_SHA384 (envelope-from ) id 1rPh1j-002zcR-FT; Tue, 16 Jan 2024 11:50:39 +0100 Received: from inpost2.zedat.fu-berlin.de ([130.133.4.69]) by outpost.zedat.fu-berlin.de (Exim 4.95) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLS1.3) tls TLS_AES_256_GCM_SHA384 (envelope-from ) id 1rPh1j-002qvo-DJ; Tue, 16 Jan 2024 11:50:39 +0100 Received: from 87-77-166-189.mna.fu-berlin.de ([87.77.166.189]) by inpost2.zedat.fu-berlin.de (Exim 4.95) for facets-of-complexity@lists.fu-berlin.de with esmtpsa (TLS1.3) tls TLS_AES_128_GCM_SHA256 (envelope-from ) id 1rPh1j-000of4-7F; Tue, 16 Jan 2024 11:50:39 +0100 Message-ID: <824aa757-980b-4bb0-8b3d-4ca664d8a856@inf.fu-berlin.de> Date: Tue, 16 Jan 2024 11:50:37 +0100 MIME-Version: 1.0 User-Agent: Mozilla Thunderbird Content-Language: en-US To: facets-of-complexity@lists.fu-berlin.de From: =?UTF-8?Q?G=C3=BCnter_Rote?= Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Original-Sender: rote@inf.fu-berlin.de X-Originating-IP: 87.77.166.189 X-ZEDAT-Hint: PO X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1705402239-4CA04FCF-42726224/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.000002, version=1.2.4 X-Spam-Flag: NO X-Spam-Status: No, score=-50.0 required=5.0 tests=ALL_TRUSTED, T_SCC_BODY_TEXT_LINE X-Spam-Checker-Version: SpamAssassin 3.4.6 on Palau.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Graduate student meeting in Berlin, April 10-12, Applied Algebra and Combinatorics 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, 16 Jan 2024 10:50:39 -0000 Registration for the 5th Student Graduate Meeting in Applied Algebra and Combinatorics is now open. It will take place 10-12 April, 2024 in Berlin, and is aimed at graduate students and postdocs in applied algebra and combinatorics from all over the world. The workshop program includes participant talks, a poster session, and two minicourses given by Georg Loho and İrem Portakal. There will also be exercise sessions and an open problem session. Conference website: https://sites.google.com/view/gsmaac24/ We expect to be able to provide some financial support, prioritising those giving talks/posters. The registration deadline is 31st of January if funding is requested and 10th of March, otherwise (subject to space). Looking forward to seeing you in Berlin! The organizers, Sofía Garzón, Kyle Huang, Dante Luber, Lorenzo Vecchi, Marcel Wack From rote@zedat.fu-berlin.de Wed Jan 24 15:02:06 2024 Received: from outpost1.zedat.fu-berlin.de ([130.133.4.66]) by list1.zedat.fu-berlin.de (Exim 4.95) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLS1.3) tls TLS_AES_256_GCM_SHA384 (envelope-from ) id 1rSdpN-001RG8-O6; Wed, 24 Jan 2024 15:02:05 +0100 Received: from inpost2.zedat.fu-berlin.de ([130.133.4.69]) by outpost.zedat.fu-berlin.de (Exim 4.95) with esmtps (TLS1.3) tls TLS_AES_256_GCM_SHA384 (envelope-from ) id 1rSdpN-003EvO-Gi; Wed, 24 Jan 2024 15:02:05 +0100 Received: from [193.174.3.100] (helo=[172.16.39.64]) by inpost2.zedat.fu-berlin.de (Exim 4.95) with esmtpsa (TLS1.3) tls TLS_AES_128_GCM_SHA256 (envelope-from ) id 1rSdpN-0008dA-9w; Wed, 24 Jan 2024 15:02:05 +0100 Message-ID: <6efb4cc3-ec43-469d-9a36-8920726d9f89@inf.fu-berlin.de> Date: Wed, 24 Jan 2024 15:02:13 +0100 MIME-Version: 1.0 User-Agent: Mozilla Thunderbird From: =?UTF-8?Q?G=C3=BCnter_Rote?= To: facets-of-complexity@lists.fu-berlin.de References: <3f3d536a-1120-0bb9-b2a0-a8ebb171a849@inf.fu-berlin.de> Content-Language: en-US Cc: Christoph Hertrich In-Reply-To: <3f3d536a-1120-0bb9-b2a0-a8ebb171a849@inf.fu-berlin.de> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Original-Sender: rote@inf.fu-berlin.de X-Originating-IP: 193.174.3.100 X-ZEDAT-Hint: PO X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1706104925-5A583C5F-4436EDC6/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.048377, version=1.2.4 X-Spam-Flag: NO X-Spam-Status: No, score=-50.0 required=5.0 tests=ALL_TRUSTED, T_SCC_BODY_TEXT_LINE X-Spam-Checker-Version: SpamAssassin 3.4.6 on Vanuatu.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Invitation to Monday Lecture on Jan 29, 14:15: Christoph Hertrich (Frankfurt) - Facets of Neural Network Complexity 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, 24 Jan 2024 14:02:06 -0000 Our next Monday Lecture takes place on January 29 at FU Berlin. *_Location_* *Seminar room 053* - Ground Floor Freie Universität Berlin, Institut für Informatik Takustr. 9 14195 Berlin *_Time_: *Monday, January 29, 2024, 14:15* *_Lecture_: Christoph Hertrich (Universität Frankfurt) *_Title_: (Old and New) Facets of Neural Network Complexity *_Abstract_:* How to use discrete mathematics and theoretical computer science to understand neural networks? Guided by this question, I will focus on neural networks with rectified linear unit (ReLU) activations, a standard model and important building block in modern machine learning pipelines. The functions represented by such networks are continuous and piecewise linear. But how does the set of representable functions depend on the architecture? And how difficult is it to train such networks to optimality? In my talk I will answer fundamental questions like these using methods from polyhedral geometry, combinatorial optimization, and complexity theory. This stream of research was started during my doctorate within _Facets of Complexity_ and carried much further since then. http://www.facetsofcomplexity.de/monday/20240129-L-Hertrich.html