Quels jeux 2P1R sont potentiellement pointus?

Les jeux à deux provers et à un tour (2P1R) sont un outil essentiel pour la dureté de l'approximation. Plus précisément, la répétition parallèle de jeux à un tour à deux prouveurs permet d'augmenter la taille d'un écart dans la version de décision d'un problème d'approximation. Voir le sondage de Ran Raz lors du CCC 2010 pour un aperçu du sujet.

La répétition parallèle d'un jeu a la propriété étonnante que même si un vérificateur aléatoire fonctionne indépendamment, les deux joueurs peuvent jouer aux jeux de manière non indépendante pour obtenir un meilleur succès que de jouer chaque jeu indépendamment. Le montant du succès est limité ci-dessus par le théorème de répétition parallèle de Raz:

Théorème : Il existe une constante universelle sorte que pour chaque jeu 2P1R de valeur et de taille de réponse , la valeur du jeu de répétition parallèle est au plus .G 1 - ϵ s G n ( 1 - ϵ c ) Ω ( n / s $c$$G$$1-\epsilon$$s$$G^n$$(1-\epsilon^c)^{\Omega(n/s)}$

Voici un aperçu du travail d'identification de cette constante :$c$

• Le papier original de Raz prouve .$c \leq 32$
• Holenstein a amélioré cela en .$c \leq 3$
• Rao a montré que $c' \leq 2$ suffit (et la dépendance à l' égard $s$ est retirée) pour le cas particulier des jeux de projection.
• Raz a donné une stratégie pour le jeu à cycle impair qui a montré que le résultat de Rao est net pour les jeux de projection.

Par cet ensemble de travaux, nous connaissons . Mes deux questions sont les suivantes:$2 \leq c\leq 3$

Question 1: Les experts dans ce domaine ont-ils un consensus sur la valeur exacte de ?$c$

Si l'on pense que , existe-t-il des jeux spécifiques qui ne sont pas projectifs, mais qui violent également spécifiquement les propriétés supplémentaires des jeux de projection dont la preuve de Rao a besoin.$c > 2$

Question 2: Si , quels jeux intéressants violent la stratégie de Rao et pourraient être des exemples précis?$c > 2$

D'après ma propre lecture, il semble que la propriété la plus importante des jeux de projection que Rao utilise est qu'une bonne stratégie de répétition parallèle n'utiliserait pas la plupart des réponses possibles pour certaines questions. Ceci est en quelque sorte lié à la localité des jeux de projection.

J'ai tendance à croire que c = 3 est la bonne réponse pour le cas général, et qu'il devrait être possible de donner un exemple. Je vais devoir y réfléchir davantage pour en être sûr. C'est une bonne question, et je ne connais pas les travaux existants à ce sujet.

La recherche s'est récemment concentrée sur les types de jeux qui ont (le meilleur possible) c = 1, principalement en raison des applications possibles à l'amplification de jeux uniques.

• Barak et al ont généralisé le contre-exemple de Raz à tous les jeux uniques avec des lacunes SDP.
• Raz et Rosen ont montré que pour étendre les jeux de projection, c = 1. Il existe également des résultats antérieurs par un super-ensemble de ces auteurs pour les jeux gratuits.

Pour faire avancer les choses, j'ai un jeu potentiel et j'aimerais avoir des commentaires.

Soit un entier et m un entier d'au moins 3 k + 1 avec . Le jeu cycle-puissance est le jeu 2P1R où les prouveurs tentent de convaincre le vérificateur que le graphe est colorable. Ici, est le graphe à sommets donné par des entiers modulo à arêtes si la distance mod- est au plus . S'il existe une coloration de , elle doit être donnée en choisissant un ordre de$k \geq 2$$m$$3k+1$C k m k + 1 C k m m m k k + 1 C k m { 1 , … , k } { 0 , … , m - 1 } k + 1 { 0 , … , m - 1 } m k + $m \not\equiv 0 {\pmod {k+1}}$$C_{m}^k$$k+1$$C_m^k$$m$$m$$k$$k+1$$C_m^{k}$$\{1,\dots,k\}$ et colorier les nombres dans cet ordre, puisque chaque ensemble d' entiers séquentiels dans forme une clique. Puisque n'est pas un multiple de , il y aura un moment où cette coloration échouera.$\{0,\dots,m-1\}$$k+1$$\{0,\dots,m-1\}$$m$$k+1$

Le vérificateur demande soit un seul sommet aux deux joueurs, pour vérifier que les couleurs correspondent, soit demande un bord pour vérifier que les couleurs sont différentes.

Je pense que c'est un bon exemple pour deux raisons:

1. Il est suffisamment similaire au jeu à cycle impair pour qu'une stratégie puisse être construite similaire à la limite inférieure de Raz. Une partie importante de cette stratégie consiste à choisir au hasard des colorations parmi les répétitions en utilisant l'aléatoire partagé.

2. En randomisant les permutations utilisées dans les colorations générées aléatoirement, le nombre de réponses données à chaque sommet couvre l'ensemble des réponses de manière uniforme, attaquant la stratégie de Rao.

Ce jeu a-t-il déjà été considéré / résolu?