[Colloquium] Aaron Zhang MS Presentation/May 25, 2022

[Megan Woodward]

This is an announcement of Aaron Zhang's MS Presentation
===============================================
Candidate: Aaron Zhang

Date: Wednesday, May 25, 2022

Time:  3 pm CST

Location: JCL 011

M.S. Paper Title: Bounds on the Total Coefficient Size of Nullstellensatz Proofs of the Pigeonhole Principle and the Ordering Principle

Abstract: We investigate the total coefficient size of Nullstellensatz proofs. We show that Nullstellensatz proofs of the pigeonhole principle on $n$ pigeons require total coefficient size $2^{\Omega(n)}$ and that there exist Nullstellensatz proofs of the ordering principle on $n$ elements with total coefficient size $2^n - n$.

Advisors: Aaron Potechin

Committee Members: Aaron Potechin, Alexander Razborov, and David Cash


-------------- next part --------------
A non-text attachment was scrubbed...
Name: MS.pdf
Type: application/pdf
Size: 289589 bytes
Desc: MS.pdf
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20220524/bf05355b/attachment-0001.pdf>