patmorin @patmorin@mathstodon.xyz
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.
A recent arXiv preprint on robust spanners. For any \(n\)-point set in \(\mathbb{R}ᵈ\), we show how to construct spanners with \(O(n\log²n\log\log n)\) edges so that, if you remove \(k\) vertices, the remaining graph is a spanner of \(n-(1+ε)k\) of its vertices.
https://arxiv.org/abs/1812.09913
We called these \((1+ε)k\)-robust spanners. Buchin, Har-Peled, and Olah have a much catchier name: 'a spanner for the day after'
New post: Gurobi versus the no-three-in-line problem
https://11011110.github.io/blog/2018/11/12/gurobi-vs-no.html
How well can a good but generic integer linear program solver stand up against 20-year-old problem-specific search code?
Two new arXiv preprints:
https://arxiv.org/abs/1811.03432
https://arxiv.org/abs/1811.03427
The first shows that if a graph \(G\) has a non-crossing straight-line drawing (a.k.a. Fáry drawing) in which some set \(S\) of vertices is drawn on a single line then, for any point set \(X\) of size \(|S|\), \(G\) has a Fáry drawing in which the vertices in \(S\) are drawn on the points in \(X\).
The second shows that, in bounded degree planar graphs, one can always find such a set \(S\) of size \(\Omega(n^{0.8})\).
