論文の概要: On the weight and density bounds of polynomial threshold functions

• arxiv url: http://arxiv.org/abs/2007.02509v1
• Date: Mon, 6 Jul 2020 03:16:13 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-13 03:30:25.594980
• Title: On the weight and density bounds of polynomial threshold functions
• Title（参考訳）: 多項式しきい値関数の重みと密度境界について
• Authors: Erhan Oztop and Minoru Asada
• Abstract要約: n-変数ブール関数はすべて、0.75倍の2n$非ゼロ整数係数を持つしきい値関数(PTF)として表せることを示す。 ベント函数の特別な場合も解析され、任意のn-変数ベント函数が2n$未満の整数係数で表せることを示した。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this report, we show that all n-variable Boolean function can be represented as polynomial threshold functions (PTF) with at most $0.75 \times 2^n$ non-zero integer coefficients and give an upper bound on the absolute value of these coefficients. To our knowledge this provides the best known bound on both the PTF density (number of monomials) and weight (sum of the coefficient magnitudes) of general Boolean functions. The special case of Bent functions is also analyzed and shown that any n-variable Bent function can be represented with integer coefficients less than $2^n$ while also obeying the aforementioned density bound. Finally, sparse Boolean functions, which are almost constant except for $m << 2^n$ number of variable assignments, are shown to have small weight PTFs with density at most $m+2^{n-1}$.
• Abstract（参考訳）: 本報告では、すべての n-変数ブール関数を、最大で0.75 \times 2^n$非ゼロ整数係数を持つ多項式しきい値関数(PTF)として表すことができ、これらの係数の絶対値に上限を与える。 我々の知る限り、これは一般ブール関数の PTF 密度(単項数)と重み(係数の大きさの仮定)の両方に最もよく知られた境界を与える。 ベント函数の特別な場合も解析され、任意の n-変数ベント函数が 2^n$ 未満の整数係数で表される一方で、上記の密度境界も従うことが示される。 最後に、変数代入の$m <<2^n$の数を除いてほとんど定数であるスパースブール函数は、最も密度が高い$m+2^{n-1}$の小さな重み付き PTF を持つことを示す。

関連論文リスト

• On the second-order zero differential properties of several classes of power functions over finite fields [4.100056500795057]
  Feistel Boomerang Connectivity Table (FBCT) は、差動攻撃やブーメラン攻撃などの攻撃に対するFeistelネットワークベースの暗号の抵抗を分析するための重要な暗号解析手法である。 本稿では、有限体上の特定の方程式の解数を計算することにより、パワー関数の2階ゼロ微分スペクトルをx2m+3$およびx2m+5$で明示的に決定する。 これらのエントリと各テーブルの濃度の計算は、Sボックスの微分およびブーメラン暗号解析を容易にすることを目的としている。
  論文  参考訳（メタデータ） (2024-09-18T04:27:03Z)
• Shift-invariant functions and almost liftings [0.0]
  我々は、$k$ビット上のブール関数から誘導される$n$ビット上のシフト不変ベクトルブール関数を$kleq n$に対して検討する。 直径$k$の関数がほぼ持ち上げである場合、誘導関数の最大衝突数は、任意の$n$に対して2k-1$である。 暗号特性が良好で、非客観性が重大なセキュリティ上の弱点を生じさせないような、ほとんど持ち上げのクラスの関数を探索する。
  論文  参考訳（メタデータ） (2024-07-16T17:23:27Z)
• On Symmetric Pseudo-Boolean Functions: Factorization, Kernels and Applications [0.0]
  任意の対称擬ブール函数が、同値に級数や分解として表せることを証明する。 これらの結果を用いて、スピングラスエネルギー関数、量子情報、テンソルネットワークの文献に現れる対称擬ブール関数を解析する。
  論文  参考訳（メタデータ） (2022-09-29T18:00:07Z)
• Infinite quantum signal processing [1.3614427997190908]
  量子信号処理(QSP)は、次数$d$の真のスカラーを表す。 QSPは多種多様なポリノミカル関数を表現できることを示す。 解析の結果,対象関数の正則性と因子の減衰特性との間には,驚くべき関連性があることが判明した。
  論文  参考訳（メタデータ） (2022-09-21T07:50:26Z)
• Shallow neural network representation of polynomials [91.3755431537592]
  d+1+sum_r=2Rbinomr+d-1d-1[binomr+d-1d-1d-1[binomr+d-1d-1d-1]binomr+d-1d-1d-1[binomr+d-1d-1d-1]binomr+d-1d-1d-1]
  論文  参考訳（メタデータ） (2022-08-17T08:14:52Z)
• Reachable sets for two-level open quantum systems driven by coherent and incoherent controls [77.34726150561087]
  我々はコヒーレントかつ非コヒーレントな制御によって駆動される2レベル開量子系の全密度行列の集合における制御性について研究する。 2つのコヒーレント制御に対して、系は全密度行列の集合において完全に制御可能であることが示されている。
  論文  参考訳（メタデータ） (2021-09-09T16:14:23Z)
• Neural networks with superexpressive activations and integer weights [91.3755431537592]
  アクティベーション関数の例 $sigma$ は、アクティベーションを持つネットワーク $sigma, lfloorcdotrfloor$, integer weights と固定アーキテクチャが与えられる。 より古い連続関数の $varepsilon$-approximation に必要な整数ウェイトの範囲が導出される。
  論文  参考訳（メタデータ） (2021-05-20T17:29:08Z)
• Finding Global Minima via Kernel Approximations [90.42048080064849]
  関数評価のみに基づく滑らかな関数のグローバル最小化を考える。 本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。
  論文  参考訳（メタデータ） (2020-12-22T12:59:30Z)
• Finite-Function-Encoding Quantum States [52.77024349608834]
  任意の$d$値論理関数を符号化する有限関数符号化(FFE)を導入する。 それらの構造的特性について検討する。
  論文  参考訳（メタデータ） (2020-12-01T13:53:23Z)
• Minimum Width for Universal Approximation [91.02689252671291]
  我々は、$Lp$関数の普遍近似に必要な最小幅がちょうど$maxd_x+1,d_y$であることを証明する。 また、同じ結論がReLUと一様近似に当てはまるのではなく、追加のしきい値アクティベーション関数で成り立つことを証明している。
  論文  参考訳（メタデータ） (2020-06-16T01:24:21Z)
• Densities of Almost Surely Terminating Probabilistic Programs are Differentiable Almost Everywhere [1.911678487931003]
  再帰と条件付き高次統計確率プログラムの微分特性について検討する。 この研究の副産物は、実パラメータを持つほぼ確実に決定論的(S)PCFプログラムがほぼすべての微分可能性を持つ関数を表すことである。
  論文  参考訳（メタデータ） (2020-04-08T10:40:14Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。