DIMACS - RUTGERS EXPERIMENTAL MATHEMATICS SEMINAR

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

Co-organizers:

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

Abstract:

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.