[Colloquium] Aaron Zhang MS Presentation/May 25, 2022
Megan Woodward
meganwoodward at uchicago.edu
Thu May 12 12:39:07 CDT 2022
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/20220512/4b60dbad/attachment-0001.pdf>
More information about the Colloquium
mailing list