Hardness of the Binary Covering Radius Problem in Large Norms
本論文は、 が約 35.31 より大きい場合の ノルムにおける格子の被覆半径問題（）が、特定の近似因子で -困難であることを初めて証明し、Manurangsi による ノルムでの結果を拡張したものである。
💻 Category
cs.CC
45 件の論文
d-QBF with Few Existential Variables Revisited
この論文は、存在量化変数の数 をパラメータとする d-QBF 問題において、一般には ETH 仮説の下で $2^{2^{o(k)}}\forall\exists$-QBF）に限定された場合にはより効率的なアルゴリズムとほぼ最適な下界を示すことで、既存研究のギャップを埋める結果を報告しています。
Reinforced Generation of Combinatorial Structures: Ramsey Numbers
この論文は、LLM ベースのコード変異エージェント「AlphaEvolve」を用いて、5 つの古典的ラムゼー数（、、、、）の既知の下限値をそれぞれ 1 ずつ引き上げる新たな結果を達成し、従来の個別の検索アルゴリズムに代わる単一のメタアルゴリズムとして機能したことを報告しています。
A Simple Constructive Bound on Circuit Size Change Under Truth Table Perturbation
この論文は、真理値表の一点変更による回路サイズの増大がで抑えられることを明示的に示し、一般のハミング距離への拡張やにおける AIG 基底での厳密な検証を通じて、この境界がでタイトであることを確認したものである。
The framework to unify all complexity dichotomy theorems for Boolean tensor networks
本論文は、ブールテンソルネットワークの複雑性二分定理を統合する包括的な枠組みを提案し、未解決問題が複素数上の 2 次元行列で構成される有限群として分類され、その 9 つのケースについて行列形式の簡略化や四元数部分群の障壁、循環群の場合の進展と解決を論じている。
Almost-Optimal Upper and Lower Bounds for Clustering in Low Dimensional Euclidean Spaces
この論文は、低次元ユークリッド空間における-median および-means 問題の-近似アルゴリズムの実行時間を大幅に改善し、さらに Gap Exponential Time 仮説の下でその実行時間の下限がほぼ一致することを示しています。
Has quantum advantage been achieved?
この論文は、量子優位性が実際に達成されたという主張を支持し、その理論と実験における次のステップを概説しています。
Tetris is Hard with Just One Piece Type
この論文は、特定の回転システム下で Tetris のクリアや生存問題が、O 型のテトロミノを除くすべてのテトロミノ（I 型を含む）の単一ピースタイプに制限された場合でも NP 困難であることを証明し、I 型のみに関する 23 年前の予想を否定するとともに、ドミノや特定の条件下の 1×k ピースについては多項式時間アルゴリズムを構築したことを示しています。
Quantum Automating -Frege Is LWE-Hard
この論文は、学習付き誤差（LWE）仮定の下では、量子アルゴリズムが-Frege 証明系を効率的に自動化できないことを示し、量子計算と命題論理証明探索の間の初めての相互作用を確立したものである。
Privately Estimating Black-Box Statistics
この論文は、感度 bound が不明なブラックボックス関数に対する差分プライバシー推定において、統計的効率とオラクル効率のトレードオフを可能にする新たな手法とその最適性下限を提示するものである。
Polynomial-time isomorphism test for -generated extensions of abelian groups
この論文は、有限環の単位群を多項式時間で計算する新規アルゴリズムを開発し、 個の生成元を持つ群によるアーベル群の拡張（特にアーベル群の循環群拡張や単純群拡張）に対する群同型判定問題を多項式時間で解決する手法を提示しています。
Three Fixed-Dimension Satisfiability Semantics for Quantum Logic: Implications and an Explicit Separator
この論文は、固定次元のヒルベルト空間における量子論理の 3 つの充足可能性意味論（標準的、大域的交換、局所的部分ブール）を比較し、標準的意味論では充足可能だが他の 2 つでは充足不可能な明示的な分離式「SEP-1」を構成することで、それらの充足可能性クラスが厳密に異なることを示しています。
A base change framework for tensor functions
この論文は、任意の体上のテンソル関数に関する結果を一般化するための基底変換の枠組みを確立し、それによって任意の体における3-テンソルのスライスランクと幾何学的ランクの線形有界性や、スライスランクの準超乗法的性およびその漸近存在性を証明しています。
Complexity Lower Bounds of Small Matrix Multiplication over Finite Fields via Backtracking and Substitution
この論文は、置換法と系統的なバックトラック探索を組み合わせる新たな手法により、有限体 上の $3 \times 3$ 行列乗算の双線形複雑度の下界を従来の 19 から 20 に引き上げる証明を、自動的かつ効率的に達成したことを報告しています。
On Factorization of Sparse Polynomials of Bounded Individual Degree
本論文は、個々の変数の次数が有界な疎多項式の因数分解に関する構造結果とアルゴリズムを確立し、疎多項式の因数の列挙や黒箱アクセスからの復元を多項式時間で可能にする新たな手法を提案しています。
The Theory and Practice of Computing the Bus-Factor
本論文は、プロジェクトのリスク指標であるバスファクターを、人員とタスクの二部グラフに基づく統一的な枠組みで定式化し、その計算がNP困難であることを証明するとともに、ネットワークの頑健性に基づいた新たな指標と効率的な近似アルゴリズムを提案し、既存手法よりも優れたリスク評価を実現することを示しています。
Quantum information advantage based on Bell inequalities
Kretschmer らの実験的提案とは異なり、並列反復 CHSH ゲームから導かれる関係に基づき、情報量に基づくメモリ測定、効率的な検証者、そしてノイズに頑健かつより効率的な量子プロバーを特徴とする量子情報優位性の新たな提案がなされています。
The Unit Gap: How Sharing Works in Boolean Circuits
この論文は、AND と NOT を用いたブール回路において、回路サイズと論理式サイズの差が常に 0 または 1 であることを証明し、その差が 1 となる条件や共有の必要性に関する厳密な定理を確立したものである。
Permutation Match Puzzles: How Young Tanvi Learned About Computational Complexity
この論文は、グリッドの行と列に昇順または降順の制約を課す「置換マッチパズル」の解の存在条件を完全特徴付けし、解の数をフック長公式で記述するとともに、解がない場合の最小修正アルゴリズムを提案し、制約を一般の置換に拡張した場合には最小修正問題が NP 完全であることを示しています。
Intrinsic Sequentiality in P: Causal Limits of Parallel Computation
この論文は、因果的実行がインスタンス仕様の一部である多項式時間決定問題を研究し、情報理論的限界により、その処理が本質的に直列的であり、並列計算による漸近的な高速化が不可能であることを示しています。