その他の計算機科学

分散計算、ゲーム理論、情報理論など。

今週の注目論文

星の付け方
  1. ★★★★★arXiv
    明示的なリード・ソロモン部分空間設計:最適なリストおよび線形復号
    注目点明示的なReed-Solomon符号の近最適リスト復号と部分空間設計の構成を与え、リストサイズを定数に抑え、厳密な証明を示す。
  2. ★★★★★arXiv
    Langberg-Médard予想の証明:ネットワーク符号化と分数ルーティングの能力に関する結論
    注目点多重ユニキャストにおける符号化と分数ルーティングの境界に関する長年の未解決予想を、完全な証明と割容量の必要十分条件で解決し、理論的影響が大きい。
  3. ★★★★★arXiv
    近接配置の点源位置推定におけるフィッシャー情報と最小平均二乗誤差
    注目点近接する点源定位について、分離と雑音に同時に依存する一致するベイズリスク上下界を証明し、奇数・偶数の源数で異なる領域を示した。影響は主に信号処理の一分野に限られる。
  4. ★★★★★arXiv
    予測付きのパレート最適スケジューリング
    注目点決定論的アルゴリズムにおける一貫性と頑健性の最適トレードオフを厳密に特定し、上下界を一致させ、従来のΘ(1/ε)を大幅に改善する完全な証明を与えている。
  5. ★★★★★arXiv
    ベクトルチャネル上のバイスタティックISACの基本限界
    注目点ベクトル通信路上のバイスタティックISACについて容量-歪み関数を単一文字で厳密に特徴づけ、フィッシャー情報行列の不等式でガウス重畳符号化の最適性を示した。
  6. ★★★★★arXiv
    学習が均衡をどのように選択し、いつ共謀につながるか
    注目点確率的安定性によって均衡選択を特徴づけ、反復クールノー博弈で学習動学が近似的共謀を必然的に生むことを示し、アルゴリズム共謀研究に影響する。
  7. ★★★★★arXiv
    Hylland-Zeckhauser モデルの計算可能性の境界を探る
    注目点未解決問題を解決し、効用値3種で既にPPAD困難であることを示し、可解と困難の境界を明確化する厳密な証明を与えた。
  8. ★★★★★arXiv
    線形ハッシュはポアソン分布に近い:ランダムF2線形写像下のビン負荷の挙動
    注目点ランダム線形写像の負荷分布がポアソン分布に支配されることを示し、最大負荷の差を3/2+o(1)に抑える厳密な理論的改良である。
  9. ★★★★★arXiv
    格タイリングにおけるGolomb–Welch予想の証明
    注目点長年未解決だったGolomb-Welch予想を完全な証明で解決し、格子Lee球充填の存在条件を完全に確定した点で分野への影響が大きい。
  10. ★★★★★arXiv
    Langberg-Médard 多重ユニキャスト予想の証明
    注目点Langberg と Médard が提唱した多重ユニキャスト予想を証明し、未解決問題を解決した。証明は厳密で、ネットワーク符号化と多重流理論への影響が大きい。

星は AI がタイトルと要旨から付けた大まかな評価です。新規性・根拠の強さ・影響範囲を採点し、1〜5 の星に換算しています(5 つ星は約 2%、4 つ星は約 10%)。サイトでは 4〜5 つ星の論文だけを「注目」として示し、注目点を一言添えています。印がないことは論文の質が低いことを意味しません。全文は読んでいないため、論文を選ぶ際の目安であり、質の評価として確定したものではありません。「コードあり」は要旨にコード・データ・ツールの公開が明記されていることを示します。

2026年10月28日(水)

arXiv cs.DC

Request-Adaptive Execution for Efficient Hybrid LLM Inference

説明要求ごとに実行を切り替える、効率的なハイブリッドLLM推論の方式

要約本論文は、モデル構造と実行環境を共同設計し、リクエストごとに推論の構成を適応させるMorphシステムを提案する。各ブロックにAttention層とSSM層を配置し、プリフィル段階のゲーティングで、デコード中は固定されるリクエスト固有の層構成を選ぶ。6つのデータセットでの実験では、既存の静的なハイブリッド基準手法より品質と効率のバランスが良いと示されている。また、システム評価ではスループットが最大3.87倍向上し、推論レイテンシも大幅に低減したとされる。

Fahao Chen, Xuzhe Yan, Qi Zhang ほか

arXiv cs.IT · cs.SY · eess.SY

Privacy-Preserving Over-the-Air Federated Learning over Cell-Free Massive MIMO System with User-Centric Clustering

説明ユーザー中心クラスタリングを用いたセルフリー大規模MIMOにおける、プライバシー保護型エアオーバーザエア連合学習

要約本論文は、セルフリー大規模MIMOネットワーク上で、空中波集約(OTA)により差分プライバシー付き連合学習を行うクロスレイヤー設計を検討しています。無線受信に伴う熱雑音をプライバシー保護に活用して人工雑音を減らし、アクセスポイントとユーザーの対応付け、送信電力、人工雑音分散を同時に最適化して集約分散を抑えます。数値実験では、従来の基準方式と比べて集約分散が最大89%低く、MNISTで97%のテスト精度を達成し、CIFAR-10でも一貫した改善が示されています。

Manobendu Sarker, Soumaya Cherkaoui

arXiv cs.IT · math.IT

The Capacity of Private Information Retrieval from Coded Storage Systems with Colluding, Robust and Byzantine Servers

説明合謀・頑健・ビザンチン型サーバーを含む符号化ストレージにおける私的情報検索の容量

要約本論文は、T 台の合謀サーバー、U 台の頑健サーバー、B 台のビザンチンサーバーを含む MDS 符号化データベースからの私的情報検索(U-B-MDS-TPIR)を扱う。線形かつ満支持ランクの方式について容量の式を示し、K=1 または T=1 の場合には線形性と満支持ランクの制約がなくても同じ式が容量を与えると述べている。さらに、M 個のファイルから P 個を検索する場合へ構成を拡張し、P≥M/2 かつ K=1 または T=1 のとき、その多ファイル方式が容量を達成するとしている。

