Networks

Distinguished Dissertation Award for Sándor Kisfaludi-Bak

profilkep-100.jpg2Former NETWORKS PhD student Sándor Kisfaludi-Bak was awarded the Distinguished Dissertation Award of the European Association for Theoretical Computer Science (EATCS), an international organization whose goal is to promote theoretical computer science, to facilitate the exchange of ideas and results among theoretical computer scientists, and to stimulate cooperation between the theoretical and the practical community in computer science.

Sándor received his PhD cum laude from TU Eindhoven, where he did his research co-supervised by Mark de Berg and Hans Bodlaender.

 

Sándor’s  thesis contains groundbreaking algorithmic results on geometric networks. Geometric networks are networks whose nodes correspond to points in some geometric space; the edges in a geometric network typically correspond to physical connections between the nodes (in road or railway networks, for instance) or they are induced by proximity between the nodes (as in wireless communication networks). Sándor obtained his results by combining and further developing sophisticated techniques and insights from two different areas, computational geometry and fixed-parameter tractable algorithms. This resulted in a powerful framework that allowed him to generalize, and at the same time improve, results on a large variety of algorithmic problems on unit-disk graphs – a popular model for sensor networks. Using ingenious lower-bound constructions, he proved the resulting algorithms are optimal under the Exponential-Time Hypothesis. His thesis also contains an ETH-optimal exact algorithm for the famous Euclidean TSP problem.