Strong vs. Weak Range Avoidance and the Linear Ordering Principle

In a pair of recent breakthroughs Chen, Hirahara, Ren and Li
proved new exponential circuit lower bounds for uniform classes by giving
new algorithms for the Range Avoidance problem. We investigate the extent
to which similar algorithms are possible for other total search problems in
the second level of the polynomial hierarchy, and more generally
investigate the landscape of the class TF\Sigma_2. On the negative side we
show that for the “Strong Avoid” problem (when the codomain is only larger
then the domain by 1 element) such algorithms are impossible in the black
box model; this is obtained by proving an exponential size depth 3 circuit
lower bound for the “strong” variant of Vyas and Williams’ Missing String
problem. On the positive side we show that Chen, Hirahara, Ren and Li’s
upper bound for Range Avoidance can be improved to give a reduction to a
natural search problem we call the “Linear Ordering Principle:” given a
binary relation < supposedly defining a linear order, find its minimal
element or else a witness that it is not a total order.