This HTML5 document contains 121 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
n26http://u.cs.biu.ac.il/~zarosih/70/files/
dbpedia-dehttp://de.dbpedia.org/resource/
n22https://arxiv.org/abs/quant-ph/
dcthttp://purl.org/dc/terms/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
n20https://global.dbpedia.org/id/
dbpedia-hehttp://he.dbpedia.org/resource/
dbpedia-trhttp://tr.dbpedia.org/resource/
dbpedia-ruhttp://ru.dbpedia.org/resource/
dbthttp://dbpedia.org/resource/Template:
rdfshttp://www.w3.org/2000/01/rdf-schema#
freebasehttp://rdf.freebase.com/ns/
dbpedia-pthttp://pt.dbpedia.org/resource/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
dbpedia-vihttp://vi.dbpedia.org/resource/
dbpedia-frhttp://fr.dbpedia.org/resource/
wikipedia-enhttp://en.wikipedia.org/wiki/
dbphttp://dbpedia.org/property/
dbchttp://dbpedia.org/resource/Category:
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
n12https://www.sciencedirect.com/science/article/pii/S030439759600062X/
wikidatahttp://www.wikidata.org/entity/
dbrhttp://dbpedia.org/resource/
dbpedia-jahttp://ja.dbpedia.org/resource/

Statements

