Related papers: A Note on Vectorial Boolean Functions as Embeddings

A Note on Vectorial Boolean Functions as Embeddings

URL: http://arxiv.org/abs/2406.06429v1
Date: Mon, 10 Jun 2024 16:23:04 GMT
Title: A Note on Vectorial Boolean Functions as Embeddings
Authors: Augustine Musukwa, Massimiliano Sala,
Abstract summary: We show that at most $2m - 2m-n$ components of $F$ can be balanced, and this maximum is achieved precisely when $F$ is an embedding. For quadratic embeddings, we demonstrate that there are always at least $2n - 1$ balanced components when $n$ is even, and $2m-1 + 2n-1 - 1$ balanced components when $n$ is odd.
Score: 0.0
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Let $F$ be a vectorial Boolean function from $\mathbb{F}^n$ to $\mathbb{F}^m$, where $m \geq n$. We define $F$ as an embedding if $F$ is injective. In this paper, we examine the component functions of $F$, focusing on constant and balanced components. Our findings reveal that at most $2^m - 2^{m-n}$ components of $F$ can be balanced, and this maximum is achieved precisely when $F$ is an embedding, with the remaining $2^{m-n}$ components being constants. Additionally, for quadratic embeddings, we demonstrate that there are always at least $2^n - 1$ balanced components when $n$ is even, and $2^{m-1} + 2^{n-1} - 1$ balanced components when $n$ is odd.

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)
A class of ternary codes with few weights [0.0]
In this paper, we investigate a ternary code $mathcalC$ of length $n$, defined by $mathcalC$ := (textTr) := (textTr(dx), dots, dots, d_n$. Using recent results on explicit evaluations of exponential sums, we determine the Weil bound, and techniques, we show that the dual code of $mathcalC$ is optimal with respect to the Hamming bound.
arXiv Detail & Related papers (2024-10-05T16:15:50Z)
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)
Coresets for Multiple $\ell_p$ Regression [47.790126028106734]
We construct coresets of size $tilde O(varepsilon-2d)$ for $p2$ and $tilde O(varepsilon-pdp/2)$ for $p>2$. For $1p2$, every matrix has a subset of $tilde O(varepsilon-1k)$ rows which spans a $(varepsilon-1k)$-approximately optimal $k$-dimensional subspace for $ell_p$ subspace approximation
arXiv Detail & Related papers (2024-06-04T15:50:42Z)
Quantum connection, charges and virtual particles [65.268245109828]
A quantum bundle $L_hbar$ is endowed with a connection $A_hbar$ and its sections are standard wave functions $psi$ obeying the Schr"odinger equation. We will lift the bundles $L_Cpm$ and connection $A_hbar$ on them to the relativistic phase space $T*R3,1$ and couple them to the Dirac spinor bundle describing both particles and antiparticles.
arXiv Detail & Related papers (2023-10-10T10:27:09Z)
Exactly solvable piecewise analytic double well potential $V_{D}(x)=min[(x+d)^2,(x-d)^2]$ and its dual single well potential $V_{S}(x)=max[(x+d)^2,(x-d)^2]$ [0.0]
Two piecewise analytic quantum systems with a free parameter $d>0$ are obtained. Their eigenvalues $E$ for the even and odd parity sectors are determined. vivid pictures unfold showing the tunneling effects between the two wells.
arXiv Detail & Related papers (2022-09-20T03:46:03Z)
The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
For every $delta>0,$ we construct CNF and formulas of size with approximate degree $Omega(n1-delta),$ essentially matching the trivial upper bound of $n. We show that for every $delta>0$, these models require $Omega(n1-delta)$, $Omega(n/4kk2)1-delta$, and $Omega(n/4kk2)1-delta$, respectively.
arXiv Detail & Related papers (2022-09-04T10:01:39Z)
Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
We study iterative methods based on Krylov subspaces for low-rank approximation under any Schatten-$p$ norm. Our main result is an algorithm that uses only $tildeO(k/sqrtepsilon)$ matrix-vector products.
arXiv Detail & Related papers (2022-02-10T16:10:41Z)
On minimal representations of shallow ReLU networks [0.0]
We show that the minimal representation for $f$ uses either $n$, $n+1$ or $n+2$ neurons. In particular, where the input layer is one-dimensional, minimal representations always use at most $n+1$ neurons but in all higher dimensional settings there are functions for which $n+2$ neurons are needed.
arXiv Detail & Related papers (2021-08-12T10:22:24Z)

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