Our press release this month features ten papers, making this one of the more crowded editions of PTRview. The lineup takes us through distribution-free testing, shortest paths, hypergraphs, numerical linear algebra, streaming, and a few other corners of sublinear algorithms.

Before we get started, let me make a small aside. I think it is worth acknowledging the increasingly rapid progress of AI in mathematics. There is clearly a lot to be excited about, but I also find some of the implications rather concerning, and I share some of Terry Tao’s caution on where this may be taking mathematical research. This is perhaps a conversation for another day—and certainly not one I want to turn this month’s PTRview into—but I do think it is something our community should be talking about.

With that out of the way, let us take a look at our spread.

Distribution-Free Halfspace Testing with Samples by Xi Chen, Renato Ferreira Pinto Jr., Nathaniel Harms, Shyamal Patel, Rocco A. Servedio (arXiv) This featured paper confronts an old classic from the learning theory literature and, as the authors colorfully put it, attempts to understand just “when is the simplest and most trivial property testing algorithm also optimal, thereby justifying our laziness and ineptitude in algorithm design”.

The classic problem they explore is learning halfspaces with respect to an unknown distribution. Let us consider the property testing analog of this task. So, you will work in the distribution-free model. Unpacking, I have an unknown distribution supported over \(\mathbb{R}^n\) and, according to some function \(f\), I tell you for any sample \(x \in \mathbb{R}^n\) whether \(f(x) = 1\) or \(f(x) = 0\).

You want to answer whether \(f\) is consistent with some halfspace, or whether it is \(\varepsilon\)-far according to the unknown distribution from all halfspaces. Staying true to their colorful promise, the paper proves in Theorem 1.1 that yes, we should be happy that we were not able to cook up some super sample-efficient algorithm for this problem—because none exists!

The paper gives two proofs of this result—one is human-generated (delegated to the appendix), and the other, which is AI-generated (with a human exposition), is provided in Section 2. The paper emphasizes that the AI proof also works when the domain is restricted to the Boolean hypercube. The proof proceeds via an application of Yao’s lemma. From a cursory glance, it appears that the construction of the YES and NO distributions is fairly elegant and allows for a slick lower-bound proof (which spans, with all the scaffolding in Section 2, a total of four pages).

Instance-Optimality of Bidirectional Dijkstra on Simple Graphs by Christian Bertram, Mads Vestergaard Jensen, Mikkel Thorup, Hanzhi Wang, Shuyi Yan (arXiv). To understand what this paper is doing in PTReview reports, let us first recall a recent result of Haeupler, Hladík, Rozhoň, Tarjan and Tětek. As covered on Quanta, this paper showed that a carefully implemented version of bidirectional Dijkstra is instance-optimal for finding shortest paths in weighted multigraphs. But what the hell do we mean by instance-optimal? To understand this, let us fix a particular graph \(G\) and a source-destination pair \((s,t)\), and consider algorithms that discover the graph by querying edges. An algorithm is instance-optimal if, on this particular instance, its number of queries is within a constant factor of the number of queries made by the best possible algorithm that accesses \(G\) only through the same query model. In particular, this is much stronger than a worst-case guarantee: we are saying that, on every individual instance, there is essentially no algorithm that can get away with substantially fewer queries. This is exactly the sort of phenomenon one hopes to exploit in sublinear algorithms—perhaps the shortest path can be found without even looking at most of the graph!

But there is a small wrinkle. The HHRTT result applies to multigraphs, whereas the canonical shortest-path problem is usually formulated on simple graphs. So the natural question is: does bidirectional Dijkstra remain instance-optimal on simple weighted graphs? The featured paper answers this question, although the answer is not a simple yes or no. For simple undirected unweighted graphs, bidirectional Dijkstra is indeed instance-optimal when the edges are presented in a random order. On the other hand, the paper gives separations showing that instance-optimality can fail for other combinations of directed/undirected graphs, edge orderings, and access models.

A simple and practical \(o(\sqrt n)\)-time algorithm for shortest paths in power law graphs by Jiaqi Mao (arXiv) This paper presents a shortest-path algorithm designed specifically for power-law graphs. I will paraphrase the abstract.

