  We establish coNExpTime-completeness of the problem of deciding
order-invariance of a given two variable first-order formula, improving and
significantly simplifying coTwoNExpTime bound by Zeume and Harwath.
