William Umboh
@swumboh
Lecturer in Computational Theory, School of Computing and Information Systems, University of Melbourne. Interests: Theoretical computer science and combinatorial optimisation, focussing on approximation and online algorithms. williamumboh.com
I find it fascinating that it was already observed in 1948, when I presume humans were executing the simplex method on pen and paper, that the simplex method was blazing fast in practice Source: An Interview with George B. Dantzig: The Father of Linear Programming www.jstor.org/stable/2686279
It’s been 3 years since I moved here but this still cracks me up. We also have a Batman Park
Love the animated traffic lights in Taiwan. Especially the part where the animation starts running
Had fun making these slides for yesterdays lecture on bipartite matching and linear programming
🎉 The University of Melbourne team solved 7 problems and finished 25th overall to earn a Bronze Medal at the 2026 ICPC Asia Pacific Championship! Congratulations to team members David Wang, Jeffrey Song and Edge Wang!
iOS autocorrects polylog to pollywog… I suppose it makes sense since pollywogs are tadpoles which kinda look like ~. Also wild that iOS autocorrect is orientation-dependent. It also suggests polyglots in landscape and poly logs in portrait.
Turns out English is all you need to speak Japanese. Just say the English word(s) with a heavy Japanese accent!
Here’s another fun one: Melbourne was almost named Batmania, after John Batman, who came from Tasmania, which was named after Abel Tasman en.wikipedia.org/wiki/John_Ba...
Excited to share a remarkably short proof that P is NOT EQUAL to NP: Here’s P Hotel and it’s clearly not the same as NP Hotel. QED
Caption this! Here’s mine: “Welcome to NP Hotel. The WiFi password is the size of the maximum independent set of this graph”
To close out the workshop, Santa* gave a closing talk on k-median, a literal textbook problem, in the dynamic setting * Ermiya Farokhnejad 6/n
@gbodwin.bsky.social telling us about the true barrier to graph metric sparsification: Turánosaurus 5/n
Kalen Patton gave a lightning talk on his SODA26 Best Student Paper work arxiv.org/abs/2510.11266 4/n
MohammadTaghi Hajiaghayi gave a plenary talk on the first better than 2 approximation for Steiner forest problem arxiv.org/abs/2504.11398 The work is a FOCS25 Best Paper and has already spurred follow up work by @anupamg.bsky.social and Vera Traub arxiv.org/abs/2511.184... 3/n