Bounds on the Total Coefficient Size of Nullstellensatz Proofs of the Pigeonhole Principle and the Ordering Principle

Zhang, Aaron

2022

Formats

Action	Filename	Size	Access	Description	License
	MS.pdf	344.1 kB	Public	-	CC BY
	Approval.pdf	723.7 kB	Restricted to Admin Use	-	CC BY

We study the total coefficient size of Nullstellensatz proofs. We show that any Nullstellensatz proof of the pigeonhole principle on

$n$ pigeons and

$n - 1$ holes has total coefficient size at least

$2^{\Omega(n)}$ , and that there is a Nullstellensatz proof of the ordering principle on

$n$ elements with total coefficient size

$2^n - n$ .

Title

Bounds on the Total Coefficient Size of Nullstellensatz Proofs of the Pigeonhole Principle and the Ordering Principle

Author

Zhang, Aaron : University of Chicago : (0000-0002-9812-5770)

Degree Type

M.S.

Content Type

Thesis

Academic Advisor

Committee Member

Digital Object Identifier

Funding Information

NSF, Further Investigation of the Sum of Squares Hierarchy, CCF-2008920
NDSEG, NDSEG Fellowship, F-9422254702

Publication Date

2022-06

Language

English

Licensing

Record Appears in

Record Created

2022-06-17