Networks

Cum laude distinction for Sándor Kisfaludi-Bak

On June 27th, Sándor Kisfaludi-Bak successfully defended his PhD thesis entitled 'ETH-Tight Algorithms for Geometric Network Problems' at TU Eindhoven. He received his degree cum laude, a very rare distinction that is only given for outstanding results that have been obtained with a very high level of independence.

 

cover_thesis_sandorThe first major contribution in Sándor’s thesis is a general framework to develop sub-exponential algorithms for certain types of geometric intersection graphs, which encompass graphs that model sensor networks. The framework applies to many different problems and leads to algorithms that are both faster and more general than what was known. A second contribution concerns the Traveling Salesman Problem, one of the most widely studied problems in all of computer science. Sándor improved the best known running time for the Euclidean version of the problem, which constitutes the first progress on the complexity of this famous problem since many years. Sándor also proved that the running times of his algorithms are best possible, assuming the widely accepted Exponential Time Hypothesis.

 

The results in the thesis were published in the most prestigious conferences in theoretical computer science. Besides the work in his (already extensive) thesis, Sándor published a large number of other papers in top conferences and journals. We wish to congratulate Sándor on these great achievements!