Preguntas relacionadas con la cantidad de comunicación necesaria para realizar una tarea computacional, cuando la información sobre la tarea se distribuye entre varios agentes
En el clásico artículo de 1979 de Andrew Chi-Chih Yao, hace referencia a "MO Rabin y AC Yao, en preparación". Esto es por el resultado de que la complejidad de la comunicación de error acotado de la función de igualdad EQ N (si dos enteros en el rango de 0 a N - 1 son iguales) es O ( log log N )...
El rango de signos de una matriz A con entradas + 1, -1 es el rango mínimo (sobre los reales) de una matriz B que tiene el mismo patrón de signos que A (es decir, para todo i , j ) Esta noción es importante en la complejidad de la comunicación y la teoría del aprendizaje.UNAyo jsiyo j>...
Además de la complejidad de comunicación (determinista) de una relación , otra medida básica para la cantidad de comunicación necesaria es el número de partición de protocolo . La relación entre estas dos medidas se conoce hasta un factor constante. La monografía de Kushilevitz y Nisan (1997) daRc...
Discusión : Últimamente he pasado algo de tiempo personal aprendiendo varias cosas en la complejidad de la comunicación. Por ejemplo, me he re-familiarizado con el capítulo relevante en Arora / Barak, comencé a leer algunos documentos y ordené el libro a Kushilevitz / Nisan. Intuitivamente, quiero...
Antecedentes: Considere el modelo habitual de dos partes de la complejidad de la comunicación donde Alice y Bob reciben cadenas de nnn bits xxx e yyy y tienen que calcular alguna función booleana f(x,y)f(x,y)f(x,y) , donde 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...
Considere el lenguaje consiste en todas las cadenas -letter sobre modo que no haya dos letras iguales: k ΣLk−distinctLk−distinctL_{k-distinct}kkkΣΣ\Sigma Lk−distinct:={w=σ1σ2...σk∣∀i∈[k]:σi∈Σ and ∀j≠i:σj≠σi}Lk−distinct:={w=σ1σ2...σk∣∀i∈[k]:σi∈Σ and ∀j≠i:σj≠σi} L_{k-distinct} :=\{w =...
La complejidad de la información ha sido una herramienta muy útil en la complejidad de la comunicación, utilizada principalmente para reducir la complejidad de la comunicación de los problemas distribuidos. ¿Existe un análogo de la complejidad de la información para la complejidad de la consulta?...
Alice y Bob tienen cadenas de n bits, y quieren averiguar si son iguales mientras hacen poca comunicación. La solución aleatoria estándar es tratar las cadenas de n bits como polinomios de grado luego evaluar los polinomios sobre algunos elementos elegidos al azar de un campo de tamaño mayor que n...
Es bien sabido que no existe un protocolo determinista de dos partes puede resolver el problema de disyunción (DISJ) en entradas -bit sin enviar bits en el peor de los casos (véase, por ejemplo, el libro de Kushilevitz y Nisan). Para protocolos aleatorios de error acotado, Razborov [Razborov92]...
En una aplicación que estoy considerando, necesito saber la complejidad de comunicación del siguiente problema: Dado , sea S el conjunto de enteros de 1 a n . Alice, Bob y Carol reciben cada uno un subconjunto de S , denotado por A , B y C , respectivamente. Ellos quieren comprobar si A , B y C...
Sea { 0 , . . . , N - 1 } y ∘ : S × S → S . Quiero calcular la complejidad de la comunicación al decidir si ∘ es asociativo.S=S=S=0 , . . . , n - 10,...,n−10,...,n-1∘ : S× S→ S∘:S×S→S\circ : S \times S \rightarrow S∘∘\circ El modelo es el siguiente. se da como una matriz M . Alice (resp. Bob)...
Digamos que descubrimos civilizaciones alienígenas que pueden enviar y recibir mensajes utilizando un canal de comunicaciones digitales interestelar. (Digamos que usando ondas de radio moduladas, pulsos láser, reubicando estrellas en varias órbitas, ¿qué tiene usted?) Supongamos que hemos decidido...
Es bien sabido que el problema de detención es indiscutible. Sin embargo, es posible "comprimir" exponencialmente la información sobre el problema de detención, de modo que descomprimirla sea computable. Más precisamente, es posible calcular a partir de una descripción de máquinas de Turing y un...
Hasta donde sé, la norma de factorización del límite inferior dada por Linial y Shraibman es esencialmente el único límite inferior conocido para la complejidad de la comunicación cuántica (o al menos subsume todos los demás). ¿Hay alguna evidencia en contra de que este límite sea estricto? La...
Sea una secuencia de enteros donde cada a j ∈ { 1 , 2 , ... , n } . Para i ∈ { 1 , 2 , ... , n } , sea m i = | { j : a j = i } | . El k ésimo momento de frecuencia se define comouna1, una2, ... , unmetroa1,a2,…,ama_1, a_2,\dotsc, a_munaj∈ { 1 , 2 , ... , n }aj∈{1,2,…,n}a_j \in \{1,2,\dotsc,n\}i ∈ {...
Actualmente estoy buscando algún buen material de referencia que relacione juegos no locales con aspectos beneficiosos en la comunicación cuántica. Por ejemplo, soy consciente de que los juegos no locales son buenos para reducir la complejidad de la comunicación, así como para garantizar la...
La prueba de Goldreich et al. De que tres colorabilidad tiene cero pruebas de conocimiento utiliza un poco de compromiso para una coloración completa del gráfico en cada ronda [1]. Si un gráfico tiene vértices y bordes e , un hash seguro tiene b bits, y buscamos la probabilidad de error p , el...
Esta es una continuación de mi pregunta anterior sobre límites inferiores de comunicación para funciones booleanas parciales . ¿Alguien puede sugerir alguna referencia en los límites inferiores para la comunicación multipartidista no determinista? He estado examinando los documentos en el campo,...
Sabemos que el registro del rango de una matriz 0-1 es el límite inferior de la complejidad de comunicación determinista, y el registro del rango aproximado es el límite inferior de la complejidad de la comunicación aleatoria. La brecha más grande entre la complejidad de comunicación determinista y...
Se sabe que para el error la definición de peor caso de complejidad de comunicación aleatoria y la definición de caso promedio son equivalentes. Pero cuando el error es , la complejidad de comunicación aleatoria en el peor de los casos es la misma que la complejidad de comunicación...