概要 - 群のFourier解析を通じて拡張歩行の擬似乱数性
タイトル
群のFourier解析を通じて拡張歩行の擬似乱数性
時間
2025-07-19 02:44:34
著者
{"Fernando Granha Jeronimo","Tushant Mittal","Sourya Roy"}
カテゴリ
{cs.CC,cs.DM,math.CO}
リンク
http://arxiv.org/abs/2507.14445v1
PDF リンク
http://arxiv.org/pdf/2507.14445v1
概要
この論文は、拡張グラフ上のランダムウォークの擬似ランダム性を群のFourier解析を使って調査しています。これは、XOR関数やAND関数などの様々な関数について研究された前の研究を基にしています。 **主要な結果**： * **対称関数**：この論文は、対称関数が任意の一般的なλ拡張グラフとアルファベットΣに対してO(|Σ|λ)で擬似ランダムウォークに欺かれることを示しています。これは、|Σ| = 2の場合の前の結果を一般化し、前の界隈O(|Σ| O(|Σ|) λ)を指数関数的に改善しています。 * **有限群**：Σが有限群Gの場合、論文は対称関数のクラスがGがD-quasirandomの場合、構造化されたλ拡張グラフ上でO(√|G| D λ)で擬似ランダムウォークに欺かれることを示しています。これは、一般的な拡張グラフに対する前の結果よりも強い界隈を提供しています。 * **下界**：論文は、有限群Gに対して対称関数の下界Ω(λ)を証明しています。これは、「構造化された」λ拡張グラフに対しても然りです。これは、拡張ウォークの擬似ランダム性がどれだけ改善できるかの基本的な限界を示しています。 * **非対称関数**：論文は、単語マップから生じる一種の非対称関数のFourierスペクトルを研究し、これらが拡張ウォークに指数関数的に欺かれることを示しています。 **証明技術**： 論文は一般的な群上のFourier解析を使用しており、これ以前の研究がZ2やZの場合に限られていたのとは異なります。これにより、構造のない集合に対しても定量的に良い界隈を得ることができます。 **重要性**： この論文は、拡張グラフの擬似ランダム性とそのコンピュータ科学や数学における適用に関する理解に寄与しています。新しい界隈と拡張ウォークの行動、関数を欺く能力に関する洞察を提供しています。また、Fourier解析がグラフ上の擬似ランダム性を研究するためのツールとしての力を強調しています。 **追加のポイント**： * 研究は「擬似ケイリー図」を使用して群の対称性を持つ関数に対する改善された界隈を得ます。 * 研究は対称関数の擬似ケイリー図上での擬似ランダムウォークの擬似ランダム性に対する下界を提供します。 * 研究は群の擬似ランダム性を利用して拡張ウォークの界隈を改善することを示します。
推奨論文
公開量子コンピュータ上での非侵襲的測定による時間の順序とLeggett-Garg不平等の検証
言語混合がバイリンガルLLMの推論に与える影響
大規模言語モデルを用いた橋の状態評価のための非破壊評価プロファイル図の自動解釈
ApproxGNN：近似計算のためのデザイン空間探索におけるパラメータ予測のための事前トレーニングGNN
「手を放つ？」ほどではない：コンテンツベースの初期化を使用した連続的な推薦におけるアイテムの冷始末問題の解決策を探る
どのグラフモチーフのパラメータが重要ですか？
顔認識精度に与える顔フィルタの影響を研究するための包括的評価枠組み
時領域におけるマクスウェル方程式の安定化二段階法式
不確実性下での堅牢最適化を通じてのパーソナライズド薬剤の計算的デザイン
時砂並べ：新しい並列ソートアルゴリズムとその実装