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

The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
We show that this problem has randomized communication complexity $Omega(frac1kcdot n2log|mathbbF|)$. As an application, we obtain an $Omega(frac1kcdot n2log|mathbbF|)$ space lower bound for any streaming algorithm with $k$ passes.
arXiv Detail & Related papers (2024-10-26T06:21:42Z)
LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions [54.54897832889028]
We show that for any $K$, there is a universal set" $U subset [n]$ of size independent of $n$, such that for any $Q$ and any row $i$, the large attention scores $A_i,j$ in row $i$ of $A$ all have $jin U$. We empirically show the benefits of our scheme for vision transformers, showing how to train new models that use our universal set while training as well.
arXiv Detail & Related papers (2024-10-07T19:47:13Z)
Further Investigation on Differential Properties of the Generalized Ness-Helleseth Function [13.67029767623542]
The function defined by $f_u(x)=uxd_1+xd_2$ is called the generalized Ness-Helleseth function over $mathbbF_pn$. For each $u$ satisfying $chi(u+1) = chi(u-1)$, the differential spectrum of $f_u(x)$ is investigated.
arXiv Detail & Related papers (2024-08-30T13:18:23Z)
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)
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)
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)

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