One contribution of this work is a simple algorithm called Pruned Bidirectional Search (PBS), which does not require any preprocessing and runs in time \(O\left(n^{(1-1/\log\log n)/2}\right)\), which is \(o(\sqrt{n})\). With high probability, the algorithm returns a path whose length is within a factor of \(41/32\) of the shortest path. If one is willing to pay for a preprocessing step of \(n^{\Theta(2-1/\log\log n)}\) time, the query time improves further to \(n^{\Theta(1/\log\log n)}\). The paper also reports experiments on real-world and synthetic power-law graphs, where PBS is \(1.84\)--\(7.76\) times faster than existing alternatives, while achieving an approximation ratio of at most \(1.05\).

A Tight Scale-Locality Bound for Partial Detection in Non-Adaptive Group Testing by Nader H. Bshouty (arXiv) Alright, so here is a group testing problem. We have \(n\) items, of which an unknown number \(d\) are defective, and our goal is only to find \(\ell\) defective items. The paper considers the non-adaptive setting where \(d\) is unknown, and proves a tight bound of \(\Theta(\ell\log^2(n/\ell))\) tests. The lower bound comes from a neat “scale-locality” argument (throwback to the title): if we knew \(d\), finding \(\ell\) defectives requires about \(\ell\log(n/d)\) bits of information. But a fixed group test is informative only when its size is somehow compatible with \(d\), and hence is useful at only \(O(1)\) of the logarithmically many possible scales. Summing this information requirement over all scales gives the lower bound. The paper also gives a matching upper bound by running the known-$d$ algorithm in parallel over dyadic guesses for \(d\).

Sublinear Algorithms for Estimating the Number of Hyperedges in Arbitrary Hypergraphs by Deeparnab Chakrabarty, Cooper LaPorte, (and our very own) C. Seshadhri (arXiv). Alright, now time for a hypergraph problem! Regular PTRview readers are no stranger to estimating the number of edges in graphs under various access models. The featured paper considers the challenge of estimating the number of hyperedges in an arbitrary \(n\)-vertex hypergraph using a sublinear in \(n\) number of queries. The paper notes that in the standard access model (which allows sampling random vertices, querying vertex degrees, and accessing incident hyperedges), there are simple lower bounds that rule out strongly sublinear algorithms for arbitrary, non-uniform hypergraphs. So, the paper instead considers a different access model motivated by a natural way to represent a hypergraph \(H\) as a bipartite incidence graph, with hyperedges on the right and vertices on the left. You connect a hyperedge to all the vertices it contains. The natural access model associated with this picture allows you to sample a random hyperedge (via its ID) as well as a random vertex. Additionally, you can query the arity of a hyperedge and obtain a random vertex incident to a hyperedge. The paper calls this the dual access model. In this model, the paper obtains a \((1+\varepsilon)\) approximation to the number \(m\) of hyperedges using \(\approx \sqrt n \cdot \log n\) queries. The paper also proves a nearly matching \(\Omega(\sqrt n)\) lower bound for obtaining even a constant-factor approximation.

Fast Length-Squared Sampling for Positive-Semidefinite Matrices by Rajarshi Bhattacharjee, Ethan N. Epperly, Cameron Musco, Aaron Tian (arXiv) Alright, here is a numerical linear-algebra primitive that most of us have probably taken for granted. Consider the task of Length-squared sampling, i.e., you want to sample a column \(i\) with probability proportional to its squared \(\ell_2\)-norm, i.e., with probability \(|A_{*,i}|_2^2/|A|_F^2\). This is a standard primitive behind a number of randomized numerical-linear-algebra algorithms, including low-rank approximation and approximate matrix multiplication. The catch is that if all you have is entry-query access to an \(n\times n\) matrix, even computing the norm of a single column costs \(n\) queries. The featured paper shows that for PSD matrices, we can nevertheless perform this exact sampling in only \(O(n)\) expected time — which is optimal.

The algorithm is a rather cute rejection-sampling scheme based on the PSD inequality \(A_{ij}^2\leq A_{ii}A_{jj}\). First sample two indices according to the “diagonal distribution”—which returns a diagonal entry with probability proportional to the entry, and then you use \(A_{ij}\) to decide whether to accept. Somehow, this gives exactly the desired length-squared distribution. The paper also gives applications of this primitive to estimating the Frobenius norm and other numerical linear-algebra tasks.

