Huffman-Bucket Sketch: A Simple Algorithm for Cardinality Estimation
HyperLogLog スケッチを、そのランク分布の集中性を利用したハフマン符号化とバケット化により、合併性を維持しつつ ビットという最適空間に圧縮し、実用的な基数推定アルゴリズムとして機能する「Huffman-Bucket Sketch」を提案する論文です。
💻 Category
cs.DS
87 件の論文
Simple minimally unsatisfiable subsets of 2-CNFs
この論文は、2-CNF の最小非充足部分集合（MUS）の認識を線形時間で行う手法を提示し、欠陥 1 の MUS に関する既存の NP 完全性の結果を拡張するとともに、単項節を含む特定の MUS の発見が多項式時間で可能であることを示すことで、2-CNF の MUS における易解・難解な領域の理解を深めることを目指しています。
Linear-Scaling Tensor Train Sketching
本論文は、テンソル積形式に特化した構造化ランダム射影「ブロック疎テンソル・トレイン・スケッチ（BSTT）」を提案し、その線形スケーリング特性とオプシブ部分空間埋め込み・注入の理論的保証を示すことで、QB 分解やランダム化 TT 丸めなどのアルゴリズムにおける誤差 bound を改善し、合成テンソルや量子化学応用における数値実験でその有効性を検証したものである。
Separating Oblivious and Adaptive Differential Privacy under Continual Observation
この論文は、継続的観測モデルにおけるオブリビアス設定と適応的設定の差分プライバシーの間に明確な分離が存在することを示し、特定の相関ベクトルクエリ問題に対してオブリビアス設定では指数関数的な時間ステップまで正確なアルゴリズムが存在する一方、適応的設定では定数ステップで精度が失われることを証明して、Jain らが提起した未解決問題を解決しました。
Instruction set for the representation of graphs
この論文は、任意の有限単純グラフを 9 文字の命令アルファベットからなるコンパクトな文字列として表現する「IsalGraph」という手法を提案し、その文字列がグラフ同型不変であり、グラフ編集距離と強い相関を持つことを示しています。
Testing Graph Properties with the Container Method
この論文は、グラフの容器法（graph container method）を拡張することで、密グラフモデルにおける-clique 性および-彩色性のテストに関するサンプル複雑性のほぼ最適な境界を確立したことを示しています。
Online Flexible Busy Time Scheduling on Heterogeneous Machines
この論文は、クラウドコンピューティングの現実的なモデルである異種マシン環境におけるオンライン繁忙時間スケジューリング問題を取り上げ、単位長さのジョブに対して競争比 8 のアルゴリズムを設計し、非ネスト型区間の場合に tight となる競争比 2 の下限を示すことで、この分野の理解を大きく進展させたものです。
Path Cover, Hamiltonicity, and Independence Number: An FPT Perspective
この論文は、グラフの頂点を独立集合のサイズ以下でパスで覆うことを保証するガリ・ミルグラムの定理を拡張し、独立集合のサイズをパラメータとする固定パラメータ可解（FPT）アルゴリズムを構築することで、パス被覆の最小化判定やハミルトニアンの決定など、従来未解決だった複数のグラフ理論問題を解決したことを報告しています。
-Motif: Parallel Subgraph Isomorphism via Tabular Operations
本論文は、サブグラフ同型性をデータベース操作として再定式化し、NVIDIA RAPIDS や Pandas などの成熟したライブラリを活用して GPU 上で並列処理を実現する「-Motif」というアルゴリズムを提案し、既存手法 VF2 と比較して最大 595 倍の高速化を達成するとともに量子回路コンパイルなどの分野への応用可能性を示したものである。
Space-efficient B-tree Implementation for Memory-Constrained Flash Embedded Devices
本論文は、農業・環境・産業モニタリングなどの IoT 用途向けに、リソースが制約された組み込みデバイス上でも効率的に動作する B 木の実装変種を開発・評価し、ストレージ固有の最適化が大幅な性能向上をもたらすことを示しています。
How to Sort in a Refrigerator: Simple Entropy-Sensitive Strictly In-Place Sorting Algorithms
この論文は、冷蔵庫などの組み込みシステム向けに、入力配列のランベースエントロピーに依存する最適時間 O(n(1+H(A))) で動作し、かつ入力以外の追加メモリを O(1) のみ使用する厳密な場内ソートアルゴリズムを初めて提案するものである。
Agnostic learning in (almost) optimal time via Gaussian surface area
この論文は、ガウス表面積がの概念クラスに対するアグノスティック学習の多項式次数の上限を、既存のからへと改善し、統計的クエリモデルにおける多項式閾値関数の学習複雑性に対してほぼ最適な結果をもたらすことを示しています。
Forwarding Packets Greedily
この論文は、線形ネットワークにおけるオンラインパケット転送問題（最大フロー時間の最小化）において、各パケットが 1 つまたは 2 つのルーターを経由する特殊なケースに対し、新たな貪欲アルゴリズムが $2-2^{1-k}4/3O(1)$ 競争アルゴリズムの存在に関する未解決問題への最初の進展を提供することを述べています。
Transversal Rank, Conformality and Enumeration
この論文は、ハイパーグラフの横断ランク判定と最小ハッティング集合の列挙に関する既存のアルゴリズムの限界を分析し、先読み手法を用いた新たな高速アルゴリズムを提案するとともに、さらに高速化が可能かどうかを-共形ハイパーグラフの認識や均一ハイパーグラフの列挙といった重要な組合せ論的問題との同値性によって特徴づけています。
Induced Minors and Coarse Tree Decompositions
この論文は、完全二部グラフとグリッドを誘導小グラフとして含まないグラフに対して、各バッグの独立数が対数多項式で抑えられる木分解の存在を証明するChudnovskyらの予想の弱い版を示すとともに、距離 8 独立数に関する新たな結果も導出しています。
Graph Generation Methods under Partial Information
この論文は、二部グラフ、有向グラフ、無向グラフの次数列を指定されたグラフ生成問題に対し、各ステップでの接続数を特徴付ける必要十分条件を導出する逐次手法を提案し、大規模インスタンスにおいても既存手法よりも優れたスケーラビリティを持つ列挙・サンプリングアルゴリズムを開発したことを報告しています。
The Complexity of Distance- Dominating Set Reconfiguration
本論文は、距離支配集合再構成問題について、の場合に分割グラフ上で多項式時間アルゴリズムを構築し複雑性の二項性を示す一方、平面グラフや二部グラフ、弦グラフなど他のグラフクラスではで完全であることを証明する結果を報告しています。
Weighted Reservoir Sampling With Replacement from Data Streams
この論文は、データストリームから重みに比例した確率で要素を復元抽出する新しい手法を提案し、その正当性と効率性を理論的に証明するとともに、実験を通じて既存手法との性能比較を行ったものである。
Efficient Computation of Time-Index Powered Weighted Sums Using Cascaded Accumulators
この論文は、大規模なデータブロックの保存や多数の乗算を不要とし、カスケード型アキュムレータを用いることで、時間インデックスのべき乗が重み付けされた和を極めて効率的に計算する新規手法を提案しています。
On the Polynomial Kernelizations of Finding a Shortest Path with Positive Disjunctive Constraints
本論文は、正の排他的制約付き最短経路問題の固定パラメータ tractability を研究し、解のサイズや制約グラフの構造的性質といったパラメータ化に対して、多項式サイズのコア化や固定パラメータ可決性アルゴリズムを確立するものである。