Rui Sun, Yiwei Zhang

arXiv cs.CG · cs.IT · math.CO

Code uniqueness of 4-cell connected disjoint clusters in spatial chromatic model

説明空間色彩モデルにおける4セル連結非交差クラスタの符号一意性

要約本論文は、実体指向の空間データモデルである空間色彩モデル(SCM)における符号の問題を扱う。SCMでは各部分空間(セル)が色彩符号を持つ。先行研究で2セルおよび3セルの連結非交差クラスタの符号一意性が示されたことを踏まえ、本論文は4セルの連結非交差クラスタの色彩符号が一意であることを証明している。

Weining Zhu

2026年10月27日(火)

arXiv cs.DC

TAO: Tool-Aware Joint Scheduling for LLM-Based Agentic Serving

説明TAO:LLMベースのエージェントサービス向けツール認識型共同スケジューリング

要約本論文は、LLMベースのエージェントサービスのためのツール認識型共同スケジューリングフレームワーク「TAO」を提案しています。ツールの戻り準備状況、時間減衰を伴うノード固有のキャッシュ価値、トークン占有量を組み合わせ、容量制約の下で動的計画法により待機中のセッションを選択・配置します。報告された12のモデル・ワークロード・並列度の設定において、各指標で最良の評価済みベースラインと比べ、遅延は最大26.8%、平均初トークン時間(TTFT)は最大36.3%削減され、デコードスループットは最大29.5%向上しました。

Shuhuai Li, Shengdong Ye, Dongdong Ge ほか

★★★★☆ 注目
arXiv cs.DC

PipeLink: Contract-Guided Linking of GPU Kernel Components

説明PipeLink:契約に基づくGPUカーネルコンポーネントのリンク手法

要約本論文は、GPUカーネルコンポーネントを契約に基づいてリンクするツールPipeLinkを提案する。各コンポーネントは要求と提供を記述した契約を持つLTOオブジェクトとして個別にコンパイルされ、PipeLinkが契約を照合し、SMの資源配置を一括で求めてコンポーネント間の転送を生成する。HopperおよびBlackwell GPU上の51構成で、一体としてコンパイルした場合との差は0.2%以内であった。

注目点契約に基づくGPUカーネル部品リンカを提案し、部品の独立したコンパイル・置換の課題に取り組む。51構成で単一ユニットとの差が0.2%以内、複数の実用的合成で高速化を実証。

Jize Guo, Xupeng Miao

arXiv eess.SP · cs.IT · math.IT

Negative Results for Reciprocity-Based Over-the-Air Split Learning Under Channel Aging: Stability, Alignment, and Geometry

説明チャネルエイジング下における互恵性ベースの空中分割学習の否定的結果:安定性、整列、幾何学

要約本論文は、チャネルエイジングによって送信機へ戻される微分信号が回転・減衰する、互恵性ベースの空中分割学習を検討しています。7つのケーススタディで数値予測、メカニズム検証、競合する予測を組み合わせて分析し、多くの学習精度の予測は支持されなかったものの、一部の局所的な物理関係は成り立つことを示しています。

Tianhao Guo, Xianzhong Li, Hao Luo

arXiv cs.IT · eess.SP · math.IT

Deep Holes and Aperture: Sign Laws for the Empirical Correlation of Lattice-Sampled Random Wave Fields

説明深い穴と開口:格子サンプリングされたランダム波場の経験相関に関する符号則(格子上でサンプリングしたランダム波の経験相関の符号規則に関する論文)

要約本論文は、有界な開口内で格子上にサンプリングしたガウス型ランダム波場について、再インデックス後の残差がVoronoi胞内で経験的ラグ相関の実部を正に保つかを検討する。正方格子、六角格子、単純立方格子、体心立方格子の符号クラス数を示し、失敗確率の漸近的および非漸近的な開口則を導出する。レイリーフェージングの鏡面経路がある場合の失敗の下限が生じる条件も扱う。

Tianhao Guo, Hao Luo, Xianzhong Li ほか

arXiv math.AC · cs.IT · math.AG

Counting the Fixed Points of Binary Belief Propagation: Generic Degree, Syzygies, and Real Solutions

説明二値信念伝播の不動点の個数の計算:一般次数、シジジー、実数解

要約本論文は、二値対ごとモデル上の信念伝播(belief propagation)の不動点の個数を研究する。複素パラメータの下で、有限な無ループ多重グラフから得られる代数族の一般次数を決定し、次数1の頂点を含まない辺集合上の和として与える。その二つの幾何学的実現を示し、強磁場の下で実不動点の下界を分析して、辺接続環の最小加群生成元の個数との関係を明らかにする。関連する結果は Lean 4 で形式化されている。

Yusuke Watanabe

arXiv cs.IT · eess.SP · math.IT

Digital Twin-Guided Wireless Localization via Probabilistic Inverse Learning

説明デジタルツインと確率的逆学習に基づく無線測位手法

要約本論文は、サイト固有のデジタルツイン(DT)を、簡易な分散インフラで無線測位に活用する方法を検討しています。単一アンテナのアクセスポイントを用いる確率的手法PRISMを提案し、測位を確率的逆問題として定式化します。多ノードのチャネルインパルス応答から学習した提案分布で候補位置を生成し、DTとの整合性で候補を重み付けして推定を洗練します。10台の単一アンテナAPを用いた場合、中央値誤差は約0.7mで、再学習なしでもDT特徴が劣化した状況で有効性を保ちます。

Mahmoud Saad Abouamer, Henrik C. M. Frederiksen, Robin J. Williams ほか

