Bipartite Perfect Matching in Deterministic NC

Nutan Limaye and Thore Husfeldt guest post on the new deterministic parallel algorithm for bipartite perfect matching by Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar, Roshan Raj and Thomas Thierauf.

The post will try to explain three main things about the result. What is the result? Why is it important? And finally, how did the authors prove it?

We will assume that the reader is an undergraduate student in CS (i.e., the reader knows basics of discrete mathematics, linear algebra, and algorithm design).

What?

The main result can be stated in just one line! Bipartite Perfect Matching can be solved in NC. Let's now understand what each of these terms means.

Bipartite Perfect Matching. A bipartite graph has two disjoint sets of vertices, say \(L, R\), and any edge connects one vertex of \(L\) and one vertex of \(R\). A matching in a graph is a subset of edges such that no two edges have a vertex in common. A perfect matching is a matching in which each vertex of the graph appears exactly once. Let's take the following example. Here is a bipartite graph.

 

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.

Consider another example. Given an integer matrix \(A\), suppose we wish to compute its determinant; we refer to this as the DET problem. Sequentially, the determinant can be computed efficiently using Gaussian elimination. More surprisingly—and this is far from obvious—the problem also admits an efficient parallel algorithm (DET \(\in\) NC). (Here are some references: Csanky's paper, Berkowitz' paper.) We will use this statement as a black box many times below.

So, overall the new result states that given a bi-adjacency matrix of a graph, checking whether it has a perfect matching or not can be solved efficiently by a parallel algorithm.

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

\(G\) has a perfect matching if and only if \(\widehat{A_G}\) has full row rank.

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?

Herman Chernoff (1923-2026)

Herman Chernoff passed away on July 6, 5 days after turning 103. Ravi Boppana wrote a guest post about Chernoff's life for his 100th birthday. 

Let me talk about his most famous work, the Chernoff Bounds themselves.

If you have a coin that will be heads with probability \(p\), and you flip it \(n\) times, the expected number of heads is \(pn\). Informally Chernoff bounds says that for large \(n\) the number of heads will be quite close to \(pn\) with an exponentially small probability of being far away from \(pn\). For example, if you flip a coin with probability 30% chance of being heads 10,000 times, the probability that you will get at most 2500 heads is less than \(10^{-18}\).

More formally, for \(\delta \in (0,1)\), Chernoff's bound shows that

\[\Pr[|X - \mu| \geq \delta\mu] \leq 2e^{-\mu\delta^2/3}\]

for \(\mu = \mathbb{E}[X]\). I find the variation known as Hoeffding's inequality \[\Pr[|X - \mu| \geq t] \leq 2e^{-2t^2/n}\] easier to use for computational complexity.

Chernoff bounds play a major role in computational complexity, for example you can use Chernoff Bounds for probabilistic, quantum and interactive proof algorithms to reduce the error to exponentially small. That means using the union bound, a single random sequence will give the correct answer for all inputs, showing that BPP is in P/poly. 

Chernoff bounds are a key ingredient in the proof that MA (prover then verifier) is contained in AM (verifier then prover). Roughly you make the MA error so small that the same random coins work no matter what the prover might say. MA in AM plays a key role in the proof that NP in BPP implies PH in BPP which itself is necessary for Toda's theorem.

The proof of Chernoff bounds comes from a simple trick: Rather than bounding \(\Pr[X \geq a]\) directly via Markov's inequality on \(X\), you apply Markov to \(e^{tX}\) for a free parameter \(t > 0.\) Since \(e^{tX}\) is nonnegative,

\[\Pr[X \geq a] = \Pr[e^{tX} \geq e^{ta}] \leq \frac{\mathbb{E}[e^{tX}]}{e^{ta}},\]

and then you optimize over \(t\). The quantity \(\mathbb{E}[e^{tX}]\) is the moment generating function, and for a sum \(X = \sum_i X_i\) of independent variables it factorizes into \(\prod_i \mathbb{E}[e^{tX_i}]\). That factorization is what converts a linear tail bound into an exponential one, each independent term contributes multiplicatively, so the deviation probability shrinks like a product rather than a sum.

