Before revision:  We extend this framework by incorporating a cost scaling technique, and show that \rm deg Det A can be computed in time polynomial of n,m,\log_2 C, where C:= \max_k |c_k| , which says that \rm deg Det A is given by linear optimization over an integral polytope with respect to objective vector c = (c_k).
After revision:  We extend this framework by incorporating a cost scaling technique, and show that \rm deg Det A can be computed in time polynomial of n,m,\log_2 C, where C:= \max_k |c_k| . We give a polyhedral interpretation of \mathop{\rm deg Det, which says that \rm deg Det A is given by linear optimization over an integral polytope with respect to objective vector c = (c_k).