arXiv cs.DC · cs.DB

Taming Multi-Dimensional Skew in Sparse Matrix Multiplication with Contention-Aware Scheduling [Technical Report]

説明稀疏行列積における多次元の偏りを、競合を考慮したスケジューリングで抑える(技術報告)

要約本論文は、データの偏りによって稀疏行列積(SpGEMM)の性能が低下する問題を扱う。原因として、計算コスト・出力密度・データ局所性の間の多次元的な不均衡と、密な部分構造によるキャッシュ競合の二つを挙げる。著者らは、適応的morselスケジューリング(AMS)を提案し、競合を考慮した負荷分散、データを考慮した同時マルチスレッディング起動機構、morselごとに累積器を選ぶハイブリッド方式を組み合わせる。行列の二乗、関係クエリ、グラフ解析などの評価では、偏りのある負荷でAMSが既存手法を大きく上回り、偏りのない負荷では同等の性能を示したと報告している。

Wentao Huang, Qiming Huang, Yunhong Ji ほか

arXiv cs.IT · math.IT

Rethinking Channel Estimation for Fluid Antenna Systems: A Physics-Informed Operator Learning

説明流体アンテナシステムのチャネル推定の再考:物理情報付き演算子学習

要約本論文は、流体アンテナシステムのチャネル推定を、射影されたヘルムホルツモデルで制約された確率的逆場再構成問題として定式化します。電磁情報理論に基づくスペクトル漏れ解析により、この問題が周波数領域の逆デコンボリューションに帰着することを示しています。雑音が多く劣決定な無線環境向けのU字型フーリエニューラル演算子(UFNO)を提案し、物理を考慮したSobolev損失で学習させます。シミュレーションでは、既存のベンチマークより高精度で、高い空間・周波数分解能において反復解法より推論遅延が桁違いに小さいことが示されています。

Zixin Wang, Lizhong Zheng, Yuanming Shi ほか

arXiv cs.IT · eess.SP · math.IT

Sensitivity of RMS Delay Spread Estimation to Power Delay Profile Thresholding in Time-Varying Channels at 33 GHz

説明33 GHz時変チャネルにおけるRMS遅延拡がり推定の電力遅延プロファイル閾値への感度

要約本論文は、33 GHzのミリ波時変チャネルにおいて、RMS遅延拡がりの推定値が相対的な電力遅延プロファイル(PDP)の閾値によってどう変化するかを調べたものです。解析には、移動車両のある動的な道路環境で行った広帯域チャネルサウンディング測定データを用いています。閾値を-20 dBから-50 dBまで変えたところ、中央値は約140 nsから168 nsへ、90パーセンタイル値は200 nsから210 nsへ増加しました。両統計量は低い閾値で収束し、-40 dBが実用的な収束水準となることが示されています。

Jaros{\l}aw Wojtu\'n, Bartosz Czaja, Tomasz Grasza ほか

arXiv cs.GT · math.PR

When do token systems stabilize? Compatibility constraints and community structure

説明トークン系はいつ安定するか:互換性制約とコミュニティ構造

要約本論文は、エージェント間に互換性制約がある場合のトークンによるサービス交換システムを研究している。システムが安定するための必要十分条件を示し、利用可能な提供者のうち残高が最も少ない者を選ぶ最小トークン規則が最適な安定領域を達成することを証明している。さらに、この判定基準を確率ブロックモデルから生成したランダムなトークン系に適用し、安定を妨げる要因として、コミュニティ群または個々のエージェントのサービス機会の不足という二つを挙げている。

Flore Sentenac, Mingwei Yang, Sophie H. Yu

arXiv math.NT · cs.IT · math.IT

Finite Fields: Root Sets, Frobenius, and Algebraic Structure

説明有限体:根集合、フロベニウス写像、代数構造(専門書)

要約根集合、フロベニウス軌道、トレース双対性、巡回加群を通じて有限体の理論を展開する専門書である。多項式の構成と代数符号理論への応用を扱い、巡回符号、BCH 符号、ランク距離符号、トレース符号などを取り上げている。指標の直交性、ガウス和、ヤコビ和、およびWeil 界の証明にも触れ、体の構造・軌道構造・線形従属性を結びつける明示的な議論を重視している。

Hongfeng Wu, Li Zhu

arXiv econ.TH · cs.GT

Characterizing Maximum Nash Welfare: Envy-Freeness and Proportionality

説明最大ナッシュ厚生の特徴づけ:羨望のなさと比例性

要約分割不可能な財の配分問題において、最大ナッシュ厚生ルールを検討する。このルールは「1財までの羨望のなさ」を満たす唯一の厚生主義ルールであることが知られている。本論文は、この公平性条件を、任意の固定された整数kに対する「k財までの羨望のなさ」または「k財までの比例性」というより弱い要件に置き換えてもよいことを示す。この特徴づけは、同一の財を含む選好プロファイルに対しても成り立つ。

Karen Frilya Celine, Warut Suksompong, Nicholas Teh

arXiv cs.IT · math.IT

The Exact Weight Spectrum of RM(m-7,m): A Counterexample to the Carlet-Solé Conjecture

説明Reed-Muller符号RM(m-7,m)の厳密な重みスペクトル:Carlet-Solé予想の反例

要約この論文は、ブール関数とReed-Muller符号RM(m-7,m)の重みスペクトル、すなわち各重みがどの程度現れるかを研究している。著者はアフィン幾何学とフーリエ解析を組み合わせ、RM(7,14)について従来予想されていた八つの重みを除外し、その結論をm≥14のすべての場合に拡張した。これによりCarlet-Solé予想の反例を与えている。

Yueying Lou, Qichun Wang

arXiv cs.IT · math.IT

Design of DoF-Robust MIMO via Generalized Pinching Antennas

説明一般化ピンチングアンテナによるDoF頑健なMIMO設計