Chernoff did not think of himself as a theorist. 

People regard me as a theoretical statistician, but I’ve decided in recent years that I’m really an applied statistician. My theoretical insights have relied upon my work in thinking about applied problems.

A good lesson for us all.

2... 1/2 THEN 3... 1/6 THEN 5 ....1/15 and so on. And So On?

The excellent graphic novel

Prime Suspects: The Anatomy of Integers and Permutations

by Andrew Granville and Jennifer Granville,  illustrated by Robert J Lewis,

(I wrote a review of this graphic novel, for SIGACT News, here.)

has an appendix, which is not in graphic-novel form, where they describe some of the math talked about in the graphic novel. 

Here is a quote that intrigued me for two reasons

2 is the smallest prime factor of half of the integers,

3 is the smallest prime factor of one-sixth of the integers,

5 is the smallest prime factor of one-fifteenth of the integers,

and so forth.

Intrigue One: and so fourth ? Really? That would indicate that it is easy to know what the next fraction is.  Is it easy? That depends on your definition of easy.

Intrigue Two: What is the next fraction? What is the fraction asymptotically? I worked  both of these out fairly fast; however, I  don't think  and so forth is appropriate.

We derive the 1/15 for 5.  1/5 of all numbers have a factor of 5. Of those, only those that are \(\equiv 1,5 \pmod 6\) have 5 as the smallest  prime factor.  Hence \(2/6=1/3\) of those numbers have 5 as the smallest  prime factor. Hence the fraction is \(1/5 \times 1/3 = 1/15\). 

More generally: For all \(i\in N\) let  \(p_i\) be the \(i\)th  prime. What fraction of numbers have \(p_n\) as the smallest factor? \(1/p_n\) of all numbers have a factor of \(p_n\). If a number that is divisible by \(p_n\) is also  \(\equiv x \pmod {p_1p_2\cdots p_{n-1}}\) where \(1\le x\le p_1\cdots p_n\) and \(x\) is rel prime to \(p_1\cdots p_n\), then that number has  \(p_n\) as the smallest factor. Hence the fraction is 

\(\frac{1}{p_n} \times \frac{\phi(p_1\cdots p_{n-1})}{p_1\cdots p_n}=\frac{1}{p_n} \times \frac{(p_1-1)\cdots(p_{n-1}-1)}{p_1\cdots p_{n-1}}= \frac{1}{p_n}\prod_{i=1}^{n-1} (1-\frac{1}{p_i})\)

where \(\phi\) is the Euler-phi function which, on input \(x\), returns the number of naturals in [1,n] that are relatively prime to \(n\). We have used the following well known facts: (a) if \(a,b\) are rel prime then \(\phi(ab)=\phi(a)\phi(b)\), and (b) if \(p\) is prime then \(\phi(p)=p-1\) (this is obvious).  

The expression

\(\frac{1}{p_n} \times \frac{(p_1-1)\cdots(p_{n-1}-1)}{p_1\cdots p_{n-1}}\)

is good for exact calculation. Let's do one!

The fraction of numbers that have 7 as their least prime factor is

\( \frac{1}{7}\times  \frac{1\times 2\times 4}{2\times 3\times 5}= \frac{4}{105} \)

From the first three terms  \( \frac{1}{2}, \frac{1}{3}, \frac{1}{15} \) I do not think that and so fourth would make anyone think the next term was \(\frac{4}{105}\).

 But what is the fraction asymptotically? 

ChatGPT tells me (and I believe it) that

 \( \prod_{i=1}^{n} (1-\frac{1}{p_i})   \sim \frac{e^{-\gamma}}{\ln p_n} \) 

where \(\gamma\) is the Euler-Mascheroni constant, roughly 0.5772 (see here for the Wikipedia entry on that constant).

Hence we get that the fraction of numbers that have \(p_n\) as their smallest prime factor is 

 \(\frac{1}{p_n} \prod_{i=1}^{n-1} (1-\frac{1}{p_i})   \sim\frac{1}{p_n} \frac{e^{-\gamma}}{\ln p_{n-1}} \) 

