Sponsored by the Rutgers University Department of Mathematics and the
Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)

Andrew Baxter, Rutgers University, baxter{at} math [dot] rutgers [dot] edu
Lara Pudwell, Rutgers University, lpudwell {at} math [dot] rutgers [dot] edu
Doron Zeilberger, Rutgers University, zeilberg {at} math [dot] rutgers [dot] edu

Title: An Isoperimetric problem on the d-dimensional torus in two flavors: discrete and continuous

Speaker: Mario Szegedy, Rutgers University

Date: Thursday, February 21, 2008 5:00pm

Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ


Higher powers of the Odd Cycle Game have been the focus of recent investigations. Feige, Kindler and Odonnell have shown that if we repeat the game $d$ times in parallel, the winning probability is upper bounded by 1-\Omega(sqrt{d}/ n\sqrt{\log d}), when d\le n^2\log n. We determine the exact value of the square of the game and develop a new metric conjectured to give the precise value of the game up-to second order precision in 1/n for constant d. Our proofs further develops on the geometric- topological intuition introduced in FKO.