要約本論文は、ユーザーと基地局の距離のばらつきによりマルチユーザーのチャネル行列がランク落ちし、空間自由度(DoF)が失われる問題を扱っている。ピンチングアンテナをユーザーの近くに配置することで、マルチユーザーのチャネルGram行列を条件の良いほぼ対角構造にできることを示している。ランク落ち確率と不通確率により評価され、解析とシミュレーションの結果から、空間的に離れたユーザーへの接続を支えつつ空間自由度を維持できることが示されている。

Zhiguo Ding, Robert Schober, H. Vincent Poor

arXiv cs.DC · cs.OS · cs.PF

Agar: What-If Analysis for Microservice Applications

説明Agar:マイクロサービス・アプリケーションのWhat-if分析

要約本論文はマイクロサービス向けの反事実的性能分析ツール AGAR を提案する。各コンポーネントの正確な値を予測する代わりに、観測されたすべての振る舞いを含み、かつ端から端までの結論に役立つ程度に厳密な、単純で解釈しやすい境界を学習し、それらを組み合わせてSLO(サービスレベル目標)の実現可能性を問う。これにより自動スケーリングを、SLOを満たす最小のリソース割り当ては何か、という反事実的な問いとして定式化する。三つのマイクロサービス・アプリケーションでの評価では、導出された自動スケーラーは最先端の水平自動スケーラーに比べ、アプリケーションのSLOを満たしつつCPU割り当てを最大36.8%削減した。

Saarth Deshpande, Neeraja J. Yadwadkar, Venkat Arun

★★★★☆ 注目
arXiv cs.GT

Noise Shapes the Surplus: Strategic Play Against No-Regret Learners

説明ノイズがもたらす余剰利得:後悔なし学習者に対する戦略的プレイ

要約本論文は、ゼロ和ゲームにおいて、摂動された利得情報と減衰する学習率を用いる後悔なし学習者(FTRL型アルゴリズム)から、オプティマイザーがミニマックス基準を上回る累積利得(余剰)をどの程度得られるかを検討している。被択的な戦略では定数オーダーの余剰しか得られないこと、更新規則と平均応答を知る最適化者は平均応答が有利な場合にΩ(1/η_T)の余剰を得られること、平均応答が不利な場合でも交互の能動的プレイによりΩ(∑η_t)の余剰を得られることを示している。標準的な学習率では、平均ゼロで有限分散の摂動に対してΩ(√T)の速度が回復されるとしている。

注目点ノイズ下のFTRL学習者に対する新たな搾取機構を提案し、減衰学習率でも√Tオーダーの戦略的余剰を示す。理論的な前進は大きいが、適用範囲はゼロ和ゲームに限られる。

Yiheng Su, Emmanouil-Vasileios Vlatakis-Gkaragkounis

arXiv cs.GT

Optimality and Impossibility in Multidimensional Strategyproof Facility Location

説明多次元における戦略耐性のある施設配置の最適性と不可能性

要約本論文は、社会的費用(各エージェントから最寄りの施設までの距離の総和)の最小化を目的として、多次元ノルム空間における施設配置問題を検討する。ユークリッド平面における単一施設について、決定論的な戦略耐性(SP)メカニズムの最適近似比が、座標ごとの中央値(CM)で得られる比と一致することを示し、その最適性結果から匿名性の仮定を除いている。また、非ユークリッド空間ではCMが常に最適とは限らないことを示し、二つ以上の施設の場合については不可能性結果を提示している。

Jianan Lin

★★★★☆ 注目
arXiv cs.GT

Learning-Augmented Coordination Mechanisms

説明学習強化型調整メカニズム:需要予測を用いて渋滞ゲームの均衡効率を改善する研究

要約本論文は、利己的行動によって資源配分の効率が低下する問題を扱う。需要の予測(不正確な場合もある)を用いてコストを修正する学習強化型調整メカニズムを提案し、信頼度パラメータβによって予測が正確な場合は最適に近い性能を、最悪の場合でも良い均衡(PoS)を保証する。さらに、PoAロバスト性の上界や不可能性の結果も示している。

注目点混雑ゲームの協調機構に学習強化の考えを導入し、予測が正確な場合と最悪均衡の保証を両立させ、不可能性結果も示している。

George Christodoulou, Vasilis Christoforidis, Alkmini Sgouritsa ほか

arXiv cs.DC

JustGoal: With Only a Goal, the AI Baseline Is Above the Expert Kernels

説明JustGoal:目標だけで与えるAIベースラインが専門家によるGPUカーネルを上回る

要約本論文は、汎用エージェントに最適化目標と制約のみを与え、カーネル専用の知識ベースや事前定義されたワークフローを与えないベースライン手法JustGoalを提案している。NVIDIA B200 GPUでは、10個の演算子のうち8個でオープンソースライブラリを上回り、演算子ごとの幾何平均高速化率は1.14倍から2.34倍であった。比較可能な9個の演算子のうち5個では、公開されている最速の専用エージェントによるカーネルも上回った。著者らは、専用の仕組みは同じモデル・同じ範囲の目標専用ベースラインに対して明確な利点を示すべきであり、基盤モデルが変わるたびに再評価すべきだと結論づけている。

Yaojian Chen, Dazhi Peng, Zhui Zhu ほか

★★★★★ 注目
arXiv cs.IT · math.IT

On the Fundamental Limits of Bistatic ISAC Over Vector Channels

説明ベクトルチャネル上のバイスタティックISACの基本限界

要約本論文は、ベクトルチャネル上のバイスタティック統合センシング・通信(ISAC)システムの基本限界を研究している。まず並列チャネルのクラスについて、可達性と逆定理を示し、容量-歪み関数C(D)の単一文字による特徴づけを得ている。加法的ガウス状態を持つベクトルガウスチャネルについては、ガウス重畳符号化の最適性を証明し、容量-歪み-電力関数C(D,P)の厳密な特徴づけを導いている。

