論文の概要: Bounded Simultaneous Messages

• arxiv url: http://arxiv.org/abs/2310.00334v4
• Date: Thu, 21 Dec 2023 15:30:41 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-25 14:15:19.802861
• Title: Bounded Simultaneous Messages
• Title（参考訳）: 境界付き同時メッセージ
• Authors: Andrej Bogdanov, Krishnamoorthy Dinesh, Yuval Filmus, Yuval Ishai, Avi Kaplan, Sruthi Sekar,
• Abstract要約: アリスとボブは、計算的に有界なキャロルにそれを送れば、入力の$f(x,y)$を評価できるだろうか? 一般的な問題は、分散計算が局所計算よりもコストがかかるアプリケーションによって、広く動機付けられる。 特に、Carolsize と計算境界を持つ BSM プロトコルの存在に対する証拠を与える。
• 参考スコア（独自算出の注目度）: 14.299998013724318
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the following question of bounded simultaneous messages (BSM) protocols: Can computationally unbounded Alice and Bob evaluate a function $f(x,y)$ of their inputs by sending polynomial-size messages to a computationally bounded Carol? The special case where $f$ is the mod-2 inner-product function and Carol is bounded to AC$^0$ has been studied in previous works. The general question can be broadly motivated by applications in which distributed computation is more costly than local computation, including secure two-party computation. In this work, we initiate a more systematic study of the BSM model, with different functions $f$ and computational bounds on Carol. In particular, we give evidence against the existence of BSM protocols with polynomial-size Carol for naturally distributed variants of NP-complete languages.
• Abstract（参考訳）: 計算的非有界アリスとボブは、多項式サイズのメッセージを計算的有界キャロルに送信することで、関数の$f(x,y)$を評価できるだろうか? f$ が mod-2 内積関数であり、Carol が AC$^0$ に有界である特別な場合については、以前の研究で研究されている。 この一般的な問題は、分散計算が局所的な計算よりもコストがかかるアプリケーションによって広く動機付けられる。 本研究では,キャロライン上の関数$f$と計算バウンダリを持つBSMモデルについて,より体系的な研究を開始する。 特に,NP完全言語の自然分布変種に対する多項式サイズのCarolを用いたBSMプロトコルの存在を示す。

関連論文リスト

• Quantum computational complexity of matrix functions [2.7488316163114823]
  2つの原始問題の計算複雑性について検討する。 単項関数、チェビシェフ関数、時間発展関数、逆関数の4つの関数を考える。
  論文  参考訳（メタデータ） (2024-10-17T18:00:03Z)
• Fast Multiplication and the PLWE-RLWE Equivalence for an Infinite Family of Cyclotomic Subextensions [6.487242614495099]
  RLWE(Ring Learning With Errors)問題とPLWE(Polynomial Learning With Errors)問題との等価性を実証する。 また、最大実部分体の環内の2つの要素の積を計算するための高速整数についても述べる。
  論文  参考訳（メタデータ） (2024-10-01T15:32:02Z)
• On Computing Pairwise Statistics with Local Differential Privacy [55.81991984375959]
  例えば$binomn2-1 sum_i ne j f(x_i, x_j)$, $x_i$ は$i$thユーザへの入力を表し、ローカルモデルでは差分プライバシ(DP)である。 この定式化は、Kendallの$tau$ coefficient、Area Under Curve、Giniの平均差、Giniのエントロピーなどの重要なメトリクスをキャプチャする。
  論文  参考訳（メタデータ） (2024-06-24T04:06:09Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。 異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。 我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
  論文  参考訳（メタデータ） (2022-06-07T18:00:01Z)
• Non-local computation of quantum circuits with small light cones [0.0]
  ポートベースのテレポーテーションは、一度に少数の量子ビットでのみ行われる場合、はるかに少ない絡み合いになる。 我々は、プロトコルの絡み合いコストが既知のプロトコルよりも良くスケールする、明示的なユニタリのクラスを提供する。
  論文  参考訳（メタデータ） (2022-03-18T18:00:06Z)
• Multi-Receiver Online Bayesian Persuasion [51.94795123103707]
  本研究では,未知の逆選択型の受信者に対して,送信者が繰り返し対面するオンライン学習フレームワークについて検討する。 オフラインモデルの慣習として、外部性やバイナリアクションのないケースに重点を置いています。 本稿では,損失関数を有限個に制限したオンライン学習問題に対処する一般的なオンライン降下スキームを提案する。
  論文  参考訳（メタデータ） (2021-06-11T16:05:31Z)
• Communication Complexity of Private Simultaneous Quantum Messages Protocols [0.609170287691728]
  本稿では、量子通信の利点と、プライベート同時量子メッセージモデルの事前絡み合いについて検討する。 プライバシ条件は,PSQMモデルの通信コストを必然的に増大させることを示す。 また,共有絡み合った状態と共有ランダム文字列を持つPSQMプロトコルの通信複雑性の指数的差を示す。
  論文  参考訳（メタデータ） (2021-05-15T03:08:01Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。 構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
  論文  参考訳（メタデータ） (2020-12-14T18:14:08Z)
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
  強化学習のコアにおける探索・探索トレードオフについて検討する。 特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。 私たちの後悔の限界はエピソードの数とは無関係です。
  論文  参考訳（メタデータ） (2020-11-09T18:32:22Z)
• Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks [48.32532049640782]
  ガウス境界の下で, 1層ReLUネットワークを$k$の隠れ単位で学習する問題をmathbbRd$で研究する。 正の係数の場合、この学習問題の初回アルゴリズムを$k$から$tildeOOmega(sqrtlog d)$まで与える。
  論文  参考訳（メタデータ） (2020-06-22T17:53:54Z)
• Communication memento: Memoryless communication complexity [5.88864611435337]
  我々は、メモリレス通信モデルにおいて、計算関数の通信複雑性を$F:0,1ntimes 0,1n rightarrow 0,1$で調べる。
  論文  参考訳（メタデータ） (2020-05-08T14:33:25Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。