From rote@zedat.fu-berlin.de Tue May 02 17:13:48 2023 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.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (envelope-from ) id 1ptrhM-003sj0-LV; Tue, 02 May 2023 17:13:48 +0200 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 1ptrhM-003xR1-J6; Tue, 02 May 2023 17:13:48 +0200 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 1ptrhM-002OMq-Dl; Tue, 02 May 2023 17:13:48 +0200 Message-ID: <5e027433-1fea-1d3a-fe6b-81ad3fe84cb6@inf.fu-berlin.de> Date: Tue, 2 May 2023 17:13:48 +0200 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.10.0 Content-Language: en-US References: To: facets-of-complexity@lists.fu-berlin.de From: =?UTF-8?Q?G=c3=bcnter_Rote?= Cc: Tamara Knoll In-Reply-To: X-Forwarded-Message-Id: 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::1683040428-EC2C2B99-EF12D90E/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, T_SCC_BODY_TEXT_LINE X-Spam-Checker-Version: SpamAssassin 3.4.6 on Tokelau.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Invitation to Monday's Lecture May 15, 16:00 s.t. 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, 02 May 2023 15:13:49 -0000 Our next Monday Lecture will take place on May 15, at 16:00 sharp (unusual time and place!) at FU Berlin. *_Location_* *Great Lecture Hall - Ground Floor* Freie Universität Berlin Takustr. 9 14195 Berlin *_Time_: *Monday, May 15, 2023, 16:00* *_Lecture_: Günter Rote (FU Berlin) *_Title_: The Generalized Combinatorial Lasoń-Alon-Zippel-Schwartz Nullstellensatz Lemma *_Abstract_:* We survey strengthenings and generalizations of the Schwartz-Zippel Lemma and Alon’s Combinatorial Nullstellensatz. Both lemmas guarantee the existence of (a certain number of) nonzeros of a multivariate polynomial when the variables run independently through sufficiently large ranges. From rote@zedat.fu-berlin.de Wed May 31 11:40:31 2023 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.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (envelope-from ) id 1q4IJj-002H8Q-Je; Wed, 31 May 2023 11:40:31 +0200 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 1q4IJj-000fHa-H1; Wed, 31 May 2023 11:40:31 +0200 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 1q4IJj-0039EF-Bd; Wed, 31 May 2023 11:40:31 +0200 Message-ID: Date: Wed, 31 May 2023 11:40:26 +0200 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.11.0 Content-Language: en-US References: <5e027433-1fea-1d3a-fe6b-81ad3fe84cb6@inf.fu-berlin.de> To: facets-of-complexity@lists.fu-berlin.de From: =?UTF-8?Q?G=c3=bcnter_Rote?= Cc: Tamara Knoll In-Reply-To: <5e027433-1fea-1d3a-fe6b-81ad3fe84cb6@inf.fu-berlin.de> X-Forwarded-Message-Id: <5e027433-1fea-1d3a-fe6b-81ad3fe84cb6@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::1685526031-55B29CF5-86515CB7/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.001614, 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 June 5, 16:00 s.t.: Grid Peeling and the Affine Curve-Shortening Flow 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, 31 May 2023 09:40:31 -0000 Our next Monday Lecture will take place on June 5 at 16:00 sharp (unusual time and place!) at FU Berlin. *_Location_* *Great Lecture Hall - Ground Floor* Freie Universität Berlin Takustr. 9 14195 Berlin *_Time_: *Monday, June 5, 2023, 16:00* *_Lecture_: Günter Rote (FU Berlin) *_Title_: Grid Peeling and the Affine Curve-Shortening Flow *_Abstract_:* Grid Peeling is the process of taking the integer grid points inside a convex region and repeatedly removing the convex hull vertices. By contrast, the Affine Curve-Shortening Flow (ACSF) is defined as a particular deformation of a smooth curve. It has been observed in 2017 by Eppstein, Har-Peled, and Nivasch, that, as the grid is refined, Grid Peeling converges to the Affine Curve-Shortening Flow. As part of the M.Ed. thesis of Moritz Rüber, we have investigated the grid peeling process for special parabolas, and we could observe some striking phenomena. This has lead to the precise value of the constant that relates the two processes. With Morteza Saghafian from IST Austria, we could prove the convergence of grid peeling for the class of parabolas with vertical axis. *_Tea break_:* Before the talk, at 15:30, there will be a "tea break" at the usual place, Room 134 (glass door, straight from the stairs) in the first floor. From rote@zedat.fu-berlin.de Thu Jun 08 16:29:25 2023 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.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (envelope-from ) id 1q7Gdh-003YKP-9J; Thu, 08 Jun 2023 16:29:25 +0200 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 1q7Gdh-002jNn-6s; Thu, 08 Jun 2023 16:29:25 +0200 Received: from strecke.imp.fu-berlin.de ([160.45.40.209]) 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 1q7Gdh-000mFU-1k; Thu, 08 Jun 2023 16:29:25 +0200 Message-ID: <20c02dd2-6042-4240-01d2-a29f18431b5b@inf.fu-berlin.de> Date: Thu, 8 Jun 2023 16:29:24 +0200 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.11.0 Content-Language: en-US References: To: facets-of-complexity@lists.fu-berlin.de From: =?UTF-8?Q?G=c3=bcnter_Rote?= In-Reply-To: X-Forwarded-Message-Id: 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::1686234565-40359743-98A6C0A7/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.175251, 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 Kiribati.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Invitation to Monday Lecture June 12, 16:00 s.t.: The Multiplicative-Weights-Update Method 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, 08 Jun 2023 14:29:25 -0000 Our next Monday Lecture will take place on June 12 at 16:00 sharp at FU Berlin. *_Location_* *Great Lecture Hall - Ground Floor* (Hörsaal Informatik) Freie Universität Berlin Department of Computer Science Takustr. 9 14195 Berlin *_Time_: *Monday, June 12, 2023, 16:00* *_Lecture_: Wolfgang Mulzer (FU Berlin) *_Title_: The Multiplicative-Weights-Update Method *_Abstract_:* The multiplicative weights update method is a design paradigm for algorithms that is used in many different areas of theoretical computer science and machine learning. A famous survey by Arora, Hazan, and Kale provides an excellent overview over the method and its applications. Together with Nabil Mustafa, we are currently working on a monograph that explores the method in more detail. I will give an overview of the method and share some nuggets that we encountered. Based on joint work with Nabil Mustafa. *_Tea break_:* Before the talk, at 15:30, there will be a tea "break" at the usual place, Room 134 in the first floor (glass door, facing the exit from the stairway). From rote@zedat.fu-berlin.de Mon Jun 19 16:10:02 2023 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.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (envelope-from ) id 1qBFZy-001RyH-Jd; Mon, 19 Jun 2023 16:10:02 +0200 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 1qBFZy-001kDT-H5; Mon, 19 Jun 2023 16:10:02 +0200 Received: from strecke.imp.fu-berlin.de ([160.45.40.209]) 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 1qBFZy-003rIo-CG; Mon, 19 Jun 2023 16:10:02 +0200 Message-ID: <43bf3188-5883-20d2-4acb-da952483f37c@inf.fu-berlin.de> Date: Mon, 19 Jun 2023 16:10:02 +0200 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.12.0 Content-Language: en-US References: To: facets-of-complexity@lists.fu-berlin.de From: =?UTF-8?Q?G=c3=bcnter_Rote?= In-Reply-To: X-Forwarded-Message-Id: 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::1687183802-531C58E4-50B69D90/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.294559, 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] Invitation to Monday Lecture on June 26, 16:00 s.t.: Topology at the North Pole / max-min allocation / Santa Claus problem 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, 19 Jun 2023 14:10:03 -0000 Our next Monday Lecture takes place on June 26 at 16:00 sharp at FU Berlin. *_Location_* *Great Lecture Hall - Ground Floor* Freie Universität Berlin Takustr. 9 14195 Berlin *_Time_: *Monday, June 26, 2023, 16:00* *_Lecture_: Tibor Szabó (FU Berlin) *_Title_: Topology at the North Pole *_Abstract_:* In the max-min allocation problem, disjoint subsets of a set R of indivisible resources are to be allocated to a set P of players, such that the minimum utility among all players is maximized. We study the restricted variant, also known as the Santa Claus problem, where each resource has an intrinsic positive value, and each player covets a subset of the resources. Bezakova and Dani showed that this problem is NP-hard to approximate within a factor less than 2, consequently a great deal of work has focused on approximate solutions. The principal approach for obtaining approximation algorithms has been via the Configuration LP (CLP) of Bansal and Sviridenko. Accordingly, there has been much interest in bounding the integrality gap of this CLP. The existing algorithms and integrality gap estimations are all based one way or another on the combinatorial augmenting tree argument of Haxell for finding perfect matchings in certain hypergraphs. Here we introduce the use of topological tools for the restricted max-min allocation problem. This approach yields substantial improvements in the integrality gap of the CLP. In particular we improve the previously best known bound of 3.808 to 3.534. The talk represents joint work with Penny Haxell. *_Tea break_:* Before the talk, at 15:30, there will be a "tea break" at the usual place, Room 134 (glass door, straight from the stairs) in the first floor. From rote@zedat.fu-berlin.de Fri Jun 30 14:56:19 2023 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.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (envelope-from ) id 1qFDff-002ex2-0J; Fri, 30 Jun 2023 14:56:19 +0200 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 1qFDfe-001AsT-U7; Fri, 30 Jun 2023 14:56:18 +0200 Received: from strecke.imp.fu-berlin.de ([160.45.40.209]) 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 1qFDfe-002pMt-On; Fri, 30 Jun 2023 14:56:18 +0200 Message-ID: <0bd785e9-2845-d200-e81e-be66404fc91d@inf.fu-berlin.de> Date: Fri, 30 Jun 2023 14:56:18 +0200 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.12.0 Content-Language: en-US References: <43bf3188-5883-20d2-4acb-da952483f37c@inf.fu-berlin.de> From: =?UTF-8?Q?G=c3=bcnter_Rote?= To: facets-of-complexity@lists.fu-berlin.de In-Reply-To: <43bf3188-5883-20d2-4acb-da952483f37c@inf.fu-berlin.de> X-Forwarded-Message-Id: <43bf3188-5883-20d2-4acb-da952483f37c@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::1688129779-CB1BEBA1-672451B1/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.105387, 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 Tokelau.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Invitation to Monday Lecture on July 3, 16:00 s.t.: Initial degenerations of Grassmannian via matroid subdivisions of hypersimplices 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, 30 Jun 2023 12:56:19 -0000 Our next Monday Lecture takes place on July 3 at 16:00 sharp at FU Berlin. *_Location_* *Great Lecture Hall - Ground Floor* Freie Universität Berlin Takustr. 9 14195 Berlin *_Time_: *Monday, July 3, 2023, 16:00* *_Lecture_: Dante Luber (TU Berlin) *_Title_: Initial degenerations of the Grassmannian via matroid subdivisions of hypersimplices *_Abstract_:* Nonempty initial degenerations of the Grassmannian are induced by weight functions in its tropicalization. On the other hand, the same weight function induces a regular matroidal subdivision of the hypersimplex. Hence, we study initial degenerations of the (3,8) Grassmannian via matroidal subdivisions of the (3,8) hypersimplex. Our techniques employ tropical, algebraic, and polyhedral geometry, as well as matroid theory, commutative algebra, and computation. *_Tea break_:* Before the talk, at 15:30, there will be a coffee and tea "break" at the usual place, Room 134 (glass door, straight from the stairs) in the first floor.