概要 - デ・モルگان基底におけるブール関数の正確な表現と近似表現

タイトル
デ・モルگان基底におけるブール関数の正確な表現と近似表現

時間
2025-07-18 14:27:11

著者
{"Arkadev Chattopadhyay","Yogesh Dahiya","Shachar Lovett"}

カテゴリ
{cs.CC}

リンク
http://arxiv.org/abs/2507.13963v1

PDF リンク
http://arxiv.org/pdf/2507.13963v1

概要

この論文は、デ・モルガン基底におけるボルツァン関数の正確な表現と近似表現の関係を調査しています。著者たちは、関数を表す多項式の稀疏性とその近似表現の稀疏性が対数スケールで多項式関係にあることを証明しています。この結果は、度数、稀疏性、係数の総重量などの様々な複雑さの測定基準に影響を与えます。 主定理は、全ての全ボルツァン関数fに対して、近似稀疏性の対数はO(log^2 sparpf) + log nであると述べています。これは、デ・モルガン基底における全てのボルツァン関数の近似が稀疏性を顕著に減少させないことを意味します。 著者たちは、この結果を証明するために新しいランダム制限法を使用しています。多くの既存のランダム制限法とは異なり、彼らの方法は適応的で、制限プロセス中に様々な複雑さの測定基準がどのように簡略化されるかに基づいています。 論文はまた、デ・モルガン基底におけるボルツァン関数の正確な表現と近似l1ノルムの類似な結果を証明しています。この結果は、デ・モルガン基底における全ボルツァン関数の近似がl1質量を顕著に減少させないことを示しています。 著者たちはさらに、一般化された多項式と単調関数への結果を一般化しています。彼らは、単調関数に対して、正確な近似一般化稀疏性とl1ノルムが対数スケールで多項式関係にあることを示しています。 この論文の結果は、複雑さ理論、通信複雑さ、学習理論を含む様々なコンピュータサイエンスの分野に影響を与えます。ボルツァン関数とその表現の近似の力に関する新たな洞察を提供しています。


推奨論文

稀疏自動エンコーダが小規模遺伝子言語モデルにおける解釈可能な構造を明らかにする

デザインアルゴリズムの分析と平面六角パネルを用いたグラフベースの二重曲率構造の製作

ノイズ軽減のための量子壁状態と永遠の純度界限

アイアンマン：プライバシープレスerving AIのための近メモリ処理を用いた忘却伝送拡張の加速

無限次元の転移確率行列の推定：一般化された階層的棒割りプロセスを用いて

SynC: ゼロショット画像キャプションのための1対多マッピングを用いた合成画像キャプションデータセットの精査

アーキヴァース：没入感のある文化遺産へのアプローチ

クラウドにおけるHSMおよびTPMセキュリティの再考：現実の攻撃と次世代の防御策

フロー・マッチングが生物学と生命科学に遭遇する：一つの調査

5Gにおけるアクティブ攻撃耐性：認証とキー合意の新しいアプローチ