Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > SHERALI-ADAMS LOWER BOUNDS:
Reports tagged with Sherali-Adams Lower Bounds:
TR26-023 | 18th February 2026
Noah Fleming, Anna Gal, Christophe Marciot, Deniz Imrek

Separations above TFNP from Sherali-Adams Lower Bounds

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 ... more >>>




ISSN 1433-8092 | Imprint