Open Collections

BIRS Workshop Lecture Videos

Banff International Research Station Logo
Featured Collection

BIRS Workshop Lecture Videos

Semi-Algebraic Proof Systems for QBF Kasche, Lea

Description

We introduce new semi-algebraic proof systems for Quantified Boolean Formulas (QBF) analogous to the propositional systems Nullstellensatz, Sherali-Adams and Sum-of-Squares. We transfer to this setting techniques both from the QBF literature (strategy extraction) and from propositional proof complexity (size-degree relations and pseudo-expectation). We obtain a number of strong QBF lower bounds and separations between these systems, even when disregarding propositional hardness.

Item Metadata

Title
Semi-Algebraic Proof Systems for QBF
Creator
Kasche, Lea
Publisher
Banff International Research Station for Mathematical Innovation and Discovery
Date Issued
2026-01-15
Description
We introduce new semi-algebraic proof systems for Quantified Boolean Formulas (QBF) analogous to the propositional systems Nullstellensatz, Sherali-Adams and Sum-of-Squares. We transfer to this setting techniques both from the QBF literature (strategy extraction) and from propositional proof complexity (size-degree relations and pseudo-expectation). We obtain a number of strong QBF lower bounds and separations between these systems, even when disregarding propositional hardness.
Extent
29.0 minutes
Subject
Mathematics; Theoretical Computer Science; Mathematical Logic And Foundations; Computer Science
Type
Moving Image
File Format
video/mp4
Language
eng
Notes
Author affiliation: University of Jena
Series
BIRS Workshop Lecture Videos (Banff, Alta)
Date Available
2026-01-19
Provider
Vancouver : University of British Columbia Library
Rights
Attribution-NonCommercial-NoDerivatives 4.0 International
DOI
10.14288/1.0451312
URI
http://hdl.handle.net/2429/93468
Affiliation
Non UBC
Peer Review Status
Unreviewed
Scholarly Level
Graduate
Rights URI
http://creativecommons.org/licenses/by-nc-nd/4.0/
Aggregated Source Repository
DSpace

Item Media

Item Citations and Data

Rights

Attribution-NonCommercial-NoDerivatives 4.0 International