PhD Defense Sándor Kisfaludi-Bak
On June 27th Sándor Kisfaludi-Bak will defend his PhD thesis entitled 'ETH-Tight Algorithms for Geometric Network Problems'.
The defense will take place at Eindhoven University of Technology at 13:30 in room 0.710 of the Atlas building.
Sándor's promotors are Mark de Berg and Hans L. Bodlaender.
From September 2019, Sándor will join the Algorithms and Complexity group in the Max Planck Institute for Informatics in Saarbrücken, Germany as a postdoctoral fellow.
Abstract
Most physically realized networks are constrained in some way by the geometry of space. The thesis explores the theory of such geometrically constrained networks from the perspective of algorithms and computational complexity. The focus is on solving classic algorithmic problems that are known to be hard even in geometric networks, and proving that the obtained running times are best possible under the Exponential Time Hypothesis (ETH), a well-established complexity- theoretic assumption. For most problems, the geometric constraints allow us to design more efficient algorithms than what is otherwise possible for general graphs.
Sándor received the cum laude distinction for his thesis, you can read more about this here.
Furthermore, Sándor received the Distinguished Dissertation Award of the European Association for Theoretical Computer Science (EATCS), you can read the newsitem here.
You can read the thesis here.