> 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

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.

Sandy Irani (one of my colleagues at UCI) is being given the IEEE TCMF Distinguished Service Award for her work chairing the ad hoc committee to combat harassment and discrimination in the theory of computing community, and for then getting many theory conferences to follow its recommendations: http://focs2019.cs.jhu.edu/awards/

For the committee and its report, see https://www.ics.uci.edu/~irani/safetoc.html

Photos from a recent computational geometry workshop in Barbados: https://11011110.github.io/blog/2019/04/07/photos-from-barbados.html

Breaking news in the algorithmic/arithmetic world!

Integer multiplication in time O(n · log n). [1]

It means you can multiply two n-bits integer using roughly n log n operations. It's a *very* important problem because a lot of mathematical software rely on efficient integer multiplication.

It breaks the last best known algorithm [2] (Schönhage–Strassen), that was in O(n · log n · log log n)

[1] https://hal.archives-ouvertes.fr/hal-02070778/document

[2] https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm

A comparison of two parallel Canadian grant funding tracks shows that when reviewers are told to focus on the investigator rather than the proposed investigation, they are significantly more biased against women: https://www.cbc.ca/news/health/cihr-gender-bias-1.5009611

How to handle journal referees who ask authors to add unjustified citations to their own papers? Is their misbehavior protected by the anonymity of peer review or can they be publicly named and shamed? https://retractionwatch.com/2019/02/07/the-case-of-the-reviewer-who-said-cite-me-or-i-wont-recommend-acceptance-of-your-work/

@patmorin So the most recent publication on the tripod problem itself is not the most up to date? That's disappointing but maybe, given the history of parallel rediscovery, not surprising.

New post: Orientations of infinite graphs, https://11011110.github.io/blog/2019/01/17/orientations-infinite-graphs.html

In many cases the existence of an orientation with desired properties can be reduced to its existence in finite subgraphs, using a mathod from Rado (1949).

Recently, Bekos et al made a major breakthrough, showing that planar graphs of bounded degree have bounded queue number.

https://arxiv.org/abs/1811.00816

We were able to generalize this to bounded degree bounded genus graphs.

Professor of Computer Science at Carleton University

Joined Oct 2018