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:
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łodarczyk (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.