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.

newsroom.publishers.org/resear

Apparently the ACM has signed onto a letter opposing a US government policy to require the free distribution of all federally funded research. WTF?

change.org/p/association-for-c

Rant: Commercial publishers suck. Wiley broke my name in a recent article. Even JoCG, which leaves formatting almost entirely up to authors, avoids this.

Luckily, most of the world doesn't have access to the official version so they will see the arXiv version instead.

Pat Morin boosted
Pat Morin boosted

Planar point sets determine many pairwise crossing segments: 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).

Pat Morin boosted

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: blog.archive.org/2019/04/10/of

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.

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.

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.

Pat Morin boosted

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: focs2019.cs.jhu.edu/awards/

For the committee and its report, see ics.uci.edu/~irani/safetoc.htm

Pat Morin boosted

Photos from a recent computational geometry workshop in Barbados: 11011110.github.io/blog/2019/0

Pat Morin boosted

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)

This is what progress in mathematics looks like.

Pat Morin boosted

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: cbc.ca/news/health/cihr-gender

Pat Morin boosted

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? retractionwatch.com/2019/02/07

Pat Morin boosted

@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.

Pat Morin boosted

New post: Orientations of infinite graphs, 11011110.github.io/blog/2019/0

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.

arxiv.org/abs/1811.00816

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

arxiv.org/pdf/1901.05594.pdf

Show older

The social network of the future: No ads, no corporate surveillance, ethical design, and decentralization! Own your data with Mastodon!