論文の概要: Regularity as seen by Alice and Bob

• arxiv url: http://arxiv.org/abs/2607.13782v1
• Date: Wed, 15 Jul 2026 12:38:07 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-16 16:39:12.760253
• Title: Regularity as seen by Alice and Bob
• Title（参考訳）: アリスとボブが見る正則性
• Abstract要約: 本稿では,異なる出力領域を持つ関数間の正則性特徴付けのための統一モデルを提案する。 ここでは、$* から domain$ への関数を考え、$$ は有限アルファベットであり、$ domain は任意のドメインである。 この枠組みを名詞集合の設定において無限のアルファベットに拡張し、その表現性を原子を持つ単語の言語で調べる。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The goal of this paper is to propose a unifying model for Nerode-style characterizations of regularity across functions with different output domains. Building on Hauser's work in communication complexity, we generalize the setting by relaxing the computability assumptions and allowing non-Boolean output domains. We consider functions of type $Σ^* \to \domain$, where $Σ$ is a finite alphabet and $\domain$ is an arbitrary domain. For several domains, we show that the model coincides with known models of computation. We further conjecture that an analogous correspondence holds for other domains that currently lack a Nerode-style characterization of regularity, and we provide ample supporting evidence. In the model, an input string $w$ is split as $w = w_1 w_2$ and distributed between two cooperating parties, Alice and Bob, who exchange a constant number of messages to compute the value of the function. Each message is either an element of the output domain or a signal drawn from a finite set of signals, and the parties must produce the correct output for every admissible split $w = w_1 w_2$. We further extend the framework to infinite alphabets in the setting of nominal sets, and investigate its expressiveness on languages of words with atoms.
• Abstract（参考訳）: 本研究の目的は,異なる出力領域を持つ関数間の規則性のNerode型特徴付けのための統一モデルを提案することである。 通信複雑性におけるHauserの仕事に基づいて、計算可能性の仮定を緩和し、非ブール出力領域を許容することで、設定を一般化する。 種数$Σ^* \to \ domain$ の関数を考えると、$Σ$ は有限アルファベット、$\ domain$ は任意の領域である。 いくつかの領域において、このモデルが既知の計算モデルと一致することを示す。 さらに、同型対応が、現在ネロード形式の正規性の特徴づけを欠いている他の領域に対して成り立つと推測し、十分な証拠を提供する。 モデルでは、入力文字列$w$は$w = w_1 w_2$として分割され、2つの協調するパーティ、アリスとボブの間で分散される。 各メッセージは出力領域の要素か、有限の信号集合から引き出された信号であり、当事者は全ての許容可能な$w = w_1 w_2$に対して正しい出力を生成する必要がある。 名目集合の設定において、この枠組みをさらに無限のアルファベットに拡張し、その表現性を原子を持つ単語の言語で調べる。

関連論文リスト

• Optimal entanglement-assisted source coding under a balanced-difference promise [0.0]
  絡み合いは、コーディングタスクに必要なコミュニケーションを減らすことができるが、その限界を理解するためには、達成可能な最小コストの確立が不可欠である。 我々は、Aliceが単語を受信し、Bobはその単語を含む無秩序な候補のペアを知っているゼロエラーソースコーディングタスクでこの問題に対処する。 我々は、$(q-1)ell$が偶数であるとき、そのタスクに正確に$n$メッセージが必要であることを証明している。
  論文  参考訳（メタデータ） (2026-09-14T15:43:27Z)
• Canonicalizing Multimodal Contrastive Representation Learning [76.15228959754727]
  ここでは,CLIP,SigLIP,FLAVAなどのモデルファミリにおいて,埋め込み空間間の幾何学的関係が存在することを示す。 この発見は、後方互換性のあるモデルアップグレードを可能にし、コストのかかる再埋め込みを回避し、学習された表現のプライバシに影響を及ぼす。
  論文  参考訳（メタデータ） (2026-02-19T18:09:36Z)
• Model Enumeration of Two-Variable Logic with Quadratic Delay Complexity [6.164137092509227]
  2変数(FO2$)を持つ一階述語論理の関数自由有限領域フラグメントのモデル列挙問題について検討する。 サイズ$n$のドメイン上で$Gamma$のすべてのモデルを列挙するにはどうすればよいのか?
  論文  参考訳（メタデータ） (2025-05-26T08:04:19Z)
• Federated Combinatorial Multi-Agent Multi-Armed Bandits [79.1700188160944]
  本稿では,Banditを用いたオンライン最適化に適したフェデレーション学習フレームワークを提案する。 この設定では、エージェントのアームサブセットは、個々のアーム情報にアクセスせずにこれらのサブセットに対するノイズの多い報酬を観察し、特定の間隔で協力して情報を共有することができる。
  論文  参考訳（メタデータ） (2024-05-09T17:40:09Z)
• Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximation [77.09836892653176]
  マルコフ決定過程の設定におけるマルチエージェント強化学習について検討した。 本稿では非同期通信が可能な値に基づく証明可能な効率的なアルゴリズムを提案する。 我々は、コラボレーションによってパフォーマンスを改善するために、最小の$Omega(dM)$通信の複雑さが必要であることを示す。
  論文  参考訳（メタデータ） (2023-05-10T20:29:29Z)
• Online Learning with Adversaries: A Differential-Inclusion Analysis [52.43460995467893]
  我々は,完全に非同期なオンラインフェデレート学習のための観察行列ベースのフレームワークを提案する。 我々の主な結果は、提案アルゴリズムがほぼ確実に所望の平均$mu.$に収束することである。 新たな差分包摂型2時間スケール解析を用いて,この収束を導出する。
  論文  参考訳（メタデータ） (2023-04-04T04:32:29Z)
• Biased Random Access Codes [0.0]
  ランダムアクセスコード(英: random access code、RAC)は、送信者が受信機によって復号される短いメッセージにランダムメッセージを符号化する通信タスクである。 本稿では,古典的戦略と量子的戦略の両方に対して最適性能を数値的に評価するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-02-16T18:53:25Z)
• Lifted Inference with Linear Order Axiom [0.0]
  We consider the task of weighted first-order model counting (WFOMC) 我々は、少なくとも2つの論理変数を持つ論理文の WFOMC が $n$ の時間で実行可能であることを示す。 線形順序でWFOMCをn$で計算できる新しい動的プログラミングベースアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-11-02T14:38:01Z)
• 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)
• Improving Robustness and Generality of NLP Models Using Disentangled Representations [62.08794500431367]
  スーパービジョンニューラルネットワークはまず入力$x$を単一の表現$z$にマップし、次に出力ラベル$y$にマッピングする。 本研究では,非交叉表現学習の観点から,NLPモデルの堅牢性と汎用性を改善する手法を提案する。 提案した基準でトレーニングしたモデルは、広範囲の教師付き学習タスクにおいて、より堅牢性とドメイン適応性を向上することを示す。
  論文  参考訳（メタデータ） (2020-09-21T02:48:46Z)
• On the Modularity of Hypernetworks [103.1147622394852]
  構造化対象関数の場合、ハイパーネットワークにおけるトレーニング可能なパラメータの総数は、標準ニューラルネットワークのトレーニング可能なパラメータの数や埋め込み法よりも桁違いに小さいことを示す。
  論文  参考訳（メタデータ） (2020-02-23T22:51:52Z)

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

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