講演名 | 2015-11-24 [招待講演]通信複雑性入門 泉 泰介(名工大), |
---|---|
PDFダウンロードページ | PDFダウンロードページへ |
抄録(和) | 通信複雑性とは,複数のプレイヤ間に分散して保持されているデータに対して大域的な関数計算を行ないたいとき,プレイヤ間で交換しなければならないビット数の上下界を明らかにする理論である.本発表では,同理論のもっとも基本的なモデルである2者間通信プロトコルについて,その導入およびその基本的な解析手法の一部を概説する. |
抄録(英) | Communication Complexity is a theory to reveal the necessary number of bitsexchanged among serveral parties for computing a given global function. In this talk, we present a quick introduction to that theory, in particular, for the case of two-party protocols, which is one of the most fundamentalmodels in communication complexity theory. |
キーワード(和) | 通信複雑性 / 2者間プロトコル / 交差判定 / 計算量理論 |
キーワード(英) | communication Complexity / two-party protocol / set-disjointness / computational complexity |
資料番号 | IT2015-44 |
発行日 | 2015-11-17 (IT) |
研究会情報 | |
研究会 | IT |
---|---|
開催期間 | 2015/11/24(から1日開催) |
開催地(和) | 岡山県 鷲羽山下電ホテル |
開催地(英) | Shimoden Hotel |
テーマ(和) | 若手研究者のための講演会(招待講演のみ) |
テーマ(英) | Lectures for Young Researchers (Invited talks only) |
委員長氏名(和) | 大濱 靖匡(電通大) |
委員長氏名(英) | Yasutada Oohama(Univ. of Electro-Comm.) |
副委員長氏名(和) | 和田山 正(名工大) |
副委員長氏名(英) | Tadashi Wadayama(Nagoya Inst. of Tech.) |
幹事氏名(和) | 岩本 貢(電通大) / 葛岡 成晃(和歌山大) |
幹事氏名(英) | Mitsugu Iwamoto(Univ. of Electro-Comm.) / Nariaki Kuzuoka(Wakayama Univ.) |
幹事補佐氏名(和) | 日下 卓也(岡山大) |
幹事補佐氏名(英) | Takuya Kusaka(Okayama Univ.) |
講演論文情報詳細 | |
申込み研究会 | Technical Committee on Information Theory |
---|---|
本文の言語 | JPN |
タイトル(和) | [招待講演]通信複雑性入門 |
サブタイトル(和) | |
タイトル(英) | [Invited Talk] A Short Introduction to Communication Complexity |
サブタイトル(和) | |
キーワード(1)(和/英) | 通信複雑性 / communication Complexity |
キーワード(2)(和/英) | 2者間プロトコル / two-party protocol |
キーワード(3)(和/英) | 交差判定 / set-disjointness |
キーワード(4)(和/英) | 計算量理論 / computational complexity |
第 1 著者 氏名(和/英) | 泉 泰介 / Taisuke Izumi |
第 1 著者 所属(和/英) | 名古屋工業大学(略称:名工大) Nagoya Institute of Technology(略称:NITECH) |
発表年月日 | 2015-11-24 |
資料番号 | IT2015-44 |
巻番号(vol) | vol.115 |
号番号(no) | IT-321 |
ページ範囲 | pp.1-6(IT), |
ページ数 | 6 |
発行日 | 2015-11-17 (IT) |