Shortform Posts
A section of the website for shortform posts, still technical, but separate from the main blog and with a lower threshold for quality.
- The last few months in HEIR
In my little corner of the FHE world, things have been steadily heating up. For those who don’t know, my main work project right now is HEIR (Homomorphic Encryption Intermediate Representation), a compiler toolchain for fully homomorphic encryption (FHE). For an extended introduction see this talk from October 2023. The primary focus of HEIR is to compile to FHE hardware accelerators. And boy there are a lot of them. There are GPU and FPGA accelerators, as well as special purpose ASICs and even optical accelerators (discrete Fourier transforms at the speed of light). - LWE Attack Benchmarking Project
Kristin Lauter and her colleagues at Facebook research recently announced a project to benchmark attacks against LWE. The announcement was on the post-quanum crypto mailing list. They state: “Our approach is motivated by the need to study more carefully the effect on security of using small secrets and small error in standardized LWE settings like Kyber and Homomorphic Encryption. In addition, as sparse secrets have been used in Homomorphic Encryption for efficiency and functionality, it is important to study sparse secrets as well. - Dynamic Programming Fail
This is a story about a failure to apply dynamic programming to a woodworking project. I’ve been building a shed in my backyard, and for one section I decided to build the floor by laying 2x4 planks side by side. I didn’t feel the need to join them with tongue-and-groove, but I did notice that using 2x4s alone wouldn’t fit the width they were supposed to fill. I also had some 2x6 boards left over from a different part of the shed, and I realized that gave a neat dynamic programming problem: Can you fill a given width by laying planks of standard dimensional lumber? - Webmentions and POSSE improvements
This blog now accepts webmentions. I used webmention.io and webmention.js for live rendering. You can see an example at the end of my old Bezier Curves post. After my initial experiments with POSSE, I’ve made a few improvements to the system. Now shortform posts are syndicated to Mastodon, Bluesky, and Twitter, and the links to the syndicated posts are automatically added to the end of each post. I don’t have any automatic social media posting for longform posts yet, though I plan to add a very simple version of that soon. - Polynomial dialect and mlir-opt tutorial upstreamed
I’ve been upstreaming a bit of my compiler work to the MLIR project. Yesterday, I merged in a tutorial on mlir-opt, the main debugging tool for running passes on MLIR code. This is roughly the upstreamable parts of my first MLIR tutorial entry, MLIR — Running and Testing a Lowering. Mehdi Amini also provided a lot of useful information during review that taught me some stuff I didn’t know about the tool. - Ben Recht on Meehl's Philosophical Psychology
Ben Recht, a computer science professor at UC Berkeley, recently wrapped up a 3-month series of blog posts on Paul Meehl’s “Philosophical Psychology.” Recht has a table of contents for his blog series. It loosely tracks a set of lectures that Meehl gave in 1989 at the University of Minnesota. In it, he surveys of the philosophy of science, lays out a framework for scientific debate, and critiques scientific practice. Recht summarizes his arguments, simplifies the ideas, provides examples, and offers his own commentary, considering today’s computerized world. - Detecting field names with C++ metaprogramming
A quick note: you can use C++11 templates to detect struct fields by name and type, and statically branch on them. I first heard of this solution from breeze1990. Say I want to detect if a struct has a field size of type int. Create two template instantiations of the same name, here HasStaticSize that defaults to false. #include <type_traits> template <typename T, typename = void> struct HasStaticSize : std::false_type {}; template <typename T> struct HasStaticSize< T, typename std::enable_if< std::is_same<int, std::decay_t<decltype(T::size)>>::value, void>::type> : std::true_type {}; The latter is only resolved if T::size is declared as int, or more specifically, something that “decays” to int. - Barycentric Lagrange Interpolation
In my studies of the Remez algorithm, I learned about the barycentric Lagrange interpolation formula. The context is finding a polynomial of degree at most $n$ that passes through $n+1$ points $(x_0, y_0), \dots, (x_n, y_n)$. The classical Lagrange interpolation formula is what you’d write down if you “just did it.” $$f(x) = \sum_{i=0}^n y_i \cdot \prod_{j \neq i}\frac{x - x_j}{x_i - x_j}$$ I wrote a 2014 article deriving this more gently, and implementing it in Haskell for secret sharing. - Random life updates
I added Twitter syndication, and because I have nothing to test it with I’ll share some random life updates. My daughter was born recently, which means I’m on paternity leave for a few months. Hopefully in the liminal hours of sleep training, I’ll have some time to work on my book. Or at least catch up on reading. I finally published my grandmother’s autobiography. I doubt anyone outside of my family will want to read it, but it’s available for sale on Amazon. - Math databases
Steven Clontz informed me of an effort he’s involved in called code4math. It’s described as a professional organization for the advancement of mathematical research through building non-research software infrastructure. By that he means, for example, writing software packages like Macaulay2 or databases of mathematical objects that other researchers can use to do their research. Clontz recently gave a talk on the topic, with ample discussion of the evaluation material they can provide to justify the academic value of this sort of work. - Experiments with POSSE
POSSE stands for Publish (on your) Own Site, Syndicate Elsewhere. I first heard about it from Cory Doctorow. I’m experimenting with automation to convert posts tagged shortform into Mastodon threads (I’m mathstodon.xyz/@j2kun). I’m using Hugo as a static site generator, with the source a (private) GitHub repository, and Netlify for deployments. After a deployment, Netlify calls a serverless function that hits the GitHub API with a POST request to trigger a GitHub action workflow. - Remez and function approximations
I’ve been learning recently about how to approximate functions by low-degree polynomials. This is useful in fully homomorphic encryption (FHE) in the context of “arithmetic FHE” (see my FHE overview article), where the computational model makes low-degree polynomials cheap to evaluate and non-polynomial functions expensive or impossible. In browsing the state of the art I came across two interesting things. The first is the software package lolremez that implements polynomial (and rational polynomial $f(x) / g(x)$) function approximation using the so-called Remez algorithm.