注目点ベクトル通信路上のバイスタティックISACについて容量-歪み関数を単一文字で厳密に特徴づけ、フィッシャー情報行列の不等式でガウス重畳符号化の最適性を示した。

Dongsheng Peng, Lei Yu, Ping Chen ほか

arXiv cs.IT · cond-mat.stat-mech · math.IT

Thermodynamic characterization of message-passing: Framework and initial study

説明メッセージパッシング復号器の熱力学的特徴づけ:枠組みと初期研究

要約本論文は、ミスマッチコスト枠組みを用いてメッセージパッシング復号器の熱力学的効率を研究する。この枠組みは、回復不能なエネルギー損失の計算可能な下限を与える。二元消失通路上で伝送された[7,4]ハミング符号を例に、チャネルが誘導する初期化統計と復号中のアルゴリズム状態分布の段階的な変化が、総ミスマッチコストをどのように決めるかを示す。復号動態、入力統計、ハードウェア特性が共同で熱力学的コストを決定し、省エネルギーな復号器設計への道筋を示す。

Kalana G. Abeywardena, Stark C. Draper

arXiv cs.DC

INC-MoE: Overlapping In-Network Collectives and Expert Computation for Expert-Parallel Mixture-of-Experts Inference

説明INC-MoE:ネットワーク内集合通信と専門家計算を重ね合わせる専門家並列MoE推論手法

要約本論文は、専門家並列の混合専門家(MoE)層を提案し、トークンの配送と結果の集約という2つの通信処理をネットワークスイッチにオフロードし、それらの集合通信と専門家計算を互いに重ね合わせる手法(INC-MoE)を示している。四ノードの拡張構成をエミュレートした環境で、OLMoEのプリフィル処理を用いて評価され、vLLMの標準の集合通信経路と比べて、最初のトークンまでの時間が最大33%短縮、スループットが最大50%向上し、出力は一致したと報告されている。

John Stephan, Razvan Puscasu, Xu Yong ほか

★★★★★ 注目
arXiv cs.GT

How Learning Selects Equilibria and When It Leads to Collusion

説明学習が均衡をどのように選択し、いつ共謀につながるか

要約本論文は、有限の状態と行動を持つ無限期割引マルコフゲームにおいて、学習アルゴリズムの設計が均衡選択にどう影響するかを検討している。確率的に安定な状態が、各プレイヤーの変換後割引価値の最小値を最大化する近似定常ナッシュ均衡に対応することを示す。繰り返しクールノー競争では、確率的に安定なすべての状態が、各企業の割引利潤の最小値がクールノー・ナッシュ基準を上回る近似的公共完全均衡に対応し、これらの条件下では共謀が不可避であるとしている。

注目点確率的安定性によって均衡選択を特徴づけ、反復クールノー博弈で学習動学が近似的共謀を必然的に生むことを示し、アルゴリズム共謀研究に影響する。

Hanzhang Wang, Manxi Wu

★★★★☆ 注目
arXiv cs.GT

The Complexity of Strategizing Against No-Regret Learners: Pure When It Is Easy, Hard Even When Mixed

説明無後悔学習者に対する戦略最適化の計算複雑性:容易な場合は純粋戦略、混合戦略でも困難

要約本論文は、有限期間の繰り返しゲームにおいて既知のオンライン学習者に対する先見的な戦略最適化の計算複雑性を研究している。一般和ゲームでは、P≠NPの仮定の下で、混合戦略を出力できても、多項式時間の最適化器は最適な純粋行動系列の報酬に対し定数cの範囲内の報酬を達成できないことを示す。対照的に、ゼロ和ゲームでは決定論的な純粋行動で、混合戦略に匹敵する利得保証を効率的に得られる。

注目点既知の計算困難性の結果を平均ベースの学習者へ拡張し、ゼロ和ゲームで純粋戦略が混合戦略と同等の保証を得られることを示した点が新しい。

Yiheng Su, Emmanouil-Vasileios Vlatakis-Gkaragkounis

★★★★★ 注目
arXiv cs.IT · cs.CC · math.IT

Explicit Reed-Solomon Subspace Designs: Optimal List and Line Decoding

説明明示的なリード・ソロモン部分空間設計:最適なリストおよび線形復号

要約本論文は、拡大体上のリード・ソロモン符号を明示的に構成する方法を示し、誤り割合1-R-εまでリスト復号でき、リストサイズがO((1-R)/ε)で最適であることを述べています。より単純な強明示的構成として、リストサイズ(1/ε)^O(1/ε)の評価点の構成も与えています。両構成に対して決定的なリスト復号アルゴリズムを提示しています。

注目点明示的なReed-Solomon符号の近最適リスト復号と部分空間設計の構成を与え、リストサイズを定数に抑え、厳密な証明を示す。

Omar Alrabiah, Rohan Goyal, and Venkatesan Guruswami

★★★★★ 注目
arXiv cs.GT

Exploring the Tractability Frontier of Hylland-Zeckhauser Models

説明Hylland-Zeckhauser モデルの計算可能性の境界を探る

要約本論文は、一方向マッチングのための Hylland-Zeckhauser(HZ)機構における均衡計算の難しさを扱う。二値効用は強多項式時間で解けることが知られているが、本論文は効用値が {0,a,1} に限られる場合でも近似均衡の計算が PPAD 困難であることを示す。分離可能な凹効用では、共通の限界傾きが二つなら多項式時間で厳密解が得られ、三つなら PPAD 困難となり、境界は二と三の間にあることを示している。

注目点未解決問題を解決し、効用値3種で既にPPAD困難であることを示し、可解と困難の境界を明確化する厳密な証明を与えた。

Ioannis Panageas, Avi Shein, Shayan Taherijam ほか

arXiv cs.IT · cs.SY · eess.SY

