Welche 2P1R-Spiele sind potenziell scharf?

Zwei-Prüfer-Einrundenspiele (2P1R) sind ein wesentliches Werkzeug für die Approximationshärte. Insbesondere die parallele Wiederholung von Zwei-Prüfer-Einrundenspielen bietet die Möglichkeit, die Lücke in der Entscheidungsversion eines Approximationsproblems zu vergrößern. Einen Überblick über das Thema finden Sie in Ran Raz 'Umfragevortrag auf der CCC 2010 .

Die parallele Wiederholung eines Spiels hat die erstaunliche Eigenschaft, dass, während ein zufälliger Verifizierer unabhängig arbeitet, die beiden Spieler die Spiele auf nicht unabhängige Weise spielen können, um einen besseren Erfolg zu erzielen, als jedes Spiel unabhängig zu spielen. Das Ausmaß des Erfolgs wird oben durch den Satz der parallelen Wiederholung von Raz begrenzt:

Satz : Es gibt eine universelle Konstante so dass für jedes 2P1R-Spiel mit dem Wert 1- \ epsilon und der Antwortgröße s der Wert des parallelen Wiederholungsspiels G ^ n höchstens (1- \ epsilon ^ c) ^ {\ beträgt Omega (n / s)} .$c$$G$$1-\epsilon$$s$$G^n$$(1-\epsilon^c)^{\Omega(n/s)}$

Hier ist ein Überblick über die Arbeit zur Identifizierung dieser Konstante $c$ :

• Raz 'Originalarbeit beweist $c \leq 32$ .
• Holenstein verbesserte dies auf $c \leq 3$ .
• Rao zeigte, dass c '\ leq 2 für den Spezialfall der Projektionsspiele $c' \leq 2$ausreicht (und die Abhängigkeit von $s$ beseitigt wird).
• Raz gab eine Strategie für das Odd-Cycle-Spiel an, die zeigte, dass Raos Ergebnis für Projektionsspiele scharf ist.

Durch dieses Werk kennen wir . Meine zwei Fragen lauten wie folgt:$2 \leq c\leq 3$

Frage 1: Haben Experten auf diesem Gebiet einen Konsens über den genauen Wert von ?$c$

Wenn angenommen wird, dass , gibt es bestimmte Spiele, die nicht projektiv sind, aber auch speziell die zusätzlichen Eigenschaften von Projektionsspielen verletzen, die Raos Beweis erfordert.$c > 2$

Frage 2: Wenn , welche interessanten Spiele verstoßen gegen Raos Strategie und können scharfe Beispiele sein?$c > 2$

Aus meiner eigenen Lektüre scheint es die wichtigste Eigenschaft von Projektionsspielen zu sein, die Rao verwendet, dass eine gute Strategie für parallele Wiederholungen nicht viele der möglichen Antworten für bestimmte Fragen verwenden würde. Dies hängt irgendwie mit der Lokalität der Projektionsspiele zusammen.

Ich neige dazu zu glauben, dass c = 3 die richtige Antwort für den allgemeinen Fall ist und dass es möglich sein sollte, ein Beispiel zu geben. Ich muss mehr darüber nachdenken, um sicher zu sein. Es ist eine gute Frage, und ich kenne keine vorhandenen Arbeiten darüber.

Die Forschung konzentrierte sich kürzlich darauf, welche Arten von Spielen (bestmöglich) c = 1 haben, hauptsächlich wegen möglicher Anwendungen zur Verstärkung einzigartiger Spiele.

• Barak et al. Verallgemeinerten das Gegenbeispiel von Raz auf alle einzigartigen Spiele mit SDP-Lücken.
• Raz und Rosen zeigten, dass für die Erweiterung von Projektionsspielen c = 1 ist. Es gibt auch frühere Ergebnisse einer Super-Gruppe dieser Autoren für kostenlose Spiele.

Um die Dinge ins Rollen zu bringen, habe ich ein potenzielles Spiel und möchte Feedback.

Sei eine ganze Zahl und eine ganze Zahl von mindestens mit . Das Zyklus-Kraft Spiel ist das Spiel , wo die 2P1R Beweiser versuchen , den Verifizierer zu überzeugen , dass der Graph ist färbbar. Hier ist die grafische Darstellung mit den Eckpunkten von ganzen Zahlen Modulo gegeben mit Kanten , wenn der mo- Abstand höchstens . Wenn es eine Färbung von , muss dies durch Auswahl einer Reihenfolge von und Färben der Zahlen angegeben werden$k \geq 2$$m$$3k+1$$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\}$$\{0,\dots,m-1\}$ in dieser Reihenfolge, da jeder Satz aufeinanderfolgender Ganzzahlen in eine Clique bildet. Da kein Vielfaches von , wird es irgendwann einen Punkt geben, an dem diese Färbung fehlschlägt.$k+1$$\{0,\dots,m-1\}$$m$$k+1$

Der Prüfer fordert entweder einen einzelnen Scheitelpunkt von beiden Spielern an, um zu überprüfen, ob die Farben übereinstimmen, oder er fragt nach einer Kante, um zu überprüfen, ob die Farben unterschiedlich sind.

Ich glaube, dies ist aus zwei Gründen ein gutes Beispiel:

1. Es ist dem Spiel mit ungeraden Zyklen ähnlich genug, dass eine Strategie ähnlich der unteren Grenze von Raz entwickelt werden könnte. Ein wichtiger Teil dieser Strategie ist die zufällige Auswahl von Farben über die Wiederholungen hinweg unter Verwendung einer gemeinsamen Zufälligkeit.

2. Durch die Randomisierung der Permutationen, die in den zufällig erzeugten Färbungen verwendet werden, überspannt die Anzahl der Antworten an jedem Scheitelpunkt die gesamte Antwort auf einheitliche Weise und greift Raos Strategie an.

Wurde dieses Spiel bereits in Betracht gezogen / gelöst?