Wolfram Alpha tells me (and I believe it) that

 \(e^{-0.5772}\sim 0.56146\).

 Hence we give our final approx for the fraction of numbers that have \(p_n\) as their least prime factor as

\(\frac{0.56146}{p_n\ln(p_{n-1})}\)   

I don't think this qualifies as and so forth.

Wither/Whither the ACM

Two editorials in the July issue of the Communications of the Association for Computing Machinery ask about the decay and future of the organization itself.

Jim Larus, editor-in-chief of the CACM, writes Wither ACM? Publish and Perish?

ACM no longer has broad appeal as a professional organization, does not advance many members’ careers, and may not be a valuable affiliation in a more diverse technical world...It is time to recognize that ACM has shifted from functioning as a professional society for the academic computing community to a professional publisher....It is time for ACM members to debate what kind of organization ACM should be and how to remake it into the society they want to belong to!

Vardi writes Whither Computing? starting with the concerns of PhD students whether they made the right choice by going into computer science and ending with a call for ACM to lead the conversation.

A new team will assume the leadership of ACM on July 1, 2026, following the current general election and search for a new chief executive officer. I believe this team will have to grapple with existential questions about the future of computing as a science and a profession...If ACM is about “advancing computing as a science and profession,” then we need to engage in a deep conversation about what this phrase means today for education, research, the profession, and ACM, and about how to truly advance computing as a science and profession.

ACM hasn't served as a true professional society for a long time. Unlike in other fields, ACM doesn't hold annual meetings for the whole community, and shares the spotlight with IEEE-CS, USENIX, AAAI, CRA and others. CRA takes the lead in research and organizes the CS department chairs meetings. ACM has focused on journals, conferences through its SIGS and awards.

This worked well while computing went through tremendous growth from after the financial crisis until a couple of years ago. But now artificial intelligence is making us rethink how we do research, publish and educate. What does it even mean to be a computer scientist in the AI era?

So good luck to incoming president Elisa Bertino and her team. Computing is changing. How will ACM change with it?

Extreme cases of clickbait!

I recently read Alan Alda's first memoir Never have your dog stuffed which was pretty good. Hence I began looking for more information about him on the web. I came across a YouTube video  At 89, Alan Alda reveals the seven actors he HATED the most.  Gee, in the book he didn't hate anyone. So I was curious what this was about. This could be interesting. It was not. The title was extremely deceptive. (More than most clickbait?)  Here is the list and what was said about them:

Wayne Rogers (Trapper John on MASH): The YouTube video said Wayne Rogers felt he didn't have a big enough role on MASH. 

Maclean Stevenson (Henry Blake on MASH): Same as Wayne Rogers.

Gary Burghoff (Radar O'Reily on MASH). The YouTube video said that Gary had emotional outbursts on set, or isolated himself. He felt trapped in the role, unable to grow. 

Robert Duvall (Played Frank Burns in the Movie MASH). The YouTube video said that Robert Duvall   had a different take on the role of Frank Burns in the movie than that Alan Alda had for the TV show. Note that this was not the role Alan Alda played. Also note that  Robert  D and Alan A have never met.

Edward Winter (Played Colonel Flagg on MASH): The YouTube video said that Winter was only in  7 of the 251 episodes. 

David Ogden Stiers (Played Charles Winchester on MASH): The YouTube video said that  David did not socialize with the crew.

Larry Linville (Played Frank Burns on MASH): The YouTube video said that Larry L did not like that his role was one-dimensional. 

Quote:

Did Alan Alda hate these actors? Probably not.

Also a common line was 

Alan has always spoken of X in positive terms.

The clickbait worked in that I read it, and indeed, I am blogging about it. But I won't fall for clickbait for another 5 years (the last time I fell for click bait before this was 5 years ago.)

Lesson of the day: do not fall for clickbait. 

Points:

1)  Since it is well known that clickbait is deceptive, does it still work. Well... I fell for it. 

2)  Is this clickbait more deceptive than usual or not?

3) The term clickbait was coined in 2008 by Jay Geiger in a blog post. The word was added to the Oxford English Dictionary in 2016. For more on the word see here.

