論文の概要: Communication memento: Memoryless communication complexity
- arxiv url: http://arxiv.org/abs/2005.04068v2
- Date: Wed, 9 Sep 2020 12:36:47 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-20 20:06:32.740254
- Title: Communication memento: Memoryless communication complexity
- Title（参考訳）: communication memento: メモリレス通信の複雑さ
- Authors: Srinivasan Arunachalam and Supartha Podder
- Abstract要約: 我々は、メモリレス通信モデルにおいて、計算関数の通信複雑性を$F:0,1ntimes 0,1n rightarrow 0,1$で調べる。
- 参考スコア（独自算出の注目度）: 5.88864611435337
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the communication complexity of computing functions
$F:\{0,1\}^n\times \{0,1\}^n \rightarrow \{0,1\}$ in the memoryless
communication model. Here, Alice is given $x\in \{0,1\}^n$, Bob is given $y\in
\{0,1\}^n$ and their goal is to compute F(x,y) subject to the following
constraint: at every round, Alice receives a message from Bob and her reply to
Bob solely depends on the message received and her input x; the same applies to
Bob. The cost of computing F in this model is the maximum number of bits
exchanged in any round between Alice and Bob (on the worst case input x,y). In
this paper, we also consider variants of our memoryless model wherein one party
is allowed to have memory, the parties are allowed to communicate quantum bits,
only one player is allowed to send messages. We show that our memoryless
communication model capture the garden-hose model of computation by Buhrman et
al. (ITCS'13), space bounded communication complexity by Brody et al. (ITCS'13)
and the overlay communication complexity by Papakonstantinou et al. (CCC'14).
Thus the memoryless communication complexity model provides a unified framework
to study space-bounded communication models. We establish the following: (1) We
show that the memoryless communication complexity of F equals the logarithm of
the size of the smallest bipartite branching program computing F (up to a
factor 2); (2) We show that memoryless communication complexity equals
garden-hose complexity; (3) We exhibit various exponential separations between
these memoryless communication models.
We end with an intriguing open question: can we find an explicit function F
and universal constant c>1 for which the memoryless communication complexity is
at least $c \log n$? Note that $c\geq 2+\varepsilon$ would imply a
$\Omega(n^{2+\varepsilon})$ lower bound for general formula size, improving
upon the best lower bound by Ne\v{c}iporuk in 1966.
- Abstract（参考訳）: メモリレス通信モデルにおいて,計算関数の通信複雑性を$F:\{0,1\}^n\times \{0,1\}^n \rightarrow \{0,1\}$で検討する。
ここで、aliceは$x\in \{0,1\}^n$、bobは$y\in \{0,1\}^n$、彼らの目標は次の制約に従うf(x,y)を計算することである。
このモデルにおけるFの計算コストは、アリスとボブの間の任意のラウンドで交換される最大ビット数である(最悪の場合、x,y)。
本稿では,一方のパーティがメモリを持つことができ,一方のパーティが量子ビットを通信でき,一方のプレーヤーだけがメッセージを送信することができる,という,メモリレスモデルのバリエーションについても検討する。
本モデルでは,buhrman et al. (itcs'13), space bounded communication complexity by brody et al. (itcs'13), and the overlay communication complexity by papakonstantinou et al. (ccc'14) による計算のガーデン・hoseモデルを取り込む。
したがって、メモリレス通信複雑性モデルは、空間境界通信モデルを研究するための統一的なフレームワークを提供する。
1) f のメモリレス通信複雑性が最小二部分岐プログラム演算 f の大きさの対数(因子2 まで)に等しいこと,(2)メモリレス通信複雑性がガーデン・ホース複雑度に等しいこと,(3)メモリレス通信モデル間の指数関数的分離を示すこと,の2つを定式化する。
明示的な関数 f と普遍定数 c>1 は、メモリレス通信の複雑さが少なくとも $c \log n$ であるようなものを見つけることができるか?
c\geq 2+\varepsilon$ は一般式のサイズに対して$\omega(n^{2+\varepsilon})$の下限を意味し、1966年のne\v{c}iporukによる最下限を改善している。
関連論文リスト
- Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messages [63.366380571397]
本稿では,プライバシのシャッフルモデルにおけるプライベートベクトル平均推定の問題について検討する。
我々は,$tildemathcalOleft(min(nvarepsilon2,d)right)$ message per users を用いて,最適なエラーを実現する新しいマルチメッセージプロトコルを提案する。
論文 参考訳（メタデータ） (2024-04-16T00:56:36Z) - Cooperative Multi-Agent Reinforcement Learning: Asynchronous
Communication and Linear Function Approximation [77.09836892653176]
マルコフ決定過程の設定におけるマルチエージェント強化学習について検討した。
本稿では非同期通信が可能な値に基づく証明可能な効率的なアルゴリズムを提案する。
我々は、コラボレーションによってパフォーマンスを改善するために、最小の$Omega(dM)$通信の複雑さが必要であることを示す。
論文 参考訳（メタデータ） (2023-05-10T20:29:29Z) - Communication complexity of entanglement assisted multi-party
computation [11.820804392113294]
プレーヤが2ドル、ドットが2ドル、n$が1に適切な情報を伝達する必要がある場合、プレーヤが$n$のマルチパーティ計算問題を考える。
量子プロトコル(複雑性$(n-1)log n$ bits)と古典的プロトコル(複雑性$(n-1)2(log n2$)ビット)を示す。
これは、我々の量子プロトコルが古典的プロトコルよりも厳密に優れていることを示している。
論文 参考訳（メタデータ） (2023-05-08T03:10:08Z) - Non-trivial lower bound for 3-coloring the ring in the quantum LOCAL
model [0.0]
本研究では,一対一の通信のみを行うリングをカラー化するための分散アルゴリズムについて検討する。
適切な$$3のカラー化を出力する量子シングルラウンドワンウェイ分散アルゴリズムの確率は、指数関数的に$n$である。
論文 参考訳（メタデータ） (2022-12-06T05:39:50Z) - The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
すべての$delta>0に対して、$はCNFと近似次数$Omega(n1-delta)の式を構築し、基本的には$nの自明な上限に一致する。
すべての$delta>0$に対して、これらのモデルは$Omega(n1-delta)$、$Omega(n/4kk2)1-delta$、$Omega(n/4kk2)1-delta$が必要です。
論文 参考訳（メタデータ） (2022-09-04T10:01:39Z) - Exponential Separation between Quantum and Classical Ordered Binary
Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
量子順序付き二項決定図($OBDD$)モデルについて検討する。
入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。
read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
論文 参考訳（メタデータ） (2022-04-22T12:37:56Z) - On relating one-way classical and quantum communication complexities [6.316693022958221]
通信複雑性とは、関数入力が複数のパーティに分散されるときに、関数を計算するのに必要な通信量である。
量子情報の基本的な問題は、一方通行の量子と古典的な通信の複雑さの関係である。
論文 参考訳（メタデータ） (2021-07-24T14:35:09Z) - RNNs can generate bounded hierarchical languages with optimal memory [113.73133308478612]
RNNは、自然言語構文の足場を反映した境界階層言語を効率的に生成できることを示す。
Dyck-($k$,$m$)は、よくネストされた括弧($k$型)と$m$バウンドされたネスト深さの言語である。
明示的な構成により,$O(m log k)$ hidden units の RNN がメモリの指数的削減に十分であることを示す。
論文 参考訳（メタデータ） (2020-10-15T04:42:29Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳（メタデータ） (2020-08-24T06:50:57Z) - DEED: A General Quantization Scheme for Communication Efficiency in Bits [14.274085532399098]
分散最適化では、通信を減らすための一般的な手法は量子化である。
量子化スキームに適用可能な不正確な降下に関する一般的な分析フレームワークを提供する。
また、量子化スキームDoubleを提案する。
勾配と誤差低減(DEED)
論文 参考訳（メタデータ） (2020-06-19T21:38:44Z) - Capacity Approaching Coding for Low Noise Interactive Quantum
Communication, Part I: Large Alphabets [15.078027648304115]
ノイズの多いチャネル上での双方向の対話型量子通信を実現する際の問題点を考察する。
$mathrmpoly(n)$ sizeアルファベット上のノイズのないquditチャネルの場合、主な結果は2-theta(nepsilon)$未満の確率で失敗するシミュレーション手法である。
我々は、$sqrtepsilon$項の定数係数まで最適であると推測する。
論文 参考訳（メタデータ） (2020-01-09T02:48:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。