On the Complexity of Branching Proofs

Daniel Dadush, Samarth Tiwari

We consider the task of proving integer infeasibility of a bounded convex $K$ in ${\mathbb{R}}^n$ using a general branching proof system. In a general branching proof, one constructs…