It has two perfect matchings. One is \(\{(v_1, w_1), (v_2, w_3), (v_3, w_2)\}\) and the other is \(\{(v_1, w_2), (v_2, w_1), (v_3, w_3)\}\).

We will assume that the graph is given as a matrix, known as the bi-adjacency matrix. The bi-adjacency matrix of a bipartite graph has \(A_{ij} = 1\) whenever \((i,j)\in E(G)\). For our running example, here is how we will receive the input: \[ A_G = \begin{bmatrix} 1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \end{bmatrix}\,. \] Now, we are ready to define the Bipartite Perfect Matching (BPM for short) problem. Given a bipartite graph as a bi-adjacency matrix, check whether there is a perfect matching in the graph or not.

NC. The next term we need to explain is NC. It is a complexity class named after Nick Pippenger, which consists of a class of problems solvable by parallel algorithms that use polynomially many processors and have parallel running time that is considerably smaller than polynomial. More specifically, the parallel running time is polylogarithmic. You can simply think of this as a class of problems that have efficient parallel algorithms.

Let us begin with a simple example. Suppose we want to multiply \(n\) numbers, \(x_1,\ldots,x_n\). One approach is to first multiply \(x_1\) and \(x_2\), then multiply the result by \(x_3\), and continue in this way until we reach \(x_n\). This is a sequential algorithm.

A parallel algorithm proceeds differently. It first pairs up the numbers and multiplies all pairs simultaneously. This produces \(n/2\) numbers, giving a new instance of the same problem with only half as many inputs. We then repeat the process: pair up the remaining numbers, multiply each pair in parallel, and continue until only one number remains.

Why it matters: TL;DR

• BPM is an extremely well-studied graph problem because it arises naturally in many practical scenarios. The problem has been a focus of intense research for more than 5 decades. (See an excellent introduction to matching and related problems here and here.)
• Derandomization is a central problem in theoretical computer science. (For a deep dive into derandomization see this or this survey.) It asks whether randomness truly adds computational power or merely provides a convenient shortcut. Bipartite Perfect Matching has long been known to admit a randomized NC algorithm. Finding a deterministic NC algorithm for the problem therefore fits naturally into the broader derandomization program. In fact, bipartite perfect matching is one of the most natural and simply stated problems in this setting. Its resolution provides a particularly striking example of randomness being removed from an efficient parallel algorithm.

How did the authors solve the problem?

Polynomial-time algorithms for this problem---Kuhn's algorithm, Hopcroft--Karp, or matching-via-max-flow with Ford--Fulkerson---are a staple of undergraduate algorithms courses and have been known since the 1960s. They work by repeatedly finding an augmenting path: a path between two unmatched vertices that alternates between edges outside and inside the current matching; augmenting along it grows the matching by one edge (Berge's theorem)---an inherently sequential process. The matching that admits an augmenting path at step \(k\) depends on exactly which edges were chosen at steps \(1\) through \(k-1\); there's no obvious way to precompute or guess ahead of time which augmentations will happen. Thus, the classical algorithms for the problem are sequential.

The randomized NC algorithm for BPM. As a warm up, let us see the randomized NC algorithm for BPM. The algorithm is as follows.

