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

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

__Location__**: **

Freie Universität Berlin

Takustr. 9

14195 Berlin

__Time__: **Monday, January 27th - 14:15 h**

__Lecture__: Haim Kaplan (Tel Aviv University**)**

__Title__: Privately Learning Thresholds

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

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

__Colloquium__: Gweneth Anne McKinley (MIT, Cambridge,
USA**)**

__Title__: Super-logarithmic cliques in dense
inhomogeneous random graphs

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

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

__Colloquium__: Michał Włodar**czyk (Universität
Eindhoven****)**

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

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

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

__Location__**: **

Freie Universität Berlin

Takustr. 9

14195 Berlin

__Time__: **Monday, February 3rd - 14:15 h**

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

__Title__: Separators and exact algorithms for geometric
intersection graphs

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

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

__Colloquium__: Yanitsa Pehova (University of Warwick**)**

__Title__: Characterisation of quasirandom permutations by
a pattern sum

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

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

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

**The Faculty will meet **after the second Colloquium.

__Location__**: **

Freie Universität Berlin

Takustr. 9

14195 Berlin

__Time__: **Monday, February 10th - 14:15 h**

__Lecture__: Lionel Pournin (Université Paris 13**)**

__Title__: Recent results on the diameter of lattice
polytopes

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

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

__Colloquium__: José Samper (Max Planck Institute Leipzig**)**

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

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

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

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

__Title__: Recent developments in the container method

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

--------------D1E5514C014F33239D926721-- From rote@inf.fu-berlin.de Thu Feb 06 18:51:53 2020 Received: from outpost1.zedat.fu-berlin.de ([130.133.4.66]) by list1.zedat.fu-berlin.de (Exim 4.85) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLSv1.2:ECDHE-RSA-AES256-GCM-SHA384:256) (envelope-fromDue to the storm 'Sabine' the second talk of today can not be
given.

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

On 03.02.2020 17:58, Ita Brunke wrote:

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

Exceptionally, there will be once again asecond Colloquiumat17:00.

The Faculty will meetafter the second Colloquium.

Location:

Room 005 - Ground Floor

Freie Universität Berlin

Takustr. 9

14195 Berlin

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

Lecture: Lionel Pournin (Université Paris 13)

Title: Recent results on the diameter of lattice polytopes

Abstract:

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

Coffee & Tea Break:

Room 134

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

Colloquium: José Samper (Max Planck Institute Leipzig)

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

Abstract:

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