Taylor Smith

Happy X-Ring Day!

December 3rd marks the anniversary of the Feast of St. Francis Xavier, also known as X-Ring Day to the #StFX community.

Congratulations to all who are receiving their rings today!

A screenshot of part of an email I received. The greeting reads "Good Morning Benevolent Professor".

There's a lot of discourse lately around whether PhD holders should be using the title "doctor" (they should), but amidst all that, I've discovered my new favourite title.

My hand holding a shortbread cookie in the shape of an airplane. There are red sprinkles in the pattern of the survivorship bias plane.

A plate of the same cookies.

Does anyone want a survivorship bias shortbread

Pope stands holding a baseball bat on a plane

Finally getting some theological clarity on the ethics of reclining in one’s plane seat

Nope, it's the first letter of the LCC class! Same system that most academic libraries use to sort books, though I haven't totally gone off the deep end and sorted my library the same way. Yet.

I once asked a bookseller at a large indie store how many people would have to buy a book for it to get the attention of the store buyer and cause an additional order and they said: Three.

A pie chart of books in my personal library sorted by LCC classification. The largest proportion of books (34.7%) fall under the "Language and Literature" category. The next-largest categories are "Science" (28.0%), "History of the Americas" (9.8%), and "Social Sciences" (5.5%).

Speaking of my library, I'm the type of person who maintains (more out of necessity, at this point) a spreadsheet of all my books, which means I'm also the type of person who adds each book's LCC number to this spreadsheet. So if you're curious about the makeup of my library, here it is.

This piece also gave me a new response to anyone who asks me whether I've read all of the books I own: "I’ve opened all of them (mostly)."

"...for me these titles represent the knowledge I’m anxious to acquire but which mortality prevents me from ever fulfilling."

Considering my own personal library only recently surpassed the 1000-volume mark, it seems pretty serendipitous to come across this piece published just yesterday!

How CBC News will use AI responsibly to benefit our journalism — and keep your trust | CBC News CBC is launching a new campaign aimed at reminding Canadians how our journalism can provide a safe harbour from the fake news and AI-generated content roiling through our feeds. As the campaign begins...

This kind of transparency is to be commended:

“human oversight is mandatory; AI is the tool, never the creator; final editorial judgment, fact-checking and accountability always rest with our journalists; our journalistic standards must be met at all times; …”

www.cbc.ca/news/editors...

I have this really hard-to-drop habit of using the word "circuitous" in class, pronouncing it "sir-kit-OO-us" (almost as if by surface analysis), and only remembering after I get back to my office that it ought to be pronounced "sir-KYU-i-tuss".

Once again starting to write a book in the only sensible way, viz, by thinking up a title and then working backwards from there to design the cover, construct the page layout, and make some key choices about the typography. Eventually I will begin to fill in the content. I am a very rational person.

Chrome pointing out how much RAM it can use

I still distinctly remember one professor in my first year of undergrad mentioning how he had "grokked" something, and I'm so mad that I can't pass down that term to my students now without having it be misinterpreted.

I don't remember everything from the one cryptography course I took during my master's degree all those years ago, but I feel like k-out-of-n secret sharing schemes aren't ideal when k = n = 3.

Stavros and I are currently collaborating on more PRAX-related work with other colleagues, and I hope we can share more exciting results with you in the new year!

For those who like empirical evidence, we also include multiple experiments showing that, for varying parameters, the answer found by our PRAX algorithm is the correct answer with high probability. (We really tried to find instances where the PRAX algorithm would fail, but it was tough!)

2. Our paper also shows we can get efficient PRAX algorithms for approximately testing problems with samplable/tractable domains (even infinite ones). We show how to test 2D automaton universality/emptiness, whether a formula is a tautology, and whether a Diophantine equation has any solutions.

1. The PRAX algorithm from the original paper required a sample size quadratic wrt. the tolerance value ε. Our paper shows that we only need a sample size linear wrt. ε. This has a huge impact, as ε is a key factor in the algorithm's runtime!

Our paper asks: 1. Can we improve this algorithm, and 2. Can we apply it to other problems? Both questions have positive answers! For example, instead of approximately testing universality, we can approximately test emptiness: is an NFA language ε-close to being empty?

My coauthor, Stavros Konstantinidis, recently introduced polynomial randomized approximation (PRAX) algorithms to approximate solutions for the hard problem of testing NFA universality. Put simply, instead of asking if an NFA language is universal, is it ε-close to being universal?

The first page of my paper, "Improved Randomized Approximation of Hard Universality and Emptiness Problems", coauthored with Pantelis Andreou of Dalhousie University and Stavros Konstantinidis of Saint Mary's University.

Check out my latest paper in JALC! "Improved Randomized Approximation of Hard Universality and Emptiness Problems":
jalc.de/issues/2025/...
(arXiv link: arxiv.org/abs/2403.08707)
#TCSSky #MathSky

James Watson, dead at 97, was a scientific legend and a pariah among his peers James Watson, the co-discoverer of the structure of DNA who died Thursday at 97, was a scientific legend and a pariah among his peers.

A Sharon Begley byline, almost 5 years after her death.

Upon hearing the news James Watson had died, a STAT reporter said in our Slack, "I wish I could read what Sharon would have written."

Incredible news: Sharon in fact did pre-write a Watson obit. And it is masterful and excoriating.
🧪🧬🧫

(Speaking as myself and not as any particular hat-wearer: it’s a shame this peer-review precondition was put in place for surveys specifically, but it’s a bigger shame that bad actors required this to be put in place at all.)

Oh, no intent to make a direct comparison! Even for not-yet-peer-reviewed work, I feel one can put greater trust in a TCS survey being human-written vs. one in another area, possibly from some combination of the surveyed work being more technical to engage with, slower pace of publication, etc.

It reflects pretty positively on the state of TCS versus other areas that one can read a survey/review in SIGACT News or BEATCS and *not* have to worry whether it’s AI-generated slop!

Remarks on separating words The separating words problem asks for the size of the smallest DFA needed to distinguish between two words of length <= n (by accepting one and rejecting the other). In this paper we survey what is kn...

This is a really fun problem actually. Given two strings x and y, what is the smallest DFA that accepts x but rejects y?

cs.uwaterloo.ca/~shallit/Tal...

You kids and your six trig functions. Back in my day we had only one, and we used it for everything.
sin(θ)
sin(π/2 - θ)
sin(θ)/sin(π/2 - θ)
1/sin(θ)
1/sin(π/2 - θ)
sin(π/2 - θ)/sin(θ)

And hey, if you want to download the book directly from my website, you can do that too: taylorjsmith.xyz/tocopen/

Theory of Computing: An Open Introduction This book is suitable for courses on the theory of computing at both the undergraduate and graduate levels, and for self-study. Topics are introduced in a logical order: we begin with the simple finit...

Just added my book, "Theory of Computing: An Open Introduction" to OER Commons, and working on getting it listed in Canadian repositories too. One step closer to making education more open and accessible to everyone!
oercommons.org/courses/theo...