A note on approximating the average degree of bounded arboricity graphs
この論文は、有界木次数グラフの平均次数を近似する Eden らのアルゴリズムを、パラメータ探索による対数因子の損失なしに完全な形で提示し、木次数と平均次数を用いた回のクエリで-近似を実現する方法を詳述するものである。
💻 Category
cs.CC
45 件の論文
The Power of Shallow-depth Toffoli and Qudit Quantum Circuits
この論文は、量子助言や中盤測定を備えた浅い深さの量子回路が古典的な定深回路よりも強力であることを示す新たな分離を証明し、無限サイズのゲート集合を用いた場合の高次元量子回路が標準的な量子ビット実装に対して追加の利点をもたらさないことを示しています。
Computational Complexity in Property Testing
この論文は、クエリ複雑性と時間複雑性の関係を体系的に研究し、時間 - クエリ階層定理の確立や半空間の距離近似問題における細粒度の時間下界の証明を通じて、プロパティテストにおける計算量的な困難性の地図を描き出すことを目指しています。
Deciding winning strategies in Yu-Gi-Oh! TCG is hard
この論文は、マジック：ザ・ギャザリングの先行研究に触発され、遊戯王 TCG における特定の計算可能な戦略が勝利するか否かを判定する問題が決定不能であり、実際には-完全であることを、現在の禁止・制限リストに準拠した具体的なデッキ構成を用いて証明したものである。
The Generation-Recognition Asymmetry: Six Dimensions of a Fundamental Divide in Formal Language Theory
この論文は、形式言語理論における生成と認識の間の本質的な非対称性を、計算複雑性や曖昧さなど新たに特定された 6 つの次元から包括的に分析し、両者が拡張的には等価であるにもかかわらず操作的にどのように異なるかを明らかにしています。
Fast polynomial computations with space constraints
この論文は、多項式計算における時間と空間の制約を考慮し、従来の高速アルゴリズムの空間効率を改善する手法と、疎多項式に対する準線形時間での補間アルゴリズムの提案など、空間制約下での効率的な多項式アルゴリズムの研究をまとめたものです。
Classical simulability of quantum circuits followed by sparse classical post-processing
この論文は、多項式サイズの量子回路にスパースな古典的後処理を施した系の古典的シミュレーション可能性を特徴づける必要十分条件を導き出し、さらに定深回路の場合には可換量子回路への効率的な還元を示すことで、その計算複雑性を明らかにしています。
Intrinsic Information Flow in Structureless NP Search
この論文は、シャノンの情報理論の観点から NP 問題の証発見を再解釈し、構造を持たない事前分布下で等価性プローブのみが可能な「psocid モデル」において、多項式回のプローブでは必要な情報を獲得できず、これが指数関数的な探索複雑性の情報論的な起源であることを示しています。
Maximum Partial List H-Coloring on P_5-free graphs in polynomial time
この論文は、任意の固定グラフ H に対して P_5 自由グラフ上の最大部分リスト H 彩色問題が多項式時間で解けることを示し、Agrawal らの SODA 2024 における未解決問題を解決するとともに、Chudnovsky らの SIDMA 2021 の結果を多項式時間アルゴリズムに改善したものである。
On complexity of restricted fragments of Decision DNNF
この論文は、決定 DNNF の制限されたクラス（特に-OBDD と構造化された決定 DNNF）の複雑性を調査し、有界な素木幅を持つ CNF に対する FPT サイズ表現と有界な incidence 木幅に対する XP サイズ表現の区別を再確認・証明するとともに、-OBDD に対する新たな下限証明手法の提案や Apply 操作の効率化、そして有界 incidence 木幅を持つ CNF に対して強力なモデルである「構造化-FBDD」の導入を行っている。
No exponential quantum speedup for anymore
2021 年に Chen らが提案した平均ケースの-Short Integer Solution（）問題に対する効率的な量子アルゴリズムは、本論文で提示された効率的な古典アルゴリズムにより、もはや指数関数的な量子高速化をもたらさないことが示されました。
A $4/3$ ratio approximation algorithm for the Tree Augmentation Problem by deferred local-ratio and climbing
この論文は、遅延局所比法とクライミング手法を用いて、木拡張問題（TAP）に対して $4/3O(m\sqrt{n})$ に抑えたことを報告しています。
Classification of Local Optimization Problems in Directed Cycles
この論文は、有向サイクルにおける局所最適化問題の分散計算複雑性を完全分類し、決定論的およびランダム化 LOCAL モデルにおける 4 つの複雑性クラスを特定するだけでなく、任意の問題と近似率に対してその複雑性クラスを自動的に判定し、非同期最適の分散アルゴリズムを効率的に合成するメタアルゴリズムを提案しています。
Why Are Linear RNNs More Parallelizable?
この論文は、線形 RNN が非線形 RNN と異なりトランスフォーマーと同様に並列化可能である理由を、線形 RNN が対数深さの算術回路（ 等）として記述できるのに対し、非線形 RNN は並列化の根本的な障壁となる P 完全問題などを解き得るという計算複雑性理論の観点から解明し、表現力と並列性の最適なバランスを設計するための基礎を提供しています。
Generalizing Fair Top- Selection: An Integrative Approach
本論文は、複数の保護グループを考慮した公平なトップ選択問題において、参照スコア関数からの乖離を最小化する課題の計算複雑性を分析し、特定の条件下で効率的なアルゴリズムを導出するとともに、重みの摂動に対して安定したスコア関数を得るための新たな「有用性損失」指標を導入し、実データを用いた実験でその有効性を示す統合的なアプローチを提案する。
Quantum Algorithms for Network Signal Coordination
この論文は、NP 完全問題であるネットワーク信号調整（NSC）問題およびその頑健な定式化に対して、グローバーの探索アルゴリズムを適用して二次的な高速化を実現し、そのシミュレーションおよび実量子コンピュータ上での実装を示したものである。
Attacking the Polynomials in the Maze of Finite Fields problem
この論文は、GMV による 2025 年 4 月の競技で提示された有限体上の多項式系に対し、構造的な疎性を活用して結果式を逐次計算することで単変数多項式を導出し、総当たり法や標準的なグレブナー基底法よりも大幅に高速に解を復元する「ResultantSolver」アルゴリズムを提案し、その有効性を実験的に検証したものである。
Recurrent Graph Neural Networks and Arithmetic Circuits
この論文は、再帰的グラフニューラルネットワーク（GNN）と実数上の再帰的算術回路の計算能力が等価であることを示し、両者の表現力に厳密な対応関係を確立しています。
ETH-Tight Complexity of Optimal Morse Matching on Bounded-Treewidth Complexes
この論文は、有界木幅の複体における最適モーシュマッチング問題に対して、$2^{O(k \log k)} n2^{o(k \log k)} n^{O(1)}$ 時間での解決が不可能であることを示すことで、この問題の ETH-tight な複雑性を決定づけたものである。
Aaronson-Ambainis Conjecture Is True For Random Restrictions
本論文は、Aaronson-Ambainis 予想が、分散が十分に高い多項式に対して、ランダムな制限を施した非無視可能な割合のケースにおいて成り立つことを示したものである。