概要 - 平等は恒常的なコストのコミュニケーションよりもずっと弱いです

タイトル

平等は恒常的なコストのコミュニケーションよりもずっと弱いです

時間

2025-07-15 10:10:21

著者

{"Mika Göös","Nathaniel Harms","Artur Riazanov"}

カテゴリ

{cs.CC}

リンク
http://arxiv.org/abs/2507.11162v1

PDF リンク
http://arxiv.org/pdf/2507.11162v1

概要

この論文は、通信複雑さにおけるシンプルなハッシュの力、特に等価性コミュニケーション問題に関する研究を発表しています。著者たちは驚くべき結果を示しました：等価性オラクルを使用して、常数コストのランダム化プロトコルを効率的に「非ランダム化」することはできません。 **主要な発見**： * **常数コスト通信と等価性オラクル**：著者たちは、常数コストのランダム化通信を持つが、nΩ(1)の確定性（または非決定性）の等価性オラクルクエリが必要な通信問題を提案しました。これは、BPP0 ̸⊆ PEq であることを示唆しており、BPP0はランダム化の常数コスト問題のクラス、PEqは等価性オラクルコストpoly log nを持つ問題のクラスです。 * **k-Hamming Distanceからの分離**：著者たちはまた、常数コスト通信がk-Hamming Distance階層に還元できないことを示し、BPP0とk-Hamming Distanceの間の分離を改善しました。 * **5つの付随結果を持つ2つの証明**：論文は、主な結果に対して2つの比較不可能な証明を提供しており、1つは解析的で、もう1つは組み合わせ的です。これらの証明は、以下のような興味深い付随結果を生み出します： * 近似スペクトルノルムO(1)を持つが、正確なスペクトルノルムが2Ω(n)を持つ関数の存在 * ランダム化パリティ決定木の大きさがO(1)を持つが、確定性パリティ決定木の大きさが2Ω(n)を持つ関数の存在 * NPEq（非決定性等価性オラクルコストpoly log nを持つ問題のクラス）との間の分離の改善 * NDEq（·）の下界の改善、非決定性等価性オラクルコスト * **影響**： * 等価性オラクルが存在する場合でも、シンプルなハッシュの限界を示唆し、通信プロトコルを効率的に非ランダム化する困難性を強調しています。 * 通信問題の複雑さと異なる種類のオラクルの力についての新しい洞察を提供しています。 * 付随結果は、複雑性理論、通信複雑さ、ブール関数解析を含む理論情報科学のさまざまな分野に影響を与えます。 **重要性**：この論文は、シンプルなハッシュの力と等価性オラクルを使用した非ランダム化の限界に関する新しい洞察を提供することで、通信複雑さの分野に重要な貢献をしています。これらの結果は、理論情報科学のさまざまな分野、特に通信複雑さと関連分野におけるさらなる研究の基盤を提供します。

推奨論文

GENIAL: ネットワーク逆転を通じて低消費電力アルゴリズム論理ユニットの生成設計空間探索

夢：インタラクティブな世界生成モデル

変額年金：リベット保証、ハイブリッド契約設計、および課税の詳細な見解

有限領域における可変 Min-Cut Max-Flow 界とアルゴリズム

PINNsと画像分類のための動的学習率スケジュールを用いた神経ネットワークトレーニングの改善

時砂並べ：新しい並列ソートアルゴリズムとその実装

エルク：深層学習コンパイラ技術を用いて、インターコア接続AIチップの効率を探求する

「分画法の構築への新しいアプローチ」

サイバー脅威情報のROIを測定する：データ駆動型アプローチ

モダリティに依存しない効率的な長距離エンコーダ