Department of Computer Science | Institute of Theoretical Computer Science | CADMO

Prof. Emo Welzl and Prof. Bernd Gärtner

Mittagsseminar Talk Information |

**Date and Time**: Thursday, March 24, 2016, 12:15 pm

**Duration**: 30 minutes

**Location**: CAB G51

**Speaker**: Jan Hazla

I am going to discuss the equivalence of the density Hales-Jewett theorem (DHJ) and parallel repetition of multi-prover games (PR). I will explain both theorems and then sketch the equivalence proof.

Then, I will discuss some further results about PR inspired by this equivalence and our previous work with Elchanan Mossel.

I will not assume familiarity with DHJ or PR. Short explanations are attached below for convenience.

Joint work with Thomas Holenstein and Anup Rao.

———

Let [k] := { 1, …, k }. A combinatorial pattern in [k]^n is a string w(x) \in ([k] \cup {x})^n, where x is a formal variable that occurs in at least one coordinate. A combinatorial line is a set of k strings { w(1), ..., w(k) }.

For example, for k = 3, n = 4, “1x3x” is a combinatorial pattern, and { 1131, 1232, 1333 } is the respective combinatorial line.

The density Hales-Jewett theorem states that a subset S of [k]^n with measure \mu always contains a combinatorial line, provided n is big enough (depending on k and \mu).

———

In a k-prover game the verifier chooses a question tuple q = (q_1, …, q_k) from some probability distribution, sends a question q_i to prover P_i, receives back an answer a_i and then accepts or rejects based on some predicate V(q_1, …, q_k, a_1, …, a_k).

The provers know the question distribution and the predicate V. They cannot communicate with each other during the game, but they can agree on a strategy in advance. The value val(G) of a game G is the highest acceptance probability the provers can achieve.

Given a game G, a repeated game G^n is a game where the verifier independently samples n question tuples for G, then sends n questions to each prover, receives n answers and accepts if the predicate for game G accepts on all n instances.

We say that a game G with val(G) < 1 admits (weak) parallel repetition if val(G^n) goes to 0 as n goes to infinity.

Upcoming talks | All previous talks | Talks by speaker | Upcoming talks in iCal format (beta version!)

Previous talks by year: 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M | admin login