A symmetric recursive algorithm for mean-payoff games
この論文は、平均報酬ゲームを解くための新しい決定論的かつ対称的な再帰アルゴリズムを提案している。
💻 Category
cs.DS
87 件の論文
Succinct QUBO formulations for permutation problems by sorting networks
この論文は、比較交換ネットワークを用いて 個の二値変数で順列を表現する新しい QUBO 定式化を提案し、従来の順列行列符号化よりも変数数が少なく疎な相互作用グラフを持つことで、制約付き順列の偏りのないサンプリングや群論的演算を可能にすることを示しています。
Structured Gossip: A Partition-Resilient DNS for Internet-Scale Dynamic Networks
この論文は、DHT のフィンガーテーブルを活用したパッシブな安定化メカニズムと版数ベクトルを導入することで、グローバルな協調なしに大規模なモバイルアドホックネットワークにおけるネットワーク分断に耐性を持ち、メッセージ複雑度を削減しながら最終的な一貫性を保証する「構造化されたゴシップ DNS」を提案しています。
The Theory and Practice of Computing the Bus-Factor
本論文は、プロジェクトのリスク指標であるバスファクターを、人員とタスクの二部グラフに基づく統一的な枠組みで定式化し、その計算がNP困難であることを証明するとともに、ネットワークの頑健性に基づいた新たな指標と効率的な近似アルゴリズムを提案し、既存手法よりも優れたリスク評価を実現することを示しています。
The Li-Chao Tree: Algorithm Specification and Analysis
この論文は、競技プログラミングで広く用いられているが正式な仕様書が存在しなかった「Li-Chao 木」の完全なアルゴリズム仕様、形式的な正しさの証明、理論的複雑性の分析、および実証的な性能評価を提供し、その実装の簡便性や数値的安定性、永続性などの高度な変種への拡張性を含む最終的な仕様書として確立するものである。
Permutation Match Puzzles: How Young Tanvi Learned About Computational Complexity
この論文は、グリッドの行と列に昇順または降順の制約を課す「置換マッチパズル」の解の存在条件を完全特徴付けし、解の数をフック長公式で記述するとともに、解がない場合の最小修正アルゴリズムを提案し、制約を一般の置換に拡張した場合には最小修正問題が NP 完全であることを示しています。
Sampling Colorings with Fixed Color Class Sizes
この論文は、多変数多項式の幾何学的手法を用いて、最大次数のグラフに対して色数のとき、各色クラスサイズがほぼ等しい（均衡）な彩色を多項式時間でサンプリングするアルゴリズムを提案し、さらにその結果として均衡彩色の存在証明や彩色クラスサイズの多変数局所中心極限定理を導出するものである。
Bayesian inference of planted matchings: Local posterior approximation and infinite-volume limit
この論文は、相関するランダム点集合間の埋め込みマッチングのベイズ推論において、部分マッチングモデルでは局所アルゴリズムによる事後分布の近似と無限体积极限の存在が成り立つ一方、完全マッチングモデルでは全体的なソートやフローに基づく点の索引付けが必要となることを示し、 の次元への拡張は未解決課題として残している。
A note on approximating the average degree of bounded arboricity graphs
この論文は、有界木次数グラフの平均次数を近似する Eden らのアルゴリズムを、パラメータ探索による対数因子の損失なしに完全な形で提示し、木次数と平均次数を用いた回のクエリで-近似を実現する方法を詳述するものである。
Faster shortest-path algorithms using the acyclic-connected tree
この論文は、グラフを再帰的に強連結成分に分解する「非循環接続木（A-C 木）」という新しい分解手法を提案し、これを前処理として利用することでダイクストラ法などの単一始点最短経路アルゴリズムの計算時間を、グラフの「ネスト幅」に依存するより良い複雑度へ改善することを示しています。
Computational Complexity in Property Testing
この論文は、クエリ複雑性と時間複雑性の関係を体系的に研究し、時間 - クエリ階層定理の確立や半空間の距離近似問題における細粒度の時間下界の証明を通じて、プロパティテストにおける計算量的な困難性の地図を描き出すことを目指しています。
Hallucination is a Consequence of Space-Optimality: A Rate-Distortion Theorem for Membership Testing
この論文は、大規模言語モデルのハルシネーションが、限られた容量下での情報理論的に最適な戦略として、事実と非事実のスコア分布間の最小 KL ダイバージェンスによって特徴づけられるレート歪み定理の必然的な帰結であることを示しています。
DRESS and the WL Hierarchy: Climbing One Deletion at a Time
本論文は、グラフの構造的特徴を抽出するフレームワーク DRESS の拡張である-DRESS が、CFI 階梯定理により任意のに対して CFIペアを区別し、特定の構造的仮定の下で-WL 階層と同等以上の識別能力を持つことを理論的に証明したものである。
Transposition is Nearly Optimal for IID List Update
この論文は、アクセス確率の分布が未知の i.i.d モデルにおけるリスト更新問題において、リクエストされた要素をその直前の要素と入れ替える「転置ルール」が、最適定常順序の期待コストに 1 を加えた程度のコストしか発生させず、50 年前のリヴェストの予想を定数項の誤差で解決したことを証明しています。
Reconstructing Bounded Treelength Graphs with Linearithmic Shortest Path Distance Queries
本論文は、有界次数および有界ツリー長を持つグラフにおいて、最短経路距離を返すオラクルを用いた辺の再構成問題を、決定論的アルゴリズムで クエリで解決し、既存の最良のアルゴリズムを 因子だけ改善するとともに、有界弦性グラフに対する既知の下限と一致することを示しています。
Density-Dependent Graph Orientation and Coloring in Scalable MPC
本論文は、部分グラフの密度に依存するグラフの向き付けと彩色問題を、強サブリニアメモリ制約下での壁を破るラウンドで解決する大規模並列計算アルゴリズムを提案しています。
Intermittent Cauchy walks enable optimal 3D search across target shapes and sizes
この論文は、3 次元空間における断続的リーヴィー歩行の数学的解析を通じて、ターゲットの形状が検出性に決定的な役割を果たし、特にリーヴィー指数（コーシー歩行）がターゲットのサイズや形状に依存せず、検出時間を最適化する唯一の戦略であることを証明しています。
Polynomial-size encoding of all cuts of small value in integer-valued symmetric submodular functions
整数値対称部分モジュール関数において、値が となるすべてのカット（集合）を、多項式サイズのリストで効率的に表現し、これを構築するアルゴリズムと固定 における多項式時間アルゴリズムを提供する。
Sublinear-Time Reconfiguration of Programmable Matter with Joint Movements
本論文は、アモエボット構造の並列移動（ジョイントムーブメント）モデルにおいて、補助的な仮定なしに任意の構造をラウンドで線形構造へ再構成するサブリニア時間普遍再構成アルゴリズムを初めて提案し、このモデルが補助仮定なしに効率的な再構成を可能にすることを示した。
Sample-and-Search: An Effective Algorithm for Learning-Augmented k-Median Clustering in High dimensions
この論文は、予測器を用いて事前ラベル付けを行う学習強化型k-メディアンクラスタリング問題に対し、次元依存性を緩和し計算複雑性を大幅に改善する「サンプリング＆サーチ」という効率的なアルゴリズムを提案し、実験によりその有効性を示したものである。