The program chairs told me today that my new paper "Finding Relevant Points for Nearest-Neighbor Classification", 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 siam.org/conferences/cm/progra and siam.org/conferences/cm/progra

You might know about regular numbers (en.wikipedia.org/wiki/Regular_, of the form $$2^i\cdot3^j\cdot5^k$$) from Babylonian mathematics, music theory, Plato, or as a test case for functional programming. But did you know that they come up in biology, as numbers of years between mass flowering in certain types of bamboo? See Veller, Nowak and Davis, "Extended flowering intervals of bamboos evolved by discrete multiplication", doi.org/10.1111%2Fele.12442, via Andrey Zabolotskiy at oeis.org/A051037

Can a convex polyhedron have an odd number of faces, all congruent? 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 (en.wikipedia.org/wiki/Trapezoh) 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 (en.wikipedia.org/wiki/Square-d), 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 (en.wikipedia.org/wiki/Subtract), 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: eclecticlight.co/2021/09/21/el

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?
blogs.ams.org/beyondreviews/20

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, 11011110.github.io/blog/2021/1

It's triggered by my new arXiv preprint (and SOSA 2022 paper) "Finding Relevant Points for Nearest-Neighbor Classification", 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.

According to the SODA web site siam.org/conferences/cm/confer, SIAM has decided that their conferences will be hybrid through July. So if (like me) you wanted to participate in SODA/SOSA/ALENEX/APOCS, but were worried about planning a trip to Virginia with another predicted winter wave of Covid, now you can stay home and conference safely. Or, if you feel hybrid conferences are problematic and organizers should do one or the other but not both, now you have another reason to be annoyed.

Cynthia Rudin wins major award with silly name for her work on machine learning systems that learn to predict behavior using simple, interpretable, and transparent formulas: pratt.duke.edu/about/news/rudi

The SIGACT Committee for the Advancement of Theoretical Computer Science is collecting information on women in theoretical computer science; if this is you, please see thmatters.wordpress.com/2021/1 for details of how to be counted.

Mathematics, morally (Eugenia Cheng, 2004): eugeniacheng.com/wp-content/up, via news.ycombinator.com/item?id=2

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.

0xDE boosted

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: quantamagazine.org/mathematici

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, arxiv.org/abs/2103.13379; see also en.wikipedia.org/wiki/Stefan_p

Why Do Bees Make Rhombic Dodecahedrons? youtube.com/watch?v=QFj-hF8XDQ

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 books.google.com/ngrams/graph?

The first physical models of the hyperbolic plane, made in 1868 by Beltrami: hyperbolic-crochet.blogspot.co, 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 (en.wikipedia.org/wiki/Pseudosp)? The rolled-up photo of Beltrami's model suggests that he did that.

Via 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: insidehighered.com/news/2021/1

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: gilkalai.wordpress.com/2021/10

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}$$.

New blog post, "Generating fibbinary numbers, three ways": 11011110.github.io/blog/2021/1

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

It's a multigraph formed by a triangle with tripled edges, and looks a lot like the drawing commons.wikimedia.org/wiki/Fil I made for en.wikipedia.org/wiki/Shannon_, 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, 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.

Show older

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