{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreidj7uixizhw345zej3ds7pw3i4pjb3dfuqym74ap2p4hly5sycjna",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mfbbll5o4d32"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2602.16810v1",
  "publishedAt": "2026-02-20T01:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Anna Gal",
    "Noah Fleming",
    "Deniz Imrek",
    "Christophe Marciot"
  ],
  "textContent": "**Authors:** Anna Gal, Noah Fleming, Deniz Imrek, Christophe Marciot\n\nUnlike in TFNP, for which there is an abundance of problems capturing natural existence principles which are incomparable (in the black-box setting), Kleinberg et al. [KKMP21] observed that many of the natural problems considered so far in the second level of the total function polynomial hierarchy (TF$Σ_2$) reduce to the Strong Avoid problem. In this work, we prove that the Linear Ordering Principle does not reduce to Strong Avoid in the black-box setting, exhibiting the first TF$Σ_2$ problem that lies outside of the class of problems reducible to Strong Avoid. The proof of our separation exploits a connection between total search problems in the polynomial hierarchy and proof complexity, recently developed by Fleming, Imrek, and Marciot [FIM25]. In particular, this implies that to show our separation, it suffices to show that there is no small proof of the Linear Ordering Principle in a $Σ_2$-variant of the Sherali-Adams proof system. To do so, we extend the classical pseudo-expectation method to the $Σ_2$ setting, showing that the existence of a $Σ_2$ pseudo-expectation precludes a $Σ_2$ Sherali-Adams proof. The main technical challenge is in proving the existence of such a pseudo-expectation, we manage to do so by solving a combinatorial covering problem about permutations. We also show that the extended pseudo-expectation bound implies that the Linear Ordering Principle cannot be reduced to any problem admitting a low-degree Sherali-Adams refutation.",
  "title": "Separations above TFNP from Sherali-Adams Lower Bounds"
}