Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People
Events

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: How Much Commutativity is Needed to Prove Polynomial Identities?
event speaker icon
Pavel Hrubes (Institute of Advanced Studies, Princeton)
event date icon
Wednesday, 09.03.2011, 12:30
event location icon
Taub 701
The so called Extended Frege system is one of the most natural propositional proof systems. Whereas we believe that there exist tautologies which require exponential Extended Frege proofs, the best known lower bound is linear. To find even a modestly superlinear lower bound is a challenging open problem. I will discuss a possible approach to this question, which is based on counting the number of commutativity axioms in an Extended Frege proof, which in turn can be phrased as an algebraic problem about non-commutative polynomials. We will see that this line of reasoning generates new difficult questions, rather than answering the original one.