{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreib353u7u6caa7qwizfb7p7wmmqthbefwhpxdlp27g63euk3pfszou",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mf4hbxvon4f2"
  },
  "path": "/report/2026/023",
  "publishedAt": "2026-02-18T02:49:42.000Z",
  "site": "https://eccc.weizmann.ac.il",
  "textContent": "Unlike 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$\\Sigma_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$\\Sigma_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 $\\Sigma_2$-variant of the Sherali-Adams proof system. To do so, we extend the classical pseudo-expectation method to the $\\Sigma_2$ setting, showing that the existence of a $\\Sigma_2$ pseudo-expectation precludes a $\\Sigma_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": "TR26-023 |  Separations above TFNP from Sherali-Adams Lower Bounds | \n\n\tAnna Gal, \n\n\tNoah Fleming, \n\n\tDeniz imrek, \n\n\tChristophe Marciot"
}