cs.DS 件の論文 | Gist.Science

Dynamic Kernel Graph Sparsifiers

この論文は、点の位置が逐次変化する幾何グラフに対して、 $n^{o(1)}$ の更新時間でスペクトルスパースファイアを維持する完全動的データ構造と、適応的敵に対する頑健性、および行列ベクトル積の高速な維持を実現するランダム化スケッチ手法を提案するものである。

Yang Cao, Yichuan Deng, Wenyu Jin + 4 more2026-03-05💻 cs

An Objective Improvement Approach to Solving Discounted Payoff Games

本論文は、割引報酬ゲームの最適解を対称的に導出するため、すべてのエッジからなる制約系と誤差最小化の目的関数を組み合わせた新たな収束手法を提案し、戦略改善と値反復の二項対立を越えるアプローチを示すものである。

Daniele Dell'Erba, Arthur Dumas, Sven Schewe2026-03-05💻 cs

A computational transition for detecting correlated stochastic block models by low-degree polynomials

この論文は、相関する疎な確率的ブロックモデルと独立なエルデシュ・レーニィグラフの区別問題において、低次多項式に基づく検出が可能な閾値が、オッター定数とケステン・スティグム閾値のいずれか小さい方によって決定されることを示しています。

Guanyi Chen, Jian Ding, Shuyang Gong + 1 more2026-03-05🤖 cs.LG

Highway Dimension: a Metric View

この論文は、格子グラフやユークリッド平面などの自然な計量空間も包含するように「ハイウェイ次元」の定義を近似最短経路を用いて緩和し、これに基づいてTSPに対するPTASを構築するとともに、パッド分解やスパースカバリングなどの計量ツールキットを開発して多数の応用を実現したものである。

Andreas Emil Feldmann, Arnold Filtser2026-03-05💻 cs

On the Inversion Modulo a Power of an Integer

この論文は、任意の整数 $n$ と $k$ に対する $a^{-1} \pmod{n^k}$ の計算を可能にする新しいアルゴリズムを提案し、さらに Dumas や Hurchalla による素数べきの法に関する手法を一般の整数 $n$ のべき $n^{2^s}$ へ拡張する一般化されたアルゴリズムを導出するものである。

Guangwu Xu, Yunxiao Tian, Bingxin Yang2026-03-05💻 cs

Even Faster Kernel Matrix Linear Algebra via Density Estimation

本論文は、カーネル密度推定（KDE）を用いることで、カーネル行列の行列ベクトル積やスペクトルノルムなどの線形代数タスクにおける計算時間を、既存の最良アルゴリズムよりも特に誤差 $\varepsilon$ とデータ数 $n$ の依存関係において大幅に改善する手法を提案し、同時にその限界を示す下界も示している。

Rikhav Shah, Sandeep Silwal, Haike Xu2026-03-05🤖 cs.LG

Deterministic Coreset for Lp Subspace

本論文は、任意の $p \in [1,\infty)$ に対して対数因子を除去した最適サイズの決定論的 $\varepsilon$ -コアセットを構築する初めての反復アルゴリズムを提案し、これにより $\ell_p$ 部分空間埋め込みおよび $\ell_p$ 回帰問題を決定論的に近似可能にしたことを示しています。

Rachit Chhaya, Anirban Dasgupta, Dan Feldman + 1 more2026-03-05🤖 cs.LG

Submodular Maximization over a Matroid $k$ -Intersection: Multiplicative Improvement over Greedy

本論文は、 $k$ 個の任意のマトロイド制約の交差下での非負単調サブモジュラ関数の最大化問題に対し、自然な貪欲法が保証する $(k+1)$ 倍近似を初めて超える乗法的改善（約$0.819k $倍）を達成するアルゴリズムを提案し、その手法は非単調な場合やより一般的なマトロイド$ k$-パリティ制約にも適用可能であることを示しています。

Moran Feldman, Justin Ward2026-03-05💻 cs

Skirting Additive Error Barriers for Private Turnstile Streams

この論文は、差分プライバシー下でのターンスタイルストリームにおける別個アイテム数や $F_2$ モーメントの継続的推定において、従来の多項式加算誤差の下限を、多項対数レベルの乗算誤差と加算誤差を許容することで回避し、かつ多項対数空間で実現可能なアルゴリズムを提案するものである。

Anders Aamand, Justin Y. Chen, Sandeep Silwal2026-03-05💻 cs

Bounding the Average Move Structure Query for Faster and Smaller RLBWT Permutations

この論文は、長い区間を切り詰めるという単純な分割手法（長さキャッピング）を用いることで、RLBWT 置換の平均クエリ時間を最適化し、構成時間を向上させるとともに、表現サイズを削減して理論的・実用的な利点を両立させる手法を提案し、その有効性を実験で検証したものである。

Nathaniel K. Brown, Ben Langmead2026-03-05💻 cs

DRESS: A Continuous Framework for Structural Graph Refinement

この論文は、グラフの構造的類似性を反復的に洗練させて同型不変な「指紋」を生成する決定論的かつパラメータ不要なフレームワーク「DRESS」を提案し、その拡張版であるΔ-DRESS が 2-Weisfeiler-Leman テスト以上の表現力を持ちながら計算コストが低く、強正則グラフベンチマークや CFI 階梯において優れた性能を示すことを示しています。

Eduar Castrillo Velilla2026-03-05🤖 cs.LG

← 前へ

cs.DS