World Model for Energy Efficiency Maximization in Dynamic Metasurface Antennas

説明動的メタサーフェスアンテナにおけるエネルギー効率最大化のためのワールドモデル

要約本論文は、時変チャネル下で動的メタサーフェスアンテナ(DMA)のデジタルビームフォーミングとDMA素子の重みを同時に最適化する問題を扱い、時間平均エネルギー効率を最大化します。送信電力、ローレンツ位相、最低伝送速度の制約を考慮しています。著者らは環境とのやり取りから潜在的なシステム動態を学習し、想像上の軌道を通じて両パラメータを最適化するワールドモデルの枠組みを提案し、制約を満たすための実行可能性保存の行動写像と安全コスト信号を組み込んでいます。シミュレーションでは、深層Qネットワークのベースラインと比べて時間平均エネルギー効率が約20%向上し、サンプル効率が高く、制約充足もより確実であったと報告されています。

Abdolrasoul Sakhaei Gharagezlou, Mehdi Monemi, Matti Latva-aho ほか

arXiv cs.DC · cs.NI · cs.SE

Making the Telemetry Pipeline Measurable: An Edge IoT Testbed and Dataset for End-to-End Latency, Provenance, and Energy-Aware Benchmarking

説明遥測パイプラインを測定可能にする:エンドツーエンド遅延・来歴・省エネ評価のためのエッジIoT試験基盤とデータセット

要約本論文は、計測を最優先に据えたエッジIoT試験基盤とデータセットを提示し、即時性・来歴・エネルギーを遥測の第一級の指標として扱います。システムは役割ベースのイベント駆動アーキテクチャとAvro形式の遥測メッセージを用い、MQTTブローカー(Mosquitto)には入出力時刻を記録するプラグインを追加しています。データセットは再生可能な生イベントとクエリ可能なParquetの表形式の両方で公開されています。一つの配備事例の遅延・計測文脈・エネルギーの集計を示していますが、新しい帰属手法や統制された性能ベンチマークは確立していません。

Dimitris Gkoulis

arXiv cs.DC

A Unified Queueing-Based Framework for Comparative Evaluation of Serverless Autoscaling Strategies under Bursty Workloads

説明バースト負荷下におけるサーバーレス自動スケーリング方式の比較評価のための統一キューイングモデル

要約本論文は、バースト性の高いワークロードに対するサーバーレス計算基盤の自動スケーリング方式を比較しています。対象は、リクエストごとのスケーリング(SPR)、同時実行数に基づくスケーリング(CLS)、メトリクスに基づくスケーリング(MBS)の三方式です。解析的キューイングネットワークモデルと、Java Modeling Tools(JMT)で実装したキューイングPetriネットを組み合わせ、二相超指数到着の下でスループット、平均応答時間、システム人口、システムパワーの四指標で評価しています。結果として、SPRは中程度の負荷で最も低遅延ですが容量上限付近では脆弱であり、CLSは突発的な条件下で設定に敏感であり、MBSは負荷範囲全体で最も安定したQoSを示すと報告しています。

Zahra Zafarzade, Ehsan Ataie

2026年10月26日(月)

arXiv physics.soc-ph · cs.GT

Formation of international environmental agreements and payoff allocation

説明国際環境協定の形成と利得配分:各国がどう減排協定に参加し、利益とコストを分けるかを研究する論文です。

要約この論文は、気候変動対策にはすべての国が減排コストを負う必要があるものの、各国は他国に努力させて自らは恩恵だけを得ようとする傾向があることを取り上げています。ゲーム理論は国際環境協定の設計に適した枠組みとされ、環境連合の形成を非協力的に扱う研究と、協力ゲームで気候変動のコストを分担する研究の二つのアプローチが紹介されています。両者にはそれぞれ長所と短所があります。

Michel Grabisch, Elena Parilina, Agnieszka Rusinowska ほか

arXiv eess.SP · cs.IT · math.IT

Movable Antenna Enabled Anti-Jamming: From Local Optimality Guaranteed Design to a Unified Antenna Position Optimization Framework

説明可動アンテナによる耐干渉:局所最適性を保証する設計と統一的なアンテナ位置最適化フレームワーク

要約本論文は、可動アンテナ(MA)を用いて無線通信の耐干渉性能を高める方法を検討しています。アンテナ位置ベクトルと受信ビームフォーマを同時に最適化し、出力の信号対干渉雑音比(SINR)の最大化を図ります。単一の妨害源と単一の見通し経路という基本的な条件に対しては、受信アンテナ数に比例した計算量で動作する減衰付き射影勾配降下法(DPGD)を提案し、ほぼ確実に局所最小解へ収束することを示しています。複数経路や複数妨害源を含む一般的な条件に対しては、低計算量の軟活性射影勾配法(SAPG)を提案し、MVDRおよびZF受信にも適用できることを示しています。数値結果から、両アルゴリズムが耐干渉性能と計算効率の両面で改善をもたらすことが確認されています。

Lebin Chen, Ming-Min Zhao, Lipeng Zhu ほか

arXiv cs.DC

How Numerical Errors Scale with Hardware

説明数値誤差はハードウェアとともにどう変化するか:同一リソース予算で算法・ハードウェアを比べる短い技術ノート

要約この短い技術ノートは、計算資源に対して数値誤差の上限をどう見積もるかを論じています。既知の計算量推定を持つ並列実行可能なアルゴリズムと、並列化の法則を組み合わせています。著者はこの手法が示された例以外にも一般化できると考えています。各構成に同一のリソースまたはエネルギー予算を課し、得られた数値誤差の評価を比較することで、アルゴリズム、ハードウェア、ソフトウェア実装を公平に比べられるとしています。

Niklas Baumgarten

★★★★☆ 注目
arXiv math.OC · cs.GT

A Unified Framework for Assortment Optimization and Matching under MNL Choice

