Sketching, Moment Estimation, and the Lévy-Khintchine Representation Theorem
この論文は、レヴィ過程へのハッシュという新たなアイデアとレヴィ・ヒンチンの表現定理を用いることで、ターンstileストリーミングモデルにおける多様な-モーメント推定を統一的に記述・一般化する汎用的なスキームを提案し、既存の手法の統合や未分類の関数の扱いやすさを示したものである。
💻 Category
cs.DS
87 件の論文
Stochastic and incremental subgradient methods for convex optimization on Hadamard spaces
この論文は、非線形構造を持つハダマード空間における凸最適化の課題を解決するため、ブセマン関数に基づく新たな部分勾配の概念を提案し、これにより確率的および増分部分勾配法の一般化と複雑性保証、ならびに BHV 樹空間におけるメディアン計算などの応用を可能にしています。
Beware of the Classical Benchmark Instances for the Traveling Salesman Problem with Time Windows
この論文は、古典的なベンチマークインスタンスの構造を突くことで極めて短時間で最適解が得られることを示し、これらのインスタンスが現在では TSPTW-M 問題の評価基準として適切でなくなったと結論付けています。
Time warping with Hellinger elasticity
任意の距離空間に値を持つ時系列のマッチング問題に対し、ヘリングカーネルを伸縮ペナルティとして用いる最適化手法「弾性時間歪み（Elastic Time Warping）」アルゴリズムを提案し、その計算量を立方（O(n³)）に抑えている。
bsort: A theoretically efficient non-comparison-based sorting algorithm for integer and floating-point numbers
この論文は、整数および浮動小数点数に対して、バイナリクイックソートに由来する手法を統合し、要素の語長 に対して の実行時間と の補助空間で動作する「bsort」という非比較ソートアルゴリズムを提案し、特に語長が小さいデータ型において既存の高度に最適化されたハイブリッドアルゴリズムと競合する性能を示すことを述べています。
Unit Interval Selection in Random Order Streams
この論文は、敵対的順序ではなく一様ランダム順序で入力される単位区間選択問題において、最適解のサイズに比例する空間で$0.74018/9\Omega(n)$の空間が必要であることを示しています。
A PTAS for Weighted Triangle-free 2-Matching
この論文は、重み付き三角形フリー 2 一致問題（WTF2M）に対して、単純な局所探索アルゴリズムと非自明な解析に基づき、任意の定数に対して多項式時間-近似アルゴリズム（PTAS）を提案するものである。
Fast and Optimal Differentially Private Frequent-Substring Mining
この論文は、Bernardini らの PODS'25 における既存手法の空間・時間計算量の課題を克服し、近似的に最適な誤差を保ちながら、頻出部分文字列マイニングを微分プライバシー条件下で の空間と の時間で実現する新しいアルゴリズムを提案するものである。
Better Bounds for the Distributed Experts Problem
この論文は、分散エキスパート問題において、通信量を最小化しつつ regret を改善する新しいプロトコルを提案し、既存の研究を上回る性能を示しています。
On the Online Weighted Non-Crossing Matching Problem
この論文は、ユークリッド平面上のオンライン重み付き非交差マッチング問題について、決定論的アルゴリズムの限界、重み制限下およびランダム化アルゴリズムによる定数競争比の達成可能性、取り消しや共線点などのバリエーション、および最適解を得るためのアドバイス複雑性の改善された限界を研究したものである。
A Critical Pair Enumeration Algorithm for String Diagram Rewriting
この論文は、対称モノイダル圏における文字列図の書き換えシステム（フロベニウス構造を含まない場合）の完全性解析を自動化し、ハイパーグラフ操作によってすべての臨界対を列挙するアルゴリズムを提案し、その正しさと網羅性を証明するものである。
Almost-Optimal Upper and Lower Bounds for Clustering in Low Dimensional Euclidean Spaces
この論文は、低次元ユークリッド空間における-median および-means 問題の-近似アルゴリズムの実行時間を大幅に改善し、さらに Gap Exponential Time 仮説の下でその実行時間の下限がほぼ一致することを示しています。
Critical Relaxed-Stable Matchings with Ties in the Many-to-Many Setting
この論文は、両側にタイと下限クォータが存在する多対多マッチング問題において、下限クォータを最大限満たす「クリティカル」かつ「緩和安定」なマッチングが常に存在し、その最大基数を求める問題は NP 困難であるが、多項式時間で最大基数の 2/3 を保証する近似アルゴリズムを提案することを示しています。
Optimizing Sparse SYK
本論文は、疎な SYK モデルにおいて、 の条件下でガウス状態を用いた古典アルゴリズムが定数倍近似を達成できない一方、Hastings-O'Donnell の量子アルゴリズムが定数倍近似を達成し続けることを証明し、両者の計算複雑性の分離を示しています。
Privately Estimating Black-Box Statistics
この論文は、感度 bound が不明なブラックボックス関数に対する差分プライバシー推定において、統計的効率とオラクル効率のトレードオフを可能にする新たな手法とその最適性下限を提示するものである。
Exploration Space Theory: Formal Foundations for Prerequisite-Aware Location-Based Recommendation
この論文は、知識空間理論を位置情報推薦に応用し、訪問地点間の前提依存関係を格子論的に定式化した「探索空間理論（EST）」を提案し、その数学的構造に基づいて構造的妥当性が保証された推薦システム（ESRS）を構築することを目的としています。
Multi-Agent Reinforcement Learning with Submodular Reward
この論文は、エージェントの貢献が重複する現実的なシナリオをモデル化する部分モジュラ報酬を備えた協調マルチエージェント強化学習の枠組みを初めて提案し、既知および未知のダイナミクス下でそれぞれ多項式時間の近似保証と regret 保証を持つアルゴリズムを開発したものである。
A Class of Unrooted Phylogenetic Networks Inspired by the Properties of Rooted Tree-Child Networks
この論文は、木の子ネットワークの性質に着想を得た新しい無根系統ネットワークのクラス「-cuttable ネットワーク」を提案し、これが多項式時間で認識可能であり、 の場合に木包含問題が多項式時間で解けるなど、計算機科学的に有用な性質を持つことを示しています。
Complexity Lower Bounds of Small Matrix Multiplication over Finite Fields via Backtracking and Substitution
この論文は、置換法と系統的なバックトラック探索を組み合わせる新たな手法により、有限体 上の $3 \times 3$ 行列乗算の双線形複雑度の下界を従来の 19 から 20 に引き上げる証明を、自動的かつ効率的に達成したことを報告しています。
Approximating Tensor Network Contraction with Sketches
本論文は、既存の手法が非巡回テンソルネットワークに限定されていたのに対し、循環を含む任意のテンソルネットワークの縮約を近似する初の手法を提案するとともに、巡回なしのネットワークに対しては縮約数に対して多項式時間で計算可能な効率的な手法も併せて提示するものである。