Computer Science/Discrete Mathematics Seminar I

The development of set theory in the 20th century was like the invention of a "mathematical telescope", through which we can observe all kinds of infinite sets and their interactions. In quite the opposite direction, bounded arithmetic serves as a "mathematical microscope", enabling us to understand and harness logical structures within elementary mathematics. 

The starting point of this talk is the bounded arithmetic theory PV (Cook '75), which intuitively captures the mind of a (weird?) mathematician who only works with Boolean strings and deterministic polynomial-time algorithms -- nothing else is allowed in theorems and proofs. This theory is "weak and strong" -- it does not seem to prove the Pigeonhole Principle, yet it can naturally formalize the celebrated PCP theorem. 

Interestingly, since this mathematician only accepts polynomial-time algorithms, probability over an exponential-sized support is not available. In this talk, I will cover classical and new approaches to extending PV with probabilistic toolkits. I will also discuss a somewhat surprising application: cryptography from the unprovability of mathematical theorems in these theories. 

(This talk will focus on high-level ideas; no prior background in logic is needed.)