説明MNL選択モデルにおけるアソートメント最適化とマッチングの統一フレームワーク

要約本論文は、多項ロジットモデル(MNL)の選択のもとで、商品アソートメントの最適化とマッチングを扱う統一的な枠組みを提案する。中心となるのは、商品の可用性が明らかになる前に企業が候補商品を確定する単一顧客の問題である。簡単な閾値方策により、比較基準に対して厳密な1/2の保証が得られ、基数制約にも対応する。この枠組みは、複数の応用で1/2または1/4の近似保証を与える。

注目点統一的な枠組みを提案し、多数の応用で近似比を改善する厳密な1/2保証を与えるが、影響は主に理論的である。

Omar El Housni, Ulysse Hennebelle

★★★★☆ 注目
arXiv math.FA · cs.IT · math-ph

Converse symplectic interlacing via low-rank singular value perturbations

説明低ランク特異値摂動による辛交錯の逆定理

要約本論文は辛交錯定理の逆を証明する。大域的な辛スペクトルと、2k段の交錯不等式を満たす局所的な辛スペクトルが与えられたとき、指定された大域スペクトルをもち、ある主部分行列が指定された局所スペクトルをもつ実対称正定値行列を構成する。主要な手法は、s主圧縮を秩kの特異値摂動に帰着させることである。ガウス量子周辺問題において、辛交錯不等式は大域と局所モードの周辺問題の完全なスペクトル両立条件であることを示す。

注目点辛スペクトル交錯定理の逆命題を証明し完全な必要十分条件を与え、低ランク特異値摂動を核心手法とする点で理論的に突出している。

Priyanka Grover, Hemant K. Mishra, Sarishti Singh ほか

arXiv cs.IT · math.IT

Minimality of Binary Codes From Weight Layers and Graph Cut Spaces

説明重みレイヤーとグラフ カット空間から得られる二元符号の極小性

要約本論文は、秘密分散方式に重要な役割を果たす二元線形符号の極小性を研究している。完全ハミング重みレイヤー単体から得られる符号、複数のレイヤーの和集合から得られる符号、グラフのカット空間符号の三種類の既知の構成を扱う。単一レイヤー符号については、t が偶数であるときに限り極小であるという完全な判定を与えている。また、任意のレイヤーの和集合については極小性の必要十分条件を示し、グラフのカット符号の極小性をグラフ理論的条件に言い換えている。

Xianhong Xie, Mengni Wang, Tingting Wu

arXiv cs.IT · math.IT

Further Study of p-Ary Self-Orthogonal Codes From Square Functions

説明平方関数から得られるp元自己直交符号のさらなる研究

要約本論文は、奇数標数の有限体上で、二つの二次トレース条件によって定義される符号族を扱う。これらの条件に対応する二次形式を解析し、対応する指標和を評価することで、符号のパラメータと完全重み分布を求めている。さらに、定義集合の乗法的軌道構造を利用して穴あけ符号を構成し、そのパラメータ、重み分布、双対距離を決定している。また、自己直交性の判定条件を確立し、構成した符号の可除性と射影性についても検討している。

Tingting Wu, Xianhong Xie

arXiv cs.GT

Who Pays for Thinking? Billing Hidden Reasoning Tokens in Model Cloud Contracts

説明思考の代金は誰が払うのか:モデルクラウド契約における非表示の推論トークンの課金

要約トークン単位で課金される言語モデルサービスで、利用者に表示されない内部推論や候補回答への課金が、事業者の判断と社会厚生にどう影響するかを研究した論文です。ユーザー、モデル事業者、計算クラウドの三者モデルを構築し、計算予算の決定と課金方式の関係を分析しています。LiveCodeBench を用いた実験で五つのモデル配備の品質、遅延、資源消費を比較し、追加の推論が社会的価値を生む場合は従量課金が、コストが便益を上回る場合は固定料金が望ましいと結論づけています。

Chao Feng, Burkhard Stiller

arXiv cs.GT

BROCADE: Broker-based Contract Design for the Multi-Agency Model

説明BROCADE:多機関モデルのためのブローカー型契約設計

要約本論文は、公共プロジェクトの成功を私的に評価する m 人の依頼人と、観測できない費用のかかる努力を行う n 人のエージェントからなる契約モデルにおける社会厚生最大化を研究している。論文は、依頼人への支払いとエージェントへの支払いを分離するブローカー、優越戦略の誘因両立性(DSIC)を特徴づける Myerson 補題の拡張、予算制約付きの単一依頼人契約設計への黒箱的帰着の三つの手法を提示している。さまざまなベンチマークに対する確定的および確率的契約の近似性能が示され、そのうち一つの確率的契約は n に依存しない O(log m) の近似比を達成する。

Yangguang Shi, Ron Lavi, Jie Zhang

★★★★☆ 注目
arXiv math.CO · cs.IT · math.IT

Sharp Bounds for Graph-Codes Avoiding Complete Bipartite Differences

説明完全二部差分を避けるグラフ符号の鋭い評価

要約[n] 上のすべてのグラフのうち、どの 2 つの異なるグラフの対称差も完全二部グラフ K_{s,t} にならないような族が占める最大割合を研究している。本論文は正の整数の組 s、t ごとにこの最大密度を決定した。両部のサイズがともに奇数なら密度は 1/2 と知られている。それ以外では、最大の偶数部サイズを 2h とすると、最大密度は Θ(n^{-h}) であることを示した。上界は Frankl–Füredi の禁止交叉定理、下界は BCH 符号を用いた二元線形符号の構成による。

注目点任意の固定s,tについてK_{s,t}対称差禁止族の密度の正確なオーダーΘ(n^{-h})を決定し、Alonの上界を改良、BCH符号による下界も厳密に示す。

Nader H. Bshouty

arXiv nlin.CD · cs.IT · math.IT

