Taylor Smith
@taylorjsmith
🇨🇦 Theoretical computer scientist. Assistant professor at @stfx-university.bsky.social. Website: taylorjsmith.xyz.
Some researchers in the hotter or faster-moving fields might not blink twice at this, but as an early-career researcher doing math-heavy work that takes time to get picked up by others, this was pretty neat to see on Google Scholar.
Why the unary case? Well, a lot is known about decidability (and complexity) for general 2D automata, but not as much for the unary variant. Also, almost nothing is decidable for 2D automata that can move in 4 directions through the input, but we recover a bit by restricting input head movement.
If you can't get enough automata theory, you'll love the companion volume also due out later this summer. Your bookshelf will be empty without it!
2024: I'm invited to the GG's Performing Arts Awards as the guest of an honouree. Okay, I should expect to see the GG then. At the reception, I turn and unexpectedly find Mary Simon right in front of me. Her aide-de-camp was between us, but my seat's a few rows behind her on the balcony.
2013: I'm an undergrad at Western. I see there's a different flag flying from the University College tower, a blue one instead of the usual Canadian flag. Soon after, I walk by a sleek black sedan, parked with the same flag on the hood. I unknowingly just walked by David Johnston in his car.
Just received the cover for a hot new title dropping later this summer. Make sure to get your copy, it's a gripping read.
What's even more unhinged is the reaction by the former EiC of CACM. This behaviour is seriously making me question the utility of renewing my @acm.org membership going forward.
Thanks to Peter Hacker, I've just discovered a brand new and innovative way to teach tree traversals in my algorithms class: introduce students to Wittgenstein's Tractatus. Course evaluations be damned.
Received all of the camera-ready submissions and getting ready to submit the two conference proceedings volumes I've been working on for the past eight months!
There's no easy way to condense everything in the paper into posts on here, so I encourage you to read the paper itself. I tried to make the material as accessible as possible to a general math/CS audience. (Plus, there are lots of pictures, and who doesn't like that?)
Now, count all primitive 2D words over a binary alphabet; call this \psi_2(m,n). We get a table with some rather fast-growing values. But if we focus on the second row (i.e., the values of \psi_2(2,n)), the number of 2xn primitive 2D words is the same as the number of exact-period-n pedal triangles!
2. A pedal triangle is constructed by dropping altitudes from a triangle's vertices to intersect the opposite side, then joining the intersection points. We can iterate the process: if a triangle T is similar to its nth pedal but not any other, we say it has exact pedal period n.
Learning that 2014 was apparently a huge year for discrete mathematicians, for some reason.
One of my favourite parts of teaching TCS is motivating concepts in a way that goes beyond just the definitions. When we cover grammars, I mention Pāṇini and his work on Sanskrit. Today, I wrote this fun little question. Can anyone familiar with Sanskrit tell me if I made any embarrassing mistakes?
Either Best Buy is really diversifying their product offerings, or I’ve done something very strange to whatever recommendation algorithm served up this ad.
This is something I've had to contend with in my own courses. I regularly tell students about Greibach (grammars), Goldwasser (zero-knowledge proofs), and Williams (matrix multiplication), but so many results in the core curriculum stem from the same group of guys and I don't know how to improve it.
That was my second-ever conference (with my first-ever taking place in Halifax the week before)! See you again in August, perhaps?
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.
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.
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.
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.
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.
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.
I had someone share with me some posts from a different website. I was just sitting here minding my own business, what'd I do to be attacked like this?
Excited to soon be able to add to my (currently very small) collection of math-related Magic cards that I put on my office door.
Recent news led me to revisit an old cartoon I used to love watching (for some reason) as a kid. I can't believe how well this 25-year-old clip has held up.
For what it's worth, I tangled with the same year-of-publication question until I came across this (fascinating!) footnote in Copeland's book "The Essential Turing", and it sounded authoritative enough for me to take it as gospel.