 ## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

 Mittagsseminar Talk Information

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!)

Information for students and suggested topics for student talks