Semi-Algebraic Proof Systems for QBF
Olaf Beyersdorff, Ilario Bonacina, Kaspar Kasche, Meena Mahajan, Luc Nicolas Spachmann · 2025
Read Semi-Algebraic Proof Systems for QBF by Olaf Beyersdorff, Ilario Bonacina, Kaspar Kasche, Meena Mahajan, Luc Nicolas Spachmann (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-08050.txt.
Description
Olaf Beyersdorff, Ilario Bonacina, Kaspar Kasche, and Meena Mahajan introduce semi algebraic proof systems for QBF Boolean rules. Such rules add for all and there exists choices to usual logic, making proof analysis harder. The new systems mirror plain Nullstellensatz, Sherali Adams, and Sum of Squares methods in the QBF setting.
Techniques come from both QBF formula research, through strategy extraction, and plain proof complexity, through size degree relations and pseudo expectations. With them, the authors prove strong lower bounds and separations between these systems. The separations hold even when plain hardness is set aside, showing genuinely QBF difficulty.
Catalog record
| CREATOR | Olaf Beyersdorff, Ilario Bonacina, Kaspar Kasche, Meena Mahajan, Luc Nicolas Spachmann |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 84 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-08050