[Facets-of-complexity] Invitation to Monday Lecture & Colloquium - January 27th 2020

[Ita Brunke <i.brunke@inf.fu-berlin.de>]

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:

Room 005 - Ground Floor
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

Abstract:

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.

Coffee & Tea Break:
Room 134

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

Abstract:

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

Abstract:

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.