Turning Awardee Sir Tony Hoare passed away last Thursday at the age of 92. Jim Miles remembers.
10.03.2026 12:31
👍 1
🔁 1
💬 0
📌 0
Turning Awardee Sir Tony Hoare passed away last Thursday at the age of 92. Jim Miles remembers.
How I introduce interactive proofs to students: "if the input shouldn't be accepted, then the prover can never get the verifier to accept no matter what certificate it provides."
How I want to introduce interactive proofs to students:
Am I sleepy because of the time change, because of the wet, cold, cloudy weather outside, or simply because it’s Sunday?
An online seminar on formal languages & automata theory that always takes place at the same time on the same weekday had/has talks:
- last week at 10am my time
- in 2 weeks at 11am my time
- 3 weeks after that at 10am my time
Daylight saving is messing me up before it even happens.
A fascinating note by Don Knuth describing how Claude helped resolve a conjecture that he had posed for an upcoming chapter of TACP. I'm now worried that he will get distracted again, produce something incredible, and TACP will once again wither away :). www-cs-faculty.stanford.edu/~knuth/paper...
A screenshot of the current version (as of today) of the Wikipedia article on Atlantic City algorithms. The claim of the origin of the term has been removed, and the text has been cleaned up slightly.
A screenshot of the talk page for the Wikipedia article on Atlantic City algorithms. I published a note on this page detailing all of the same findings I describe in this thread.
I've updated the Wikipedia article to remove the false claim, and published a note on the article's talk page detailing my findings thus far.
Will I uncover the true origins of the term "Atlantic City"? I'm not sure. But I do know, like any sane academic, I won't let go of this hunt anytime soon.
His reply to my inquiry?
"I am not the originator of the term Atlantic City algorithms. The wiki stub article is erroneous."
Not what I was expecting! So now I'm well and truly stuck. It seems "Atlantic City" somehow appeared in the literature before 1996 and somehow attached itself to J. Finn.
The report didn't pan out, and my itch still wasn't scratched. So again, I did what any sane academic would do. I tracked down J. Finn through Google and emailed him directly.
He works as a teaching professor, though he keeps a low profile. He generously and quickly replied to me.
A screenshot of the cover page of Princeton EECS Technical Report 297, "Comparison of Probabilistic Tests for Primality", published in 1982 by James Finn.
So I did what any sane academic would do. I requested a copy from the one place on Earth that still verifiably had a copy: Princeton, where J. Finn got his PhD.
But, to my shock, this report didn't use the term "Atlantic City" at all! It talks about Las Vegas and Monte Carlo, but no Atlantic City.
Well, I'm not the type to take every claim at face value. I decided to do some digging. But how could I get my hands on a 44-year-old unpublished manuscript?
I discovered, in the references of one of the books, that J. Finn published a tech report in 1982 with the exact same title.
![An excerpt from Bach and Shallit's 1996 text "Algorithmic Number Theory". It reads "The name "Atlantic City" was first used by J. Finn [1982a]."](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:f6tvcgb4p6fmvinz23kus77k/bafkreibsv74arridrdrmogldzejtzmqhdn2brldv424k6quxxgulpnmdfq)
An excerpt from Bach and Shallit's 1996 text "Algorithmic Number Theory". It reads "The name "Atlantic City" was first used by J. Finn [1982a]."
An excerpt from Mollin's 2003 text "RSA and Public-Key Cryptography". It reads "The term "Atlantic City" was first introduced in 1982 by J. Finn in an unpublished manuscript entitled _Comparison of probabilistic tests for primality_."
A screenshot of an old version (Nov. 12, 2025) of the Wikipedia article on Atlantic City algorithms. It reads "The term "Atlantic City" was first introduced in 1982 by J. Finn in an unpublished manuscript entitled _Comparison of probabilistic tests for primality_."
If you checked Wikipedia, the article on these algorithms claimed for a long time that the term "Atlantic City" originated in an unpublished work of one "J. Finn" from 1982. This same claim appears elsewhere in the literature, going back to at least 1996 in a book on algorithmic number theory.
A photo of the waterfront at dusk in Atlantic City, New Jersey. Like Las Vegas, the large buildings are lit up in bright lights and neon and extend to the horizon, contrasting the darkening waves rolling on the shore.
For the sake of fixing definitions:
- Las Vegas algs. always give correct answers, but have unknown runtimes.
- Monte Carlo algs. have fixed runtimes, but give correct answers with prob. ≥ 0.5.
In the literature, you sometimes also find:
- Atlantic City algs., like Monte Carlo but with prob. ≥ 0.75.
A photo of Las Vegas at night. The grandiose buildings and attractions are all illuminated in bright lights and neon.
A photo of the Monte Carlo Casino at dusk. The Beaux-Arts architecture is tastefully illuminated from below, highlighting every detail and facet of the stonework, while a variety of pristine and polished supercars sits outside of the entrance.
I fear I've gone down a bit of a rabbit hole over the course of this past week. Read on...
Everyone (or at least, every computer scientist) knows there are two kinds of randomized algorithms: Las Vegas and Monte Carlo. But did you know there's a third? I did, or at least I thought I did.
The logo of the CIAA 2026 conference.
Please submit your research papers and join us at the 30th International Conference on Implementation and Application of Automata (CIAA 2026), to be held in Kingston, Canada from August 5 to 8, 2026!
Details: research.cs.queensu.ca/ciaa2026/
#tcssky #mathsky
The logo of the DCFS 2026 conference.
Please submit your research papers and join us at the 27th International Conference on Descriptional Complexity of Formal Systems (DCFS 2026), to be held in Kingston, Canada from August 9 to 11, 2026!
Details: research.cs.queensu.ca/dcfs2026/
#tcssky #mathsky
Other exciting news to close out the month: my university's now written an article about it!
Tim Houston continues his attack on the institutions that make this democracy worthwhile
Morning File by @timbousquet.bsky.social
Line drawing from Cambridge Latin Course - Metella and her cook Grumio hanging out. She is clearly very impressed with his cooking. Proper chef’s kiss.
Age verification? I know how Caecilius and his missus died
Image with purple text in a white box on yellow background Text: Townhall: Protecting Post Secondary Education in Nova Scotia A Conversation about Provincially Mandated Program Reviews and Bill 12
Why does the Nova Scotia government want to cost universities hundreds of thousands (if not millions) of dollars? Why have they spent almost half a million dollars on an American consulting firm?
Find out more tonight! Online town hall (zoom link on linked page below)
cocogov.org/blog/townhall/
Likewise, the composer for the 2024 Olympics in Paris set a high bar for whoever's tasked with the music for the 2030 Olympics in the French Alps. Combining orchestra with French house was just a stroke of brilliance.
Composers for the Olympics always seem to understand the assignment. This piece managed to bring together multiple Italian musical themes from across centuries, and the finale starting at 10:20 was a fantastic (pardon the pun) backdrop for each of the medal ceremonies.
Proud of Team Canada and proud to be Canadian 🇨🇦
Canadian Tire store in Ottawa. giant red triangles everywhere
in Canada we have a store called "Canadian Tire" and you're probably thinking "a store named after a tire definitely has a circle for a logo" but no, you're wrong. they chose a colossal red triangle
An illustration of my brand-new (digital) IEEE senior membership card, with appropriate personal details censored, of course.
Some exciting professional news this week: the IEEE has awarded me a senior status to go along with the growing number of gray hairs on my head.
Valentine’s Day: tiresome, expected to spend money to show one’s love, exclusive of single people
Flag Day: exciting, one can look at the flag for free, inclusive of everyone who appreciates waving fabric
Title: A Valentine’s Day experiment In an effort to test the efficacy of cupids arrows of desire. A placebo group is shot with regular arrows. Their injuries range from moderate to sever. Unexpectedly, romances struck up in hospital and lawyers’ waiting rooms create a "romance ratio" similar to that of magic arrows. However, once the cost of compensation claims is factored in, it is decided to discontinue.
A Valentine’s Day cartoon for @newscientist.com
(This is my extremely unsubtle way of hinting that I'm very receptive to collaborating with my complexity theory colleagues. I won't try to corrupt you too much by going on about the beauty of automata theory.)
Looking through the list of accepted papers for STOC 2026, I see a lot of impressive work, but also a huge emphasis on algorithms+complexity. It'd be nice to publish in one of these big theory conferences, but I don't imagine Eurotheory like automata+languages is what they're targeting anymore.
I heard that, in the past, evaluation groups met in-person in Ottawa. It's kind of a shame things have shifted online - I think we as a society ought to agree to move past MS Teams once and for all.
It's my first day of participating in NSERC Discovery Grant deliberation meetings, and I'm surviving so far! But check in with me again by the end of the week and we'll see if my answer stays the same.