分散計算、ゲーム理論、情報理論など。
説明整列ドリフト下の分子通信における正確なキャップ応答と開口選択
要約本論文は、指定されたキャップ内の吸収事象のみを数える全吸収型球状受信機を対象に、方向性のある分子輸送下での空間受信を検討している。整列ドリフト下の結合初到達則を用いて、キャップのインパルス、累積、最終的な応答を厳密に導出し、粒子シミュレーションと時間刻み比較で検証している。記号長0.15秒の条件では、信号干渉差（SID）を最大化する開口角がドリフト大きさ0から40 μm/sの間で29.13°から61.86°へ増加することが示されている。
説明ブール確率におけるエントロピー不等式と極限定理
要約本論文は、ブール・エントロピーとブール・フィッシャー情報を研究し、部分和の任意の分数分割に関連するブール・フィッシャー情報の分数型スタム不等式を証明しています。また、ブール独立確率変数の和に対するエントロピー冪不等式とその重み付き版を導いています。さらに、ブール中心極限定理に沿ったバロン型のエントロピー収束結果を示し、コーシー変換のネヴァンリンナ表現に基づいて議論を進めています。
説明情報理論と形式検証の整合：レート歪み理論の Lean による形式化
要約本論文は、有損圧縮や機械学習解析の中核的な枠組みであるレート歪み理論の主要部分を、証明支援系 Lean で初めて形式化したものです。これまで形式化された情報理論の定理は、ほぼシャノンの無損失符号化定理に限られていました。歪み尺度、典型性、達成可能性などの定義を証明支援系に移す際の整合上の課題を扱い、教科書の慣例に忠実な再利用可能な定義と補題のライブラリを構築しています。
説明二値巡回勾配符号化：厳密な復元と圧縮への頑健性
要約本論文は、n 台のワーカーと最大 s 台のストラグラーに対応する厳密な勾配符号化方式、二値巡回勾配符号化（BCGC）を提案している。符号化行列は二値で、復号はひとつの総和で行われる。二値符号化は圧縮を伴う場合、粗い分割上の非符号化圧縮方式と等価であることが示され、実験では MDS 符号が発散する一方で安定することが確認された。四つのデータセットで理論が検証されている。
説明無向ネットワーク符号化と高速な外部メモリ整数ソート
要約本論文は、無向ネットワークにおいてネットワーク符号化と分数ルーティングで達成できるレート組み合わせが異なりうることを示す有限の反例を与え、多重ユニキャスト予想に反することを述べています。その線形構造を利用して、決定的な外部メモリ整数ソートアルゴリズムを提案し、一部のパラメータ範囲では比較ソートの入出力界より漸近的に小さいことを示しています。アルゴリズムの正しさとI/O計算量の上界はLeanで形式的に検証されています。
注目点多元化ネットワーク符号化と分数ルーティングの非等価性の有限反例を示し、その線形構造で外部記憶整数ソートのI/O上界を改善、比較ソートの古典的下界を破る。
説明攻撃者タイプの集合が未知かつ有界な Stackelberg セキュリティゲームにおける後悔なし学習
要約本論文は、繰り返し Stackelberg セキュリティゲームにおける防御側の後悔なし学習を扱う。従来の結果は攻撃者タイプの集合を防御側が事前に知っていると仮定していたが、本論文ではこの仮定を外し、タイプ数の上界 K_max のみが与えられる場合を扱う。各攻撃者のタイプを観測できれば後悔は Õ(nK_max√T) となる。攻撃された標的しか観測できず、タイプが無限の集合から来る場合は、いかなるアルゴリズムも後悔が T−2 以上になる。一方、B ラウンドごとにそれまでに現れたタイプを知らされれば、後悔は Õ(nK_max^{4/3}T^{2/3}+K_max B) で次線形になる。
注目点攻撃者タイプ集合が未知の場合の後悔学習を完全に特徴づけ、完全情報では√T率、部分情報では不可能性と遅延付きアルゴリズム、さらに遅延コストの不可避性を示す。
説明TrimSO(2)：等変原子間ポテンシャルを高速かつ省メモリで学習する手法
要約本論文は、SO(2)畳み込みに基づく等変原子間ポテンシャルモデルの学習手法TrimSO(2)を提案する。回転変換をモデルの既存のデータフローに組み込み、大きな中間テンソルの生成を避けることで、メモリ使用量とデータ移動を削減する。A100およびH100 GPU上で、PyTorch実装と比べて学習速度が2.07～2.94倍、ピーク学習メモリが1.53～3.16倍改善したと報告している。
説明モーメント配置の実数リフトによる非線形固定距離符号
要約本論文は、長さnで最小ハミング距離dを持つ符号の最大サイズを扱い、固定された記号数q≥2とd≥4について、log_q nの項に低次の項を加えた冗余度の上界をもつ非線形符号を構成している。d=4とd=5では対数項の係数がハミング界と一致し、d=4では線形符号より優れることが示されている。
注目点実数リフトを用いた非線形等距離符号で、d=4,5では冗長度の係数がハミング界と一致し、線形符号より優れることを厳密に示しており、影響は主に符号理論の理論分野に限られる。
説明Accord：Solana向けの組み合わせ可能なシェリング・ポイント仲裁プリミティブ
要約本論文はSolana上の仲裁オラクルAccordを紹介します。任意のSolanaプログラムが用途別の法廷（subaccord）を作成し、紛争を提起できます。専門化されたステーク加重型陪審員プールからランダムに陪審団が選ばれ、暗号化された証拠を確認し、コミット・リビール方式で投票します。最終判決と一致した陪審員は報酬を得て、不一致の陪審員はステークを没収されます。EVM上のKlerosとの違いや、Solana固有の実装上の詳細も議論されています。
説明最適なオンライン確率的マッチング：到着法則既知の場合の最適競争比
要約本論文は、到着法則が既知の場合の重みなしオンライン確率的マッチング問題を扱い、その最適競争比を確定しています。ポアソン到着では1-e/e^e（約0.8206）を達成し、Chierichettiらの上界（ICALP 2025）と一致します。n個の独立同分布到着では、加法的O(n^{-1/2})の誤差を除いて同じ保証が得られます。さらに、到着法則が未知の場合の最適競争比は1-e/e^eより厳密に小さいことを示しています。
注目点ポアソン型マッチングと指数スケジューリングの厳密な対応により、既知の到着分布下でのオンライン確率マッチングの最適競争比を与え、厳密な証明で子分野に影響する。
説明コンテキストの代償：大規模言語モデルの入力トークンのエネルギー消費分析
要約本論文はNVIDIA A100上でLlama-3.1とQwen-2を高解像度で計測し、長文脈や検索拡張生成における入力トークン（プリフィル段階）のエネルギー消費を調べています。PagedAttentionなどのメモリ最適化は、注意機構の拡張ボトルネックを遅らせ、112,000トークンで標準的な基準より最大8.9倍のエネルギー効率を示しました。また、入力と出力トークンのエネルギー差や、文脈拡大に伴う傾向も比較しています。
説明無雑音フィードバック付き状態依存通信路における同時識別・伝送・センシング
要約本論文は、無雑音フィードバックを持つ離散無記憶状態依存通信路を対象とし、送信側がランダム化符号化により、メッセージ伝送、識別、通信路状態のセンシングを同時に行う方式を扱う。平均歪み制約の下で未知の状態系列を推定する設定である。随機化された識別・伝送・センシングの容量・歪み領域について単一文字による特徴づけを与えている。伝送速度は相互情報量、識別速度は出力エントロピーで決まり、いずれもセンシングに由来する入力分布の制約を受ける。
説明平均電力制約下の光干渉チャネルの容量上限
要約本論文は、カー非線形性と波長分散の影響を受ける波長分割多重光リンクの多元干渉チャネルを扱い、従来のピーク電力制約を実際により近い平均入力電力制約に置き換えて分析しています。高SNR領域では単一ユーザの容量上限を閉形式で導出し、特定の条件下では有限SNRでの極値性も示しています。さらに時分割により達成可能領域を構成し、非線形シュレディンガー方程式の数値シミュレーションで実用的な送信電力でも結論が成り立つことを確認しています。
説明二部グラフの動的3彩色と最適な局所性
要約本論文は、辺の挿入に対して二部グラフの3彩色を維持する動的グラフアルゴリズムを示します。挿入された辺の周囲半径 O(log n) の範囲内でのみ彩色が変化します。分散グラフアルゴリズムの局所性理論において、動的 LOCAL モデルでの局所性の上界を与えます。Chang らの研究（PODC 2024）により、より強力なオンライン LOCAL モデルで Ω(log n) の対応する下界が存在することが示されており、この問題における動的局所性とオンライン局所性の差を埋める結果です。
説明定数アルファベット上の部分空間設計符号を効率よく構成する研究
要約部分空間設計符号は符号理論の中核的な枠組みで、Goyalらは定数サイズのアルファベットで初めて明示的な構成を与えました。本論文は、アルファベットサイズが r に対して指数的に増える、定数アルファベット上の r 次元部分空間設計符号の明示的構成を提案します。符号化は符号長に対して二次、次元 r に対して線形の体演算数で実行できます。さらに多重度符号を代数幾何符号へ一般化し、最適なパラメータを持つことを示しています。
注目点修正した代数幾何符号により定数アルファベット上の部分空間設計符号を構成し、アルファベットを二重指数から指数的に改善、符号化も効率的で理論的改善が明確。
説明二層半順序ゲームはPSPACE完全問題であることの証明
要約半順序ゲームはNimやChompなどの古典的ゲームを含む組合せゲームの基本的な一類です。高さが3以下の半順序ゲームの勝敗判定はPSPACE完全であることが知られていましたが、高さが2以下の二層半順序ゲームの正確な計算量は10年以上未解決のままでした。本論文は、正のCNF論理式上のAvoid True問題からの多項式時間帰着により、二層半順序ゲームがPSPACE完全であることを示しています。
注目点高さ2以下の半順序ゲームの計算量という十年来の未解決問題を、Avoid Trueからの多項式時間帰着によるPSPACE完全性証明で解決している。
説明ダーティ集合はどう動くか：増分スパース行列乗算におけるスケジュール再利用の特性分析
要約行列は固定されたまま毎ステップ少数の入力行だけが変化する（ダーティ集合）場合に、増分スパース行列乗算で分割（タイル）スケジュールを保持して再利用することが有利かどうかを検討した論文です。21のSuiteSparse行列と制御された変化パターンで、直接的な列単位の増分更新は八つの全再計算手法中の最速より2.1〜8.2倍速いと報告しています。837の作業負荷のうち779では、タイル準備を保持しスケジュールをキャッシュする方式より直接更新が優れていました。有利性を決めるのはスケジュールの洗練度ではなく、行列の構造とダーティ集合の移動だと結論づけています。
説明学んだことから得られる利益：情報価値の特徴づけと計算複雑性
要約本論文は、拡張形式の意思決定問題における情報価値、すなわちあらゆる利得環境において情報の精緻化から決定者が得られる最大の乗法的利得を研究する。任意の情報精緻化の下での情報価値について統一的な特徴づけを与え、ある衝突グラフ族の最大分数色数との関係を示す。さらに、完全情報の価値はNP完全、想起の価値はS2P完全であることを示している。
注目点情報価値の統一的特徴付けを分数色数と結びつけ、完全情報価値のNP完全性と想起価値のS2P完全性を示し、理論的に大きな進展があるが影響は理論分野に限られる。
説明ε プライバシー下におけるグラフ型ストレージ向けの弱い秘密情報検索
要約本論文は、サーバーをグラフの頂点、各ファイルを保存する二台のサーバーを結ぶ辺として表す、グラフベースの複製ストレージ系における弱い秘密情報検索（G-WPIR）を扱います。ε プライバシー指標の下で、任意のグラフに対応する既存の G-WPIR 方式を改良し、その性能を分析しています。また、任意のグラフにおける期待ダウンロードコストの下界を示し、そこから完全グラフの速度上界を導いています。さらに、完全グラフと完全二部グラフの二種類について、達成可能な速度とプライバシーのトレードオフを示しています。
説明循環置換行列とアフィン置換行列による高周長量子LDPC符号の構成
要約本論文は、検査重みが6の二元CSS量子低密度パリティ検査（QLDPC）符号を、二つの明示的な構成法で検討している。第一の構成は固定の循環シフトパターンを用い、N=31およびN≥37のすべてについて、Tanner グラフの周長12のパラメータ[[6N,2N+2,6]]を与える。第二の構成は循環係数とアフィン置換係数を持つ固定行列多項式を用い、四つの実現例を示す。そのうちTanner グラフの周長は8で、距離は計算機により検証されている。
説明テンソルコンパイラ向けの並列スパース出力
要約スパーステンソルコンパイラは、複雑なスパースデータ構造上のテンソル演算を最適化するために使われますが、並列スパーステンソルコンパイラの研究はほとんどありません。本論文は、任意の標準スパース形式で全てのループ順序を並列に扱える初のテンソルコンパイラ「Birdseed」を提案し、fibertree形式のlist、bytemap、hash、dense各レベルへ直接書き込めるとしています。メモリと時間について従来研究を漸近的に上回り、ヒストグラム構築やSpMSpVなどの並列化が難しいカーネルで実測の高速化を示したと述べています。
説明ノイズ付きちぎり紙チャネルとノイズ付きシャッフルチャネルの容量
要約本論文は、符号語を断片に分割して元の順序を失わせて返すちぎり紙チャネルを扱います。ノイズ付きの場合は、各断片にビット置換誤りも加わります。著者らはノイズ付きちぎり紙チャネルの容量上界を示し、これはRavi、Vahid、Shomonyが達成可能と示した速度と一致するため、彼らの予想を解決しています。また、全断片の長さが等しいノイズ付きシャッフルチャネルの容量も決定し、Shomonyとのheckelの未解決問題に答えています。
注目点ノイズ付き紙片化チャネルの容量上界を示し既知の達成可能レートと一致させ、公開予想を解決した理論的成果。
説明二種類の物品に対する最大最小シェア配分
要約本論文は、分割不可能な物品を、加法的な評価値（またはコスト）を持つ複数のエージェントに公平に配分する問題を、最大最小シェア（MMS）という公平性の基準で検討しています。エージェントが3人以上の場合、MMS配分は必ずしも存在しないため、正確なMMS配分が保証される特殊な事例を特定する研究が進められてきました。論文は、物品が二種類の嫌悪物（chores）に分けられる場合、MMS配分は常に存在し、ジョブスケジューリング研究に着想を得た新しい幾何学的手法により多項式時間で計算できることを示しています。さらに、この手法を二種類の財への拡張や、一種類の財と一種類の嫌悪物が混在する事例にどう適用できるかについても論じています。
注目点MMS配分の存在性という未解決問題に対し、二種類の物品で存在と多項式時間計算を示し、スケジューリング由来の幾何的手法を用いる。
説明離散フィッシャー情報量の研究
要約本論文はフィッシャー情報量の離散版を研究している。離散ラプラシアン演算子を用いて離散的なスコア関数を構成し、そこから情報量を定義する。この枠組みは、離散の設定で情報理論の不等式をいくつか示すための自然な土台を与える。
説明相互蒸留下のフェデレーテッドアンラーニングのための知識系譜追跡
要約本論文は、エッジサーバと周辺デバイスが相互蒸留によって異なるサイズの言語モデルを共同学習する場合のフェデレーテッドアンラーニングを扱う。従来の削除処理は一つのモデルにのみ作用するが、削除対象データの影響は複数の生徒モデルに複製され、アップロードを通じて修正済みの教師モデルへ戻ってしまう。著者らはHERD（Holder-level Erasure via Replication-weighted Delta-closure）を提案する。HERDはサーバが既に行う転送から知識系譜グラフを記録し、各保持者の残差の複製回数を計算して、削除要求後の累積残差を抑える最小コストの修正対象集合を選ぶ。TOFUデータセットでは、最強のベースラインに比べ修正コストは6%から12%でありながら、累積残差を18%から52%少なく抑えたと報告されている。
説明持続可能なドローン任務のための分散型エネルギー中継フレームワーク
要約本論文は、遠隔地の原野、山岳地帯、被災地など、インフラのない地域（ILR）におけるUAVの航続時間の制約に取り組んでいます。搬送用ドローンが協調してバッテリーを届ける分散型エネルギー中継フレームワークを提案し、中継・キャッシュによる輸送方式（TRC）を導入しています。各拠点は配送能力を評価して任務調整者に入札し、調整者は必要条件を満たし費用を最小化する配送連合を選びます。解析評価により、電池特性とドローン性能がエネルギー投射に与える影響と、フレームワークの有効性が示されています。
説明最適な台集合サイズ検定
要約本論文は、未知の確率分布が n 個の要素の上に台を持つのか、全変動距離で ε 以上離れているのかを判定する、最適な台集合サイズ（support size）検定器を提示している。そのサンプル複雑度は Θ(n/(ε log n)) であり、Ferreira Pinto Jr. と Harms（STOC 2025）による従来の最良結果 O(n/(ε log n) · log(min{1/ε, n})) を改善している。さらに台集合サイズに対する比較的良い下界も与えている。
注目点台集合サイズ検定の標本複雑度を改善し、先行結果の対数因子を除去して最適境界と厳密な下界を与えている。
説明Han型およびShearer型情報不等式：等号条件と組合せ論への応用
要約Madimanと Tetaliは、Han不等式やShearerの補題といった古典的なエントロピー部分集合不等式を包含する、強い形と弱い形の分数不等式を確立した。本論文では、強い分数不等式における差の分解を導き、それを用いてHan不等式の強い形で等号が成立するための必要十分条件を示す。さらに、極値グラフ理論の問題に弱い分数不等式を適用し、Han不等式に依拠するSason（2022）およびBoucheronら（2013）の結果を再現し拡張している。
説明積制約付き2次元min-max最適化のCLS困難性
要約本論文は、一次元のmin・max プレイヤーと積制約を持つmin-max最適化問題において、近似一次Nash均衡を計算する複雑さを研究している。目的関数へのブラックボックスアクセスの場合、ε一次Nash点を見つけるには任意のアルゴリズムが Ω(1/√ε) 回のクエリを必要とすることを証明している。ホワイトボックス設定では、End-of-Potential-Line からの帰着によりCLS困難性を示し、最も単純な一次元の場合でもCLSと少なくとも同程度に困難であることを示している。
注目点低次元の min-max 問題の一次ナッシュ均衡に対し、CLS困難性とクエリ下界を示し、新規性が高い。証明は帰着と下界論証による。
説明選択されたビットのソロモノフ帰納とオンライン分類
要約本論文は、アルゴリズム情報理論の基礎となるソロモノフ帰納（系列予測の一般的手法）を、計算可能なパターンで固定されたビットの予測誤差について検討している。あるパターンでは位置ごとの誤差の総和が有界でないが、誤差の二乗和はパターンのプログラム長に対して指数的に有界であることを示す。計算可能な分類関数で固定されたビットでは、誤差の二乗和はプログラム長の多項式で抑えられ、より速く収束する。
説明RIS対応全二重通信とユーザー中継のためのレート分割多元接続
要約本論文は、再構成可能インテリジェントサーフェス（RIS）とユーザー中継で支援される協調型レート分割多元接続（C-RSMA）伝送フレームワークを検討している。送信電力制約の下で共通レートと個別レートを最大化するため、基地局の送信ビームフォーマとRISの反射ビームフォーマを同時に最適化する。変数が結合し強い残留自己干渉を含むため問題は困難でNP困難とされ、そこで低複雑度の交互最適化手法を提案している。シミュレーションでは、提案手法がRIS支援のSDMA、半二重RSMA、RISを用いないSDMA方式よりも優れた和レート性能を示すとされている。
説明Orrery：SimGrid による GPU ダイレクト MPI 通信のモデリングとシミュレーション
要約本論文は、GPU 対応 MPI 通信をモデル化するために SimGrid の SMPI 上に構築された中間層 Orrery を提案しています。GPU メモリ割り当て、カーネル起動、データ転送、MPI 操作を傍受し、対象システムの仕様に基づいて SimGrid 内で実行をモデル化するため、物理的な GPU がなくてもシミュレーションできます。MUSICA スーパーコンピュータの最大 32 ノードで、CUDA 対応 MPI のマイクロベンチマークと Jacobi ソルバを用いて検証し、主要な GPU 対応 MPI の仕組みを再現できることを示しています。
説明LLM推論におけるサイレントデータ破損検出のためのコーシー・シュワルツ・ノルム境界の再検討
要約大規模言語モデルの推論では多数の浮動小数点演算が行われ、ハードウェア故障によりサイレントデータ破損（SDC）が生じることがあります。本論文は、低オーバーヘッドの代替手法としてコーシー・シュワルツ・ノルム境界（CSNB）を再検討し、現在の主流であるABFTと比較しています。稠密LLMの線形層では、CSNBはABFTの故障検出能力の99%を保持しつつ、検証オーバーヘッドを87%、閾値決定オーバーヘッドを67%削減しました。一方、MoEルーターのゲート計算では保持率は55%にとどまり、チェックサムによる検証が依然として適しているとしています。
説明Tremulant：サーバーレス基盤における99パーセンタイルを超えた遅延
要約本論文は、7つのFaaS（Function-as-a-Service）基盤で得られた数百万件のリクエストのデータを分析しました。ウォームスタートの中で最も遅いものは中央値の数百倍に達する一方、基準として使った仮想マシンははるかに安定していました。作者は2020年から2025年にわたる4つの独立した公開データセットでも同じ傾向を確認しています。最も極端な遅延では、コールドスタートだけでなくウォームスタートの割合も再び増えるため、コールドスタートの緩和だけでは解消できないと述べています。
