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.

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!

> 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

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.

Buy my free book!

https://3dpancakes.typepad.com/ernie/2019/06/buy-my-free-book.html

Planar point sets determine many pairwise crossing segments: https://arxiv.org/abs/1904.08845

János Pach, Natan Rubin, and Gábor Tardos make significant progress on whether every \(n\) points in the plane have a large matching where all edges cross each other. A 1994 paper by Paul Erdős and half a dozen others only managed to prove this for "large" meaning \(\Omega(\sqrt{n})\). The new paper proves a much stronger bound, \(n/2^{O(\sqrt{\log n})}\) (Ryan Williams' favorite function).

EU falsely calls Internet Archive's major collection pages, scholarly articles, and copies of US government publications "terrorism" and demands they be taken down from the internet: https://blog.archive.org/2019/04/10/official-eu-agencies-falsely-report-more-than-550-archive-org-urls-as-terrorist-content/

(see also https://boingboing.net/2019/04/11/one-hour-service.html).

The EU is about to vote to require terrorism takedowns to happen within an hour, and these requests are coming on European times when all Internet Archive employees (in California) are asleep, making manual review of these bad takedowns difficult.

Another application of layered $H$-partitions: Planar graphs have bounded non-repetitive chromatic number.

https://arxiv.org/abs/1904.05269

Thue colourings and queue layouts of planar graphs are problems that I've thought about for several years. It's satisfying to see both problems solved, within weeks of each other.

A few weeks ago, I posted a photo of some happy people who had just proven a theorem a few minutes earlier.

That theorem appears in the arXiv today and the theorem is the title of the paper: Planar Graphs Have Bounded Queue Number.

https://arxiv.org/abs/1904.04791

More important than theorem though, is the tool used to prove it: layered $H$-partitions of small layered width where $H$ has small treewidth.

Expect another result tomorrow: Planar Graphs Have Bounded Nonrepetitive Chromatic Number.

Professor of Computer Science at Carleton University

Joined Oct 2018