Pat Morin @patmorin@mathstodon.xyz
Professor of Computer Science at Carleton University
Joined Oct 2018
Today I'm heading to the clinic to receive my first dose of the AstraZeneca vaccine. Ignoring the possibility that it might save me from death by covid, the worst case estimates suggest that this increases my odds of dying in the next 365 days from 1/444 to 1/442. I can live with that.
An implementation of the Product Structure Theorem for planar graphs, in Python:
https://github.com/patmorin/lhp
Not exactly industrial-strength, and leans towards simplicity over performance. Still, it can decompose 100k-vertex triangulations in a few seconds. I'm open to feature requests.
Good to see that the pandemic hasn't affected every aspect of our lives. SoDA is still charging exorbitant registration fees:
Tip: When you "attend" an online conference, book everything off: teaching, meetings, etc. I'm currently "attending" a conference and have only gotten to see one live session since I've been in meetings or teaching the rest of the time.
Pat Morin
boosted
New blog post, Hex, books, and queues: https://11011110.github.io/blog/2020/11/10/hex-books-queues.html
And new arXiv preprint, Stack-number is not bounded by queue-number (with Vida Dujmović, Robert Hickingbotham, Pat Morin, and David R. Wood), https://arxiv.org/abs/2011.04195
Banff Alberta, Election Day, 2016, Alan Frieze and Luc Devroye watching election results arrive.
How many integer colours are sufficient to colour an \(n\)-vertex planar graph so that the maximum colour encountered along any path of length at most 2 occurs only once along that path? It turns out that the correct answer is \(\Theta(\log n/\log\log\log n)\). The triple-log comes from the fact every planar graph is contained in the strong product of a planar 3-tree and a very simple graph.
Pat Morin
boosted
if you like well-quantified risk info
https://www.erinbromage.com/post/the-risks-know-them-avoid-them
Congratulations to my (now former) student, Luís Fernando Schulz Xavier da Silveira, who successfully defended his PhD thesis titled Turán Triangles, Cell Covers, Road Placement and Train Scheduling on Monday.
This is the first thesis defense I've taken part in where no two participants were in the same room.
Here's an option, Elsevier: Open up your catalogues for the duration of the crisis (at least):
Today the was the first day of three weeks (at least) of home school. This morning was intro to algebra for my nine year-old. Addition, subtraction, and number-recognition for my 5 year old. This afternoon was bicycling and stump-jumping. :)
Online investment site today: "We're currently experiencing a display issue. Your account earnings may appear incorrectly. We're working on a fix and everything will be back to normal shortly."
No, I don't think that's a display issue...
Congratulations to our student (cosupervised with Vida Dujmović) Céline Yelle who just masterfully defended her Master's thesis titled Stack Number, Track Number, and Layered Pathwidth.
The thesis contains two results:
1. \(\mathrm{sn}(G) \le 4\mathrm{lpw}(G) \)
2. \(\mathrm{tn}(G)\le 3\) implies \(\mathrm{lpw}(G)\le 4\).
Planar graphs (and related families of graphs) have \((1+o(1))\log n\)-bit adjacency labelling schemes. Equivalently, there is a graph with \(n^{1+o(1)}\) vertices that contains every \(n\)-vertex planar graph as an induced subgraph.
https://arxiv.org/abs/2003.04280
The proof combines our year-old product structure theorem with binary search trees!
Pat Morin
boosted
> We have computed the very first chosen-prefix collision for SHA-1. In a nutshell, this means a complete and practical break of the SHA-1 hash function, with dangerous practical implications if you are still using this hash function. To put it in another way: all attacks that are practical on MD5 are now also practical on SHA-1. Check our paper here for more details.
And a response from the president of the ACM: https://www.acm.org/about-acm/statement-regarding-open-access
More information about ACM's opposition to mandatory open access of publicly-funded research:
Apparently the ACM has signed onto a letter opposing a US government policy to require the free distribution of all federally funded research. WTF?
https://www.change.org/p/association-for-computing-machinery-acm-support-open-access?signed=true
Pat Morin
boosted
the American Mathematical Society just published a free ebook called Living Proof, a collection of mathematicians recounting their often turbulent paths to where they are now. i've read a few of the stories and i think this is an amazing read, not just for scholars of math, but for anyone who is doing something where they simply don't feel "smart enough" to succeed. success is often made up of struggle and failure; this can be difficult to remember in our current times.
Professor of Computer Science at Carleton University
Joined Oct 2018
