The program chairs told me today that my new paper "Finding Relevant Points for Nearest-Neighbor Classification", https://arxiv.org/abs/2110.06163, has won the best paper award of the SIAM Symposium on Simplicity in Algorithms (SOSA22). Woo!

In other news, the lists of accepted papers at both SOSA and SODA are now up: see https://www.siam.org/conferences/cm/program/accepted-papers/sosa22-accepted-papers and https://www.siam.org/conferences/cm/program/accepted-papers/soda22-accepted-papers

Can a convex polyhedron have an odd number of faces, all congruent? https://mathoverflow.net/q/406120/440

If so the faces would have to all be kites, per comments at the link. Which raises the question: can a convex polyhedron with congruent kite faces avoid being either a trapezohedron (https://en.wikipedia.org/wiki/Trapezohedron) or formed from deltahedron (a polyhedron with equilateral triangle faces) by subdividing each triangle into three kites? Both automatically have evenly many faces.

Square-difference-free set (https://en.wikipedia.org/wiki/Square-difference-free_set), now a Good Article on Wikipedia.

As the name suggests, these are sets of integers no two of which differ by a square. My favorite is the losing positions in subtract-a-square (https://en.wikipedia.org/wiki/Subtract_a_square), where each move removes a square number of coins from a pile of coins, winning by taking the last coin.

This general class of sets and the subtract-a-square set have \(o(n)\) elements up to \(n\), but their maximum density remains unknown.

I haven't been using my office desktop Mac much because I haven't been into my office much, so it took me a while to pay attention to the fact that much of its networking had recently broken. Here's why: https://eclecticlight.co/2021/09/21/el-capitan-and-older-mac-os-x-are-about-to-have-a-security-certificate-problem/

It was still running OS X El Capitan (10.11.6) and a crucial top-level certificate expired. The machine is too old (late 2009) for the latest OS X but it looks like I can and should upgrade to High Sierra, 10.13. So much for getting anything else accomplished today...

Rarely is the question asked: Are math papers getting longer?

https://blogs.ams.org/beyondreviews/2021/10/14/are-math-papers-getting-longer/

Following earlier work by Nick Trefethen, Edward Dunne provides some data suggesting that (for certain journals, at least, and not the ones with page limits) the answer is yes. I'm not convinced by the suggested explanation that it's because they are taking more effort to explain "connections with other work", though: is that really a big enough fraction of most papers?

New blog post: Relevant neighbors, https://11011110.github.io/blog/2021/10/13/relevant-neighbors.html

It's triggered by my new arXiv preprint (and SOSA 2022 paper) "Finding Relevant Points for Nearest-Neighbor Classification", https://arxiv.org/abs/2110.06163, but really the content of the post is more closely related to earlier work by @bremner @patmorin and their coauthors.

Mathematics, morally (Eugenia Cheng, 2004): http://eugeniacheng.com/wp-content/uploads/2017/02/cheng-morality.pdf, via https://news.ycombinator.com/item?id=28816050

Somehow I hadn't run across this before. It argues that much philosophy of mathematics is irrelevant to practice ("You can’t tell from somebody’s mathematics if they are a fictionalist, a rationalist, a platonist, a realist, an operationalist, a logicist, a formalist, structuralist, nominalist, intuitionist.") and instead considerations of the right way of handling certain topics are more central.

So there's this thing going around about how

\[

\sum_{n=1}^4 2n

\]

is just a for-loop.

I mean, yes, sort of, but a sum is not a for-loop. For one, there's no requirement to sum the thing in a particular order, whereas a for-loop usually has a definite, procedural order defined. For-loops do a lot more things than what we usually want to express with Greek letters.

There's other ways in which the analogy breaks down.

Mathematicians prove melting ice stays smooth: https://www.quantamagazine.org/mathematicians-prove-melting-ice-stays-smooth-20211006/

The headline is a little overstated: you're probably familiar with thin necks of ice melting to sharp points at the instant they separate. But these singularities are instantaneous: mathematical models of ice stay smooth for all but a measure-zero set of times.

Original paper: "The singular set in the Stefan problem", Alessio Figalli, Xavier Ros-Oton, Joaquim Serra, https://arxiv.org/abs/2103.13379; see also https://en.wikipedia.org/wiki/Stefan_problem

Why Do Bees Make Rhombic Dodecahedrons? https://www.youtube.com/watch?v=QFj-hF8XDQ0

Nice video from Matt Parker (Stand-up Maths) on why bees usually end the cells of their honeycombs with rhombic dodecahedron faces, why this isn't the optimal solution to fitting two layers of cells together (in terms of minimum wax usage), and why it isn't reasonable to expect bees to find exact optima for this problem.

If I have to quibble with something, though, it's his plural. It's not wrong, but see https://books.google.com/ngrams/graph?content=dodecahedrons%2Cdodecahedra

The first physical models of the hyperbolic plane, made in 1868 by Beltrami: http://hyperbolic-crochet.blogspot.com/2010/07/story-about-origins-of-model-of.html, blog post by Daina Taimiņa from 2010.

Maybe you could make something like this by wrapping and stretching a disk of wet paper in a roll around a pseudosphere (https://en.wikipedia.org/wiki/Pseudosphere)? The rolled-up photo of Beltrami's model suggests that he did that.

Via http://www.open.ac.uk/blogs/is/?p=731 which shows this as a tangent to a story about triangulated polygons, frieze patterns, and the Farey tessellation.

University System of Georgia moves to gut tenure: https://www.insidehighered.com/news/2021/10/04/tenure-under-threat-georgia

The proposed new policy includes procedures for removal of tenure under certain enumerated grounds, including failure to perform their jobs (this is pretty normal) but then adds a massive escape clause in which the board of regents can remove tenured faculty at any time as long as their reason for doing so is not one of the enumerated ones.

Non-concentration of the chromatic number of random graphs: https://gilkalai.wordpress.com/2021/10/03/to-cheer-you-up-in-difficult-times-32-annika-heckels-guest-post-how-does-the-chromatic-number-of-a-random-graph-vary/

Uniformly random graphs, \( G(n,1/2) \) in the Erdős–Rényi–Gilbert model, turn out to have chromatic numbers that, for infinitely many \(n\), are spread over roughly \(\sqrt n\) values. But there are weird fluctuations so that, conjecturally, for some \(n\) the concentration is much tighter, more like \(n^{1/4}\).

Interested to see a familiar-looking graph drawing as one of the answers to the prompt "multiplicity" for the first entry in Mathober 2021, https://fractalkitty.com/2021/10/02/mathober-2021-begins/

It's a multigraph formed by a triangle with tripled edges, and looks a lot like the drawing https://commons.wikimedia.org/wiki/File:Multigraph-edge-coloring.svg I made for https://en.wikipedia.org/wiki/Shannon_multigraph, prettied up by making an infinitely recessing sequence of these drawings rather than just one.

Good choice for multiplicity.

Every invertible function computable both ways in polynomial time has polynomial-size reversible logic circuits, using extra "dummy" values that are 0 on both input and output (Jacopini, Mentrasti, & Sontacchi, https://doi.org/10.1137/0403020).

Theorem: No circuit of reversible gates of arity less than \(n\), without dummy values, can compute \(n\)-bit 2's-complement negation.

Proof: Each gate performs an even permutation on the \(2^n\) inputs, but negation is an odd permutation. #ProofInAToot

- Home page
- https://www.ics.uci.edu/~eppstein/

I'm a computer scientist at the University of California, Irvine, interested in algorithms, data structures, discrete geometry, and graph theory.

Joined Apr 2017