seminar

Seminar

Constraints, Logic and Derandomization

Gabor Kun, Simon Fraser University; Member, School of Mathematics
Tue, 05/26/2009 - 10:30 to 12:30
Room: 
S-101

In their seminal paper Feder and Vardi proved that every problem in the class Monotone Monadic Strict NP (MMSNP) is random polynomial-time equivalent to a finite union of Constraint Satisfaction Problems (CSP). The class MMSNP is the "largest natural" subclass defined by syntactical restrictions on existential, second order formulas that might have the dichotomy property. This was the main reason for the famous dichotomy conjecture of Feder and Vardi for CSP problems.

events: 

To Check is To Know is To Prove

Doron Zeilberger, Rutgers, The State University
Tue, 05/19/2009 - 10:30 to 12:30
Room: 
S-101

It has been checked, for zillions of even numbers, that they can all be expressed as a sum of two primes. It has also been checked for zillions of (non-trivial) zeros of Zeta(s), that their real parts are all equal to one half. Alas, these checks do not (yet) constitute a proof. But in many other analogous cases, such checks lead to fully rigorous proof, and there is always the low-budget option, of checking less, and settling for a semi-rigorous proof, since absolute certainty (like a Ferrari or a diamond ring) is an unnecessary luxury, whose only purpose is to cater to human vanity.

events: 

The Density Hales-Jewett Theorem and Open-Source Mathematics

Ryan O'Donnell, Carnegie Mellon University
Mon, 05/18/2009 - 11:15

On Feb. 1, in his blog, Tim Gowers proposed an open collaboration on a math problem. Specifically, he suggested working on a combinatorial proof of the Density Hales-Jewett Theorem. This theorem states that for every delta > 0, if n is sufficiently large and A is a set of at least delta 3^n strings from {1,2,3}^n, then A must contain a "combinatorial line"; i.e., three strings achievable by replacing the *'s by 1, by 2, and by 3 in a template from {1,2,3,*}^n. This theorem had been previously proven using ergodic-theory methods which gave no effective bound for n in terms of delta.

events: