-
Blooming caterpillars
When a polyhedron’s surface can be cut and flattened into a polygon, the resulting flattened shape is called a net, and the system of cuts is called an unfolding. A familiar example is the Latin cross of six squares, unfolded after cutting seven edges of a cube. This example is an edge unfolding: its cuts are on edges of the polyhedron, and the resulting net consists of faces of the polyhedron connected edge-to-edge. We don’t know whether all convex polyhedra have edge unfoldings (they do always have unfoldings of other types). We also don’t know whether every net has a blooming, a continuous motion from the cut surface of the polyhedron to its flat unfolded state, throughout which the moving surface avoids crossing itself and stays flat except at the uncut edges of the polyhedron. (Nets do always have continuous flattening motions if bending the faces is allowed; see my work on unfolding simply-connected developable surfaces). And when a net does have a blooming, we don’t know whether we can restrict the blooming to only increase dihedral angles monotonically.
-
Visualizing the Henson graph
When visualizing finite graphs, you can simply draw the whole graph. But that doesn’t really work for infinite graphs. What you need to visualize is not so much the graph itself, but the rule by which it is constructed.
-
Linkage with incoming gloom
- New book-sorting algorithm almost reaches perfection (\(\mathbb{M}\)): Quanta on the list labeling problem, based on “Nearly Optimal List Labeling” by Bender, Conway, Farach-Colton, Komlós, Koucký, Kuszmaul, and Saks, from FOCS 2024.
-
Linkage
- Lance Fortnow’s pet peeve (\(\mathbb{M}\)): A speaker who cites their own work using only their initial instead of their name.
-
Twenty questions with a random liar
I have another new arXiv preprint: “Computational geometry with probabilistically noisy primitive operations”, arXiv:2501.07707, with Mike Goodrich and his student Vinesh Sridhar. Many computational geometry algorithms are designed around the use of primitives, subroutines that access the coordinate data of the input and convert it into combinatorial information, with the assumption that all access to the input goes through these primitives. For instance, a key primitive often used for computing convex hulls (and central to my book on forbidden configurations) takes as input an ordered triple of points in the plane and determines whether they are ordered clockwise around the triangle they generate, counterclockwise, or collinear. The premise of the new preprint is that this primitive could randomly produce the wrong result, with some constant probability, independent of any past errors or successes.
-
Linkage
- My drunken theorem (\(\mathbb{M}\)). Bill Gasarch’s open problems column in memory of Luca Trevisan brings Lance Fortnow vague memories of drinking and deriving.
-
Linus Pauling Commemorative Ceramic Mural
While in Palo Alto for the holidays, I stumbled on a piece of public art I didn’t previously know about: the Linus Pauling Commemorative Ceramic Mural, created in 2000 by Ross Drago.
-
End-of-year linkage
-
Pseudonymity in academic publishing
The January issue of the Notices of the AMS is out, and it includes a new article coauthored by me, as well as what look like interesting articles on machine-assisted proof by Terry Tao and on rational approximation by Lloyd Trefethen fils (better known as Nick). My article is about editing mathematics on Wikipedia, with the pretentious or maybe just silly name Princ-wiki-a Mathematica: Wikipedia Editing and Mathematics; it’s by Joel B. Lewis, Russ Woodroofe, XOR’easter, and myself.
-
Linkage
- Modern CPUs have \(\mathbb{F}_2\) polynomial multiplication as a single operation (\(\mathbb{M}\)). This should be useful for other kinds of bit-hacking, not just algebraic computation.
subscribe via RSS