Algorithms & Complexity

An IPA online afternoon (IPAndemic afternoon, if you will) will take place Wednesday, May 26^th, starting at 13:00 (social chat open at 12:30).

The afternoon has an algorithms & complexity flavour, with speakers both from inside IPA’s algorithms & complexity ‘blood group’ as well as outside, and the afternoon will also feature introductory talks by some of the many IPA PhD students who joined IPA in the last year, as well as ample breaks and other opportunities to foster interaction.

After the last talk, the social chat (2D audio/video SpatialChat) will stay open, but it’ll be `bring your own drink’.

Schedule

12:30 Social chat open

13:00 Opening — Loek Cleophas (IPA research school)

13:00–13:30 Wouter Meulemans (TU/e) — Efficient Optimal Overlap Removal. Various forms of visualization, such as symbol maps, show data using a scaled symbol (such as a square or circle) to show the magnitude of a value at a certain local (for example, earthquakes shown by symbols at their epicenter, using symbol sizes to represent their magnitude). Placing many symbols often leads to overlap, though this can be removed by permitting some displacement of the symbols. Clearly, we want to distort the information as little as possible and thus we want to minimize the displacement. Many forms of this problem, however, are NP-hard, even in seemingly simple cases such as equally sized squares where we require the order of their centers along the x-axis and y-axis to remain the same (orthogonal order). Surprisingly, this same problem is efficiently solvable if the shapes are diamonds (squares rotated by 45 degrees) instead of squares. We will look into why this change makes such a big difference, and learn about polyhedral distance functions along the way.

13:30–14:00 Walter Kosters (UL) — Combinatorial Game Theory: From Conway to Nash. In Combinatorial Game Theory we analyze two-player games with perfect information, and no chance elements. Conway and others produced beautiful books about this exciting research area, discussing games like Hackenbush and Nim. We will provide a basic introduction, and mention current research about synchronized versions, where we are looking for Nash equilibria.

30 min. break (social chat open)

14:30–15:00 Irina Kostitsyna (TU/e) — Reconfiguration algorithms for programmable matter

15:00–15:10 PhD intro talk: Tom Smeding (Utrecht University)

15:10–15:20 PhD intro talk: Christopher Esterhuyse (University of Amsterdam)

15:20–15:30 PhD intro talk: Xiaoyun Xu (Leiden University)

30 min. break (social chat open)

16:00–16:30 Tom van Dijk (UT) — Algorithms for solving parity games. I will present different approaches to solving parity games as well as discuss how I develop new algorithms.

16:30–ca. 17:30 Social chat open, `bring your own drink’

Registration

Registration has now closed. Please register ASAP (we just ask for your e-mail, first and last name, affiliation, and background (IPA / non-IPA, PhD student / staff member).

Registration closes Tuesday May 25th 13:00, after which the meeting link (likely MS Teams) and details will be sent around.

IPAndemic online events beyond this one

We plan to offer an IPAndemic online event every 3–4 weeks, alternating between online course days (usually 10:00–16:00 with ample breaks) and afternoons (usually 13:00 until 17:30 including `bring your own drink’ socializing) with talks and networking such as this event.

Theme-wise, both event types will rotate over the three IPA `blood groups’ (Algorithmics & Complexity; Formal Methods; Software Engineering).