Pytania oznaczone «communication-complexity»

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...

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:...

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

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...

Tło: Rozważmy modelu zwykłe dwie grupy komunikacji złożoności gdzie Alicja i Bob podane nnn -bitowe łańcuchy xxx i yyy i muszą oblicz logiczna funkcja fa( x , y)f(x,y)f(x,y) , gdzie fa: { 0 , 1 }n× { 0 , 1 }n→ { 0 , 1 }f:{0,1}n×{0,1}n→{0,1}f:\{0,1\}^n \times \{0,1\}^n \to \{0,1\} . Definiujemy...

Rozważmy język składający się ze wszystkich ciągów -lettera nad tak aby żadne dwie litery nie były równe:L k - d i s t i n c tLk−distinctL_{k-distinct} k kkΣΣ\Sigma L k - d i s t i n c t : = { w = σ 1 σ 2 . . . σ k ∣ ∀ i ∈ [ k ] : σ i ∈ Σ  and  ∀ j ≠ i : σ j ≠ σ i...

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...

Dobrze wiadomo, że żaden deterministyczny protokół dwupartyjny nie może rozwiązać problemu rozłączności (DISJ) na wejściach bitowych bez wysyłania n + 1 bitów w najgorszym przypadku (patrz np. Książka Kushilevitza i Nisana). W przypadku protokołów losowych z ograniczonym błędem dolną granicę δ n ,...

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...

W aplikacji, którą rozważam, muszę znać złożoność komunikacyjną następującego problemu: Biorąc pod uwagę , niech S będzie zbiorem liczb całkowitych od 1 do n . Alicja, Bob Carol każdy odbiera podzbiór S , oznaczony jako A , B i C , odpowiednio. Chcą sprawdzić, czy , B i C tworzą partycję S ,...

Niech { 0 , . . . , N - 1 }, a ∘ : S x S → S . Chcę obliczyć złożoność komunikacji przy podejmowaniu decyzji, czy ∘ jest skojarzone.S=S=S=0,...,n−10,...,n−10,...,n-1∘:S×S→S∘:S×S→S\circ : S \times S \rightarrow S∘∘\circ Model jest następujący. podano jako matrycy M . Alice (lub. Bob) otrzymuje...

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...

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ź...

Dowód Goldreicha i in., Że trzy kolory mogą mieć zerowe dowody wiedzy, wykorzystuje bitowe zaangażowanie w całe zabarwienie wykresu w każdej rundzie [1]. Jeśli wykres ma wierzchołków i krawędzie, bezpieczne hash ma bitów i szukamy błędów prawdopodobieństwo , całkowity koszt komunikacjie b...

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...

Niech 1 , 2 , ... , m jest ciągiem liczb całkowitych, gdzie każdy J ∈ { 1 , 2 , ... , N } . Dla i ∈ { 1 , 2 , … , n } , niech m i = | { j : a j = i } | . K th chwili częstotliwości określa sięza1, a2), … , Ama1,a2,…,ama_1, a_2,\dotsc, a_mzajot∈ { 1 , 2 , … , n }aj∈{1,2,…,n}a_j \in \{1,2,\dotsc,n\}i...

Obecnie szukam dobrych materiałów referencyjnych dotyczących nielokalnych gier o korzystnych aspektach w komunikacji kwantowej. Na przykład jestem świadomy, że gry nielokalne są dobre w ograniczaniu złożoności komunikacji, a także w zapewnieniu bezpieczeństwa protokołów QKD. Chciałbym wiedzieć,...

Jest to kontynuacja mojego poprzedniego pytania dotyczącego dolnych granic komunikacji dla częściowych funkcji boolowskich . Czy ktoś może zasugerować jakieś odniesienie do dolnych granic niedeterministycznej komunikacji wielopartyjnej? Przeglądam dokumenty w terenie, ale wydaje się, że wszyscy...

Wiadomo, że dla błędu definicja najgorszego przypadku złożoności losowej komunikacji i definicja średniego przypadku są równoważne. Ale gdy błąd wynosi , najgorszy przypadek złożoności komunikacji losowej jest taki sam, jak deterministyczna złożoność komunikacji.Θ ( 1 )Θ(1)\Theta(1)000 Czy jakaś...

W złożoności komunikacyjnej domniemanie log-rank stwierdza, że c c ( M) = ( logr k ( M) )O ( 1 )cc(M)=(log⁡rk(M))O(1)cc(M) = (\log rk(M))^{O(1)} Gdzie jest złożoność komunikacji M ( x , y ) , a r k ( M ) jest rangę M (jako matrycy) w liczb rzeczywistych.c c ( M)cc(M)cc(M)M.( x , y)M(x,y)M(x,y)r k...