MCSP is Hard for Read-Once Nondeterministic Branching Programs

We show that every read-once nondeterministic branching program computing the Minimum Circuit Size Problem on inputs of length N has size Omega(N (log log(N))). This is the first superpolynomial lower bound on the size of 1-NBP computing MCSP. This lower bound is tight for the version of MCSP restricted to a linear circuit size parameter. To show this result we adapt a conditional lower bound of Ilango [10] on the deterministic Turing Machine time complexity of computing MCSP*, the generalization of MCSP to partial functions. In contrast, our lower bound is unconditional and holds even for the total MCSP function. En route, we get two results that may be of independent interest: - The size of the minimal 1- NBP computing MCSP equals, up to a constant factor, the size of the minimal 1-NBP computing MCSP*; - The size of any 1- NBP computing (2nx2n)-Bipartite Independent Set is O(n!).