-
Linkage with pelicans
- ViXra launches archive of AI-generated papers (\(\mathbb{M}\)). In case your daily dose of crankpottery needed supercharging.
-
Two recent preprints
I have two new(ish) arXiv preprints that I thought I would announce together here rather than devoting a separate post to each of them.
-
Linkage
- Anti-inductive dice (\(\mathbb{M}\)). One player rolling \(n\) copies of one die is more likely to win than the other player rolling \(n\) copies of the other die, except when \(n=4\).
-
Bandwidth vs breadth-first search
Another new preprint of mine recently appeared: “Bandwidth vs BFS width in matrix reordering, graph reconstruction, and graph drawing”, arXiv:2505.10789, with Mike Goodrich and his student Alfred Liu. For me, it started with a mistake.
-
Linkage
- Nature on National Science Foundation terminating hundreds of grants and planning for massive budget cuts (\(\mathbb{M}\)). Terence Tao writes “this is going to be hugely disruptive … and in conflict with the congressional authorization of funds appropriated for the NSF”.
-
Turnstile majority
A famous algorithm of Boyer and Moore for the majority problem finds a majority element in a stream of elements while storing only two values, a single tentative majority element \(m\) and a counter \(c\). Every time it seems a stream value equal to \(m\), it increments the counter, and every time it sees an unequal element, it decrements the counter. If this would cause the counter to go negative, it replaces \(m\) by the value that it sees and resets the counter to one. At the end of the algorithm, if there is any element that repeats for more than half of the items in the stream, then that element will be the one stored in \(m\). But otherwise, the result of the algorithm is undefined. Here’s a visualization I made of the algorithm for its Wikipedia article, with the data stream running across the bottom, the height of the graph showing the stored counter, and the icons on the graph showing the stored stream value:
-
Why I linkage
- Archaeologists claim intellectual property rights to ancient Roman dodecahedra (\(\mathbb{M}\), via), dozens of which exist in multiple museums, and block online sales of replicas. According to Wikipedia there are “more than fifty possible explanations” for what these things might have been used for.
-
Which infinite graphs can DFS explore?
I recently revisited the Wikipedia article on normal spanning trees, rooted spanning trees of infinite undirected graphs that act like depth-first search trees in the sense that every non-tree edge of the graph connects an ancestor to a descendant. They exist in every connected countable undirected graph, but cannot always be generated by a depth-first search. It occurred to me to wonder: in which connected countable undirected graphs is it possible for a depth-first search to visit all vertices? It turns out to be possible if and only if the graph has one of the following two connectivity properties. Either:
-
Linkage
- Exchange rates between CS conferences (\(\mathbb{M}\)). Assuming that the people who publish in top conferences are equally productive, how many machine learning papers are the equivalent effort to one paper in other areas?
-
Congratulations, Dr. Zheng!
Today I served as the external member on the doctoral defense of Da Wei (David) Zheng, a student of Timothy Chan at the University of Illinois. He has an impressive portfolio of recent publications on geometric data structures and geometric graph algorithms, some of which featured in his thesis, From Geometry to Graphs and Back: Geometric Range Searching and Algorithms in Structured Graphs, and in his defense talk.
subscribe via RSS