Pytania otagowane jako communication-complexity

Pytania dotyczące ilości komunikacji potrzebnej do wykonania zadania obliczeniowego, gdy informacje o zadaniu są rozłożone na kilku agentów

1
Czy istnieje Rabin / Yao (przynajmniej w formie, którą można zacytować)?
W klasycznym artykule Andrew Chi-Chiha Yao z 1979 r. Nawiązuje do „MO Rabin i AC Yao w przygotowaniu”. Wynika to z tego, że złożoność komunikacji z błędem ograniczonym funkcji równości EQ (czy dwie liczby całkowite z zakresu od do są równe) wynosi .NN_N000N−1N−1N-1O(loglogN)O(log⁡log⁡N)O(\log\log N) Andrew Chi-Chih Yao, Niektóre pytania dotyczące …
2
Przybliżenie rangi znaku macierzy
Ranga znaku macierzy A z wpisami + 1, -1 jest najmniejszą rangą (ponad rzeczywistymi) macierzy B, która ma taki sam wzór znaków jak A (tj. dla wszystkich i , j ). Pojęcie to jest ważne w złożoności komunikacji i teorii uczenia się.AijBij>0AijBij>0A_{ij}B_{ij}>0i,ji,ji,j Moje pytanie brzmi: czy są jakieś znane algorytmy …
2
Numer podziału protokołu i deterministyczna złożoność komunikacji
Oprócz (deterministycznej) złożoności komunikacji cc(R)cc(R)cc(R) relacji RRR , inną podstawową miarą ilości potrzebnej komunikacji jest numer podziału protokołu pp(R)pp(R)pp(R) . Zależność między tymi dwoma miarami jest znana aż do stałego współczynnika. Monografia Kushilevitza i Nisana (1997) daje cc(R)/3≤log2(pp(R))≤cc(R).cc(R)/3≤log2⁡(pp(R))≤cc(R).cc(R)/3 \le \log_2(pp(R)) \le cc(R). Jeśli chodzi o drugą nierówność, łatwo jest podać …
4
Złożoność komunikacji… Klasy?
Dyskusja : Spędziłem ostatnio trochę czasu na nauce różnych rzeczy w złożoności komunikacji. Na przykład ponownie zapoznałem się z odpowiednim rozdziałem w Arora / Barak, zacząłem czytać kilka artykułów i zamówiłem książkę Kushilevitz / Nisan. Intuicyjnie chcę porównać złożoność komunikacji ze złożonością obliczeniową. W szczególności uderza mnie fakt, że złożoność …
1
Złożoność informacji algorytmów zapytań?
Złożoność informacji jest bardzo przydatnym narzędziem w złożoności komunikacji, stosowanym głównie w celu ograniczenia złożoności komunikacyjnej rozproszonych problemów. Czy istnieje analogia złożoności informacji dla złożoności zapytań? Istnieje wiele podobieństw między złożonością zapytań a złożonością komunikacji; często (ale nie zawsze!) dolna granica w jednym modelu zostaje przetłumaczona na dolną granicę w …
2
Testowanie pozytywności zamiast równości
Alice i Bob mają n-bitowe ciągi i chcą dowiedzieć się, czy są równe, podczas niewielkiej komunikacji. Standardowe rozwiązanie randomizowane polega na traktowaniu ciągów n-bitowych jako wielomianów stopnia a następnie ocenie wielomianów na kilku losowo wybranych elementach z pola o wielkości większej niż n . Wymaga to komunikacji O ( log …
1
Kompresowanie informacji o problemie zatrzymania w maszynach wyroczni Turinga
Wiadomo, że problem zatrzymania jest niemożliwy do obliczenia. Możliwe jest jednak wykładnicze „kompresowanie” informacji o problemie zatrzymania, tak aby dekompresowanie było możliwe do obliczenia. Dokładniej, można obliczyć na podstawie opisu maszyn Turinga, a n- bitowa porada stanowi odpowiedź na problem zatrzymania dla wszystkich 2 n - 1 maszyn Turinga, przy …
2
Najlepszy protokół komunikacyjny dla obcych?
Załóżmy, że odkrywamy obce cywilizacje, które są w stanie wysyłać i odbierać wiadomości za pomocą międzygwiezdnego kanału komunikacji cyfrowej. (Powiedz, używając modulowanych fal radiowych, impulsów laserowych, zmiany położenia gwiazd na różnych orbitach, co masz). Załóżmy, że postanowiliśmy się z nimi skontaktować. Po zainicjowaniu dialogu, jak byśmy przystąpili do ustanowienia protokołu …
1
Jakieś dowody na to, że Linial, Shraibman niższa granica złożoności komunikacji kwantowej nie jest ścisła?
O ile mi wiadomo, dolna granica normy faktoryzacji podana przez Liniala i Shraibmana jest zasadniczo jedyną dolną granicą znaną ze złożoności komunikacji kwantowej (lub przynajmniej obejmuje wszystkie inne). Czy są jakieś dowody przeciwko ścisłości tego powiązania? Ograniczona normą faktoryzacji (zwana także granicą ), o której mówię, to Twierdzenie 13 Linial, …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.