arXiv雑要約
プログラム - 2026/03/23 公開
ブリッジ補題を用いた巡回セールスマン問題の近似 [cs.DS]目的：2種類の距離空間における巡回セールスマン問題（TSP）変種の近似アルゴリズムの改善
- TSPは組み合わせ最適化問題の代表であり，物流，スケジューリングなど様々な応用分野で重要である。
- 既存のTSP変種問題に対する近似アルゴリズムの性能向上の余地があり，より効率的な解法が求められている。
- ブリッジ補題を応用し，オーダー付きTSPおよびk-Person TSP Pathの近似比率を改善することを目指す。
- オーダー付きTSPにおいて，既存の自明な近似アルゴリズムを上回る，3/2 + e^{-1} < 1.878 の近似比率を達成した。
- k-Person TSP Pathにおいても，自明な近似アルゴリズムを上回る，1 + 2・e^{-1/2} < 2.214 の近似比率を達成した。
- これらのアルゴリズムは，より一般的な車両経路問題への応用も期待されるブリッジ補題の変形版を利用している。
利己的なマイナーはいつ二重支出すべきか [cs.AR, cs.RO, cs.CR, cs.DC, cs.DM, cs.IT, math.IT, math.PR]目的：二重支出攻撃における収益損失と，攻撃者が無コストで二重支出する機会の分析
- ブロックチェーンのセキュリティ確保は重要であり，攻撃に対する脆弱性の理解が不可欠である。
- 既存の研究では，孤立ブロックの損失や無コストでの二重支出機会が十分に考慮されていない。
- 利己的なマイニングと頑固なマイニングを組み合わせた戦略で，最適な頑固さを見出す。
- 頑固なマイニングから利己的なマイニングへの移行時期を最適化する手法を提案した。
- 頑固さのレベルがk確認ルールを超える場合，攻撃者は無料で二重支出を試みることができることを示した。
- 頑固なマイニング戦略を改良し，攻撃を隠蔽し，二重支出の確率を高めることを試みた。
バンディット情報を用いたデータ系列のオンラインクラスタリング [cs.LG, cs.IT, math.IT, math.ST, stat.TH]目的：データ系列のオンラインクラスタリング
- データ分析において，未知のパラメータを持つデータ群を効率的に分類することは重要である。
- 既存手法では，データ分布の多様性や高次元性に対応した効率的なクラスタリングが課題である。
- 本研究では，バンディット問題を導入することで，サンプル数を最小化しつつ高精度なクラスタリングを実現する。
- 提案手法であるATBOCアルゴリズムは，多変量ガウス分布に対して漸近的に最適解に近い性能を示す。
- 単パラメータ指数分布の場合には，ATBOCアルゴリズムは下限と同等の性能を発揮する。
- LUCBBOCおよびBOC-ELIMは，ATBOCと同等の性能を持ちながら，計算コストを削減する。
プログラム合成によるテンソルネットワーク構造探索 [cs.CE, cs.PL]目的：テンソルネットワーク構造の探索
- 多次元データの圧縮において，テンソルネットワークは強力な枠組みを提供する。効率的な圧縮は計算コスト削減に繋がる。
- 最適なネットワーク構造はデータに依存するため，探索は困難である。既存手法は計算量が多く，実用性に限界がある。
- プログラム合成の視点を取り入れ，高コストなテンソル分解を回避することで，効率的な構造探索を実現する。
- 提案手法は，探索速度を最大10倍に向上させ，既存手法を上回る圧縮率を達成した。
- 大規模なテンソルへの適用が可能となり，より広範なデータに対して圧縮性能を発揮する。
- 発見されたトポロジーは類似データにも適用でき，汎用的な構造と比較して最大2.4倍の圧縮率を維持した。
深層強化学習に基づくクロスサイトスクリプティングの敵対的攻撃：評価と拡張研究 [cs.SE, cs.AI, cs.CR]目的：クロスサイトスクリプティング攻撃に対する敵対的攻撃の評価と改善
- ウェブアプリケーションのセキュリティにおいて，クロスサイトスクリプティングは重大な脅威であるため，その対策が重要となる。
- 深層学習はXSS攻撃の検出に有効だが，入力と出力の間の非連続性により，敵対的攻撃に対して脆弱であるという課題がある。
- 既存の敵対的攻撃手法の妥当性を検証し，より効果的な評価戦略とXSS Oracleを導入することで，攻撃の回避率向上を目指す。
- 再現実験により，既存研究の妥当性に関する問題を指摘し，XSS Oracleの導入により，より厳密な評価が可能となった。
- 妥当性に関する問題を修正した結果，攻撃成功率（エスケープ率）が96%を超え，既存手法の改善が示された。
- 本研究は，深層学習モデルがXSS攻撃に対して抱える脆弱性を明らかにし，より堅牢なセキュリティシステムの構築に貢献する。
企業データの統計に配慮した秘匿性保護：QCEWへの応用 [cs.CR, cs.DS, stat.AP]目的：企業データの秘匿性保護に関する新たな枠組み
- 企業データは経済分析に不可欠だが，秘匿性保護は重要課題である。
- 既存手法は企業データの特性に対応できず，有用性と秘匿性の両立が難しい。
- 属性推測の精度低下による秘匿性確保を目指し，政策担当者への解釈性を重視する。
- 本研究では，属性値の不確実性帯域を定義し，帯域内値の識別困難性を秘匿性の指標とする枠組みを提案する。
- QCEWデータと公開データセットを用いて，提案手法の有効性を検証した結果，実用的な秘匿性と有用性のバランスが実現できることが示された。
- 従来の会員推測攻撃ではなく，属性推測に対する保護に焦点を当てることで，より適切な秘匿性保護を実現する。
優先順位制約付き決定木とカバレッジ [eess.SY, cs.SY, cs.DS, cs.LG]目的：最適決定木と集合被覆における優先順位制約下での最適化
- 意思決定や分類において，効率的な探索戦略は不可欠であり，計算資源の最適化に繋がる。
- 既存手法では，優先順位制約を考慮した最適化アルゴリズムが十分に確立されていない。
- 優先順位制約下での最適決定木と集合被覆問題に対する近似アルゴリズムを開発し，性能評価を行う。
- 最適決定木と集合被覆問題に対し，$\mathcal{O}^*(\sqrt{m})$近似アルゴリズムを提案した。
- 一般的な優先順位制約下での困難性を示す結果も得られ，近似の限界を示唆した。
- 特に重要なアウトフォレストとインフォレストに対し，多対数近似保証とそれに対応する困難性を示すことができた。
自動脆弱性修復におけるパッチ検証 [cs.RO, cs.SE]目的：自動脆弱性修復システムのパッチ検証手法の信頼性向上
- ソフトウェアの脆弱性はセキュリティリスクであり，迅速な修復が不可欠である。
- 既存の自動修復システムは，基本的なテストに合格するだけでパッチの正確性を判断している。
- 開発者が追加する詳細なテスト（PoC+テスト）を検証することで，より正確な評価を目指す。
- 構築したベンチマークPVBenchを用いた評価で，40%以上のパッチがPoC+テストに失敗することが判明した。
- 既存のシステムはパッチの成功率を過大評価している可能性が示唆された。
- 根本原因分析，プログラム仕様への準拠，開発者の意図把握が，改善の重要なポイントである。
テンソルトレイン分解に基づくMIMO-AFDMシステムにおける分数の遅延とドップラーによるチャネル推定 [cs.IT, math.IT]目的：MIMO-AFDMシステムにおけるチャネル推定手法
- 高速通信において，多様性利得を最大限に活用するには正確なチャネル推定が不可欠である。
- 従来のチャネル推定は整数遅延を前提としており，実際の分数遅延を考慮できていない。
- 分数遅延とドップラーの影響を考慮した，効率的なチャネル推定手法を開発すること。
- 提案手法は，時間アフィン周波数領域パイロット構造とテンソルトレイン分解を活用することで，高い計算効率を実現した。
- 従来のCRBに代わる指標としてZiv-Zakai boundを導出し，低SNR領域における性能評価の精度向上を示した。
- 既存手法と比較して，優れた通信性能と大幅な計算時間の短縮（1桁の削減）を達成した。
クリティカルセクションはスレッド毎ではない：ロックベースの並行処理に対するトレース意味論 [cs.RO, cs.PL]目的：ロックを用いた並行処理におけるクリティカルセクションのトレースに基づく特性化
- 並行処理は現代のコンピューティングにおいて不可欠であり，効率的な同期メカニズムが求められている。
- 従来のクリティカルセクションの定義は，単一スレッド内でのロック獲得に限定されており，柔軟性に欠ける。
- 本研究は，複数のスレッドにまたがるクリティカルセクションを考慮することで，より正確な並行処理モデルを構築することを目指す。
- 本研究では，C/Pthreadプログラムの本質を捉えるトレースモデルを用いることで，スレッド毎の制限のないクリティカルセクションの定義を提示した。
- その結果，クリティカルセクションは複数のスレッドにまたがる可能性があり，実世界のプログラムにおけるセマンティックギャップを埋めることができる。
- この新しいアプローチは，従来のロックセット構築の拡張を可能にし，並行処理プログラムの正確な解析に貢献する。
ClawWorm: LLMエージェント生態系における自己伝播攻撃 [cs.CR, cs.AI, cs.LG, cs.MA, cs.SE]目的：LLMエージェント生態系における自己伝播攻撃の実現と評価
- LLMエージェントの利用拡大に伴い，長期実行プロセス間のセキュリティ確保が急務となっている。
- 既存のLLMエージェントフレームワークのセキュリティ特性は十分に検証されていない。
- 本研究は，実運用規模のLLMエージェントフレームワークに対する自己伝播型攻撃の可能性を明らかにする。
- ClawWormは，単一のメッセージから完全に自律的な感染サイクルを達成する初の自己複製ワーム攻撃である。
- 実験の結果，攻撃成功率は64.5%であり，複数ホップにわたる持続的な伝播が確認された。
- モデルのセキュリティ態勢には大きな差があり，実行レベルフィルタリングは有効だが，スキルサプライチェーンは脆弱である。
無線ネットワークにおける有用領域解析のための統一的フレームワーク：セルあり，セルなし，そしてその中間 [eess.SP, cs.IT, math.IT]目的：無線ネットワークの有用領域解析に関する統一的な枠組み
- 無線通信の性能向上には，干渉環境を正確に把握し，効率的な資源配分を行うことが不可欠である。
- 大規模MIMOやセルレスネットワークなど，複雑なネットワーク構成における干渉パターン解析は困難である。
- 非線形写像のスペクトル半径を用いて，有用領域の実現可能性を簡潔に表現する手法を提示する。
- 本研究により，弱パレート境界の既存の表現を簡潔な表記で一般化することが可能になった。
- 有用領域が凸であるための十分条件を導出し，時間分割による性能向上の限界を示すことができた。
- 総和レート最大化問題が本質的に凸であることを示し，効率的な最適解法開発の道を開いた。
ヒルツェブルッフ曲面からの代数幾何符号の双対 [math.AG, cs.IT, math.IT]目的：ヒルツェブルッフ曲面$\mathcal{H}_e$上定義された代数幾何符号$C_e(a,b)$の双対の明示的な表現
- 符号理論は，通信や情報伝送における誤り検出・訂正に不可欠な分野である。
- 代数幾何符号は，そのパラメータの解析が難しく，性能評価が課題となっていた。
- ヒルツェブルッフ曲面上の代数幾何符号の双対構造を明らかにすることで，符号の性能改善に貢献する。
- 代数幾何符号$C_e(a,b)$の双対$C_e(a,b)^\perp$の最小距離の下限を計算した。
- 符号$C_e(a,b)$の新しい明示的な表現を提示し，他の既知の符号との関係を調査した。
- 符号$C_e(a,b)$間の直交包含の十分条件を導出し，CSS量子符号の構成に利用できることを示した。
- 1
- 2