-
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.
-
Fast Schulze voting using quickselect
I have a new preprint, “Fast Schulze voting using quickselect” (arXiv:2411.18790), with two UCI students, Randy Huynh and Arushi Arora. Randy was an undergraduate when he worked on this with me, and Arushi is about to finish her master’s program. (There’s apparently another Arushi Arora studying computer science at Purdue; that’s someone else.)
-
Linkage
- Gray on gray cats (my cats but not my photo of them; \(\mathbb{M}\)).
-
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?)
subscribe via RSS