A quasi-polynomial algorithm for well-spaced hyperbolic TSP: https://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.

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

https://arxiv.org/abs/1909.06947

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.

Fusible Numbers

Article by Erickson, Jeff

In collections: Unusual arithmetic, Easily explained

URL: http://www.mathpuzzle.com/fusible.pdf

Entry: http://read.somethingorotherwhatever.com/entry/Erickson

CRA finally copies MathJobs: https://cra.org/cv-database/

How to peel self-intersecting onions: https://arxiv.org/abs/1909.00263

Update on the Safe ToC initiative: https://windowsontheory.org/2019/08/30/update-on-the-safe-toc-initiative-guest-post-by-sandy-irani/

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: https://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.

(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.)

https://www.ams.org/journals/notices/201907/rnoti-p1079.pdf

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

CS professor at Illinois

Joined May 2017