Złożoność komunikacji z sędzią

Załóżmy, że w strukturze złożoności komunikacyjnej mamy dwóch graczy A (wszy) i B (ob) i R (eferee). A i B nie komunikują się bezpośrednio ze sobą. W każdej rundzie komunikacji każda z nich wysyła wiadomość ($m_A$, $m_B$) do R. R oblicza dwie funkcje $f_A(m_A,m_B)$ i $f_B(m_A,m_B)$i wysyła do nich wyniki. Funkcje są ustalone. Chodzi o to, że komunikacja między graczami jest ograniczona. Ponadto sędzia może wykonać pewne przetwarzanie wiadomości.

Przykład:

A i B wysyłają dwie (dowolnie duże) liczby do R, R sprawdza, która z nich jest większa i informuje graczy.

W tym środowisku możemy zaprojektować prosty protokół, który z łatwością obliczy następującą funkcję za pomocą jednej rundy. Wysyłanie A i B.$x$ i $y$ do R, R zwraca odpowiedź, a oni wysyłają odpowiedź.

Oczywiście nie jest to interesujący przypadek, ponieważ obliczana przez nas funkcja jest taka sama jak funkcja sędziego. Bardziej interesujący jest przypadek, gdy mamy stałą nierówność liniową$\vec{a} \cdot \vec{x} \leq \vec{b} \cdot \vec{y}$ a wartości zmiennych są podzielone między graczy (A ma $\vec{x}$ a B ma $\vec{y}$). Zadaniem jest podjęcie decyzji, czy nierówność jest prawidłowa. W tym przypadku protokół polega na tym, że gracze obliczają swoją część, a następnie wysyłają ją do sędziego.

Pytanie:

Czy zbadano tego rodzaju złożoność komunikacji? Jeśli tak, gdzie mogę znaleźć więcej informacji na ten temat?

Uwaga 1: na stronie 49 Kushilevitz i Nisan wspominają o strukturze, która obejmuje sędziego, ale wydaje się bardzo różna od tego, o co proszę.

Uwaga 2: Nie jestem pewien, czy powołanie sędziego R. jest właściwe, proszę o komentarz, jeśli masz lepszą sugestię.

Jestem pewien, że znasz następujący artykuł, ale umieszczam link do niego, ponieważ inni czytelnicy mogą być zainteresowani: Interpolacja przez Gry

Ten artykuł jest próbą wykorzystania struktury złożoności komunikacyjnej do pokazania dolnych granic dla wycinania płaszczyzn. Protokół służy do wytworzenia obwodu interpolacyjnego dla niezadowalającego CNF:

Gracz $A$ dostaje wkład $a$ i $y^a$, gracz $B$ dostaje $b$ i $z^b$. Jeśli w płaszczyznach cięcia występuje dowód podobny do płytkiego drzewa, wówczas dwaj gracze mają taki protokół komunikacji

• w każdej komunikacji pośredniczy sędzia, co pomaga w ocenie nierówności w dowodzie;
• ilość komunikacji jest niewielka (drzewo jest płytkie);
• obaj gracze decydują, który z nich $A$ lub $B$ jest sfałszowany;
• znajdują pozycję $i$ w którym $a_i \not= b_i$.

Sędzia zostaje przekształcony w protokół probabilistyczny dotyczący nierówności. W ten sposób można zmienić dolną granicę dla drzewopodobnych protokołów probabilistycznych w strukturze złożoności komunikacyjnej na dolną granicę dla prób drzewiastych płaszczyzn cięcia.

Gdybyśmy mieli dolną granicę dla protokołu komunikacyjnego w postaci PLS, to otrzymalibyśmy dolną granicę dla próbnych wycinania płaszczyzn cięcia.

Zauważ, że ta technika nie zależy od faktycznych reguł wnioskowania płaszczyzn cięcia. Jeśli przyjmiemy, że reguły wnioskowania to (1) dodatnia kombinacja (2) dzielenie liczb całkowitych z podłogą, możemy zbudować monotoniczny obwód interpolacyjny za pomocą argumentu Pavla Pudláka .

