Mittagsseminar (in cooperation with J. Lengler, A. Steger, and D. Steurer)

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

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Jan Hazla

Parallel Repetition and Density Hales-Jewett Theorem

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:   2024  2023  2022  2021  2020  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