Related papers: When does a bent concatenation not belong to the completed Maiorana-McFarland class?

When does a bent concatenation not belong to the completed Maiorana-McFarland class?

URL: http://arxiv.org/abs/2404.16220v1
Date: Wed, 24 Apr 2024 21:36:19 GMT
Title: When does a bent concatenation not belong to the completed Maiorana-McFarland class?
Authors: Sadmir Kudin, Enes Pasalic, Alexandr Polujan, Fengrong Zhang,
Abstract summary: When does a bent concatenation $f$ (not) belong to the completed Maiorana-McFarland class $mathcalM#$? We show how to specify bent functions outside $mathcalM#$.
Score: 47.2382573252527
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Every Boolean bent function $f$ can be written either as a concatenation $f=f_1||f_2$ of two complementary semi-bent functions $f_1,f_2$; or as a concatenation $f=f_1||f_2||f_3||f_4$ of four Boolean functions $f_1,f_2,f_3,f_4$, all of which are simultaneously bent, semi-bent, or 5-valued spectra-functions. In this context, it is essential to ask: When does a bent concatenation $f$ (not) belong to the completed Maiorana-McFarland class $\mathcal{M}^\#$? In this article, we answer this question completely by providing a full characterization of the structure of $\mathcal{M}$-subspaces for the concatenation of the form $f=f_1||f_2$ and $f=f_1||f_2||f_3||f_4$, which allows us to specify the necessary and sufficient conditions so that $f$ is outside $\mathcal{M}^\#$. Based on these conditions, we propose several explicit design methods of specifying bent functions outside $\mathcal{M}^\#$ in the special case when $f=g||h||g||(h+1)$, where $g$ and $h$ are bent functions.

Related papers

Dimension Independent Disentanglers from Unentanglement and Applications [55.86191108738564]
We construct a dimension-independent k-partite disentangler (like) channel from bipartite unentangled input. We show that to capture NEXP, it suffices to have unentangled proofs of the form $| psi rangle = sqrta | sqrt1-a | psi_+ rangle where $| psi_+ rangle has non-negative amplitudes.
arXiv Detail & Related papers (2024-02-23T12:22:03Z)
Quantum and classical query complexities of functions of matrices [0.0]
We show that for any continuous function $f(x):[-1,1]rightarrow [-1,1]$, the quantum query complexity of computing $brai f(A) ketjpm varepsilon/4$ is lower bounded by $Omega(widetildedeg_varepsilon(f))$.
arXiv Detail & Related papers (2023-11-13T00:45:41Z)
A polynomial quantum computing algorithm for solving the dualization problem [75.38606213726906]
Given two monotone prime functions $f:0,1n to 0,1$ and $g:0,1n to 0,1$ the dualization problem consists in determining if $g$ is the dual of $f$. We present a quantum computing algorithm that solves the decision version of the dualization problem in time.
arXiv Detail & Related papers (2023-08-28T18:12:54Z)
Online Learning of Smooth Functions [0.35534933448684125]
We study the online learning of real-valued functions where the hidden function is known to have certain smoothness properties. We find new bounds for $textopt_p(mathcal F_q)$ that are sharp up to a constant factor. In the multi-variable setup, we establish inequalities relating $textopt_p(mathcal F_q,d)$ to $textopt_p(mathcal F_q,d)$ and show that $textopt_p(mathcal F
arXiv Detail & Related papers (2023-01-04T04:05:58Z)
On Outer Bi-Lipschitz Extensions of Linear Johnson-Lindenstrauss Embeddings of Low-Dimensional Submanifolds of $\mathbb{R}^N$ [0.24366811507669117]
Let $mathcalM$ be a compact $d$-dimensional submanifold of $mathbbRN$ with reach $tau$ and volume $V_mathcal M$. We prove that a nonlinear function $f: mathbbRN rightarrow mathbbRmm exists with $m leq C left(d / epsilon2right) log left(fracsqrt[d]V_math
arXiv Detail & Related papers (2022-06-07T15:10:46Z)
Beyond the Berry Phase: Extrinsic Geometry of Quantum States [77.34726150561087]
We show how all properties of a quantum manifold of states are fully described by a gauge-invariant Bargmann. We show how our results have immediate applications to the modern theory of polarization.
arXiv Detail & Related papers (2022-05-30T18:01:34Z)
Low-degree learning and the metric entropy of polynomials [49.1574468325115]
We prove that any (deterministic or randomized) algorithm which learns $mathscrF_nd$ with $L$-accuracy $varepsilon$ requires at least $Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon) satisfies the two-sided estimate $$c (1-varepsilon)2dlog
arXiv Detail & Related papers (2022-03-17T23:52:08Z)
Sharper bounds for online learning of smooth functions of a single variable [0.0]
We show that $opt_1+epsilon(mathcalF_q) = Theta(epsilon-frac12)$, where the constants in the bound do not depend on $q$. We also show that $opt_1+epsilon(mathcalF_q) = Theta(epsilon-frac12)$, where the constants in the bound do not depend on $q$.
arXiv Detail & Related papers (2021-05-30T23:06:21Z)
Analytic Behaviour of Wave Function [0.0]
We find that the order and the type of wave function are compatible with the condition $|sigma|rho =sqrtv_m$ except to $m=-2$. We ansatz that the wave function satisfaction $psi(r)=f(r)exp[g(r)]$, where $f(r),g(r)$ are relations, and the power of $g(r)$ is no more than the order $rho$.
arXiv Detail & Related papers (2020-06-15T12:14:52Z)
On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
We exploit the finite noise structure of finite sums to derive a matching $O(n2)$-upper bound under the global oracle model. Following a similar approach, we propose a novel adaptation of SVRG which is both emphcompatible with oracles, and achieves complexity bounds of $tildeO(n2+nsqrtL/mu)log (1/epsilon)$ and $O(nsqrtL/epsilon)$, for $mu>0$ and $mu=0$
arXiv Detail & Related papers (2020-02-09T03:39:46Z)

This list is automatically generated from the titles and abstracts of the papers in this site.