William Umboh
@swumboh.bsky.social
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
Pinned
William Umboh
@swumboh.bsky.social
· Dec 31
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
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.
Also wild that iOS autocorrect is orientation-dependent. It also suggests polyglots in landscape and poly logs in portrait.
February 12, 2026 at 11:30 PM
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.
Also wild that iOS autocorrect is orientation-dependent. It also suggests polyglots in landscape and poly logs in portrait.
Excited for my first journal editorial board membership at Theoretical Computer Science!
February 12, 2026 at 8:10 PM
Excited for my first journal editorial board membership at Theoretical Computer Science!
Reposted by William Umboh
I certainly don't dismiss all of this. Especially for some jobs. And even given that its message is "Buy our products". But: "If you’ve always wanted to write a book but couldn’t find the time or struggled with the writing, you can work with AI to get it done." So...
fortune.com/2026/02/11/s...
fortune.com/2026/02/11/s...
Something big is happening in AI — and most people will be blindsided | Fortune
It’s not like a light switch... more like the moment you realize the water has been rising around you and is now at your chest.
fortune.com
February 12, 2026 at 10:07 AM
I certainly don't dismiss all of this. Especially for some jobs. And even given that its message is "Buy our products". But: "If you’ve always wanted to write a book but couldn’t find the time or struggled with the writing, you can work with AI to get it done." So...
fortune.com/2026/02/11/s...
fortune.com/2026/02/11/s...
Petition to call pairs that are hard to distinguish “fauxrelated”
In the Forrelation task, an algo is given some ε in (0,1] and query access to f,g: {0,1}^n→{0,1}, with the promise that f *and the Fourier transform of g* have correlation at least ε, or at most -ε. Task: figure out which!
That's a task easy by design for quantum algos, "because Hadamard": 1 query!
That's a task easy by design for quantum algos, "because Hadamard": 1 query!
hulk says " i was made for this " in front of a gray background
Alt: The Hulk says " i was made for this " in front of a gray background
media.tenor.com
February 11, 2026 at 8:46 PM
Petition to call pairs that are hard to distinguish “fauxrelated”
Reposted by William Umboh
𝗖𝗮𝗹𝗹 𝗳𝗼𝗿 𝗣𝗼𝘀𝘁𝗱𝗼𝗰𝘁𝗼𝗿𝗮𝗹 𝗙𝗲𝗹𝗹𝗼𝘄𝘀 𝗶𝗻 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺𝘀 & 𝗧𝗵𝗲𝗼𝗿𝘆
𝗜𝗻𝗱𝗶𝗮𝗻 𝗜𝗻𝘀𝘁𝗶𝘁𝘂𝘁𝗲 𝗼𝗳 𝗦𝗰𝗶𝗲𝗻𝗰𝗲 (𝗜𝗜𝗦𝗰), 𝗕𝗲𝗻𝗴𝗮𝗹𝘂𝗿𝘂
The Algorithms group at IISc invites applications for multiple 𝗣𝗼𝘀𝘁-𝗗𝗼𝗰𝘁𝗼𝗿𝗮𝗹 𝗙𝗲𝗹𝗹𝗼𝘄𝘀𝗵𝗶𝗽𝘀 in Algorithms & Theory.
𝗔𝗽𝗽𝗹𝗶𝗰𝗮𝘁𝗶𝗼𝗻 𝗟𝗶𝗻𝗸: forms.gle/moz2vx7tiNFC...
𝗗𝗲𝗮𝗱𝗹𝗶𝗻𝗲: 28 February
#postdocs
(1/n)
𝗜𝗻𝗱𝗶𝗮𝗻 𝗜𝗻𝘀𝘁𝗶𝘁𝘂𝘁𝗲 𝗼𝗳 𝗦𝗰𝗶𝗲𝗻𝗰𝗲 (𝗜𝗜𝗦𝗰), 𝗕𝗲𝗻𝗴𝗮𝗹𝘂𝗿𝘂
The Algorithms group at IISc invites applications for multiple 𝗣𝗼𝘀𝘁-𝗗𝗼𝗰𝘁𝗼𝗿𝗮𝗹 𝗙𝗲𝗹𝗹𝗼𝘄𝘀𝗵𝗶𝗽𝘀 in Algorithms & Theory.
𝗔𝗽𝗽𝗹𝗶𝗰𝗮𝘁𝗶𝗼𝗻 𝗟𝗶𝗻𝗸: forms.gle/moz2vx7tiNFC...
𝗗𝗲𝗮𝗱𝗹𝗶𝗻𝗲: 28 February
#postdocs
(1/n)
LinkedIn
This link will take you to a page that’s not on LinkedIn
lnkd.in
February 11, 2026 at 9:50 AM
𝗖𝗮𝗹𝗹 𝗳𝗼𝗿 𝗣𝗼𝘀𝘁𝗱𝗼𝗰𝘁𝗼𝗿𝗮𝗹 𝗙𝗲𝗹𝗹𝗼𝘄𝘀 𝗶𝗻 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺𝘀 & 𝗧𝗵𝗲𝗼𝗿𝘆
𝗜𝗻𝗱𝗶𝗮𝗻 𝗜𝗻𝘀𝘁𝗶𝘁𝘂𝘁𝗲 𝗼𝗳 𝗦𝗰𝗶𝗲𝗻𝗰𝗲 (𝗜𝗜𝗦𝗰), 𝗕𝗲𝗻𝗴𝗮𝗹𝘂𝗿𝘂
The Algorithms group at IISc invites applications for multiple 𝗣𝗼𝘀𝘁-𝗗𝗼𝗰𝘁𝗼𝗿𝗮𝗹 𝗙𝗲𝗹𝗹𝗼𝘄𝘀𝗵𝗶𝗽𝘀 in Algorithms & Theory.
𝗔𝗽𝗽𝗹𝗶𝗰𝗮𝘁𝗶𝗼𝗻 𝗟𝗶𝗻𝗸: forms.gle/moz2vx7tiNFC...
𝗗𝗲𝗮𝗱𝗹𝗶𝗻𝗲: 28 February
#postdocs
(1/n)
𝗜𝗻𝗱𝗶𝗮𝗻 𝗜𝗻𝘀𝘁𝗶𝘁𝘂𝘁𝗲 𝗼𝗳 𝗦𝗰𝗶𝗲𝗻𝗰𝗲 (𝗜𝗜𝗦𝗰), 𝗕𝗲𝗻𝗴𝗮𝗹𝘂𝗿𝘂
The Algorithms group at IISc invites applications for multiple 𝗣𝗼𝘀𝘁-𝗗𝗼𝗰𝘁𝗼𝗿𝗮𝗹 𝗙𝗲𝗹𝗹𝗼𝘄𝘀𝗵𝗶𝗽𝘀 in Algorithms & Theory.
𝗔𝗽𝗽𝗹𝗶𝗰𝗮𝘁𝗶𝗼𝗻 𝗟𝗶𝗻𝗸: forms.gle/moz2vx7tiNFC...
𝗗𝗲𝗮𝗱𝗹𝗶𝗻𝗲: 28 February
#postdocs
(1/n)
Reposted by William Umboh
Question:
1. Are you familiar with Polylog on YouTube?
2. If so, how did it impact you?
1. Are you familiar with Polylog on YouTube?
2. If so, how did it impact you?
Polylog
Deep dives into all kinds of topics in computer science, with an emphasis on algorithms. If you want to support us, check out our Patreon.
www.youtube.com
February 11, 2026 at 10:01 AM
Question:
1. Are you familiar with Polylog on YouTube?
2. If so, how did it impact you?
1. Are you familiar with Polylog on YouTube?
2. If so, how did it impact you?
Reposted by William Umboh
Theoretical CS community! I have a small favor to ask. If you ever used, read, watched some of the (excellent IMO) exposition content by Ryan O'Donnell, would you mind filling this very short survey, and maybe say how useful to you it was?
📝 forms.gle/xrvc2mLRbMqK...
Please spread this! #TCSSky
📝 forms.gle/xrvc2mLRbMqK...
Please spread this! #TCSSky
February 8, 2026 at 5:29 AM
Theoretical CS community! I have a small favor to ask. If you ever used, read, watched some of the (excellent IMO) exposition content by Ryan O'Donnell, would you mind filling this very short survey, and maybe say how useful to you it was?
📝 forms.gle/xrvc2mLRbMqK...
Please spread this! #TCSSky
📝 forms.gle/xrvc2mLRbMqK...
Please spread this! #TCSSky
Reposted by William Umboh
Fine, we admit it. Computer was a big op and there actually is a little guy inside of it
February 6, 2026 at 8:07 PM
Fine, we admit it. Computer was a big op and there actually is a little guy inside of it
Reposted by William Umboh
Cats of Meowbourne
February 5, 2026 at 11:37 AM
Cats of Meowbourne
Reposted by William Umboh
3rd "Mathematics of Data" Summer School is being held in Singapore in June. Applications for attendance (with accommodation for most & no registration fee for all) are open throughout February and possibly longer: ims.nus.edu.sg/events/ma_da...
February 4, 2026 at 6:45 AM
3rd "Mathematics of Data" Summer School is being held in Singapore in June. Applications for attendance (with accommodation for most & no registration fee for all) are open throughout February and possibly longer: ims.nus.edu.sg/events/ma_da...
Reposted by William Umboh
Thomas Watson has a new computational complexity textbook about to be published by Cambridge University Press. There's a free version online for personal use.
complexityincs.com
complexityincs.com
February 3, 2026 at 4:09 PM
Thomas Watson has a new computational complexity textbook about to be published by Cambridge University Press. There's a free version online for personal use.
complexityincs.com
complexityincs.com
Reposted by William Umboh
Our paper will be in STOC this summer! 🌎
The simplex algorithm is super efficient. 80 years of experience says it runs in linear time. Nobody can explain _why_ it is so fast.
We invented a new algorithm analysis framework to find out.
We invented a new algorithm analysis framework to find out.
Beyond Smoothed Analysis: Analyzing the Simplex Method by the Book
Narrowing the gap between theory and practice is a longstanding goal of the algorithm analysis community. To further progress our understanding of how algorithms work in practice, we propose a new alg...
arxiv.org
February 1, 2026 at 8:35 PM
Our paper will be in STOC this summer! 🌎
Come play with me!
January 31, 2026 at 2:26 AM
Come play with me!
Reposted by William Umboh
ICYMI: (most of) the slides for our "Celebration of Theoretical CS" event (pre- #FOCS2025) are now available on the website:
sites.google.com/view/celebra...
sites.google.com/view/celebra...
FOCS 2025 Satellite Event: Celebration of TCS - Speaker info
Shafi Goldwasser (Inspirational Talk) Massachusetts Institute of Technology (MIT)
sites.google.com
January 28, 2026 at 9:53 PM
ICYMI: (most of) the slides for our "Celebration of Theoretical CS" event (pre- #FOCS2025) are now available on the website:
sites.google.com/view/celebra...
sites.google.com/view/celebra...
Reposted by William Umboh
A few tickets still going for my talk about JWST this Thursday in St Peters!
www.eventbrite.com.au/e/the-telesc...
www.eventbrite.com.au/e/the-telesc...
The Telescope That Sees Time - Drinks & JWST!
Explore the universe over a beverage! Expert breaks down the James Webb Space Telescope in a fun, beginner-friendly brewery talk.
www.eventbrite.com.au
January 27, 2026 at 12:24 AM
A few tickets still going for my talk about JWST this Thursday in St Peters!
www.eventbrite.com.au/e/the-telesc...
www.eventbrite.com.au/e/the-telesc...
Reposted by William Umboh
On the topic of online resources, worth spreading the word again about Ryan O'Donnell's "CS Theory Toolkit" course: "Covers a large number of the math/CS topics that you need to know for reading and doing research in Computer Science Theory"
youtube.com/playlist?lis... @booleananalysis.bsky.social
youtube.com/playlist?lis... @booleananalysis.bsky.social
January 26, 2026 at 3:55 AM
On the topic of online resources, worth spreading the word again about Ryan O'Donnell's "CS Theory Toolkit" course: "Covers a large number of the math/CS topics that you need to know for reading and doing research in Computer Science Theory"
youtube.com/playlist?lis... @booleananalysis.bsky.social
youtube.com/playlist?lis... @booleananalysis.bsky.social
Reposted by William Umboh
The number of people arguing, following the #NeurIPS2025 case, that a bit of systematically bad scholarship and borderline academic misconduct is OK because doing things the right way is tedious and time-consuming is concerning.
Yes, doing things well might be boring. But doing them badly is... bad
Yes, doing things well might be boring. But doing them badly is... bad
January 24, 2026 at 10:25 PM
The number of people arguing, following the #NeurIPS2025 case, that a bit of systematically bad scholarship and borderline academic misconduct is OK because doing things the right way is tedious and time-consuming is concerning.
Yes, doing things well might be boring. But doing them badly is... bad
Yes, doing things well might be boring. But doing them badly is... bad
The negative impact is that when conferences optimize for CORE, the easiest ways are also the ones that do not necessarily improve scientific quality: acceptance rate and location (being designated “regional” or “national” means it is unranked) www.core.edu.au/conference-p...
January 24, 2026 at 12:51 AM
The negative impact is that when conferences optimize for CORE, the easiest ways are also the ones that do not necessarily improve scientific quality: acceptance rate and location (being designated “regional” or “national” means it is unranked) www.core.edu.au/conference-p...
Reposted by William Umboh
New ICORE conference rankings are out. Theory, logic and formal methods seem to have been heavily penalised. I vibe coded an analysis of, for each Field of Research (FOR), how many associated venues increased or decreased in rank. Here's the summary. FOR 4613 had 13 venues decrease their rank! 1/2
January 21, 2026 at 6:43 AM
New ICORE conference rankings are out. Theory, logic and formal methods seem to have been heavily penalised. I vibe coded an analysis of, for each Field of Research (FOR), how many associated venues increased or decreased in rank. Here's the summary. FOR 4613 had 13 venues decrease their rank! 1/2
Reposted by William Umboh
I wrote a short expository note about a beautiful result of Carmosino, Gao, Impagliazzo, Mihajlin,
Paturi, and Schneider for certifying NO instances of 3-SUM in roughly n^{3/2} time, beating the fastest known, roughly n^2-time deterministic algorithm: home.cs.colorado.edu/~hbennett/no.... 1/
Paturi, and Schneider for certifying NO instances of 3-SUM in roughly n^{3/2} time, beating the fastest known, roughly n^2-time deterministic algorithm: home.cs.colorado.edu/~hbennett/no.... 1/
home.cs.colorado.edu
January 23, 2026 at 4:36 PM
I wrote a short expository note about a beautiful result of Carmosino, Gao, Impagliazzo, Mihajlin,
Paturi, and Schneider for certifying NO instances of 3-SUM in roughly n^{3/2} time, beating the fastest known, roughly n^2-time deterministic algorithm: home.cs.colorado.edu/~hbennett/no.... 1/
Paturi, and Schneider for certifying NO instances of 3-SUM in roughly n^{3/2} time, beating the fastest known, roughly n^2-time deterministic algorithm: home.cs.colorado.edu/~hbennett/no.... 1/
Great idea, terrible name. Call it: dehydrated water
Finally ready to go public on my startup idea: powdered water.
Water bottles are heavy and cumbersome to carry? No longer a problem! A simple powder: just add water, you get water
Water bottles are heavy and cumbersome to carry? No longer a problem! A simple powder: just add water, you get water
January 23, 2026 at 8:44 AM
Great idea, terrible name. Call it: dehydrated water
Reposted by William Umboh
Very happy to see this paper "Prior-independent and Subgame Optimal Online Algorithms" in print, and looking forward to my coauthor Anant Shah presenting it at #ITCS2026 in Milan next week.
drops.dagstuhl.de/entities/doc...
drops.dagstuhl.de/entities/doc...
Prior-Independent and Subgame Optimal Online Algorithms
drops.dagstuhl.de
January 23, 2026 at 8:18 AM
Very happy to see this paper "Prior-independent and Subgame Optimal Online Algorithms" in print, and looking forward to my coauthor Anant Shah presenting it at #ITCS2026 in Milan next week.
drops.dagstuhl.de/entities/doc...
drops.dagstuhl.de/entities/doc...