Friday, 21 Nov 2025, 11:00 - 12:00
Maarintie 8, AS3 |
Augusto Modanese
Aalto University
|
Predicting two-dimensional sandpiles
Sandpile automata are simple models for particle diffusion. Concretely, we imagine grains of sand placed in cells of a lattice. If too many grains share the same cell, the pile "topples", spreading grains in every possible direction.
It has been shown that this model can be predicted by a parallel strategy if the lattice is one-dimensional. However, the same is not possible in the case of three dimensions (unless $P = NC$). The case of two dimensions has been open for more than two decades.
In this session, we will try to tackle a simplified version of the
two-dimensional case.
|
|
Friday, 17 Oct 2025, 11:00 - 12:00
|
Juha Harviainen
University of Helsinki
|
Deterministic constructions for pair-isolating families
A pair-isolating family of a universe $U$ of $n$ elements is a family of subsets such that for all distinct elements $i, j, x_1, x_2, \dots, x_k$ of $U$, there is a subset $Q$ for which $i$ and $j$ are in $Q$ but $x_1, x_2, \dots, x_k$ are not. A probabilistic argument suffices for showing that there exists a pair-isolating family of size $O(k^3 \log n/k)$, but can we efficiently construct such a family deterministically?
|
Slides
|
Friday, 19 Sep 2025, 11:00 - 12:00
|
Tuomas Hakoniemi
University of Helsinki
|
Open Problems in Low-Depth Boolean Circuits
We will discuss some open problems in Boolean circuits of depth 2 or 3.
|
-
|
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
|
