Noon seminar

The informal research seminar of the ALGO cluster. Talks last roughly 25 minutes, with five extra minutes allocated for discussion. Many presentations are focused on recent conference presentations, or practice talks for upcoming conferences. New members are often asked to give an overview of their field of research. Talks given by invited speakers may take up to 45–60 minutes including questions.

To be kept up-to-date about noon seminar presentations, please subscribe to the algoseminar-l mailing list.

This is the schedule for 2025. Schedules are available between 2005 and 2025.

• Presentation
• Master's defense
• Midterm
• Invited talk
• External talk
• Practice talk
• PhD defense
• Cancelled

Upcoming talks

Send an email to Thijs to schedule your talk. No talks are planned at the moment.

Past talks

• Apr 03, 14:00—15:00 (MetaForum 3.122)
  Javier Cembrano and Golnoosh Shahkarami: External Talks by Visitors from MPI Saarbrücken.
  － Abstract
  

  In this session we have two presentations by visitors from MPI Saarbrücken:
  
  
  Javier Cembrano: New Combinatorial Insights for Monotone Apportionment
  
  The apportionment problem constitutes a fundamental problem in democratic societies: How to distribute a fixed number of seats among a set of states in proportion to the states' populations? This--seemingly simple--task has led to a rich literature and has become well known in the context of the US House of Representatives. In this paper, we connect the design of monotone apportionment methods to classic problems from discrete geometry and combinatorial optimization and explore the extent to which randomization can enhance proportionality.
  We first focus on the well-studied family of stationary divisor methods, which satisfy the strong population monotonicity property, and show that this family produces only a slightly superlinear number of different outputs as a function of the number of states. While our upper and lower bounds leave a small gap, we show that--surprisingly--closing this gap would solve a long-standing open problem from discrete geometry, known as the complexity of k-levels in line arrangements. The main downside of divisor methods is their violation of the quota axiom, i.e., every state should receive ⌊qi⌋ or ⌈qi⌉ seats, where qi is the proportional share of the state. As we show that randomizing over divisor methods can only partially overcome this issue, we propose a relaxed version of divisor methods in which the total number of seats may slightly deviate from the house size. By randomizing over them, we can simultaneously satisfy population monotonicity, quota, and ex-ante proportionality.
  
  
  Golnoosh Shahkarami: Learning-Augmented Mechanism Design
  
  In the strategic facility location problem, a set of agents report their locations in a metric space, and the goal is to use these reports to open a new facility, minimizing an aggregate distance measure from the agents to the facility. However, agents are strategic and may misreport their locations to influence the facility's placement in their favor. The aim is to design truthful mechanisms that ensure agents cannot gain by misreporting. This problem was recently revisited through the learning-augmented framework, aiming to move beyond worst-case analysis by designing truthful mechanisms augmented with (machine-learned) predictions. In this talk, we will explore this problem in both deterministic and randomized settings, as well as the impact of different types of predictions on the performance of truthful learning-augmented mechanisms.

• Apr 01, 15:30—17:00 (MetaForum 3.119)
  : EuroCG Practice Session III.
• Mar 26, 13:00—15:00 (MetaForum 3.119)
  : EuroCG Practice Session II.
• Mar 25, 15:30—17:00 (MetaForum 3.122)
  : EuroCG Practice Session I.
• Feb 27, 14:00—14:45 (MetaForum 4.210)
  Maxim Snoep: IMR2025 Practice Talk.
  － Abstract
  

  This is a session for practicing IMR presentations.
  Presentations are 20 minutes, after which there are 5 minutes for questions.
  There is one talk in this session:
  
  Maxim Snoep: Polycubes via Dual Loops

• Jan 27, 13:30—14:00 (MetaForum 3.119)
  Gijs de Man: On the Parameterized Complexity of Reeb Graph Drawings.
• Jan 16, 14:00—14:45 (MetaForum 3.119)
  Arjen Simons: SOFSEM Practice Talk.
  － Abstract
  

  This is a session for practicing SOFSEM presentations.
  Presentations are (likely to be) 25 minutes, after which there is room for questions and feedback.
  There is one talk in this session:
  
  Arjen Simons: Visual Complexity of Point Set Mappings