First-Order Reasoning and Efficient Semi-Algebraic Proofs

Fedor Part, Neil Thapen, Iddo Tzameret

Semi-algebraic proof systems such as sum-of-squares (SoS) have attracted a lot of attention recently due to their relation to approximation algorithms: constant degree semi-algebra…