• ## Relevant neighbors

I have a new preprint, “Finding Relevant Points for Nearest-Neighbor Classification”, arXiv:2110.06163, to appear in January at the SIAM Symposium on Simplicity in Algorithms (SOSA22). It’s about points in Euclidean spaces of dimension three or more, but I thought it would make a good warm-up to discuss here the one-dimensional version of the same problem, solved (together with the 2d version) by Bremner, Demaine, Erickson, Iacono, Langerman, Morin, and Toussaint in their paper “Output-sensitive algorithms for computing nearest-neighbour decision boundaries”, Discrete Comput. Geom. 2005.

• ## Generating fibbinary numbers, three ways

I just added to Wikipedia two articles on the Jordan–Pólya numbers and fibbinary numbers, two integer sequences used in my recent paper on Egyptian fractions. Jordan–Pólya numbers are the products of factorials, while the fibbinary numbers are the ones with binary representations having no two consecutive 1’s. The OEIS page on the fibbinary numbers, A003714, lists many ways of generating this sequence algorithmically, of which most are boring or slow (generate all binary numbers and test which ones belong to the sequence; you can test if a variable x is fibbinary by checking that x&(x>>1) is zero). I thought it might be interesting to highlight two of those methods that are a little more clever and generate these numbers in small numbers of operations.

• ## Multilayer tiles

You’re probably familiar with the fact that you can draw a convex octagon with corners in an integer grid, fitting into a $$3\times 3$$ square. It’s not regular, because its side lengths alternate between $$1$$ and $$\sqrt 2$$, but it has the same angles as a regular octagon and looks close enough to it for some purposes.

• ## Which integer sequences form denominators of Egyptian fractions?

I have a new paper out: “Egyptian Fractions with Denominators from Sequences Closed Under Doubling”, in the Journal of Integer Sequences. (There should also be an arXiv version soon but despite my long association with arXiv they made me get an endorser before I could upload to the number theory category, slowing down my submission there.)

• Does anyone but me find it odd that car tire sizes are measured in millimeters for width, inches for inner radius, and a dimensionless number expressed as a percentage for (difference between inner and outer radius)/width Imagine the fun if we tried to do solid geometry this way.
• ## Congratulations, Dr. Maxwell!

I took part today in the successful dissertation defense of Will Maxwell, a student of Amir Nayyeri and Cora Borradaile at Oregon State University. Will has also visited me at UC Irvine, and I’ve worked with him on two papers, on low-stretch spanning trees and Hanoi graph treewidth. But his dissertation has a different focus, his work on generalizations of graph algorithms to higher-dimensional topological spaces.

• Finding a stationary point of a smooth function (as can be done, eventually, by gradient descent) is complete for $$\mathsf{PPAD}\cap\mathsf{PLS}$$ ($$\mathbb{M}$$, via) as Fearnley, Goldberg, Hollender, and Savani write in STOC 2021 best paper “The complexity of gradient descent”. Gradient descent finds local minima quickly in many cases, but can be slow to navigate shallow labyrinthine optimization landscapes; this result suggests that there are unlikely to be much better shortcuts.