Nearly Optimal Deterministic Algorithm for Sparse Walsh-Hadamard Transform

A certain type of paper gradually permeates an entire field but doesn’t make headlines when it first appears. Among them is the paper by Cheraghchi-Indyk on the sparse Walsh-Hadamard transform. It first surfaced on arXiv in late April 2015. Like most theoretical computer science papers, it languished there for a while before making its way into ACM Transactions on Algorithms two years later. It’s difficult to ignore the fact that it has continued to receive citations over the years, including a new round in 2025 from venues related to information theory and cryptography.

The stakes are strangely intuitive, but the problem the authors tackled sounds technical. Let’s say you have a large signal with N entries and you believe that only k of its frequency components are truly significant. You must grind through the entire process in N log N time when using the traditional fast Walsh-Hadamard transform. When N is small, that is acceptable.

When N begins to resemble the size of a high-dimensional machine learning feature space or a genomics dataset, it is no longer acceptable. Cheraghchi and Indyk developed an algorithm that executes in approximately k^(1+α)(log N)^O(1) time, where α can be made as small as desired. The catch, if you can call it that, is that the privilege of being completely deterministic comes at a small cost in the exponent.

This is where the word “deterministic” comes into play. Prior to this algorithm, the majority of fast sparse Fourier algorithms relied, sometimes significantly, on randomness. Although randomized approaches are frequently quicker and simpler to design, they have drawbacks that no hardware engineer enjoys discussing. In the theoretical community, there is a belief that determinism is simply cleaner when it is attainable. This paper’s algorithm consistently yields the same result, employs non-adaptive queries that can all be executed simultaneously, and remains remarkably close to the randomized state of the art.

The paper becomes truly fascinating when it comes to the technical machinery. The authors rely on a lossless condenser, which is a meticulous implementation of the GUV construction from a paper published in 2009. This compressed sensing scheme builds on an earlier expander-based construction by Berinde, Gilbert, Indyk, Karloff, and Strauss. Condensers are objects from pseudorandomness theory that no one outside of a fairly small circle considers. It’s the kind of cross-pollination that theoretical computer science sometimes generates, where tools designed for one application end up resolving an issue in a related field.

The modesty of the framing is what I find subtly captivating. The authors point out that better parameters here would inevitably result from any future advancements in explicit condenser constructions. In essence, they have made a unique and somewhat modest design decision by creating a framework that improves as the underlying mathematics improves. Academic papers don’t always manage to be honest.

It’s still unclear if the algorithm will ever leave the lecture hall and end up in production code. The journey of compressed sensing has been peculiar; it has been promising in theory but occasionally awkward in practice. However, the concepts presented in this paper continue to appear in unexpected places, such as recent research on generalized q-ary functions and functional encryption. That is worth something. Occasionally, the most significant documents are the ones you are unaware of until you discover that others have been subtly expanding upon them.