4) Is the title of this blog  post, Extreme cases of clickbait!, itself clickbait? 

5) Could an AI be trained to classify videos as Clickbait or Not? In general no since one person's clickbait is another person's  HMMM- what is the opposite of clickbait? (Google said  anti-clickbait and honest-headline, neither of which really works.) Perhaps AI could be trained on what (say) Lance thinks is clickbait. 

Request

If you have an extreme example of clickbait, please leave a comment about it. 

The True Method

Harry Lewis pointed Bill and me to Gottfried Leibniz's 1677 treatise The True Method (translated from the original French). I highly recommend taking the time to read this three page document where he talks about formalizing all human knowledge.

The second paragraph has some of the intuition for P v NP three centuries before Cook, Levin and Gödel. 

But knowledge depends on proof, and discovering proofs requires a certain method that is not known to everyone. Every person is capable of judging a proof, since it would not deserve to be called a proof unless everyone who considered it carefully found it convincing. Nevertheless, not everyone is capable of discovering proofs independently or of presenting them clearly once they have been found, whether for lack of time or for lack of method. 

Though by "not everyone" he might have excluded himself.

Every investigation that depends on reasoning would be carried out by manipulating these symbols, through a kind of calculation. This would make the discovery of important results entirely straightforward. We would no longer have to rack our brains as much as we do today, while still being certain that we could accomplish everything that was possible from the information given.

Though not clear if "that was possible" took computational time into account. Is he claiming P = NP?

The article as a whole talks about a project to develop a fully logical language to cover not just mathematics, but the sciences like physics and medicine and even morality, politics and law. Here he was just being too ambitious and missing complexity issues, for example that you can't create laws that fully cover all potential futures.

Leibniz does give himself an out, a nod to the scientific method that was being developed during that time.

Some experiences will always be needed as the foundation for reasoning. But once those experiences have been supplied, we could derive from them everything that anyone could ever derive. We could even determine which further experiments still needed to be performed in order to clear up all remaining doubts.

He even gives a nod to probability. 

This would be of extraordinary assistance even in politics and medicine, where we must reason consistently and correctly from given symptoms and circumstances. Even when there are not enough facts to form an infallible judgment, it would still be possible to determine what is most probable from the information available. That is everything reason can do.

Sort of how machine learning works now.

Guest Post by Peter Brass on the new NSF guidelines

Peter Brass is a prior NSF theory director. He has written an intelligent guest post on the new NSF guidelines that we present here.

---

You have received many mails regarding the proposed OMB Uniform Guidance for federal grant making. It is a very long document. So far the OMB has received more than 32,000 comments, which nominally all will be read and taken into account, but actually most are general comments along the lines of “this will destroy scientific research,” and unspecific comments will achieve nothing. You can sample the comments, they are public, and you will be disappointed: much heat but no illumination.

It is my aim to bring a bit more content to the debate, and encourage you to file comments, but on specific issues, in my opinion primarily on the passage against “promoting anti-American Values,” which might indeed be a catch-all for political pressure on research. Otherwise there is little new: reviews were always only advisory.

The relevant section is https://www.federalregister.gov/d/2026-10817/p-amd-155, the revision of section 200.205, especially section (b) “pre-issuance review,” which states (underline and boldface mine):

(b) Pre-issuance review. As part of the merit review process, Federal agencies must perform pre-issuance reviews to ensure that Federal award proposals selected for funding are consistent with applicable law, Federal agency priorities, and the national interest. In doing so, Federal agencies heads must designate one or more senior appointees to conduct a pre-issuance review of all discretionary awards. As part of this pre-issuance review for discretionary awards, senior appointees (or their designee) must, as relevant and to the extent consistent with applicable law, apply the following principles when reviewing Federal award proposals:

This is followed by a list of criteria, but to summarize this: The agency head (a presidential appointment) designates a senior appointee (possibly a presidential appointment) who might designate another person inside the agency, who checks all intended awards that certain criteria are satisfied. This is not really different from the state before 2025: any proposal I proposed for award needed to be checked by the division director.

So if there is a problem, it must be in the criteria. It turns out there might be, depending on the interpretation.