Revisiting entropy and entropy-related magnitudes of a symbolic sequence and their estimation

説明記号列のエントロピーとその関連量、および推定法の再検討

要約本論文は、系列データ解析に用いられるエントロピー、エントロピー密度、有効測度複雑性、情報距離などの量を再検討し、情報理論とエルゴード理論における数学的基礎を示しています。中心的な結果であるZivの定理は、正規化した異なる単語数とエントロピー密度が漸近的に等価であることを示し、Lempel-Ziv分解による推定の理論的根拠を与えています。有限系列に対する推定手法と、並列計算を用いたオープンソースのライブラリも提示され、fMRIによる脳機能結合、結合非線形振動子、心電図による心房細動分類の3つの事例で有用性が示されています。

Efren Aragon-Perez, Ania Mesa-Rodriguez, Karel Garcia-Medina ほか

arXiv cs.IT · math.IT

New families of additive non-RS MDS codes and ACD codes from twisted Reed-Solomon codes

説明ねじれReed-Solomon符号から構成される新しい加法的非RS MDS符号とACD符号

要約本論文は有限体上の単一ねじれ加法的一般化ねじれReed-Solomon(GTRS)符号を研究する。任意のhookおよびtwistパラメータに対し、これらの符号がMDS符号となるための必要十分条件を導く。さらにSchur平方を用い、そのような加法的MDS符号が加法的Reed-Solomon符号と単項式同値でないことを示す。また、双対が再び加法的GTRS符号となる符号のクラスを特定し、標数が有限集合を避ける十分大きい素数冪qについて、これらのGTRS符号がACD符号を与えることを示している。

Xia Li, Yu Wang, Yansheng Wu

arXiv cs.DC · cs.SE

Priority-Aware Scheduler for Serverless Functions Provision and Load Balancing

説明サーバーレス関数のプロビジョニングと負荷分散のための優先度認識スケジューラ

要約本論文は、メモリ制約のある分散ワーカーノード向けのルールベース優先度認識スケジューラ SPES-Ext を提案している。呼び出しパターンに基づいて関数を分類し、予測的な関数プロビジョニング、エビクション最適化、動的負荷分散の三つの要素を統合している。報告された実験では、既存手法と比べて第75パーセンタイルのコールドスタートが80%減少し、メモリ浪費が83.92%減少、ワーカー負荷分散が52.49%改善したとされている。

Cheryl Lee, Zishan Su, Zhouruixing Zhu ほか

★★★★☆ 注目
arXiv cs.GT · math.OC

Follow the Regularized Leader Does Not Converge in Constrained Optimization

説明制約付き最適化におけるFollow the Regularized Leader(FTRL)の非収束性

要約本論文は、オンライン学習の基礎的アルゴリズムであるFollow the Regularized Leader(FTRL)が、制約付き非凸最適化において一階定常点に収束するかを検討している。無限に滑らかな制約付き最適化問題を構成し、連続時間FTRLのKKTギャップがゼロから離れたまま無期限に残りうることを示している。また、目的関数が解析的である場合、ユークリッド正則化のFTRLは収束することも示している。

注目点無限に滑らかな制約付き最適化問題を構成し、連続時間FTRLのKKTギャップが消えないことを示す。理論的な新規性は高い。

Ioannis Anagnostides, Ioannis Panageas, Nikolas Patris ほか

arXiv cs.IT · math.IT

Subcodes with Prescribed Hull Dimensions in Linear Codes:Enumeration, Containment, and Asymptotic Distributions

説明線形符号のhull次元を指定した部分符号:列挙、包含、漸近分布

要約本論文は、与えられた親符号の内部で、指定された次元・hull次元・型をもつ部分符号の個数を数え上げる問題を扱う。親符号をLCD補符号とそのhullに分解し、射影を用いてLCD補符号内の問題に帰着させることで、完全型で細分化された明示的な公式を導く。さらに双対包含問題と、部分符号の次元が無限大に近づく場合の漸近分布を調べる。

Linhan Xiong, Hongwei Liu, Liren Lin

arXiv cs.DC

FrontGI: Architecture-Aware Parallel GNN Inference on Chiplet-Based Multicore Systems

説明FrontGI:チップレット型マルチコアシステム向けのアーキテクチャ対応並列GNN推論

要約大規模グラフデータに対するグラフニューラルネットワーク(GNN)の推論では、既存のライブラリが百コア超のマルチコアシステムでスケールしにくい問題があります。本論文は、グラフの構造特性とアーキテクチャを考慮して並列化戦略を選ぶFrontGIを提案し、多段キャッシュの活用を高めます。128コアのAMD EPYCシステムでの評価では、DGLに対してGCN、GraphSAGE、GIN、SGCでそれぞれ最大3.35倍、3.20倍、2.89倍、3.10倍の高速化を示し、PyGに対してはさらに大きな改善が報告されています。

Binglin Ji, Chenfeng Zhao, Roger Chamberlain

arXiv cs.DC · cs.AR

When and Why to Use TMA: A Workload-Grounded Characterization of Tensor Memory Acceleration on NVIDIA Hopper GPUs

説明TMAをいつ、なぜ使うか:Hopper GPUにおけるテンソルメモリアクセラレータの、ワークロードに基づく特性分析

要約本論文は、NVIDIA Hopper世代のテンソルメモリアクセラレータ(TMA)について、カーネル内でいつTMAを使い、クラスタマルチキャストを併用すべきかを検討しています。FlashAttention-3の順伝播におけるTMA、マルチキャスト、分散共有メモリ(DSM)、cp.asyncの選択を整理し、H100上のマイクロベンチマークからロード方式の選択指針を示しています。さらにB200でのCUTLASS GEMM実験により、これらの判断規則がBlackwell(SM100)でも概ね成り立つことを示しています。

Christin David Bose, Cesar Avalos, Junrui Pan ほか