Abstract

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.