論文の概要: Trace Monomial Boolean Functions with Large High-Order Nonlinearities
- arxiv url: http://arxiv.org/abs/2309.11229v1
- Date: Wed, 20 Sep 2023 11:40:19 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-19 04:10:47.819627
- Title: Trace Monomial Boolean Functions with Large High-Order Nonlinearities
- Title(参考訳): 高次非線形性を有するトレース単項ブール関数
- Authors: Jinjie Gao, Haibin Kan, Yuan Li, Jiahua Xu, Qichun Wang,
- Abstract要約: トレース単項ブール関数の2階・3階・高階非線形性に対する下界を証明する。
すべてのトレースモノミアルのうち、我々の境界は citeCar08 と citeYT20 の2階非線形性の下限と一致している。
- 参考スコア(独自算出の注目度): 18.103637463837305
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Exhibiting an explicit Boolean function with a large high-order nonlinearity is an important problem in cryptography, coding theory, and computational complexity. We prove lower bounds on the second-order, third-order, and higher-order nonlinearities of some trace monomial Boolean functions. We prove lower bounds on the second-order nonlinearities of functions $\mathrm{tr}_n(x^7)$ and $\mathrm{tr}_n(x^{2^r+3})$ where $n=2r$. Among all trace monomials, our bounds match the best second-order nonlinearity lower bounds by \cite{Car08} and \cite{YT20} for odd and even $n$ respectively. We prove a lower bound on the third-order nonlinearity for functions $\mathrm{tr}_n(x^{15})$, which is the best third-order nonlinearity lower bound. For any $r$, we prove that the $r$-th order nonlinearity of $\mathrm{tr}_n(x^{2^{r+1}-1})$ is at least $2^{n-1}-2^{(1-2^{-r})n+\frac{r}{2^{r-1}}-1}- O(2^{\frac{n}{2}})$. For $r \ll \log_2 n$, this is the best lower bound among all explicit functions.
- Abstract(参考訳): 明らかにブール関数を高次非線形性で表すことは、暗号、符号化理論、計算複雑性において重要な問題である。
トレース単項ブール関数の2階・3階・高階非線形性に対する下界を証明する。
函数の2階非線形性に対する下界を$\mathrm{tr}_n(x^7)$と$\mathrm{tr}_n(x^{2^r+3})$で証明する。
すべてのトレース単項式の中で、我々の境界は、それぞれ奇数と偶数に対して \cite{Car08} と \cite{YT20} によって最高の二階非線形性の下界と一致する。
我々は、函数 $\mathrm{tr}_n(x^{15})$ の3階非線形性に対する下界を証明する。
任意の$r$に対して、$\mathrm{tr}_n(x^{2^{r+1}-1})$の$r$-次非線形性が少なくとも2^{n-1}-2^{(1-2^{-r})n+\frac{r}{2^{r-1}}-1}-O(2^{\frac{n}{2}})$であることを証明する。
$r \ll \log_2 n$ の場合、これはすべての明示関数の中で最高の下界である。
関連論文リスト
- Quantum and classical query complexities of functions of matrices [0.0]
任意の連続関数 $f(x):[-1,1]rightarrow [-1,1]$ に対して、計算の量子クエリ複雑性 $brai f(A) ketjpm varepsilon/4$ は$Omega(widetildedeg_varepsilon(f))$ で制限される。
論文 参考訳(メタデータ) (2023-11-13T00:45:41Z) - A polynomial quantum computing algorithm for solving the dualization
problem [75.38606213726906]
2つの単調素関数 $f:0,1n to 0,1$ と $g:0,1n to 0,1$ が与えられたとき、双対化問題は$g$が$f$の双対かどうかを決定することである。
本稿では,双対化問題の決定版を時間内に解く量子コンピューティングアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-08-28T18:12:54Z) - Krylov Methods are (nearly) Optimal for Low-Rank Approximation [8.017116107657206]
任意のアルゴリズムが$Omegaleft(log(n)/varepsilon1/2right)$ matrix-vector productを必要とし、Krylov法で得られる上限値と正確に一致することを示す。
我々の下位境界はOpen Question 1WooWoo14で、Spectral LRAのアルゴリズムの進歩の欠如の証拠を提供している。
論文 参考訳(メタデータ) (2023-04-06T16:15:19Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳(メタデータ) (2022-06-17T17:55:43Z) - The First Optimal Acceleration of High-Order Methods in Smooth Convex
Optimization [88.91190483500932]
本研究では,滑らかな凸最小化問題の解法として最適高次アルゴリズムを求めるための基本的オープンな問題について検討する。
この理由は、これらのアルゴリズムが複雑なバイナリプロシージャを実行する必要があるため、最適でも実用でもないからである。
我々は、最初のアルゴリズムに$mathcalOleft(epsilon-2/(p+1)right)$pthのオーダーオーラクル複雑性を与えることで、この根本的な問題を解決する。
論文 参考訳(メタデータ) (2022-05-19T16:04:40Z) - Low-degree learning and the metric entropy of polynomials [49.1574468325115]
少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
論文 参考訳(メタデータ) (2022-03-17T23:52:08Z) - Improved Regret Bounds for Online Submodular Maximization [10.089520556398575]
我々は、各ステップ$tin[T]$において、固定凸からアクション$x_t$を選択し、コンパクトなドメインセット$mathcalK$を選択するオンライン最適化問題を考える。
ユーティリティ関数 $f_t(cdot)$ が明らかになり、アルゴリズムはペイオフ $f_t(x_t)$ を受け取る。
論文 参考訳(メタデータ) (2021-06-15T02:05:35Z) - Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Loss [41.17536985461902]
オラクルの複雑さを$Omega(Nepsilon-2/3)$として証明し、N$への依存が多対数因子に最適であることを示す。
非滑らかな場合、$tildeO(Nepsilon-2/3 + sqrtNepsilon-8/3)$と$tildeO(Nepsilon-2/3 + sqrtNepsilon-1)$の複雑さ境界を改善した手法を開発する。
論文 参考訳(メタデータ) (2021-05-04T21:49:15Z) - Linear Bandits on Uniformly Convex Sets [88.3673525964507]
線形バンディットアルゴリズムはコンパクト凸作用集合上の $tildemathcalo(nsqrtt)$ pseudo-regret 境界を与える。
2種類の構造的仮定は、より良い擬似回帰境界をもたらす。
論文 参考訳(メタデータ) (2021-03-10T07:33:03Z) - On the Complexity of Minimizing Convex Finite Sums Without Using the
Indices of the Individual Functions [62.01594253618911]
有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。
同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
論文 参考訳(メタデータ) (2020-02-09T03:39:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。