論文の概要: Optimal Small Set Expanders and Their Codes

• arxiv url: http://arxiv.org/abs/2606.23579v1
• Date: Mon, 22 Jun 2026 16:46:20 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-24 18:08:12.533966
• Title: Optimal Small Set Expanders and Their Codes
• Title（参考訳）: 最適小集合展開とその符号
• Authors: Tristram Bogart, Marcelo Fiori, Pedro Raigorodsky, Mauricio Velasco,
• Abstract要約: そのようなグラフは、小さな部分集合ができるだけ多くの近傍を持つ場合、最適な小集合拡大器である。 量子後暗号における鍵交換プロトコルの良コード構築における最適小集合拡張器の使用について論じる。
• 参考スコア（独自算出の注目度）: 0.8749675983608171
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A left-regular bipartite graph $G$ of degree $d$ is called a $(t,α)$-small-set-expander if every subset $X$ of left vertices of size at most $t$ has at least $α|X|$ neighbors. Such a graph is an optimal small-set expander if small subsets have as many neighbors as possible. We characterize optimal expanders combinatorially via girth and prove the existence of $s$-optimal expanders for every $s$. We also prove that $s$-optimality yields new "transfer" lower bounds on the number of neighbors of sets of size $h\geq s$. Finally, as an application, we discuss the use of optimal small-set expanders in building good codes for key exchange protocols in post-quantum cryptography.
• Abstract（参考訳）: 左正則二部グラフ $G$ of degree $d$ は、すべての部分集合 $X$ of size at least $t$ が少なくとも $α|X|$ 近傍を持つとき、$(t,α)$-小集合-エクスパンダーと呼ばれる。 そのようなグラフは、小さな部分集合ができるだけ多くの近傍を持つ場合、最適な小集合拡大器である。 最適拡大器を girth を介して組合せて特徴付け、各$s$に対して$s$-最適拡大器の存在を証明する。 また、$s$-最適性は、サイズ$h\geq s$の集合の近傍の個数に新しい「移動」下界をもたらすことを証明している。 最後に、量子後暗号における鍵交換プロトコルの良コード構築における最適小集合拡張器の使用について論じる。

関連論文リスト

• On Exact Sizes of Minimal CNOT Circuits [2.831145157553215]
  我々は、可逆性と量子コンピューティングの基本的なバイナリゲートであるCNOTゲートの回路を考える。 我々はG_n$で距離を計算する新しい手法を開発し、これまでは到達できなかった最小限の回路を合成する。 また、すべての$nleq 8$に対して、長い周期の置換が3(n-1)$で、以前の$nleq 5$の範囲を延ばすという予想も確認する。
  論文  参考訳（メタデータ） (2025-03-03T12:20:48Z)
• Optimal and Efficient Algorithms for Decentralized Online Convex Optimization [51.00357162913229]
  分散オンライン凸最適化(D-OCO)は、局所計算と通信のみを用いて、グローバルな損失関数の列を最小化するように設計されている。 我々は,凸関数と強凸関数の残差を$tildeO(nrho-1/4sqrtT)$と$tildeO(nrho-1/2log T)$に削減できる新しいD-OCOアルゴリズムを開発した。 我々の分析によると、射影自由多様体は$O(nT3/4)$と$O(n)を達成できる。
  論文  参考訳（メタデータ） (2024-02-14T13:44:16Z)
• Listing Maximal k-Plexes in Large Real-World Graphs [21.79007529359561]
  大きなグラフで高密度なサブグラフをリストすることは、コミュニティ検出のような様々なネットワーク分析アプリケーションにおいて重要なタスクである。 本稿では、最大$k$-プレックスと最大$k$-プレックスを所定の大きさで列挙する研究線を継続する。 私たちの最初のコントリビューションはアルゴリズムListPlexで、すべての最大$k$-plexesを$O*(gammaD)$ time for each constant $k$, where $gamma$ is a value to $k$ but strictly smaller than 2, and $D$ is the degeneracy of the graph that far less。
  論文  参考訳（メタデータ） (2022-02-17T16:25:56Z)
• Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
  高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。 実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
  論文  参考訳（メタデータ） (2021-10-21T18:43:00Z)
• Near Optimal Stochastic Algorithms for Finite-Sum Unbalanced Convex-Concave Minimax Optimization [41.432757205864796]
  本稿では,$min_bf xmax_yf(bfbf y)という形の凸-凸最小値問題の1次アルゴリズムを同時に検討する。 我々の手法は、より一般的な不均衡なミニマックス問題を解くために使用することができ、また、ほぼ最適である。
  論文  参考訳（メタデータ） (2021-06-03T11:30:32Z)
• Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrap [84.66885506098724]
  本稿では,アダプティブ・マルチステップ・ブートストラップ (AMB) を用いた表層有限水平マルコフ決定過程 (MDP) のモデルフリーアルゴリズムを提案する。 AMBは,部分最適ギャップの逆の和でのみスケールする,ギャップ依存的後悔境界を達成できることを示す。 また、AMB は $frac|Z_mul|Delta_min$ regret という追加の $frac|Z_mul|Delta_min$ を被っていることも示しています。
  論文  参考訳（メタデータ） (2021-02-09T07:46:34Z)
• 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)
• $Q$-learning with Logarithmic Regret [60.24952657636464]
  楽観的な$Q$は$mathcalOleft(fracSAcdot mathrmpolyleft(Hright)Delta_minlogleft(SATright)right)$ cumulative regret bound, where $S$ is the number of state, $A$ is the number of action, $H$ is the planning horizon, $T$ is the total number of steps, $Delta_min$ is the least sub-Optitimality gap。
  論文  参考訳（メタデータ） (2020-06-16T13:01:33Z)

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

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