Subject Item
dbr:Proof_complexity
dbo:wikiPageWikiLink
dbr:Communication_complexity
Subject Item
dbr:Proof_of_secure_erasure
dbo:wikiPageWikiLink
dbr:Communication_complexity
Subject Item
dbr:Alon_Orlitsky
dbo:wikiPageWikiLink
dbr:Communication_complexity
Subject Item
dbr:List_of_pioneers_in_computer_science
dbo:wikiPageWikiLink
dbr:Communication_complexity
Subject Item
dbr:Jaikumar_Radhakrishnan
dbo:wikiPageWikiLink
dbr:Communication_complexity
dbp:field
dbr:Communication_complexity
dbo:academicDiscipline
dbr:Communication_complexity
Subject Item
dbr:Matrix_norm
dbo:wikiPageWikiLink
dbr:Communication_complexity
Subject Item
dbr:Oded_Regev_(computer_scientist)
dbo:wikiPageWikiLink
dbr:Communication_complexity
Subject Item
dbr:Quantum_nonlocality
dbo:wikiPageWikiLink
dbr:Communication_complexity
Subject Item
dbr:Multiparty_communication_complexity
dbo:wikiPageWikiLink
dbr:Communication_complexity
Subject Item
dbr:Concentration_inequality
dbo:wikiPageWikiLink
dbr:Communication_complexity
Subject Item
dbr:Andrew_Yao
dbo:wikiPageWikiLink
dbr:Communication_complexity
Subject Item
dbr:Communication_complexity
rdfs:label
Complexité de la communication 通信複雑性 Kommunikationskomplexität Communication complexity Complexidade de comunicação Коммуникационная сложность
rdfs:comment
В теоретической информатике коммуникационная сложность изучает количество коммуникации, необходимое для решения задачи, параметры которой распределены между двумя или более сторонами. Это понятие было введено Эндрю Яо в 1979 году, который исследовал следующую задачу для двух участников, традиционно называемых Алисой и Бобом. Алиса получает n-битную строку x, а Bob — n-битную строку y, и их цель состоит в том, чтобы один из них (например, Боб) вычислил определенную и известную обоим участникам функцию , при этом с наименьшим количеством коммуникации между ними. Конечно, они всегда могут вычислить следующим образом: Алиса отправляет всю свою n-битную строку Бобу, который затем вычисляет функцию . Поэтому в данной постановке задачи интересно, для каких функций f существует способ вычислить La complexité de la communication ou complexité de communication est une notion étudiée en informatique théorique. Le dispositif abstrait classique est le suivant : Alice et Bob ont chacun un message, et ils veulent calculer un nouveau message à partir de leurs messages, en se transmettant un minimum d'information. Par exemple, Alice et Bob reçoivent un mot chacun, et ils doivent décider s'ils ont reçu le même mot ; ils peuvent bien sûr s'envoyer leur mot l'un à l'autre et comparer, mais la question est de minimiser le nombre de messages. In theoretical computer science, communication complexity studies the amount of communication required to solve a problem when the input to the problem is distributed among two or more parties. The study of communication complexity was first introduced by Andrew Yao in 1979, while studying the problem of computation distributed among several machines.The problem is usually stated as follows: two parties (traditionally called Alice and Bob) each receive a (potentially different) -bit string and . The goal is for Alice to compute the value of a certain function, , that depends on both and , with the least amount of communication between them. 通信複雑性（つうしんふくざつせい、Communication Complexity、CC）は、1979年にアンドリュー・チーチー・ヤオによって導入された用語である。ヤオは2つの個体間の通信問題を研究していた。アリスは n ビットの文字列 x を受信し、ボブも別の n ビットの文字列 y を受信する。目標は両者のいずれかが最小限の通信によって関数 f(x,y) を計算することである。ここでは、計算のステップ数を問題にしているのでも、計算に必要なメモリ量を問題にしているのでもない。通信複雑性とは、このような分散計算で必要となる通信の量を測るものである。 もちろん、上記の例でアリスが n ビットの文字列全体をボブに送ってしまえば、ボブがその関数を計算でき、問題は解決する。しかし、ここで考えているのは、n ビットより少ない通信量で関数を計算する賢い手法の探索である。 この抽象的な問題は様々な場面で応用できる。VLSIの回路設計では、消費電力を低減させるために、ある部分から別の部分に流れる信号の量を最小化したい場合がある。他にもデータ構造の研究やコンピュータネットワークの最適化にも関連する。応用に関しては、参考文献にある Kushilevitz と Nisan の著書に詳しい。 A noção de complexidade de comunicação foi introduzida por em 1979,que investigou o seguinte problema envolvendo duas partes (Alice e Bob). Alice recebe uma cadeia x de n bits e Bob outra cadeia y de n bits, e o objetivo é que um deles (digamos, Bob) compute uma certa função f(x,y) com a menor quantidade de comunicação entre eles. Note que não estamos preocupados com o número de passos da computação, ou com o tamanho da memória (informática) utilizada. Complexidade de comunicação tenta quantificar quanta comunicação é necessário para essas computações distribuídas. Die Kommunikationskomplexität ist ein Teilgebiet der Komplexitätstheorie und wird angewendet um die Frage zu untersuchen, wie viel Kommunikation zum Lösen bestimmter Aufgaben nötig ist, wobei die Eingabe auf mehrere Rechner verteilt ist. Das Hauptaugenmerk liegt dabei auf der Anzahl der Bits, die zwischen den Rechnern versendet werden müssen, damit diese die ihnen gestellte Aufgabe erfüllen können. Die Kommunikationskomplexität ist ein Werkzeug der theoretischen Informatik, insbesondere beim Beweis von unteren Schranken für den Ressourcenbedarf von Berechnungen.
dct:subject
dbc:Computational_complexity_theory dbc:Communication dbc:Quantum_complexity_theory
dbo:wikiPageID
50329
dbo:wikiPageRevisionID
1108502621
dbo:wikiPageWikiLink
dbr:Bit dbr:Ran_Raz dbr:Function_(mathematics) dbr:Gap-Hamming_problem dbr:Distributed_computation dbr:Dot_product dbr:Alice_and_Bob dbr:Space–time_tradeoff dbc:Computational_complexity_theory dbr:Decision_tree_complexity dbc:Communication dbr:Matrix_(mathematics) dbr:Qubit dbr:Streaming_algorithms dbr:Finite_field dbr:Hoeffding's_inequality dbr:Quantum_entanglement dbc:Quantum_complexity_theory dbr:Theoretical_computer_science dbr:Rank_(linear_algebra) dbr:VLSI_circuit dbr:Photons dbr:Multiparty_communication_complexity dbr:Nonnegative_rank_(linear_algebra) dbr:Computational_complexity dbr:Computational_complexity_theory dbr:Andrew_Yao dbr:Submatrix dbr:Optical_fiber dbr:VLSI dbr:Computer_memory dbr:Protocol_(computing) dbr:Communication
dbo:wikiPageExternalLink
n12:pdf%3Fmd5=673842d5f5b8a83d07e2c183ffa357a1&pid=1-s2.0-S030439759600062X-main.pdf&_valck=1 n22:0101005 n26:private_vs__common_random_bits_in_commun_493418.pdf
owl:sameAs
dbpedia-tr:İletişim_karmaşıklığı dbpedia-fr:Complexité_de_la_communication wikidata:Q5154130 dbpedia-pt:Complexidade_de_comunicação dbpedia-ja:通信複雑性 dbpedia-ru:Коммуникационная_сложность n20:4iHVZ dbpedia-vi:Độ_phức_tạp_truyền_thông freebase:m.0d9qw dbpedia-he:סיבוכיות_תקשורת dbpedia-de:Kommunikationskomplexität
dbp:wikiPageUsesTemplate
dbt:Tmath dbt:Val dbt:Use_American_English dbt:Reflist dbt:Short_description dbt:Mvar dbt:Cite_book dbt:Harvtxt
dbo:abstract
Die Kommunikationskomplexität ist ein Teilgebiet der Komplexitätstheorie und wird angewendet um die Frage zu untersuchen, wie viel Kommunikation zum Lösen bestimmter Aufgaben nötig ist, wobei die Eingabe auf mehrere Rechner verteilt ist. Das Hauptaugenmerk liegt dabei auf der Anzahl der Bits, die zwischen den Rechnern versendet werden müssen, damit diese die ihnen gestellte Aufgabe erfüllen können. Die Kommunikationskomplexität ist ein Werkzeug der theoretischen Informatik, insbesondere beim Beweis von unteren Schranken für den Ressourcenbedarf von Berechnungen. La complexité de la communication ou complexité de communication est une notion étudiée en informatique théorique. Le dispositif abstrait classique est le suivant : Alice et Bob ont chacun un message, et ils veulent calculer un nouveau message à partir de leurs messages, en se transmettant un minimum d'information. Par exemple, Alice et Bob reçoivent un mot chacun, et ils doivent décider s'ils ont reçu le même mot ; ils peuvent bien sûr s'envoyer leur mot l'un à l'autre et comparer, mais la question est de minimiser le nombre de messages. Utiliser une ressources en communication est le fait d'envoyer une information à l'autre. Alice peut ainsi envoyer la première lettre de son mot à bob, ceci a un coût de 1. La théorie de la complexité de communication a donc pour but de calculer quelles sont les ressources en communication nécessaires pour effectuer certaines tâches dans un contexte de calcul distribué. Contrairement à la théorie de la complexité classique, on ne compte pas les ressources nécessaires aux calculs (temps et espace par exemple). Cette notion a été définie en 1979 par Andrew Yao et est utilisée notamment pour l'étude des algorithmes en ligne et le design des circuits VLSI. In theoretical computer science, communication complexity studies the amount of communication required to solve a problem when the input to the problem is distributed among two or more parties. The study of communication complexity was first introduced by Andrew Yao in 1979, while studying the problem of computation distributed among several machines.The problem is usually stated as follows: two parties (traditionally called Alice and Bob) each receive a (potentially different) -bit string and . The goal is for Alice to compute the value of a certain function, , that depends on both and , with the least amount of communication between them. While Alice and Bob can always succeed by having Bob send his whole -bit string to Alice (who then computes the function ), the idea here is to find clever ways of calculating with fewer than bits of communication. Note that, unlike in computational complexity theory, communication complexity is not concerned with the amount of computation performed by Alice or Bob, or the size of the memory used, as we generally assume nothing about the computational power of either Alice or Bob. This abstract problem with two parties (called two-party communication complexity), and its general form with more than two parties, is relevant in many contexts. In VLSI circuit design, for example, one seeks to minimize energy used by decreasing the amount of electric signals passed between the different components during a distributed computation. The problem is also relevant in the study of data structures and in the optimization of computer networks. For surveys of the field, see the textbooks by and . A noção de complexidade de comunicação foi introduzida por em 1979,que investigou o seguinte problema envolvendo duas partes (Alice e Bob). Alice recebe uma cadeia x de n bits e Bob outra cadeia y de n bits, e o objetivo é que um deles (digamos, Bob) compute uma certa função f(x,y) com a menor quantidade de comunicação entre eles. Note que não estamos preocupados com o número de passos da computação, ou com o tamanho da memória (informática) utilizada. Complexidade de comunicação tenta quantificar quanta comunicação é necessário para essas computações distribuídas. Claro que eles podem conseguir com Alice enviando sua cadeia inteira para Bob, que então computa a função, mas a ideia aqui é encontrar maneiras inteligentes de calcular f com menos de n bits de comunicação. Esse problema abstrato é relevante em vários contextos: no design de circuitos VSLI, por exemplo, deseja-se minimizar a energia utilizada diminuindo a quantidade de sinal elétricos necessários entre os diferentes componentes durante uma computação distribuída. O problema também é relevante no estudo de estruturas de dados, e na otimização de redes de computadores. Para um panorama da área, veja o livro de Kushilevitz e Nisan. В теоретической информатике коммуникационная сложность изучает количество коммуникации, необходимое для решения задачи, параметры которой распределены между двумя или более сторонами. Это понятие было введено Эндрю Яо в 1979 году, который исследовал следующую задачу для двух участников, традиционно называемых Алисой и Бобом. Алиса получает n-битную строку x, а Bob — n-битную строку y, и их цель состоит в том, чтобы один из них (например, Боб) вычислил определенную и известную обоим участникам функцию , при этом с наименьшим количеством коммуникации между ними. Конечно, они всегда могут вычислить следующим образом: Алиса отправляет всю свою n-битную строку Бобу, который затем вычисляет функцию . Поэтому в данной постановке задачи интересно, для каких функций f существует способ вычислить передав менее n битов. Важное отметить, что в данной задаче нас не интересует сложность вычислений, выполненных Алисой или Бобом, или размер используемой для этих вычислений памяти. Эта абстрактная проблема с двумя участниками (называемая коммуникационной сложностью с двумя участниками) и ее общая форма с большим количеством участников возникает в различных областях компьютерных наук: например, при проектировании схем больших интегральных схем требуется минимизировать используемую энергию, путём уменьшения количества электрических сигналов между различными компонентами во время распределенных вычислений. Коммуникационная сложность используется также при изучении структур данных и алгоритмов, при оптимизации компьютерных сетей, в теории вычислительной сложности и сложности доказательств и в других областях. 通信複雑性（つうしんふくざつせい、Communication Complexity、CC）は、1979年にアンドリュー・チーチー・ヤオによって導入された用語である。ヤオは2つの個体間の通信問題を研究していた。アリスは n ビットの文字列 x を受信し、ボブも別の n ビットの文字列 y を受信する。目標は両者のいずれかが最小限の通信によって関数 f(x,y) を計算することである。ここでは、計算のステップ数を問題にしているのでも、計算に必要なメモリ量を問題にしているのでもない。通信複雑性とは、このような分散計算で必要となる通信の量を測るものである。 もちろん、上記の例でアリスが n ビットの文字列全体をボブに送ってしまえば、ボブがその関数を計算でき、問題は解決する。しかし、ここで考えているのは、n ビットより少ない通信量で関数を計算する賢い手法の探索である。 この抽象的な問題は様々な場面で応用できる。VLSIの回路設計では、消費電力を低減させるために、ある部分から別の部分に流れる信号の量を最小化したい場合がある。他にもデータ構造の研究やコンピュータネットワークの最適化にも関連する。応用に関しては、参考文献にある Kushilevitz と Nisan の著書に詳しい。
prov:wasDerivedFrom
wikipedia-en:Communication_complexity?oldid=1108502621&ns=0
dbo:wikiPageLength
26060
foaf:isPrimaryTopicOf
wikipedia-en:Communication_complexity
Subject Item
dbr:Computational_complexity_theory
dbo:wikiPageWikiLink
dbr:Communication_complexity
Subject Item
dbr:Harry_Buhrman
dbo:wikiPageWikiLink
dbr:Communication_complexity
dbo:knownFor
dbr:Communication_complexity
Subject Item
dbr:Theoretical_computer_science
dbo:wikiPageWikiLink
dbr:Communication_complexity
Subject Item
dbr:Active_networking
dbo:wikiPageWikiLink
dbr:Communication_complexity
Subject Item
dbr:Centre_for_Quantum_Technologies
dbo:wikiPageWikiLink
dbr:Communication_complexity
Subject Item
dbr:Turing_Award
dbo:wikiPageWikiLink
dbr:Communication_complexity
Subject Item
dbr:Distributed_computing
dbo:wikiPageWikiLink
dbr:Communication_complexity
Subject Item
dbr:Gap-Hamming_problem
dbo:wikiPageWikiLink
dbr:Communication_complexity
Subject Item
dbr:Log-rank_conjecture
dbo:wikiPageWikiLink
dbr:Communication_complexity
Subject Item
dbr:Predecessor_problem
dbo:wikiPageWikiLink
dbr:Communication_complexity
Subject Item
dbr:Rank_(linear_algebra)
dbo:wikiPageWikiLink
dbr:Communication_complexity
Subject Item
dbr:Szemerédi_regularity_lemma
dbo:wikiPageWikiLink
dbr:Communication_complexity
Subject Item
dbr:Ashok_K._Chandra
dbo:wikiPageWikiLink
dbr:Communication_complexity
Subject Item
dbr:Hidden_Matching_Problem
dbo:wikiPageWikiLink
dbr:Communication_complexity
Subject Item
dbr:Greenberger–Horne–Zeilinger_state
dbo:wikiPageWikiLink
dbr:Communication_complexity
Subject Item
dbr:Randomized_algorithm
dbo:wikiPageWikiLink
dbr:Communication_complexity
Subject Item
dbr:Exponential_time_hypothesis
dbo:wikiPageWikiLink
dbr:Communication_complexity
Subject Item
dbr:Streaming_algorithm
dbo:wikiPageWikiLink
dbr:Communication_complexity
Subject Item
dbr:Picking_sequence
dbo:wikiPageWikiLink
dbr:Communication_complexity
Subject Item
dbr:S2S_(mathematics)
dbo:wikiPageWikiLink
dbr:Communication_complexity
Subject Item
dbr:Ronald_de_Wolf
dbo:wikiPageWikiLink
dbr:Communication_complexity
dbp:knownFor
dbr:Communication_complexity
dbo:knownFor
dbr:Communication_complexity
Subject Item
dbr:Quantum_communication_complexity
dbo:wikiPageWikiLink
dbr:Communication_complexity
dbo:wikiPageRedirects
dbr:Communication_complexity
Subject Item
wikipedia-en:Communication_complexity
foaf:primaryTopic
dbr:Communication_complexity