IPA Dissertation Awards Event – Rescheduled to Tuesday March 29th 2022

Celebrating the 2019 and 2020 awards 

IPA is organizing a (hopefully in-person) IPA Dissertation Awards Event on Tuesday, March 29th, starting at 13:00 12:00, on Friday, December 10th, starting at 12:00, to honor the winners of the award for best IPA dissertation published in 2019 and 2020.

Speakers at the event will be:

The event will take place on March 29th, in-person.

In addition to the talks, there will be a sandwich lunch beforehand (from 13:00 12:00), and tea, coffee, juice, cookies throughout the event.

Assuming Covid measures at the time allow it, this will be an opportunity for the IPA community to finally meet and network again in substantial numbers, in order to network, socialize, and learn about the winners of the IPA dissertation awards and their PhD research as well as more recent research.

Venue

Tutorial room 0.42, ground floor of David de Wied Building, Universiteitsweg 99, Utrecht University Science Park. The venue is within 5 minutes walking from

  • sneltram (line 22) stop Heidelberglaan, giving a direct connection to Utrecht Centraal train station in 12 minutes;
  • parking garage at the Cambridgelaan.

Registration

Please register ASAP via this link (we just ask for your e-mail, first and last name, affiliation, and background (IPA / non-IPA, PhD student / staff member), as well as optional additional remarks such as dietary constraints). We will use a first come first serve registration policy, especially in case we need to restrict numbers e.g. due to a move to a 1.5m distancing scenario. If you register and need to cancel participation later on, please send an e-mail to ipa@tue.nl.

Registration closes Monday March 21st 10:00 Tuesday March 22nd 23:59.

Tentative Schedule

13:00 Arrival, and sandwich lunch

13:30 Opening

13:40 Mark de Berg (TU/e, first promotor of Sándor Kisfaludi-Bak), ETH-Tight Exact Algorithms for Hard Geometric Network Problems.
Many well-known optimization problems on graphs are NP-hard. Hence, we do not expect to have polynomial-time algorithms for solving these problems exactly. However, we may still be able to develop so-called sub-exponential algorithms, that is, algorithms whose running time is of the form 2^o(n), where n is the input size. This turns out to be the case for many problems when the input graph is planar. For example, Independent Set and Hamiltonian Cycle can be solved in 2^O(sqrt(n)) time on n-vertex planar graphs. A main tool behind these algorithms is the famous Planar Separator Theorem. In his thesis, Sándor Kisfaludi-Bak has proved a generalization of this theorem to certain geometric intersection graphs. In this talk I will discuss this generalization. I will also discuss a novel geometric separator for point sets, which can be applied to solve the famous Euclidean Traveling Salesman problem.  The algorithms resulting from these new separator results have running time 2^O(sqrt(n)), which is optimal under the so-called Exponential-Time Hypothesis (ETH).

14:30 (online) Sándor Kisfaludi-Bak (Aalto University, Finland; winner of the award for best IPA dissertation 2019 with his dissertation “ETH-Tight Algorithms for Geometric Network Problems”), Conditionally optimal approximation for geometric problems.
The modern fine-grained approach to computational complexity now allows for approximation algorithms to be conditionally optimal: we can find algorithms that have the best tradeoff between the accuracy of the solution they find and their running time, under some established hypothesis in computational complexity. In this talk, we will discuss one such result, our recent approximation scheme for Euclidean TSP. I will show how the lower bound machinery is a natural continuation of my earlier work done during my PhD. The new results are joint with Jesper Nederlof and Karol Wegrzycki. A preprint is available here: https://arxiv.org/abs/2011.03778.

15:15 Break

15:30 Tim Willemse (TU/e; first promotor of Thomas Neele), Advances in Solving Parameterised Boolean Equation Systems.
Parameterised Boolean equation systems (PBESs) play a fundamental role in verifying software systems. For instance, the question whether two systems are behaviourally equivalent can be answered by solving a PBES. Likewise, deciding whether a system satisfies a given requirement can be done by solving a PBES obtained from the system and the requirement. Consequently, efficient techniques and algorithms for solving a PBES are of particular practical relevance. We will highlight several of the advances that have been made in this area in recent years.

16:15 Thomas Neele (TU/e; winner of the award for best IPA dissertation 2020 with his dissertation “Reductions for Parity Games and Model Checking”), Model Checking, Parity Games and Reductions: A PhD story.
A famous problem in formal methods, and specifically model checking, is the state explosion problem. In my thesis, called “Reductions for Parity Games and Model Checking”, I presented several state space reduction techniques to (partially) alleviate this issue. In this talk, I will give an overview of the contributions in my thesis, how I approached the research, the lessons I have learned and my plans for the future.

17:15 Drinks + bites

Ca. 18:15–18:30 End.