Streaming Algorithms for Monotonicity Testing by Amir Azarmehr, Soheil Behnezhad, Lily Chung, Alma Ghafari, Jane Lange, Ronitt Rubinfeld (arXiv) This paper takes a streaming take on a classic property testing problem. Consider an \(n\)-vertex DAG \(G\) and a Boolean function \(f\) on its vertices. We say \(f\) is monotone if \(f(u)\leq f(v)\) whenever there is a directed edge from \(u\) to \(v\). The paper asks how well we can estimate the distance of \(f\) to monotonicity when the edges of \(G\) arrive in an arbitrary order and we are only allowed \(\widetilde O(n)\) space. The main result is a \((1+\varepsilon)\)-approximation using \(\sqrt{n}^{1+o(1)}\) passes, which is essentially optimal: any constant-factor approximation with fewer passes would imply a faster streaming algorithm for \(st\)-reachability.

I find the main technical idea cool. The distance to monotonicity is exactly the size of a maximum matching in the violation graph of \(f\). So the problem becomes one of estimating maximum matching size in a graph that we only have implicit access to through the original DAG. The paper connects this to sublinear-time algorithms for maximum matching, introducing stronger vertex and subset query models that can be implemented efficiently in the streaming setting. In particular, only polylogarithmically many subset queries are needed for a constant-factor approximation of maximum matching, which is what ultimately gives the \(\sqrt{n}^{1+o(1)}\) pass bound.

Ranked spreadness and sample-based testing by Gaia Carenini (arXiv) Let us start the story from our News for April 2015 where we covered a paper by Fischer-Lachish-Vasudev which tried to understand the properties we could test when given only sample access to a combinatorial object. The main result of the paper showed that one can simulate a \(q\)-query (think \(q = O(1)\)), non-adaptive tester for an abstract property by a sample-based tester which used \(O(n^{1-1/q^2})\) samples. The featured paper presents a simulation that uses only \(O(n^{1-1/q})\) samples which was the bound conjectured in the preceding work. This is achieved via a suitable notion of rank-spreadness, a pseudorandom notion inspired from the pseudorandom style notions which were used to improve bounds on sunflower lemma.

A quantitative container characterization of one-sided testability by Gaia Carenini, Cameron Seth, Yuichi Yoshida (arXiv) So, containers strike again! Regular PTRview readers may remember our News for March 2024, where we covered another paper using the hypergraph container method in property testing. For those who missed it, let me briefly recall the basic idea: containers are a way of covering a complicated family of combinatorial objects by a much smaller collection of simpler objects. In the featured paper, the containers are used to characterize one-sided testability of hereditary graph properties. Roughly speaking, the paper shows that a hereditary graph property is one-sided testable if and only if a suitable family of associated hypergraphs admits an appropriate container structure. In short, the containers are back—and apparently they have not finished carrying things yet.

Sublinear Time Eigenvector Approximation via Column Sampling by Rajarshi Bhattacharjee, Cameron Musco, Dominic Rutkowski (arXiv) We close with another problem from numerical linear-algebra with a sublinear twist. Given a symmetric matrix \(A\in\mathbb{R}^{n\times n}\) whose entries are bounded by \(1\), the paper asks whether we can approximate its outlying eigenvectors without even reading the whole matrix. The main result says yes: by uniformly sampling only \(\widetilde O(\log n/\varepsilon^4)\) columns, one can recover an approximate eigenvector for every eigenvalue \(\lambda\) satisfying \(|\lambda|\geq\varepsilon n\), with residual \(|Av-\lambda v|_2\leq\varepsilon n\). For the top eigenvector, the sample complexity improves to \(\widetilde O(\log n/\varepsilon^2)\), and the paper shows that this is tight up to logarithmic factors.

The cute part is that the resulting eigenvectors are actually spanned by the small collection of sampled columns, so individual entries of the approximation can be computed in \(poly(\log n,1/\varepsilon)\) time. This puts the result squarely in the quantum-inspired algorithms framework, and gives the first sublinear-time classical algorithms for eigenvector approximation with additive error \(\varepsilon|A|_F\)