🚀 go-pugleaf

There have been several requests to have the seminar announced by mail.
As far as I know, there is no ``official'' mailing list for theory
people. I have constructed a list from /etc/groups. If you wish to receive
seminar announcements by mail and are not on the list, please let me know.

Time: Tuesday, November 22, 2pm EST

Location: University College Rm. 257

Speaker: Toni Pitassi

Summary:

This week we will look at a modified version of Armin Haken's
superpolynomial lower bound on the size of resolution proofs. 
In contrast with Armin's proof which relies on counting, 
this proof is adversarial (ie. feasibly constructive) 
in that we give a (polynomial) algorithm which
finds a contradiction when given an alleged short 
proof of the propositional pigeon-hole principle.

If time permits, we will see from this analysis 
when generalized versions of the pigeon-hole principle can and
cannot yield superpolynomial lower bounds using the same technique
(and why this is interesting).

Lastly, I'll try to fit these results into the bigger complexity
theoretic picture.