1. Discretionary awards must, where applicable, demonstrably advance the President’s policy priorities.
   Whether this is applicable is the agency’s decision.
2. Discretionary awards must not be used to fund, promote, encourage, subsidize, or facilitate:
   • (i) Racial preferences or other forms of racial discrimination by the recipient, including activities where race or intentional proxies for race will be used as a selection criterion for employment or program participation;
   • (ii) Denial by the recipient of the sex binary in humans or the notion that sex is a chosen or mutable characteristic;
   • (iii) Illegal immigration; or
   • (iv) Any other initiatives that compromise public safety or promote anti-American values.
   That last one is a catch-all, which can indeed be used by politics to suppress research. This is the passage against which we should protest.
3. All else being equal, preference for discretionary awards should be given to institutions with lower indirect cost rates.
   All else is never equal, but it is in the program director’s discretion to consider how much funding actually reaches science.
4. Discretionary awards should be given to a broad range of recipients. Research grants should be awarded to a mix of recipients likely to produce immediately demonstrable results and recipients with the potential for potentially longer-term, breakthrough results, in a manner consistent with the notice of funding opportunity.
   I am quite happy about this explicit recognition of the importance of basic research.
5. In performing activities under Federal awards, applicants should commit to complying with administration policies, procedures, and guidance respecting Gold Standard Science.
   It is fairly unclear what Gold Standard Science is, but that seems to affect only lab or simulation sciences with results that are advisory to politics.
6. Discretionary awards should include benchmarks for measuring success and progress towards relevant goals and, as relevant for awards pertaining to scientific research, a commitment to achieving Gold Standard Science.
   Same. For us the benchmark measuring success is publication, so no news.
7. To the extent institutional affiliation is considered in making discretionary awards, agencies should prioritize an institution’s commitment to rigorous, reproducible scholarship over its historical reputation or perceived prestige. For science grants, agencies should prioritize institutions that have demonstrated success in implementing Gold Standard Science.
   No news either. We should not give extra credit to a proposal coming from a famous institution. Of course that is in the discretion of the program director.

(c) Procedure for pre-issuance review. When conducting a pre-issuance review, senior appointees (or their designee) must not ministerially ratify or routinely defer to the recommendations of others, but must instead use their independent judgment when evaluating Federal award proposals.

(so the designee should actually look at the proposal before approving the award)

(d) Use of peer review. Nothing in this part must be construed to discourage or prevent the use of peer review methods to evaluate proposals for discretionary awards or otherwise inform agency decision making, provided that peer review recommendations remain advisory and are not ministerially ratified, routinely deferred to, or otherwise treated as de facto binding by senior appointees or their designees. Further, nothing in this part must be construed to create any rights to any particular level of review or consideration for any funding applicant except as consistent with applicable law.

(good news: nothing changes)

(e) Agency discretion to reissue funding opportunities. A Federal agency is not required to issue a discretionary award as a result of a NOFO if doing so would fund low-quality proposals or be inconsistent with the principles of this part. The agency may, at its discretion, repost a funding opportunity.

(so the agency can decide not to make any award)

This is the entire section which causes so much outcries. I believe that the proposed budget cuts are a much larger danger to research than these recommended OMB rules.

The Zone

When you start thinking deeply about a mathematics problem you may enter the "zone", a period of intense focus where you think solely about the problem and potential solutions, and more importantly block out all other thoughts and even lose track of time. Mathematicians don't own the zone, actors, musicians, athletes and many others have their own version of the zone. But for math, when working on an open problem, you have no idea how difficult a solution may be, or if a solution exists at all. Most of the time you will fail (if not you need to try harder problems). Failure is not wasted time. You may find a counterexample, a partial solution and always you will come out with a better understanding of the problem. Then days, months or years later, some new proof idea comes from a paper, a talk or just the back of your head, and back in the zone you go. And when you do succeed you get a feeling not unlike scoring a goal in a soccer game. You should see my proof dance.

With AI generated and assisted proofs, we may think of outsourcing the zone to ChatGPT and Claude. We may prove more and stronger theorems, but you'll understand the results just a little bit less and mathematics will become a little less fun.