• Start with the given bi-adjacency matrix \(A_G\) of the bipartite graph \(G\).
• Replace each \(1\) entry by a random number from the range \([1, 100n]\), where \(n\) is the number of vertices in \(G\). This creates a new matrix \(A_G'\).
• Compute DET of \(A_G'\).
• If it is non-zero, then accept else reject.

Using the fact that DET \(\in\) NC as a black box, it is straightforward to see that the algorithm above runs in randomized NC. But why is it correct? Establishing correctness requires a connection between determinants and perfect matchings. At a very high level, the terms of the determinant of \(A_G'\) are in one-to-one correspondence with the perfect matchings of \(G\). Thus computing the determinant leads to checking the existence of a matching. For more rigorous details about this connection, we refer the reader to Lovász' paper.

The next question is whether the randomness can be removed. Informally, the randomization is needed to prevent cancellations in the determinant. Recall that computing a determinant involves both additions and subtractions. Thus, even if the graph has a perfect matching, different terms in the determinant expansion may cancel, causing the determinant to vanish. This would make the algorithm incorrect.

To avoid this, each nonzero entry is replaced by a random value. With high probability, the resulting determinant is nonzero whenever a perfect matching exists. The challenge, then, is to achieve the same effect deterministically: how can we prevent these cancellations without relying on randomness?

The first major breakthrough came about a decade ago, in work by Fenner, Gurjar, and Thierauf -- notice the overlap with the authors of the new result. Their approach traded randomness for parallel resources: they showed that the algorithm could indeed be derandomized, but only by allowing many more processors. Specifically, their algorithm required quasi-polynomially many processors. Recall that a polynomial function grows as \(n^c\) for some constant \(c\), whereas a quasi-polynomial function may grow as \(n^{\log n}\). In the latter case, the exponent of \(n\) is itself a growing function of \(n\), rather than a fixed constant.

The new approach

Let us reiterate the question we posed after reviewing the randomized NC algorithm.

How can we prevent these cancellations without relying on randomness?

The authors say, the answer lies in coding theory! At a very high level, the algorithm can be described as follows.

• Start with the given bi-adjacency matrix \(A_G\) of the bipartite graph \(G\).
• Replace each \(1\) entry in location \((i,j)\) with a fixed thin and tall matrix \(V_{ij}\) to produce a new matrix \(A_G'\).
• Compute DET of \(A_G'\).
• If it is non-zero, then accept else reject.

If you feed this algorithm to a computer, it will complain: Cannot compute DET because AG' is not a square matrix. But this is not a big deal. One could simply say, check whether it has full rank (either row-rank or column rank, whichever is smaller). This problem is also solvable in NC.

However, instead of replacing the original adjacency matrix, they first create an intermediate matrix \(\widehat{A_G'}\) from \(A_G\) by padding \(A_G\) with \(n(n-1)\) columns of unit vectors. For our example, \[ \widehat{A_G'} = \begin{bmatrix} 1 & 1 & 0 \quad & 1 & 1 \,& 0 & 0\, & 0& 0\\ 1 & 0 & 1 \quad & 0 & 0 \,& 1 & 1\, & 0& 0\\ 0 & 1 & 1 \quad & 0 & 0 \,& 0 & 0\, & 1& 1\\ \end{bmatrix} \] Now, in \(\widehat{A_G'}\), replace each non-zero entry \((i,j)\) with a thin and tall matrix \(V_{ij}\) to obtain \(\widehat{A_G}\). The matrix dimension and the padding length are chosen such that the overall matrix \(\widehat{A_G}\) becomes almost square. It now has slightly fewer rows than columns.

Note that the entire algorithm is deterministic. The main work is to show that this deterministic replacement works. Specifically, the authors show that
While we don't plan to present the proof here, the goal is to give you a high-level outline of the approach. In order to do that, let us first see what these matrices \(V_{ij}\) look like. This is exactly where the connection to coding theory comes up! Each matrix is indeed a Folded Vandermonde matrix, which comes up in folded Reed-Solomon codes and subspace designs.

Fix \(\gamma\in \mathbb{F}\) that has a large order, i.e. it needs to be raised to a very large power before it circles back to itself. (This is relevant when we are over finite fields.) For parameters \(r,D\in \mathbb{N}\), the folded Vandermonde matrix is the \(D\times r\) matrix whose \(ij\)th entry is \(\left(\alpha\gamma^{(j-1)}\right)^{i-1}\): \[ V(\alpha_{}, \gamma) = \begin{bmatrix} 1 & 1 & \cdots & 1 \\ \alpha_{} & \alpha_{}\gamma & \cdots & \alpha_{}\gamma^{r-1} \\ \alpha_{}^2 & (\alpha_{}\gamma)^2 & \cdots & (\alpha_{}\gamma^{r-1})^2 \\ \vdots & \vdots & \vdots & \vdots \\ \vdots & \vdots & \vdots & \vdots \\ \vdots & \vdots & \vdots & \vdots \\ \vdots & \vdots & \vdots & \vdots \\ \vdots & \vdots & \vdots & \vdots \\ \vdots & \vdots & \vdots & \vdots \\ \alpha_{}^{D-1} & (\alpha_{}\gamma)^{D-1} & \cdots & (\alpha_{}\gamma^{r-1})^{D-1} \\ \end{bmatrix} \] The parameters \(r,D\) are chosen such that the matrix is thin and tall. For our example \(G\) with \(n=3\), the matrix ends up as having \(D=n(n^3+1-n)=75\) rows and \(r=n^3+1=28\) columns. To obtain \(\widehat{A_G}\) from \(\widehat{A_G'}\), replace all the \(1\) entries from each column \(j\) of \(\widehat{A_G'}\) by \(V(\alpha_j, \gamma)\), where all \(\alpha\)s are distinct.

Swastik Kopparty and Shubhangi Saraf recently announced a variation of this approach. 

How does the proof proceed from here? One direction of the proof is quite easy. When there is no perfect matching, it is quite easy to see that the matrix cannot achieve full row rank. This is because, when there is no perfect matching, then by Hall's Theorem we know that there is a Hall blocker. That is, there is a set \(S \subseteq L\) such that if you look at the neighbours of \(S\), denoted as \(N(S) \subseteq R\), then \(|S| > |N(S)|\). This deficit in the size of the neighbour set for one of the subsets in \(L\) suffices to observe that the number of columns with nonzero entries is strictly less than the number of rows. Thus, one cannot have full row rank.

For the other direction, things are more intricate. The proof proceeds by proving the contrapositive. They show that if the row rank of the matrix is not full, then there will be a subset \(S \subseteq L\) such that \(|S| > |N(S)|\).

To prove this, they start with a vector \(v\) that certifies the linear dependence between the rows of \(\widehat{A_G}\). This vector is viewed as a tuple of \(n\) vectors of dimension \(D\) each. Now, they prove two things about it.

• First, they show that the non-zero elements of the tuple, say \(\mathcal{P}\), are linearly independent vectors.
• Second, they view these vectors as polynomials and consider the span of these linearly independent polynomials. They count the folded roots of the span of \(\mathcal{P}\) in two ways to derive the fact that \(|S| > |N(S)|\).

Both the parts above invoke a Lemma due to Guruswami and Kopparty which proves an upper bound on the number of folded roots of a linear space of polynomials.

Conclusion

Here are some final thoughts.

• The paper proves many more results. The proofs are self-contained and well-written. So, I highly encourage you to read it.
• Venkat Guruswami gave a keynote at ICALP 2026, where he explained how one can view the idea of subspace designs as a derandomization tool. He explained subspace designs by analogy with the more familiar notion of hash functions: subspace designs play for linear spaces a role similar to that played by hash functions for sets. He then sketched the BPM in NC proof from this perspective.
• One big open problem is resolved by humans. Going forward, will we have such only-human proofs? In fact, the authors first developed an algorithm for the problem, then used AI to help adapt the underlying idea to a broader setting. That is, they used AI to extend human ideas. Currently, this seems to be a trend in TCS. What can we expect going forward?

Article URL: https://www.modular.com/blog/qualcomm-to-acquire-modular

Comments URL: https://news.ycombinator.com/item?id=48658464

Points: 67

# Comments: 1

Article URL: https://aiclambake.com/clamtakes/linear-a/

Comments URL: https://news.ycombinator.com/item?id=48600107

Points: 447

# Comments: 178

Article URL: https://www.modeloop.app/

Comments URL: https://news.ycombinator.com/item?id=48543968

Points: 46

# Comments: 30