Friday, 9 May 2025, 11:00 - 12:00
|
Sándor Kisfaludi-Bak
Aalto University
|
Given a set of objects (e.g. axis-aligned cubes, balls, discrete point sets, etc.) in 3-dimensional Euclidean space, find the minimum volume convex polytope intersecting all of the objects. Is this problem in P or NP-hard? What if we want minimum surface area instead of minimum volume? Can we get good approximations (or approximation schemes)? This is a far-reaching generalization of convex hulls, and very little is known about it algorithmically. In fact, several 2-dimensional variants also remain open that we could try to make progress on.
|
Slides
|
Friday, 11 Apr 2025, 11:00 - 12:00
|
Petteri Kaski
Aalto University
|
The Light Bulb Problem captures the setting of finding a hidden correlation among a large number of observables. The problem asks us to observe $n$ light bulbs for $d$ time instants. At each time instant, each light bulb is either on or off, independently and uniformly at random, except for one hidden pair of light bulbs that is $\rho$-correlated for some constant $\rho>0$. (To guarantee that the hidden pair is unique with high probability as $n$ grows, it suffices to assume that $d\geq 10\rho^{-2}\log n$.) The task is to find the hidden pair given the observations.
|
Slides
|
Friday, 14 Mar 2025, 11:00 - 12:00
|
Corinna Coupette
Aalto University
|
We introduce the problem of distributing a set of indivisible goods among a set of agents such that the resulting allocation of goods to agents can be considered fair under the fairness notion of envyfreeness up to any good (EFX). The existence of EFX allocations is considered one of the biggest open problems in fair division, with interesting connections to extremal graph problems and significant barriers inherent in current techniques.
|
Slides
|
| Friday, 14 Feb 2025, 11:00 - 12:00 |
Juha Harviainen
University of Helsinki
|
Vertex integrity is a parameter that measures how easy it is to break a graph into small components. We will study whether the parameterized algorithms for computing it can be improved.
|
Slides
|
