Electrical Reduction, Homotopy Moves, and Defect

Hsien-Chih Chang, Jeff Erickson

We prove the first nontrivial worst-case lower bounds for two closely related problems. First, $\Omega (n^{3/2})$ degree-1 reductions, series-parallel reductions, and $\Delta$Y transformation…