分散計算、ゲーム理論、情報理論など。
説明Campbell コストの下での Rényi 通道シミュレーション発散による厳密サンプリング
要約本論文は、Campbell の指数符号化基準のもとで厳密サンプリングに必要な通信コストを研究している。送信者と受信者は Q に従う独立同分布のサンプルを共有し、送信者はインデックスだけを送って、選ばれたサンプルの分布が正確に P になるようにする。著者らは Rényi 通道シミュレーション発散 R_α(P‖Q) を導入し、これがあらゆる厳密サンプラーの Campbell コストの下界になること、また新しい階層化サンプリング法により Campbell パラメータのみに依存する定数の加法的誤差の範囲で達成可能であることを示す。独立同分布の積分布では、適切な条件のもとで、主要な Rényi 発散項を超える差は (1/2)log n + O(1) であることも示されている。
説明分散型Wi-Fiシステムにおける3次元ターゲット測位のためのバイスタティック遅延・ドップラー センシング
要約本論文は、分散型Wi-Fiセンシングにおいて、バイスタティックな遅延情報が3次元移動ターゲットの可観測性と測位性能をどのように向上させるかを検討しています。仅ドップラーによるセンシングと遅延・ドップラーによるセンシングを比較し、それぞれのフィッシャー情報行列を導出しています。解析の結果、仅ドップラーでは一般に6台の受信機が必要であるのに対し、遅延・ドップラーでは非縮退の幾何条件下で3台で局所的に識別可能になることが示されています。
説明多項式ハッシュとエントロピー再利用による複数編集を訂正する二値符号
要約本論文は、長さ n の系列における t 回の編集（削除・挿入・置換）を訂正できる二値符号を明示的に構成する新手法を提案します。DNA ストレージやレーストラックメモリへの応用が想定されています。まず多項式ハッシュを用いて冗余度が (4t+2)log n＋O_t(log log n) ビットの組織的符号を構成し、次に「エントロピー再利用」により良好なハッシュの索引で情報を運ぶことで、冗余度を (2t+1)log n＋O_t(log log n) ビット以下に減らします。決定的な多項式時間の符号化・復号アルゴリズムも示されています。
注目点多項式ハッシュとエントロピー再利用という新技法を提案し、t編集訂正の冗余を(2t+1)log nへ改善。証明は厳密で、符号理論の一分野に影響が大きい。
説明切断可能な分散問題に対するほぼ無損失な変換
要約本論文は、加法的な局所頂点部分集合最小化問題に対する定数ラウンドのLOCAL近似を研究している。二つの変換法を提案し、近似比を源アルゴリズムの α から α+1+η および α+η へと改善する。目標グラフクラスにはより強い局所的性質が必要である。両方式とも決定的かつ計算可能であり、平面グラフなどに関する具体的な近似比も示されている。
注目点分布式局所近似の変換比をα+ηへ改善し、平面グラフの2-支配で19から6+ηへの大幅な改善を証明により示している。
説明事後ラベルサンプリングによるガウス混合モデルのレート歪み理論
要約本論文は、有限ガウス混合モデル（GMM）における平均二乗誤差のレート歪み関数を研究している。閉形式の解も最適なテストチャネルも知られていない問題を扱う。著者らは上界と下界で挟み込み、Gibbs再ラベリング法（GRM）が上界を達成できることを示し、低レート向けの確率的スカラー量子化（SSQ）も提案している。有限コードブックのレート差と歪み下限についても分析している。
説明シンプレクティック線形符号の hull 次元の変動
要約本論文は、シンプレクティック距離を保つ同値変換の下で、シンプレクティック線形符号の hull 次元がどのように変化するかを研究している。著者は偶数値の不変量 Δ(C) を導入し、到達可能な最小のシンプレクティック hull 次元が k−Δ(C) であることを示す。これにより、符号がシンプレクティック LCD 符号と同値かどうかを判定できる。さらに、自己直交符号が取りうる hull 次元の全体や、グラフ構成による符号の作り方も扱っている。
説明加法的効用に対する頑健な比例性公理
要約本論文は、予算制約の下で候補の一部を選ぶ参加型予算モデルを研究する。有権者は各候補に数値の効用を割り当てて選好を表明する。複数議席選挙における公平性の中心概念である比例性、すなわち有権者の各集団が規模に概ね比例して結果に影響すべきことを扱う。既存の、承認型選好に限られていた「plus」公理（EJR+ と Core+）を一般の加法的効用へ拡張する。手法は、候補の費用を支持者間で分担し有権者の総支払額を均衡させる支払いベースの解釈に基づく。
説明SiteEvo：サイト適応型大規模MIMO検出器を自律的に発見するLLMエージェント
要約本論文は、特定の展開サイトに合わせた大規模MIMO検出器を、大規模言語モデル（LLM）エージェントが既存の枠組みの調整ではなく、実行可能な検出器プログラムを丸ごと生成する手法SiteEvoを提案している。生成された検出器は通信システムのバックエンドでパラメータが最適化され、ビット誤り率の維持を条件に構造が簡素化された後、オンラインのLLM推論なしで配備される。シミュレーションでは、三つのサイトにおいて6 dBの時点でBERが各サイトの最良の比較検出器より2.6～6.0倍低く、計算量は16.7～34.1%削減された。
説明ラッソゲーム：最初のループ形成で終わるグラフ上のゲームの研究
要約本論文は、有限グラフ上で辺にラベルや重みが付いたゲームを扱い、最初のループが形成された時点で終了するプレイを対象とする。プレイは経路（ヘッド）の後に循環（ループ）が続く、ラッソ型の形になる。勝敗の判定には、ループ部分のみを見るループ意味論と、プレイ全体を見るラッソ意味論の二つを比較している。ラッソ意味論を採用すると、ゲームの計算量と最適プレイに必要な記憶量が大きく変わることが示される。例えば平均利得ゲームは PSPACE 完全になり、ラッソ・パリティゲームは多項式時間で解ける。
説明エージェントのオンライン到着下における家事（分割不可能な負担）のMMS配分のための乱択アルゴリズム
要約本論文は、エージェントが順次到着し、アルゴリズムが即座かつ取り消し不能に割り当てを行わなければならないオンライン環境で、n 人のエージェントに m 個の分割不可能な家事（負担）を公平に配分する問題を扱います。公平性は最大最小シェア（MMS）で測り、事後MMS近似比で評価します。二値の加法的コストに対し期待比約 3/2 のアルゴリズムを示し、任意の乱択オンラインアルゴリズムの期待比が少なくとも 3/2 であることを証明しています。また、ある変種は高確率で近似比 2 を保証します。
説明配分の公平性（シェア基準と羨望基準）を同時に保証する多項式時間アルゴリズム
要約分割不可能な財の配分において、シェア基準の公平性（AnyPrice シェア APS）と羨望基準の公平性（EFL、MXS など）を同時に満たす問題を扱っています。論文は、多項式時間、擬多項式時間、そしてエージェント数を固定した場合のアルゴリズムを提案し、例えば厳密な EFL と (1-ε)-MXS、2n/(3n-1)-APS を同時に保証できることを示しています。また、MXS と RMMS の間の数値閾値の計算は弱 NP 困難であることも証明されています。
注目点複数の公平性基準を同時に満たす多項式・擬多項式アルゴリズムを示し弱NP困難性も証明している。厳密な証明で、影響は分野の一部に限られる。
説明不等誤り保護のためのユニバーサル復号
要約本論文は、離散無記憶通信路上で単一の特別なメッセージを対象とするユニバーサル不等誤り保護(unequal error protection)を研究している。著者らは、復号規則が通信路の遷移確率に依存しない符号列を構成している。普通のメッセージの信頼できる復号を保証しつつ、特別なメッセージに対して達成可能な誤り指数を導出しており、その指数は等誤り保護のランダム符号化基準を厳密に上回り、レートが通信路容量に近づいても正の値を保つ。
説明消失訂正（erasure）復号における正のレートでの未検出誤り指数の上界
要約本論文は、消失復号を用いる離散無記憶通信路の未検出誤り指数を扱う。未検出誤り確率と消失確率が零に近づくと仮定し、正のレートにおけるこの指数の上界を導出している。証明では、補助出力によって復号器に符号語のリストを与える Somekh-Baruch の genie-aided 論証を用いる。この上界は Telatar の零レートにおける緊密な逆定理を再現し、直線境界（straight-line bound）と同等以上に厳しい。数値例では、直線境界からの改善が厳密に生じうることが示されている。
説明半シングルトン限界までの挿入・削除Reed-Solomon復号アルゴリズム
要約本論文は、次元2の最適Reed-Solomon符号を挿入・削除誤りに対して復号する問題を扱い、誤りは半シングルトン限界まで対象とします。総当たり復号より時間計算量の小さい、挿入と削除が混在する一般的な場合の復号アルゴリズムを提案し、既存手法の範囲を超えて誤りを訂正します。さらに、挿入のみと削除のみの特殊な誤りパターンについては、一般アルゴリズムよりも計算量の小さい2つのアルゴリズムを示しています。
説明ワイナーの共通情報と共通エントロピーは計算がNP困難であることの証明
要約本論文は、有限値をとる確率変数の組に対する二つの情報量、ワイナーの共通情報J(p)と共通エントロピーG(p)を扱います。いずれもXとYを条件付き独立にする補助変数に関する最適化で定義されます。著者らは両量の計算がNP困難であることを示し、J(p)が与えられた整数より厳密に小さいかどうかの判定は特定の表について NP完全であることを証明しています。さらに、逆多項式の誤差での近似もNP困難であることを示しています。
注目点古典的情報量2つのNP困難性を厳密な判定基準と帰着で示し、長年の未解決問題に答えを与えた。理論情報理論への影響は大きい。
説明情報複雑性における定数損失・ラウンド保存型の直和定理
要約本論文は、独立した多数の通信問題インスタンスを解くのに必要な情報量と、一つのインスタンスに必要な情報量との関係（強い直和定理）を扱います。Gap-Majority 合成について、通信ラウンド数を保存すると従来は対数的な損失が生じていましたが、著者らはインスタンス数やラウンド数に依存しない定数の加法的情報損失を持つ補題を証明しています。さらに、積分布上の加法的な二乗可積分観測量に対する分散直和定理と、任意の終端出力に対する同一ラウンドでの平均二乗推定の上界を示しています。
注目点Gap-Majority合成で轮次保存時の情報損失を対数から定数へ改善し、分散直和定理を与えた点は技術的に明確な前進である。証明は厳密だが、影響は情報複雑性理論の一分野に限られる。
説明階層型KVキャッシュを備えたLLM推論クラスタの合成的性能モデリング
要約本論文は、LLM推論クラスタにおいてハードウェアや提供ポリシーが階層型KVキャッシュと相互作用する様子を予測する合成的離散事象シミュレータを提案している。局所的なサービスコストと共有リソース・KV可用性を分離してモデル化し、1P-1D構成で校正した計算・転送モデルを互換性のあるワーカー間で再利用する。SGLangとの比較検証では、質問応答の平均エンドツーエンド遅延誤差は1.34%、コーディングセッションは6.36%であった。CPUシミュレーションにより再生時間は平均15.33倍短縮された。
説明すべての許容修復次数に対応する小さなサブパケット化水準の新しい最小記憶再生符号
要約本論文は、分散ストレージシステム向けの新しい (n, k) 最小記憶再生符号（MSR符号）のファミリーを提案する。検査行列を対角行列と一般化置換行列からなるブロックヴァンデルモンド行列として構成し、サブパケット化水準 N=(d-k+1)^{⌈n/2⌉} を達成し、k+1≤d<n の任意の修復次数をサポートする。新構成の重要な点は、Ye-Barg 符号の検査行列の構成要素に従来必要だった厳密な可換性条件を緩和したことである。
説明併合モードにおける（非）線形符号の変換に関するエントロピー/長さプロファイル境界
要約本論文は、非線形符号の変換のための情報理論的枠組みを提案します。併合モードにおいて、エントロピー/長さプロファイル（ELP）を用いて、任意の (n,M)_q 符号について、変更されない記号数の上界と読み出される記号数の下界を導出します。線形性や log_q M が整数であることは仮定しません。線形符号の場合、これらの境界は一般化ハミング重み（GHW）境界に帰着します。さらに、ハミング符号と準群に基づく構成が示され、非線形符号の場合にも境界が tight であると述べられています。
説明ランダム摂動下の指向性推定と許容誤差のトレードオフ：高指向性放射源の実現可能性を一般化した感度指標で検討する研究。
要約本論文は、誤差摂動下で高指向性放射源を実際に実現できるかを評価するための一般化された感度指標を提案します。この手法は連続源、理想的な非結合アレイ、相互結合を持つ異種アレイにも適用できるとされています。選択した誤差モデルの下での実現指向性の系の平均値を求め、源の摂動による指向性低下を素早く予測できます。指向性と許容誤差の指標を用いて最適化問題を構成し、両者のトレードオフを示しています。
説明疎な近傍場ビームフォーミングにおける有効自由度の崩壊：ブロック階数1の機構
要約疎な近傍場アレイは、離れて配置された複数のサブアレイを位相コヒーレントに結合し、分散型MIMO、衛星編隊、統合センシング・通信などを支えます。論文は、保護領域に対する干渉抑圧は編隊全体の広がりではなく単一サブアレイ内の可干渉性で決まり、領域共分散の有効階数がMNからMへ崩壊しうることを示しています。非漸近的な十分条件を与え、8機のLEO衛星による数値実験で理論と実際の最悪ケースの信号対干渉比を検証しています。
説明並行更新下のフィルタ付きマルチテナントANNグラフ索引における再現率有界の陳腐化解析
要約本論文は、ストリーミング更新、フィルタ検索、マルチテナントを組み合わせたグラフ型索引を提案し、テナントごとの再現率低下を未統合更新による陳腐化と、述語を満たす点の局所密度に依存するフィルタ下の到達可能性に分解する理論を示します。固定した挿入期間で統合規模を20倍にすると、最終的なrecall@10は99.44%から99.01%へ単調に低下したと報告しています。さらに、テナント感知のキャッシュと陳腐化上限付きのスケジューラを提案し、FreshDiskANN上で評価したチャーン負荷では厳しい層のSLA違反を解消したとしています。
説明重み付きビーピングネットワーク：信号強度を取り入れた無線通信モデル
要約ビーピングネットワークは無線通信と計算のモデルですが、干渉は有無の二値として扱われます。本論文は辺の重みで信号強度を表し、近傍の信号の累積が受信閾値を超えたときのみビープを受信する重み付きビーピングネットワーク（WBN）を提案します。閾値σ以上の重みを持つ辺でのみメッセージ配送を保証する局所ブロードキャスト問題を扱い、その計算量を示すアルゴリズムを与えています。また、古典モデル向けの多項式ラウンドのアルゴリズムは、対数的オーバーヘッドで重み付きネットワーク上にエミュレートできると示しています。
注目点信号強度を重みとした重み付きビーコンネットワークを提案し、ほぼ最適な局所同報アルゴリズムと古典モデルのシミュレーション結果を示す。
説明ほぼすべての論理関数の閾値次数は中央の一つか二つの整数に集中する
要約本論文は、ブール関数の多項式閾値次数、すなわちその符号でその関数を表せる実多項式の最小次数を研究している。n変数の一様ランダムなブール関数は、例外的な確率を除き、閾値次数が⌊n/2⌋または⌈n/2⌉になることを示している。これは1991年のAspnes、Beigel、Furst、Rudichの予想を証明するものであり、Wang と Williams の関連予想にも触れている。
注目点ほぼすべてのブール関数の閾値次数が中央の1〜2整数に集中することを示し、1991年の二つの予想を解決した。証明は完全である。
説明反復ゲームにおける反応戦略のマルチエージェント学習：学習率のばらつきが協力を促す
要約本論文は、反復囚人のジレンマにおいて、互恵性と寛容性からなる反応戦略空間で自己利益追求型の勾配上昇学習者がどのように戦略を調整するかを研究している。学習率が一様な集団は常に裏切る戦略（ALLD）に収束する一方、学習率にばらつきのある集団は寛大なしっぺ返し（GTFT）に近づき、集団的利得はほぼ最適になることが示される。さらに、ALLDまたはTFTへの収束の十分条件が証明され、学習率のばらつきにより摂動後も協力が回復しうることが述べられている。
注目点反応型戦略空間で勾配上昇学習を扱い、学習率の異質性が協力を生むことを示し、収束条件も証明しており新規性が高い。
説明補助金を用いた不可分財の両立型（BoBW）公平分配
要約本論文は、補助金付き公平分配と不可分財に対する両立型（BoBW）公平性の関係を研究している。ある評価関数のクラスで、補助金によって妬みのない状態にできる事後的性質を満たす割り当てが常に存在するなら、その性質を満たす割り当てに支えられた事前に妬みのない抽選が存在することを証明する。加法的財、家事、財と家事の混合などの既知の結果も、この還元から導かれる。
注目点一般的な帰着を証明し、反例と三エージェントの結果を与えてBoBW存在性と補助金付き無嫉妬性を結び付けた点が新規性の根拠である。
