本サイトは 12 時間以上更新されていません（通常は 3 時間ごと）。以下の内容は最新でない可能性があります。
このページに条件に合う項目はありません（絞り込みはこのページ内のみ）。
説明下方閉じ制約付きの預言者問題と秘書問題に対する厳密な上下界
要約本論文は、任意の下方閉じ実行可能性制約のもとでのオンライン選択問題を、異なる到着順序と分布仮定の下で研究する。標準（敵対的順序）の預言者問題、ベイズ的ランダム順序の預言者秘書問題（およびそれを通じた標準秘書問題）、自由順序の預言者問題について、漸近的に厳密な競合比の上下界を示している。これらの結果は先行研究の補完的な界と合わせて、各変種の漸近的に厳密な競合比を確定する。
注目点下方閉制約の下で、複数の到着順序に対する預言者・秘書問題のタイトな競争比を示し、ランダム順序と自由順序の差を紧界で明らかにする。
説明局所性と干渉の出会い：無線マルチキャストにおける構造とスケジューリング
要約本論文は、参加者の位置が未知で、メッセージの集約を制限なしに許す同期型無線ネットワークにおける多点対多点マルチキャストを研究している。距離2彩色、単位円盤グラフの幾何情報、強選択性、独立ランダム送信などの方式について、完了までのスロット数の上界を示している。さらに、一跳指定配信の場合には、最適なスケジュール長が関連する衝突グラフの彩色数に等しく、2b−1以下であることを証明している。
説明多重彩色化による明示的編集符号の構成
要約本論文は、固定された q 元符号について、長さ n の符号語に含まれる最大 t 個の挿入・削除・置換の任意の組み合わせを訂正できる明示的な符号を構成しています。冗長度は 2t·log_q n と O(log log n) の q 元記号であり、Levenshtein の古典的存在証明の主要な冗長項と一致します。手法は、編集混同グラフに素数ベースの多重彩色を適用するものです。
注目点新規性は素数ベースの多重彩色により各語に複数の色を割り当て、冗長性をLevenshteinの主項2t log_q nに合わせる点にある。決定的な符号化・復号の時間界を示す。
説明多元接続通路の情報スペクトル法 第3部：K利用者ガウス通路の強逆定理
要約本稿は連作の第3部で、K利用者多元接続通路（MAC）を扱う。二つの基本補題から、費用制約付きの一般K利用者MACの容量領域を導き、それがK利用者ガウスMACのポリマトロイド容量領域を含むことを示す。情報スペクトルの計算により、ガウスMACの強逆定理、すなわち容量領域外のすべての速率組で誤り確率が1に近づくことを証明する。この結果は以前Fong と Tan が確立したものである。
説明多元接続通路の情報スペクトル法（第2部）：有限アルファベットの混合ケースにおけるε容量領域
要約本論文は、符号語全体を通じて通路の法則が固定される非エルゴード通路（例：緩やかなフェージングのリンク）について、有限アルファベットの2ユーザ混合多元接続通路（MAC）のε容量領域を研究している。単一字母の内界と外界（アウテージ領域）を導出し、順序付けられた混合MACなどの場合にその両者が一致することを示している。さらに、Ahlswedeの強逆定理をK ユーザの場合へ拡張している。
説明計算場上の自律移動ロボット：床そのものを計算媒体とするロボットモデル
要約本論文は、ロボットが動く離散平面を受動的な舞台ではなく計算媒体とみなす計算モデル CABOT を提案する。ロボット自体は非常に弱く、見えるのは近接マスの状態と他ロボットの位置だけで、床の状態数 |Q| が計算資源の尺度となる。少数の状態で線形成、集合、グリッド探索などが可能になることを示し、一部の作業は床が沈黙する条件では解けないことを証明している。
注目点格子環境をセルオートマトンとして計算資源とみなし、極めて弱いロボットで線形成・集合・探索を実現する。状態数に関するタイトな界を報告する。
説明高次変調向けに最適化された Zak-OTFS 用 Mirabbasi-Martin パルス整形フィルタ
要約本論文は、Zak-OTFS 変調のための分離可能な二次元 Mirabbasi-Martin（MM）フィルタを提案し、コンパクトな構造を保ったままサイドローブエネルギーを最小化するフィルタ係数の最適化手法を示す。最適化後のフィルタは遅延ドップラー領域においてサイドローブがなく、-40 dB のパルス幅が sinc、ガウス、GS パルスと比べて最も狭い。シミュレーションでは、64-QAM などの高次変調において、これらの従来フィルタより優れた誤り率性能が示されている。
説明規則が不確実なデータ取引：自己適応・自己診断型の多機械学習エージェントシステムのためのゲーム理論フレームワーク
要約大規模組織の自律的な機械学習エージェントが、データやモデル出力を組織や法的境界をまたいでやり取りする状況を扱う論文です。どの規則が適用されるかは、データ主体の居住地、エージェントの稼働地、対象地域などによって変わるため、著者はこの交換を二つのエージェントと執行者の三者による「規則不確実な移転ゲーム」として定式化し、法的制約付きナッシュ交渉（LCNB）を提案しています。合成シミュレータでの三つの検証ケースのうち二つでは、国籍ベースの規則で21〜37％の共有レコードが違反となった一方、LCNBでは1％未満でした。ただし、既定の経済条件ではほぼ集計データしか共有されず、その点が低い違反率の一因であるなど、限界も示されています。
説明SS-HSDP：実行時と更新の分離による効率的で柔軟なシャーディング型データ並列化
要約本論文は、実行時パラメータと更新パラメータを分離する学習フレームワークSS-HSDPを提案し、計算レイアウトと最適化単位を独立に構成できるようにします。共有データビューと階層的シャーディングにより、冗長なデータ移動を避けながらこの分離を実現します。Muonなどの行列ベースの手法や完全なゼロコピー実行にも対応します。MXFP8による動画・言語モデルの学習実験では、FSDP2、veScale-FSDP、Megatron-FSDPより高いモデルFLOPs利用率（MFU）を示し、128GPUでは最速の比較基準に対してMFUが最大21.7%向上し、ピークメモリ使用量は同等以下でした。
説明線形符号および量子符号に対するGilbert-Varshamov限界のΘ(n)倍改善
要約本論文は誤り訂正符号の存在性を示す基準であるGilbert-Varshamov限界を扱う。従来、q元線形符号に対する一般的な改善はΘ(√n)にとどまっていた。著者らは、低重みベクトルを残したまま後で一括して除去する新しい証明法を示し、線形符号でもΘ(n)倍の改善を得た。さらにこの手法を量子符号に拡張し、一定の条件を満たす相対距離の範囲で量子GV限界のΘ(n)倍改善を得た。
注目点新規性は、O(n)個の低重みベクトルを許容し射影空間での独立性を利用して一括消去することで、線形符号のGV界改善をΘ(n)へ引き上げ、量子符号にも拡張した点にある。作者は証明と量子への拡張を報告している。
説明安全なMISO通信を強化するフレキシブル知的メタサーフェス
要約本論文は、複数アンテナを持つ盗聴者が存在する状況で、フレキシブル知的メタサーフェス（FIM）を用いた安全な多入力単出力（MISO）通信を検討している。送信共分散行列とFIM表面形状を同時に最適化して保秘レートを最大化し、ブロック座標上昇法で解く手法を提案している。数値結果では、従来の剛体アンテナアレイと比べてFIMが保秘レートを向上させ、同じ保秘レートで約2.5 dBの送信電力削減を達成することが示されている。
説明戦略的にロバストなマルチエージェント制御：ゲーム理論的制御とロバスト制御の間を埋める新しい均衡概念
要約本論文は、ゲーム理論的制御とロバスト制御の中間を埋める「戦略的にロバストなマルチエージェント制御」を提案する。動的ゲームにおいて各プレイヤーは、他のプレイヤーの制御方策が誤って設定されている場合に備えた保護を求める。この枠組みから、両者の間を補間する新しい均衡概念が導かれる。著者らは開ループおよび閉ループの標準的な設定でこの概念を検討し、車両隊列走行、在庫管理、ネットワーク制御の数値実験により、設定誤りに対する耐性と、戦略的ロバスト性が性能や社会的厚生を向上させる場合があることを示している。
説明有限Leeトーラス上の普遍最適性：有限Leeトーラスで、任意の離散完全単調ポテンシャルに対し、同じ個数の集合のうちペアエネルギーを最小にする部品集合を調べる研究。
要約本論文は有限Leeトーラスの部分集合について、同じ濃度の集合の中で、離散完全単調ポテンシャルごとにペアエネルギーを最小化するものを研究する。偶数長の巡回群の直積における半分の占有では、2つの市松模様集合が全エネルギーと個々の最大エネルギーをともに最小化し、Bouman・Draisma・van Leeuwaardenの市松模様予想をこのクラスについて証明している。Z_q^n上の距離1グラフの独立数で普遍最適集合が存在する条件や、Z_5^n の密度1/5での特徴づけも示される。証明には傅里葉線形計画法を強めた整数の箱占有上界と傅里葉証明書が用いられる。
注目点新規性は市松模様予想の証明と有限Leeトーラス上の普遍最適集合の特徴づけにあり、整数箱占有界とフーリエ証明書により論証したと作者は報告している。影響は組合せ論と情報理論の狭い範囲に限られる。
説明Snoopie：マルチGPU通信のプロファイリング・可視化ツール
要約本論文は、NVBitベースの計測方式によるマルチGPU通信プロファイリングツールSnoopieを紹介しています。GPU間のピアツーピア転送とGPU中心の通信ライブラリ呼び出しを追跡でき、データ移動をソースコードの行や関連データオブジェクトに帰属させることができます。システム全体の粗い表示から個々の命令やアドレスまで、粒度の異なる可視化モードを備えています。事例研究により、データ移動の監視、性能上の問題の特定、通信ライブラリの内側で行われる実際のデータ転送の把握に有効であることが示されています。本ツールは公開されています。
説明森の中での情報設計：アルゴリズムの観点から
要約本論文は、送り手が複数の受け手に情報を伝えるベイズ的説得の枠組みを扱い、受け手の情報の階層が事前に与えられた有向森林で表される場合を研究している。二値の状態と二値の行動という設定の下で、対称な効用に関する計算可能性の結果を森の階層へ拡張し、モジュラ効用の場合には多項式時間アルゴリズムを示している。また、超モジュラ効用の場合はNP困難でFPTASが存在しないこと（P≠NPの仮定の下で）を示し、森の深さに線形に依存する近似アルゴリズムを与えている。
説明分散型極大独立集の平滑化解析：ランダム摂動で最悪ケースの下界を超える
要約本論文は分散型極大独立集（MIS）問題の平滑化解析を行う。任意の基グラフの各辺を確率pで独立に反転させて平滑化グラフを作り、p=β·ln n/n（βは十分大きい定数）のとき、LOCALモデルのランダム化アルゴリズムが高い確率でO(√log n)ラウンドにMISを求められることを示す。これは最悪ケースの下界Ω(log n/log log n)より速い。逆に、p≤(1/2-δ)·ln n/nの場合には、どのランダム化アルゴリズムもΩ(log n/log log n)ラウンドを要する基グラフが存在する。
注目点分布MISに平滑解析を導入し、ランダム摂動下でO(√log n)ラウンドのアルゴリズムと、ほぼタイトな下界を示す。
説明プロセス機器の最適選定のための並列計算システム
要約本論文は、多品種バッチプラントの化学工学システムにおける機器の最適選定問題を扱います。これは大規模なNP困難な離散最適化問題で、可操作性と所要時間内の製品生産を満たしつつ設備の総資本コストを最小化します。著者らは数理モデルを構築し、分枝限定法とその共有メモリ、分散メモリ、GPU向けの並列版を開発しました。さらに、アリコロニー最適化と焼きなまし法を組み合わせたハイブリッドメタヒューリスティックも提案しています。並列ハイブリッド手法は、分枝限定法の最適解との差が0.01%以内の解を数十秒で得られ、従来の数十時間に比べ大幅に高速であることが示されています。
説明閉形式レート歪み関数の構成的理論（レート歪み関数を解析的に表す方法を体系化した理論）
要約本論文は、条件付きエントロピーを共通の歪み座標として用いる事後分布ベースの構成フレームワークにより、レート歪み関数の解析的な求め方を研究している。有限アルファベットの離散情報源と可積分な対数密度をもつ連続情報源について、エントロピー水準での到達可能性を構成的な符号化証明で示している。さらに、Gamma源、zeta源、負の二項分布源などについて、特定の歪み尺度の下での閉形式または区間上の厳密な表現を導いている。
説明MegaOps：PyTorch風のモジュール性とMegakernelの性能を両立するカーネル重畳フレームワーク
要約論文は、各演算子を個別のGPUカーネルとして実行する従来方式のまま、依存関係のあるカーネル間の待ち合わせを中間テンソルのデータタイル単位で行うMegaOpsというフレームワークを提案しています。カーネルを融合せずにカーネル間の屈服（バリア）を取り除くことが狙いです。Llama3やQwen3の稠密モデルをH100、A100、L40および複数GPUサーバーで評価した結果、手作業で最適化されたThunderKittensのMegakernelと同等のスループットを示し、デコードは最良のベースラインの1.09〜1.10倍、プリフィルは0.98〜1.10倍でした。
注目点カーネルを融合せずにデータタイル単位の依存関係でカーネル間の障壁を除去する点が新しい。摘要はLlama3とQwen3で、ThunderKittensのメガカーネルと同等の性能と、解码で1.09～1.10倍のスループット向上を報告している。
説明2/3 凸ゲームのコア非空性：凸性を緩めた協力ゲームに安定した配分（コア）が必ず存在するかを調べた研究
要約本論文は、任意の三つの異なる提携のうち少なくとも二つが劣モジュラ不等式を満たすことを要求する 2/3 凸ゲームのコアを研究しています。すべての 2/3 凸ゲームには限界貢献ベクトルがコアに含まれることを示し、コアが非空であることを証明しています。その証明は構成的で、コア配分を線形時間で求めるアルゴリズムを与えます。さらに、2/3 凸性と置換凸性の関係、およびOSCE の「コンセンサス減二」手続きに着想を得たゲームモデルについても論じています。
説明起動処理の共有と事前ウォームアップによるサーバーレスLLMの高速コールドスタート
要約論文は、サーバーレスLLMプラットフォームでモデルワーカーをオンデマンド起動する際のコールドスタートが約1分かかり、重みの読み込みに使われるのは5〜11%にすぎないと指摘しています。残りはコンパイル、メモリプロファイリング、ランタイム初期化に費やされ、各サーバーが同じ処理を繰り返しています。提案システムのCairnは、最初に起動したサーバーが重みとエンジン成果物をクラスター共有のCXLメモリプールに公開し、他のサーバーはそれを直接読み取ります。モデルに依存しない初期化は、ウォームコンテナ内で事前に完了させます。vLLM v0.20と1B〜14Bの6モデルを用いた評価では、コールドスタートが4.1〜5.2倍速くなり、リクエスト列の中央値TTFTが64%減少したと報告されています。
説明単一の内符号を用いる連接符号：代数幾何符号による低符号率 Gilbert-Varshamov 漸近評価
要約本論文は、すべての外部座標で一つの二元内符号を再利用する連接符号を研究している。外符号は、指定された代数符号の拡大コピーのランダムな部分符号とされる。著者らは最小距離の失敗確率に関する一般的な上界と、指数的減衰の十分条件を示した。Garcia-Stichtenoth タワー上の代数幾何符号を用いて、符号化率が ε² に近づく確率的二元符号族を構成し、低符号率において距離保証が GV 限界の主要係数に一致することを示した。
注目点単一の内符号を用いる連接符号と Garcia-Stichtenoth タワーの代数幾何符号の部分符号を組み合わせ、低レートでGV界の主係数に一致する距離保証を与え、指数的減衰の確率界を示す。
説明無線ネットワークにおける分散型変分量子計算の高速化：インセンティブ機構設計
要約分散型変分量子計算（DVQC）では、量子プロセッサの参加意欲を高めることが課題となっている。本論文は、無線DVQCのための二段階インセンティブ枠組みを提案する。第一段階では、サブ回路パラメータ、ノイズ測定回数、送信電力を同時最適化してプロセッサ側のエネルギーコストを下げ、第二段階では、そのコストに基づいて集約側の系統効用を最大化するプロセッサ集合を選択する。MNISTとCIFAR-10での実験では、集中型量子計算と同程度の性能が示され、エネルギー効率と系統効用で基準手法を上回った。
説明二段階秘密分散：秘密が段階的に得られる場合の配布と情報保持の方法
要約本論文は、秘密情報が段階的に利用可能になる状況のための二段階秘密分散を、情報理論の枠組みで定式化する。第一段階では秘密の初期部分のシェアを配布し、第二段階では残りの部分が得られた後に新しい参加者へシェアを配布する。既に配布したシェアは更新しない。二段階アクセス構造を定義して特徴付け、二段階の間にディーラーが保持すべき第一段階秘密の情報量について普遍的な下界を導出し、すべての二段階アクセス構造でその下界を達成する構成を示す。さらに、事前共有が本モデルの特別な場合であることを示し、古典的な情報理論的秘密分散における特徴付けと関連する構成を与える。
説明首位繰り返し規則によるh-Majorityの多数意見合意（論文）
要約本論文はh-Majority動態を扱う。n個のエージェントがk個の意見のいずれかを持ち、各ラウンドで無作為に選んだh個のエージェントの意見を観察し、そのうち最も多い意見を採用する。著者らは、h≥3の任意の値について、初期多数意見の偏差が十分大きければ、高い確率でO((1+n/(h²M₀)) log n)ラウンド以内に初期多数意見で合意に至ることを示す。中心となるのは比較原理で、対称的な規則の中で多数決規則が、最多意見を出力する確率と任意の競合意見を出力する確率との差を最大化することを示す。
注目点比較原理によりh-Majorityの1ラウンド解析をDejaVuへ帰着させ、O((1+n/(h^2 M_0)) log n)ラウンドの合意時間界を、特定条件下でDejaVuと同等のバイアス条件で示す。
説明埋め込みハイパーキューブとBeta-ガウス混合分布に対する閉形式のガウス情報射影
要約本論文は、接線成分がアフィン埋め込みハイパーキューブ上に台を持ち、法線成分がガウス分布に従うBeta-ガウス分布について、閉形式のガウス情報射影を導出する。最適なガウス分布はモーメント・マッチングによって一意に定まり、対応する最小KL情報量は内在的なBeta パラメータのみに依存する。さらに、有限の純粋埋め込み立方複体上の混合分布へと拡張し、KL情報量の同時凸性を用いて近似誤差の明示的な上界を与えている。
説明NVIDIA Vera のマイクロアーキテクチャ比較：Grace、Turin、Granite Rapids との対比
要約本論文は、NVIDIA のデータセンター向け CPU「Vera」を AMD Turin および Intel Granite Rapids と比較し、NVIDIA Grace を基準としています。マイクロベンチマーク、NAS カーネルおよびミニアプリ、さまざまな科学計算コードのシングルソケット性能まで段階的に評価しています。その結果、試験したほとんどのコードで Vera が最高性能を示し、その要因は高いメモリ帯域幅、効果的な空間マルチスレッディング、低遅延のメモリサブシステムにあるとしています。一方、一部の演算負荷が大きいワークロードでは浮点性能が Intel と AMD に劣るとしています。
説明指定されたブール融合規則下の分散検出における、規則に敏感なセンサー参加
要約本論文は、融合ノードが指定されたブール判定規則を実装しなければならない場合の分散二値検出を扱う。条件付き独立なベルヌーイ観測のもとで、任意のブール規則に成り立つ符号付き影響経路恒等式を導出し、単調な規則では座標影響によるRusso-Margulis表現に帰着することを示す。これにより、目標ベイズ誤差に対する規則に敏感な必要条件と、影響で重み付けしたKullback-Leibler実現可能性界が得られる。さらに、必要な参加センサー数の下界を導き、数値およびモンテカルロ実験で、指定融合規則を保持した場合に尤度比融合と比べて生じうる性能低下を示す。
説明位置多様性型車載クラウドセンシングのための、カバレッジを考慮した経路推薦と近似均衡保証
要約一般車両のセンサーで都市を監視する車載クラウドセンシングで、交通が少数の道路に集中し多くの路網が未センシングになる問題を扱う。著者は二段階の手法を提案する。まず多様性加重報酬を持つ非協力ゲームで各車両の均衡迂回量を求め、次に迂回量が許容差内にあり、カバレッジを改善する実行可能な経路を各車両に推薦する。ロンドンとモナコの路網での実験では、小規模事例で最適なカバレッジ罰則削減量の約99%を達成したと報告されている。
説明入力サブサンプリングによる最悪ケースを超えたオンラインアルゴリズム
要約本論文は、オンラインアルゴリズムと離散最適解を同一のサブサンプリング入力で評価したとき、古典的な競合比が入力サブサンプリング後も保たれるかを検討する。対象はプロフェット不等式とスキーレンタルという代表的問題である。単一のサンプリング率では古典的な最悪ケースの比は変わらないが、同じ敵対的入力が二つの異なるサンプリング率で同時に最悪ケースであり続けるかが問われる。結果として、一方の率で最悪となる事例が、両方の率で同様に困難であるとは限らないことが示されている。
説明5G LDPC符号向けの全ノード並列アーキテクチャにおける有限アルファベット・メッセージパッシング復号の最適化
要約本論文は、最小再構成・計算・量子化（min-RCQ）LDPC復号アルゴリズムのルックアップテーブル（LUT）を設計する新しい手法を提案します。ベイズ最適化を用い、設計空間の部分空間からサンプリングします。損失関数にはフレーム誤り率（FER）を用います。パンクチャリングとショートニングを施した非正則LDPC符号に適用でき、全反復で使える反復非依存のLUTを生成するため、全ノード並列復号器アーキテクチャに適しています。提案手法は、先進の正規化最小和（NMS）復号器と比べ、誤り訂正性能を損なわずにエネルギー効率を38.6%向上させると報告されています。
説明二値m系列の次数不一致に関する経験的平方根則
要約周期が2^k−1の原始的二値線形帰還シフトレジスタ（LFSR）系列について、長さrの窓における全開始オフセットにわたる全変動次数不一致の範囲を調べた論文です。k≤28のデータは最大値がΘ(√N)（N=2^k）の尺度を示し、その平方根則を予想しています。表の最大値は離散格子上の下界にすぎないことも述べられています。
説明ハイパーグラフの極大b-マッチングを求める並列貪欲アルゴリズム
要約本論文は、ハイパーグラフの極大b-マッチングを求める並列バッチ投票アルゴリズムを提案する。辺の順序が与えられれば決定的に動作し、逐次的な貪欲法と同じ出力を得る。ランダムな優先順位の下での期待作業量と深さの解析も示し、CUDAで実装して実世界のハイパーグラフ上で評価した。容量b=5の場合、既存の貪欲法より最大19.07倍高速である。
説明黄金比：加法的財の EF1 と序数 MMS 配分
要約本論文は、財を複数のエージェントに分配する公平配分問題を扱う。加法的評価については、EF1（任意の一財を除けば妬みがない）と、1-out-of-⌊φn⌋ の序数的最大最小配分（MMS）保証を同時に満たす完全配分が必ず存在することを示す。ここで φ は黄金比である。各エージェントが財ごとに二つの非負値を持つ双値評価については、EFX と 1-out-of-⌈(7n-1)/6⌉ の MMS 保証を同時に満たす完全配分を得ている。
注目点EF1に加えて序数MMS保証を同時に満たす割当を構成し、既知の1-out-of-(2n-1)を黄金比の界へ改善する。作者は双値の場合のEFX結果も示す。