It is a long-standing open problem in algebraic complexity to prove lower bounds against multilinear algebraic branching programs (mABPs). The best lower bounds in this setting are still quadratic (Alon, Kumar and Volk (Combinatorica 2020)). At the same time, it remains a possibility that the “min-partition rank” method introduced by Raz (Theory Comput. 2006), which is used to prove all known multilinear lower bounds, can also be used to prove superpoly- nomial lower bounds on the size of mABPs.

In this paper, we analyze the potential of the min-partition rank method to prove lower bounds on the size of mABPs and prove the following:

1. We relate this method to a purely combinatorial question regarding the minimum size of a set system whose chains satisfy a discrepancy condition. In the case of set-multilinear ABPs, this characterizes the best lower bound that can be achieved.

2. We prove a non-trivial upper bounds on the size of set systems with this combinatorial property. This recovers a superpolynomial separation between mABPs and multilinear formulas (Dvir, Malod, Perifel and Yehudayoff (STOC 2012)). Our proof is conceptually different, and may have wider consequences.

3. The property we study extends combinatorial notions of “balancing sets” considered in previous works, for which near-tight bounds are known via intervals. We show that intervals are very far from satisfying our property. This showcases how our methods capture combinatorial structure that evades previous techniques.

These results build a bridge between algebraic complexity theory and the behavior of random walks. The upper bound uses the fact (Csáki, Erdos, and Révész (PTRF 1985)) that a random walk of length $n$ on the integers returns to its starting point once every $\leq n/ log n$ steps with noticeable probability. To show the latter result, we prove that two independent random walks are “far” from each other in discrete Fréchet distance.