論文の概要: The Maximum Nonlinearity of 8-variable Balanced Boolean Functions is 116

• arxiv url: http://arxiv.org/abs/2610.17897v1
• Date: Tue, 13 Oct 2026 07:52:44 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-17 08:16:34.761142
• Title: The Maximum Nonlinearity of 8-variable Balanced Boolean Functions is 116
• Title（参考訳）: 8変数平衡ブール関数の最大非線形性は116である
• Abstract要約: 我々は、平衡函数のウォルシュピークのドブベルトンの予想再帰の8変数の例を確立する。 極位6の二次形式を取得し、26以上の非線形性を持つ6変数ブール関数の存在に問題を還元することで、結果を導出する。
• 参考スコア（独自算出の注目度）: 0.764671395172401
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Does there exist an 8-variable balanced Boolean function with nonlinearity 118? This is a famous and long-standing open problem in Boolean functions. In this paper, we give a negative answer to this open problem, and prove that the maximum nonlinearity of balanced Boolean functions in 8 variables is 116, establishing the 8-variable instance of Dobbertin's conjectured recursion for the minimum Walsh peak of balanced functions. Equivalently, the covering radius of the Reed--Muller code RM(1,8) in 0-resilient Boolean functions is 116. We deduce the result by obtaining a quadratic form of polar rank 6, and reducing the problem to the existence of a 6-variable Boolean function with nonlinearity greater than 26 whose Hamming distance to a bent function is between 4 and 6.
• Abstract（参考訳）: 非線形性 118 を持つ8変数の平衡ブール函数は存在するか。 これはブール関数における有名な、そして長年続くオープンな問題である。 本論文では、この開問題に対して負の答えを与え、8変数の平衡ブール関数の最大非線形性は116であり、平衡関数のウォルシュピークの最小値に対するドブベルトの予想再帰の8変数のインスタンスを確立する。 同様に、0-レジリエントブール関数におけるリード・ミュラー符号RM(1,8)の被覆半径は116である。 偏位6の二次形式を得るとともに、曲がり関数に対するハミング距離が4から6である26以上の非線形性を持つ6変数ブール関数の存在に問題を還元することで、結果を導出する。

関連論文リスト

• IDEM Enough? Evolving Highly Nonlinear Idempotent Boolean Functions [25.80284220818612]
  Idempotent Boolean関数は暗号設計の候補として魅力的である。 軌道上の真理表を符号化することで、イデオポテンスを強制できることが示される。 次に、軌道上の真理表を符号化することで、イデオポテンスを強制できることを示し、異なる赤道軌道の数に匹敵する大きさのコンパクトなゲノムを生成する。
  論文  参考訳（メタデータ） (2026-01-31T18:06:38Z)
• On Counts and Densities of Homogeneous Bent Functions: An Evolutionary Approach [60.00535100780336]
  本稿では, 等質屈曲ブール関数の進化における進化的アルゴリズム(EA)の利用について検討する。 等質な曲がり関数の密度の概念を導入し、異なる変数数の2次および3次曲がり関数を見つけるアルゴリズム設計を容易にする。
  論文  参考訳（メタデータ） (2025-11-16T15:33:40Z)
• The More the Merrier: On Evolving Five-valued Spectra Boolean Functions [32.90791284928444]
  ウォルシュ=アダマール係数を持つ5値のスペクトルブール関数は、5つの異なる値しか持たない。 木符号化は他の選択よりも優れていることを示し、高い非線形性を持つ5値のブール関数を得ることができる。
  論文  参考訳（メタデータ） (2024-11-19T18:57:55Z)
• On Symmetric Pseudo-Boolean Functions: Factorization, Kernels and Applications [0.0]
  任意の対称擬ブール函数が、同値に級数や分解として表せることを証明する。 これらの結果を用いて、スピングラスエネルギー関数、量子情報、テンソルネットワークの文献に現れる対称擬ブール関数を解析する。
  論文  参考訳（メタデータ） (2022-09-29T18:00:07Z)
• Inference on Strongly Identified Functionals of Weakly Identified Functions [71.42652863687117]
  本研究では,ニュアンス関数が存在しない場合でも,関数を強く識別するための新しい条件について検討する。 本稿では,プライマリおよびデバイアスのニュアンス関数に対するペナル化ミニマックス推定器を提案する。
  論文  参考訳（メタデータ） (2022-08-17T13:38:31Z)
• Submodular + Concave [53.208470310734825]
  第一次最適化法が凹関数の最大目的値に収束できることはよく確立されている。 本研究では、滑らかな函数凸体(英語版)の行列式を$F(x) = G(x) +C(x)$で始める。 このクラスの函数は、保証がないような凹凸函数と連続DR-部分モジュラ函数の両方の拡張である。
  論文  参考訳（メタデータ） (2021-06-09T01:59:55Z)
• Size and Depth Separation in Approximating Natural Functions with Neural Networks [52.73592689730044]
  本稿では,ReLUネットワークを用いた自然関数の近似におけるサイズと深さの利点を示す。 我々は、そのような結果が$O(d)$を超えることを証明するための複雑性理論上の障壁を示す。 また、サイズ$O(d)$のネットワークで近似できる明示的な自然関数も示している。
  論文  参考訳（メタデータ） (2021-01-30T21:30:11Z)
• Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
  アルゴリズムの族は高い確率でほぼ最適な解を生成できないことを示す。 ブール回路の場合、回路複雑性理論で知られている最先端境界を改善する。
  論文  参考訳（メタデータ） (2020-04-25T05:45:59Z)

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

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