概要 - 「1-in-3-SATの強いスパーサイズ化：多項式Freiman-Ruzsa」
タイトル
「1-in-3-SATの強いスパーサイズ化：多項式Freiman-Ruzsa」
時間
2025-07-23 19:11:32
著者
{"Benjamin Bedert","Tamio-Vesa Nakajima","Karolina Okrasa","Stanislav Živný"}
カテゴリ
{cs.DS,cs.CC,cs.DM,math.CO}
リンク
http://arxiv.org/abs/2507.17878v1
PDF リンク
http://arxiv.org/pdf/2507.17878v1
概要
論文「Polynomial Freiman-Ruzsaを用いた1-in-3-SATの強いスパース化」では、変数が制約の削除の代わりに統合されるという新しいスパース化の概念、強いスパース化が提案されています。著者たちは、1-in-3-SAT問題に対する強いスパース化アルゴリズムを提案し、これまでの二次的な上界を改善しました。 この論文の主要な技術的成果は、多項式Freiman-Ruzsa定理を使用して得られた、F_d^2の中の特定のベクトル集合のサイズに対する二次以下の界です。この結果は独立した興味を持つ可能性があります。 また、著者たちは、強いスパース化アルゴリズムを用いて、3-ユニフォームハイパーグラフの線形順序の着色を近似する最も進んだアルゴリズムを改善しました。 主要な貢献： * 強いスパース化の概念を導入。 * 二次以下の性能を持つ1-in-3-SATに対する強いスパース化アルゴリズムを提案。 * 多項式Freiman-Ruzsa定理を使用して、F_d^2の中の特定のベクトル集合のサイズに対する二次以下の界を得る。 * 強いスパース化アルゴリズムを用いて、3-ユニフォームハイパーグラフの線形順序の着色を近似する最も進んだアルゴリズムを改善。
推奨論文
未来の知能のためのヴォン・ノイマンのアーキテクチャを強化する
JWB-DH-V1：第1版 联合全身トーカングアバターや音声生成のベンチマーク
高速計算深熱化
特徴なし回帰クリージング
最もシンプルな非局在化量子臨界点のブートストラッピング
感情記憶リンク：記憶性アノテーションがインテリジェントシステムにとって重要か？
非屏蔽環境で動作するMRIスキャナーに対する電磁干渉を減少させるための主題の接地
予算制約下での長期資産管理のための階層的ディープレインforcement learningフレームワーク
CRAFT: エッジ-フォグ環境におけるノード配置のための遺伝子ベースの遅延とコスト意識フレームワーク
ツイートを用いた混合専門家による説明可能な株価予測の学習