11011110

The integer complexity of a number \(n\) is the minimum number of ones needed to express \(n\) as a parenthesized combination of sums and products of ones. For instance, 10 has complexity 7 as it can be expressed using seven ones, but not fewer: \[10 = (1+1+1)(1+1+1)+1.\] The largest number with complexity \(k\) can be obtained by breaking up the sequence of \(k\) ones into subsequences of two and three ones (with as many threes as possible) and multiplying. For instance, for ten ones, you…

Another mathematics journal leaving its commercial publisher (\(\mathbb{M}\)), but with a twist: usually this is accomplished by a mass resignation of the editorial board. But in this case, Communications on Pure and Applied Mathematics is owned by the Courant Institute and was published by Wiley, so taking it in-house is just a matter of not renewing the contract. The causes of friction were increased publisher interference with editorial decisions (the usual), but also editor dissatisfaction…

I have another new preprint, the result of a research project with UC Irvine undergraduate Cindy Zhang: “Sudoku grids that require many clues” (arXiv:2607.05728, to appear at JCDCG3 2026). The main result is, I think, surprising: When generalized to \(n^2\times n^2\) grids, almost all sudoku puzzles must be almost entirely covered by clues, leaving only a logarithmic fraction of cells blank. This implies an average case time for solving randomly chosen puzzles that is exponential in \(n^4/\log…

On the scale of stupid things the US government is doing this is pretty small, but they appear to be banning the census bureau from any effective methods of privacy-preserving information release, and in particular from adding noise to their data to help create differential privacy (\(\mathbb{M}\), via). Sadly, taking away valuable disclosure avoidance tools doesn’t make fundamental trade-offs go away. Bipartite matching is in \(\mathsf{NC}\) (\(\mathbb{M}\)). New preprint by Abhranil…

I’ve been hesitating in writing up a blog post about my latest preprint, “Minimum-weight Steiner triangulation of convex polygons requires interior Steiner points” (with my student Zahra Hadizadeh, arXiv:2606.25302, to appear at CCCG) because, despite being a completely concrete two-dimensional construction, its exponential scale makes it difficult to visualize. In the paper we included an illustration using logarithmic coordinates but I didn’t find that entirely satisfactory so I’m trying…

David Richter, a mathematician at the University of Western Michigan, recently found himself with a surfeit of ceramic orthogonal polyhedra and, knowing of my own interest in orthogonal polyhedra, generously offloaded two of them to me. They fit nicely in my office together with the paper and crochet orthogonal polyhedra I already had: The blue one is an orthogonal realization of Boy’s surface, an immersion of the projective plane into three-dimensional space with three-way symmetry and a…

My latest preprint, “Tangent spheres and integer distances” (arXiv:2606.18569, to appear at CCCG), involves the patterns of external tangencies of circles, spheres or higher-dimensional hyperspheres. You can make a graph whose vertices are a given set of spheres and whose edges are pairs of externally-tangent spheres, and I’d like to understand which graphs are possible. By the circle packing theorem, any planar graph can be represented by interior-disjoint circles in this way, but here I’m not…

Biomedical papers with fabricated references blew up by more than a factor of ten from 2023 to 2026 (\(\mathbb{M}\), via). Relatedly, arXiv has added a new policy banning author of papers with hallucinated citations or other artifacts of unchecked LLM use for a year (and after that permanently requiring publication prior to allowing a preprint, kind of problematic for publication in journals whose submission process depends on having an arXiv preprint. Unfortunately I can’t find a direct…

This past week was the final exam week for our spring term, and in it we also held the doctoral defense of another Ph.D. student, Vinesh Sridhar (advised by Mike Goodrich). Vinesh organized his thesis in an unusually symmetric way, with two parts on computing with noisy primitives, two parts on in-place algorithms, two parts on sequential algorithms, and two parts on parallel algorithms, in four combinations (noisy sequential, noisy parallel, in-place sequential, in-place parallel). I’ve…

Real-world application of square packing: Packing ten quart bottles in a milk crate slightly larger than a \(3\times 3\) packing. Significant increases in perceived cheating, and decreased willingness of honest students to turn in cheaters, lead Stanford and Princeton to give up on honor code based unproctored exams (\(\mathbb{M}\), via). Ars Technica blames the cheating on AI, but although it seems likely to me that the ease of cheating with AI is a factor, I’m skeptical that it’s the root…

I participated today in the successful Ph.D. defense of Nikolas Patris, a student of my newly-tenured colleague Ioannis Panageas. Nikolas has been working on problems of learning Nash equilibria of games and more generally finding saddle points of smooth functions, a crossover area between theoretical computer science and machine learning. His results are theoretical but his papers on them are in machine learning conferences: “Exponential Lower Bounds for Fictitious Play in Potential Games”,…

Daniel Lemire speeds up binary search using parallel data-comparison instructions (\(\mathbb{M}\), see also). Presenting only the surname of an author is inconvenient, especially for authors from some East Asian cultures with a few very popular surnames. As posted by Joanna Ko, who has one of them. You might know that if you make a Sierpinski tetrahedron (by subdividing a regular tetrahedron into four smaller tetrahedra at its corners and a central regular octahedron, removing the octahedron,…

The Fibonacci heap is a priority queue data structure in which finding and removing the top-priority item takes logarithmic time (like a binary heap) but reprioritizing items to have higher priority takes only constant time, under amortized time analysis. This property is useful for speeding up the time complexity of algorithms including Dijkstra’s algorithm for shortest paths and Jarník’s algorithm for minimum spanning trees, so that they take logarithmic time per vertex and constant time per…

Retraction Watch reports on the mass resignation of the editorial board of Elsevier’s Journal of Approximation Theory (\(\mathbb{M}\)). This follows in close succession from the mass resignation from Taylor & Francis’s Communications in Algebra. On Max Bill’s gelbes feld (\(\mathbb{M}\)), Barry Cipra, Notices of the AMS. Analysis of this artwork reveals that it depicts a magic square, with dice-like dot patterns encoding its digits, and with equal numbers of dots in each row or column of dots.…

Good news: Email from Knuth. Bad news: It begins “is there a bug in your paper?” The paper in question is “The traveling salesman problem for cubic graphs” (WADS 2003 and JGAA 2007). Of course the bug report is accurate, but fortunately it can be easily patched. My paper has algorithms for finding a minimum-weight Hamiltonian cycle (when it exists), in an \(n\)-vertex graph of maximum degree three, in time \(O(2^{n/3})\), and for listing all Hamiltonian cycles in time \(O(2^{3n/8})\). Both have…

Congratulations to Ken Clarkson and the rest of the newly-named SIAM Fellows (\(\mathbb{M}\))!

A sheet of a4 paper has aspect ratio \(1:\sqrt2\). This means you can crease it along the shorter of its two midlines to get two rectangles with the same aspect ratio (of a5 size) and continue in the same way recursively.

Firefox testing reveals as many as 5% of crashes are caused by hardware memory faults.

Remembering Joe Halpern (\(\mathbb{M}\)) focuses on Joe’s pivotal role in founding and guiding the CS section of the arXiv.