Вопросы относительно объема связи, необходимого для выполнения вычислительной задачи, когда информация о задаче распределена по нескольким агентам
В классической работе Эндрю Чи-Чжа Яо 1979 года он упоминает "М.О. Рабин и А.С. Яо, в процессе подготовки". Это связано с тем, что сложность связи с ограниченной ошибкой функции равенства EQ (два целых числа в диапазоне от до 0 N - 1 O ( журнал регистрации N )NN_N000N−1N−1N-1 ) равна...
Знаковый ранг матрицы A с элементами + 1, -1 является наименьшим рангом (по реалам) матрицы B, которая имеет такой же шаблон знака, что и A (то есть для всех i , к ). Это понятие важно в сложности общения и теории обучения.Aя жВя ж> 0AяJВяJ>0A_{ij}B_{ij}>0я , джя,Ji,j Мой вопрос: существуют...
Помимо (детерминированной) сложности связи отношения , другой основной мерой для объема необходимой связи является номер раздела протокола . Связь между этими двумя показателями известна до постоянного фактора. Монография Кушилевица и Нисана (1997) даетRc c ( R )сс(р)cc(R)ррR p p ( R )пп(р)pp(R) c...
Обсуждение : В последнее время я проводил некоторое личное время, изучая различные вещи в сложности общения. Например, я повторно ознакомился с соответствующей главой в Арора / Барак, начал читать некоторые статьи и заказал книгу Кушилевица / Нисана. Интуитивно я хочу сравнить сложность...
Фон: Рассмотрим обычную двухстороннюю модель сложности коммуникации, где Алисе и Бобу даны битные строки и и они должны вычислить некоторую булеву функцию , где .nnnxxxyyyf(x,y)f(x,y)f(x,y)f:{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\} Мы определяем следующие...
Рассмотрим язык different состоящий из всех строк k- букв над Σ, таких, что никакие две буквы не равны:L k - d i s t i n c tLk−distinctL_{k-distinct}kkΣ\Sigma L k - d i s t i n c t : = { w = σ 1 σ 2 . , , σ к | ∀ я ∈ [ к ] : σ я ∈ Е и ∀ J ≠ я : σ J ≠ σ я...
Информационная сложность была очень полезным инструментом в сложности коммуникации, в основном используемой для снижения сложности коммуникации в распределенных задачах. Есть ли аналог сложности информации для сложности запросов? Существует много параллелей между сложностью запросов и сложностью...
Хорошо известно, что никакой детерминированный двухсторонний протокол не может решить проблему дизъюнктивности (DISJ) на битных входах без отправки n + 1 бит в худшем случае (см., Например, книгу Kushilevitz and Nisan). Для рандомизированных протоколов с ограниченной ошибкой нижняя граница δ n для...
Алиса и Боб имеют n-битные строки и хотят выяснить, равны ли они при небольшом общении. Стандартным рандомизированным решением является обработка n-битных строк как полиномов степени nnn а затем оценка полиномов по нескольким случайно выбранным элементам из поля размером больше nnn . Это требует...
В рассматриваемом приложении мне необходимо знать сложность связи следующей проблемы: Для данного пусть S будет множеством целых чисел от 1 до n . Алиса, Боб и Кэрол каждый получает подмножество S , обозначенное A , B и C соответственно. Они хотят , чтобы проверить , является ли , B и C образуют...
Пусть { 0 , . , , , П - 1 } и ∘ : S × S → S . Я хочу вычислить сложность коммуникации, решая, является ли ∘ ассоциативным.Sзнак равноS=S=0 , . , , , n - 10,...,n−10,...,n-1∘ : S× S→ S∘:S×S→S\circ : S \times S \rightarrow S∘∘\circ Модель следующая. задается в виде матрицы М . Алиса (соответственно...
Допустим, мы обнаруживаем инопланетные цивилизации, которые могут отправлять и получать сообщения, используя межзвездный цифровой канал связи. (Скажем, с помощью модулированных радиоволн, лазерных импульсов, изменения положения звезд на различных орбитах.) Предположим, мы решили установить с ними...
Хорошо известно, что проблема остановки является неисчислимой. Тем не менее, можно экспоненциально «сжать» информацию о проблеме остановки, так что ее распаковка является вычислимой. Точнее, можно вычислить из описания машин Тьюринга и n- битного состояния рекомендации ответ на проблему остановки...
В доказательстве Голдрайха и др. О том, что три цвета имеют нулевое доказательство знания, используется битовое обязательство для полной раскраски графа в каждом раунде [1]. Если граф имеет вершин и ребер, безопасный хеш имеет битов, и мы ищем вероятность ошибки , общая стоимость связи равнае б...
Насколько я знаю, нижняя граница нормы факторизации, данная Линиалом и Шрайбманом, является по существу единственной нижней границей, известной для сложности квантовой связи (или, по крайней мере, она включает все остальные). Есть ли доказательства того, что эта граница была жесткой? Граница...
Пусть - последовательность целых чисел, где каждый . Для , пусть, - й момент частоты определяется какa j ∈ { 1 , 2 , … , n } i ∈ { 1 , 2 , … , n } m i = | { j : a j = i } | Кa1,a2,…,ama1,a2,…,ama_1, a_2,\dotsc, a_maj∈{1,2,…,n}aj∈{1,2,…,n}a_j \in \{1,2,\dotsc,n\}i∈{1,2,…,n}i∈{1,2,…,n}i \in...
В настоящее время я ищу хороший справочный материал о нелокальных играх с полезными аспектами квантовой коммуникации. Например, я знаю, что нелокальные игры хороши для более низкой сложности связи, а также для обеспечения безопасности протоколов QKD. То, что я хотел бы знать, - это какие-то большие...
Это продолжение моего предыдущего вопроса о нижних границах связи для частичных булевых функций . Может ли кто-нибудь предложить какую-либо ссылку на нижние границы для недетерминированного многопартийного общения? Я просматривал статьи в этой области, но все, кажется, демонстрируют разделение...
Известно, что для ошибки определение рандомизированной сложности связи в худшем случае и определение среднего случая эквивалентны. Но когда ошибка равна , сложность рандомизированной связи в худшем случае такая же, как сложность детерминированной связи.Θ(1)Θ(1)\Theta(1)000 Известно ли, что любая...
В сложности связи гипотеза лог-ранга утверждает, что с с ( М) = ( журналr k ( М) )O ( 1 )cc(M)=(logrk(M))O(1)cc(M) = (\log rk(M))^{O(1)} Где - сложность связи а - ранг (в виде матрицы) над реалами.M ( x , y ) r k ( M ) Mс с ( М)cc(M)cc(M)M( х , у)M(x,y)M(x,y)r k ( М)rk(M)rk(M)MMM Однако, когда вы...