Questions concernant la quantité de communication nécessaire pour accomplir une tâche de calcul, lorsque les informations sur la tâche sont réparties sur plusieurs agents
Dans son article classique de 1979, Andrew Chi-Chih Yao mentionne "MO Rabin et AC Yao, en préparation". Cela signifie que la complexité de la communication d'erreur corrigée de la fonction d'égalité EQ (que deux entiers compris entre et soient égaux) est égale à
Le rang de signe d'une matrice A avec + 1, -1 entrées est le plus petit rang (sur les réels) d'une matrice B qui a le même motif de signe que A (c'est-à-dire pour tous ). Cette notion est importante dans la complexité de la communication et la théorie de l'apprentissage.UNEje jBje j>...
Outre la complexité de communication (déterministe) d'une relation , une autre mesure de base pour la quantité de communication nécessaire est le numéro de partition de protocole . La relation entre ces deux mesures est connue jusqu'à un facteur constant. La monographie de Kushilevitz et Nisan...
Discussion : J'ai passé un peu de temps récemment à apprendre différentes choses sur la complexité de la communication. Par exemple, je me suis familiarisé avec le chapitre pertinent d'Arora / Barak, j'ai commencé à lire certains articles et commandé le livre de Kushilevitz / Nisan. Intuitivement,...
Contexte: Considérons le modèle habituel à deux parties de la complexité de la communication où Alice et Bob reçoivent des chaînes de nnn bits Xxx et yyy et doivent calculer une fonction booléenne F( x , y)f(x,y)f(x,y) , où F: { 0 , 1 }n× { 0 , 1 }n→ { 0 , 1 }f:{0,1}n×{0,1}n→{0,1}f:\{0,1\}^n \times...
Considérons le langage composé de toutes les chaînes de k lettres sur Σ de telle sorte qu'il n'y ait pas deux lettres égales: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}...
La complexité de l'information a été un outil très utile dans la complexité de la communication, principalement utilisée pour réduire la complexité de la communication des problèmes distribués. Existe-t-il un analogue de la complexité des informations pour la complexité des requêtes? Il existe de...
Il est bien connu qu'aucun protocole déterministe bipartite ne peut résoudre le problème de disjonction (DISJ) sur les entrées à bits sans envoyer n + 1 bits dans le pire des cas (voir, par exemple, le livre de Kushilevitz et Nisan). Pour les protocoles randomisés à erreur bornée, une borne...
Alice et Bob ont des chaînes de n bits et veulent savoir s'ils sont égaux tout en faisant peu de communication. La solution randomisée standard consiste à traiter les chaînes de n bits comme des polynômes de degré , puis à évaluer les polynômes sur quelques éléments choisis au hasard dans un champ...
Dans une application que j'envisage, j'ai besoin de connaître la complexité de communication du problème suivant: Étant donné , soit S l'ensemble des entiers de 1 à n . Alice, Bob, Carol et chacun reçoit un sous - ensemble de S , notée A , B et C , respectivement. Ils veulent vérifier si A , B et C...
Soit { 0 , . . . , N - 1 } et ∘ : S × S → S . Je veux calculer la complexité de la communication pour décider si ∘ est associatif.S=S=S=0 , . . . , n - 10,...,n−10,...,n-1∘ : S× S→ S∘:S×S→S\circ : S \times S \rightarrow S∘∘\circ Le modèle est le suivant. est donnée à une matrice M . Alice (resp....
Disons que nous découvrons des civilisations extraterrestres capables d'envoyer et de recevoir des messages à l'aide d'un canal de communication numérique interstellaire. (Par exemple, en utilisant des ondes radio modulées, des impulsions laser, en repositionnant des étoiles sur diverses orbites,...
Il est bien connu que le problème d'arrêt n'est pas calculable. Cependant, il est possible de "compresser" exponentiellement des informations sur le problème d'arrêt, de sorte que sa décompression soit calculable. Plus précisément, il est possible de calculer à partir d'une description de machines...
La preuve de Goldreich et al. Que la trois colorabilité n'a aucune preuve de connaissance utilise l'engagement de bits pour une coloration entière du graphique à chaque tour [1]. Si un graphe a sommets et e arêtes, un hachage sécurisé a b bits et que nous recherchons la probabilité d'erreur p , le...
Pour autant que je sache, la borne inférieure de la norme de factorisation donnée par Linial et Shraibman est essentiellement la seule borne inférieure connue pour la complexité de la communication quantique (ou du moins elle subsume toutes les autres). Y a-t-il des preuves que cette limite n'est...
Soit une séquence d'entiers où chacun . Pour , soit. Le ème moment de fréquence est défini comme étanta j ∈ { 1 , 2 , … , n } i ∈ { 1 , 2 , … , n } m i = | { j : a j = i } | kune1, un2, … , Unmune1,une2,…,unema_1, a_2,\dotsc, a_munej∈ { 1 , 2 , … , n }unej∈{1,2,…,n}a_j \in \{1,2,\dotsc,n\}i ∈ { 1 ,...
Je suis actuellement à la recherche de bons documents de référence concernant les jeux non locaux avec des aspects bénéfiques en communication quantique. Par exemple, je suis conscient que les jeux non locaux sont bons pour réduire la complexité de la communication sur les limites inférieures et...
Il s'agit d'une continuation de ma question précédente sur les limites inférieures de communication pour les fonctions booléennes partielles . Quelqu'un peut-il suggérer une référence sur les limites inférieures pour la communication multipartite non déterministe? J'ai examiné les articles sur le...
Il est connu que pour l' erreur , la pire définition de cas de complexité de communication aléatoire et la définition de cas moyenne sont équivalentes. Mais lorsque l'erreur est , la pire complexité de communication aléatoire est la même que la complexité de communication...
Dans la complexité de la communication, la conjecture log-rank déclare que cc(M)=(logrk(M))O(1)cc(M)=(logrk(M))O(1)cc(M) = (\log rk(M))^{O(1)} Où est la complexité de communication de M ( x , y ) et r k ( M ) est le rang de M (sous forme de matrice) sur les