A quasi-polynomial algorithm for well-spaced hyperbolic TSP: arxiv.org/abs/2002.05414

This new preprint by Sándor Kisfaludi-Bak (accepted to SoCG) just came out and caught my attention. TSP is NP-hard for Euclidean points or close-together hyperbolic points. This paper shows that it's much easier when the points are widely spaced in the hyperbolic plane. The idea is to separate the input by a short line segment that the solution crosses few times and apply dynamic programming.

One of the first non-trivial straight skeletons (as a roof model), from _Kotirte Ebenen (Kotirte Projektionen) und deren Anwendung_ by Gustav A. von Peschka (1877). See en.wikipedia.org/wiki/Straight

Consider the algorithm "M(x): if x<0 return -x, else return M(x-M(x-1))/2". This algorithm terminates for all real x, though this is not so easy to prove. In fact, Peano Arithmetic cannot prove the statement "M(x) terminates for all natural x". Paper to come! Joint work with @jeffgerickson and @alreadydone


In which we show that the knots K13n592 and K15n41127 (pictured) both have stick number 10. These are the first non-torus knots with more than 9 crossings for which the exact stick number is known.

Update on the Safe ToC initiative: windowsontheory.org/2019/08/30

Sandy Irani describes progress in combatting harassment and discrimination at theoretical computer science conferences, and calls for volunteer advocates to serve as contact points at conferences.

$400 online calculus course for full (transferrable) credit at Pitt: outlier.org/calculus

While it's tempting to call this a MOOC, but it's not open. Let's give them the benefit of the doubt and call it a MOC.

A generic closed curve that is not isotopic to any 36-gon, derived from Ringel's non-stretchable arrangement of 9 pseudolines, which was derived in turn from Pappus's hexagon theorem.

(Written when the author was 11, and submitted when he was 12. See the affiliation "Jr. High School 246" on the last page of the article, and the letter from the author's mother on page 91 of the same issue.)

aeon.co/essays/how-european-sa — "Soon after this, mariners started cramming for exams. Instead of paying 36 florins for an entire winter of lessons, Amsterdam-based mariners paid just 6 florins for a crash course focused on the oral and written portions of the tests. Later manuscript workbooks confirm this strategy: students often focused on the questions they knew would be on their exam. Teachers at the close of the 17th century were already ‘teaching to the test’."

Mental Health in the Mathematics Community, by Mikael Vejdemo-Johansson, Justin Curry, and Julie Corrigan, in the most recent Notices of the AMS.

Consider unfollowing that person that always leaves you feeling worse about things.

Sorry, that's Panckoucke with a P. (I have no idea where that M came from.)

Here's his actual theorem statement: "Every rectilinear polygon can be split into as many triangles as it has sides, minus two."

Show thread
Show more

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