-
Linkage
- Math hats (\(\mathbb{M}\)): the mathematicians of yore and their silly headwear, 2017. Later published in revised form as “MathCap History” in Math Horizons.
-
Congratulations, Dr. Tröbst!
Thorben Tröbst, a student of Vijay Vazirani at UC Irvine, passed his Ph.D. defense today. Thorben joined UCI in 2019, already very knowledgeable about linear programming and related topics through a master’s degree at the University of Bonn. His doctoral research includes work from five of his papers related to matching, especially focusing on matching problems that pair up agents (with preferences) and goods (without) but that do not involve payments. Examples of problems like this include some systems for assigning donated organs to patients in need of a transplant, assigning students to schools in large school systems, or matching would-be visitors to open time slots in oversubscribed public parks. These systems are often either randomized, or produce fractional matchings, as this is required for fairness. (How else could you fairly assign even one thing to multiple people requesting it?)
-
Some highlights from FOCS
Lance Fortnow has already posted a high-level overview of this year’s FOCS conference (the annual IEEE Symposium on Foundations of Computer Science). So instead of posting something similar I thought I’d share my impressions of a few of the contributed talks that particularly caught my attention. In many cases, 20-minute videos for these talks are linked from the conference schedule, and are more complete than the far-too-short 12-minute talks that were presented in person.
-
Halloween linkage
-
2-adic numbering for binary tilings
I’ve posted quite a bit about the binary tiling of the hyperbolic plane recently, including what you get when you shrink its vertical edges, a related “nowhere-neat” tessellation, the connection to Smith charts and Escher, a method to 3-color its tiles, a half-flipped variation of the tiling, and its applications in proving that folding origami is hard. But I thought there might be room for one more post, in honor of the Wikipedia binary tiling article’s new Good Article Status. This one is about something I wanted to include in the Wikipedia article, but couldn’t, because I couldn’t find published sources describing it: a way of numbering tiles that encodes their position in a tiling and instantly proves the assertion in the article that there are uncountably many binary tilings.
-
Splines for graph drawing theory
For a long time there has been a tension in graph drawing between theoretical and practical methods. Typical theoretical results show that graphs in certain special classes can be drawn with guaranteed bounds on certain measures of the drawing quality: for instance, the edges may be shaped as polylines with a hard limit on the number of bends per polyline, on the number of crossings per edge, and on the angle of each crossing. In practice we just want to draw arbitrary graphs and produce something legible. Few crossings and avoiding sharp angles are still good, but polylines are not: it can be difficult to distinguish bends from vertices or follow edges that repeatedly bend. For this reason, when straight line segments are inadequate, practical heuristics often use smooth curves rather than polylines, and especially spline curves.
-
Linkage
- Possibly all the ways to get loop-finding in graphs wrong (\(\mathbb{M}\)). Simon Tatham tries various ways of finding the edges of a graph that belong to at least one cycle, with bugs of various levels of sophistication, until finally settling on Tarjan’s bridge-finding algorithm. The application: checking puzzle solutions.
-
Computational complexities of folding
I turned my talks at OSME and JCGCG3 this summer into a paper: “Computational Complexities of Folding”, arXiv:2410.07666. It includes the following results:
-
A half-flipped binary tiling
In this tiling of the hyperbolic plane, all of the tiles are the same shape and size (despite their varied appearance), they are not square, and they are not polygons.
-
Linkage for the start of another academic year
- Shift networks (\(\mathbb{M}\)). Jeremy Kun asks how to permute vectors using few vector additions, elementwise multiplications, and rotation operations, for an application involving homomorphic encryption.
subscribe via RSS