Kilka uwag. Po pierwsze, nie rozumiem, dlaczego w ogóle potrzebujemy sędziego. Jeśli jego funkcja jest znana graczom, dlaczego nie mogą po prostu symulować sędziego? Alice wysyła$m_A$ Bobowi, on (nie widząc $m_A$) oblicza $m_B$, potem oblicza $f(m_A,m_B)$i przekazuje wynik Alice. Być może zakładasz to$f_A$nie jest znany Bobowi i$f_B$ do Alice?

Po drugie, protokoły związane z nierównościami liniowymi są rzeczywiście interesujące w kontekście sprawdzania płaszczyzny cięcia. W tym przypadku wystarczy rozważyć protokoły, w których forma komunikatów jest bardzo ograniczona : można przekazać tylko wartości niektórych liniowych kombinacji zmiennych wejściowych.

Aby być bardziej precyzyjnym, załóżmy, że otrzymujemy system liniowych nierówności o współczynnikach całkowitych. Wiemy, że system nie ma$0$-$1$rozwiązanie. Zmienne są w jakiś sposób podzielone między graczy (w pięćdziesiąt pięćdziesiąt sposób); jest to scenariusz „najgorszej partycji”: przeciwnik może wybrać partycję „najgorszą”. Dawać$0$-$1$ciąg, celem graczy jest znalezienie niezadowolonej nierówności. Oznacza to, że odpowiedź nie jest teraz ani jednym bitem, ale nazwą jednej nierówności naszego systemu. (Jest to gra komunikacyjna typu Karchmer-Wigderson.)

Rozważmy teraz następujące ograniczone protokoły dla takiej gry: (i) sędziowie działają, jeśli tylko $f(\alpha,\beta)=1$ iff $\alpha \leq \beta$, (ii) wiadomości graczy są ograniczone do wiadomości liniowych : w każdej rundzie Alicja musi wysłać wiadomość z formularza$m_A(\vec{x})=\vec{c}\cdot \vec{x}$, a Bob przesłanie formularza $m_B(\vec{y})=\vec{d}\cdot \vec{y}$.

Impagliazzo, Pitassi i Urquhart (1994) zaobserwowali, co następuje: Jeśli wszystkie współczynniki użyte w proofach płaszczyzny cięcia są wielomianowe pod względem liczby zmiennych i jeśli ta gra potrzebuje$t$ fragmenty komunikacji, a następnie każdy drzewny dowód na niezadowolenie danego systemu musi dać $\exp(t/\log n)$nierówności. Następnie wykorzystali znane dolne granice złożoności komunikacji, aby uzyskać wyraźny system wymagający dowodów wielkości wykładniczej. Wadą tego wyniku jest to, że system jest bardzo sztuczny , nie odpowiada „rzeczywistemu” problemowi optymalizacji. Dlatego interesujące jest ustalenie dolnej granicy „rzeczywistych” problemów z optymalizacją.

Jednym z takich problemów jest problem z niezależnym zestawem grafów. Biorąc pod uwagę wykres $G=(V,E)$ możemy skojarzyć z każdym wierzchołkiem $u$ zmienna $x_u$ i rozważmy system nierówności składający się z nierówności $\sum_{v\in V}x_v>\alpha(G)$i wszystkie nierówności $x_u+x_v\leq 1$ dla wszystkich krawędzi $uv$ z $G$. Ponieważ każdy$0$-$1$ rozwiązanie podsystemu tych ostatnich nierówności daje niezależny zestaw $G$, cały system nie ma rozwiązań zero-jedynkowych. Jaka jest złożoność komunikacyjna gier dla takich systemów?

Jeśli nasz wykres $=(L\cup R,E)$ jest dwustronny, to naturalne (dla przeciwnika) dzielenie zmiennych według ich części. W tym przypadku Alice otrzymuje podzbiór$A\subseteq L$, Bob podzbiór $B\subseteq R$ z obietnicą, że $|A\cup B|>\alpha(G)$. Celem jest znalezienie przewagi między $A$ i $B$. Tutaj$\alpha(G)$ jest „dwustronną” liczbą niezależności: maksymalny rozmiar niezależnego zestawu, który nie leży całkowicie $L$ lub w $R$. Jednym z moich ulubionych problemów jest: Udowodnij to$n\times n$ wymagające wykresy $\omega(\log^2 n)$istnieją fragmenty komunikacji .

@Kaveh: Przepraszamy za „odpowiadanie” na twoje pytanie pytaniami.