Congrats Simon!Today, Simon Weber defended his doctoral thesis on unique sink orientations (USOs), which model a very broad class of computational problems such as linear programs. Simon proved a wealth of non-trivial and in parts quite surprising connections between USOs and different complementarity and division problems. His results build on findings by Jiří Matoušek and his main advisor Bernd Gärtner. 
photo by Manuel Wettstein One of my personal favourite results was the introduction of a promise problem P-LIN-Bellman that proved as a very powerful tool to show polynomial-time equivalence of different problems. While making a few very significant steps towards resolving some long standing open problems in theoretical computer science, Simon's work also shed some light on which important questions to tackle next. Further Reading |