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
- 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 charges of harmonic oscillators [55.2480439325792]
We show that the energy eigenfunctions $psi_n$ with $nge 1$ are complex coordinates on orbifolds $mathbbR2/mathbbZ_n$.
We also discuss "antioscillators" with opposite quantum charges and the same positive energy.
arXiv Detail & Related papers (2024-04-02T09:16:18Z) - Exact Synthesis of Multiqubit Clifford-Cyclotomic Circuits [0.8411424745913132]
We show that when $n$ is a power of 2, a multiqubit unitary matrix $U$ can be exactly represented by a circuit over $mathcalG_n$.
We moreover show that $log(n)-2$ ancillas are always sufficient to construct a circuit for $U$.
arXiv Detail & Related papers (2023-11-13T20:46:51Z) - 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) - Learning low-degree functions from a logarithmic number of random
queries [77.34726150561087]
We prove that for any integer $ninmathbbN$, $din1,ldots,n$ and any $varepsilon,deltain(0,1)$, a bounded function $f:-1,1nto[-1,1]$ of degree at most $d$ can be learned.
arXiv Detail & Related papers (2021-09-21T13:19:04Z) - 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) - Learning and Testing Variable Partitions [13.575794982844222]
We show that $mathcalO(k n2)(delta + epsilon)$ can be learned in time $tildemathcalO(n2 mathrmpoly (1/epsilon)$ for any $epsilon > 0$.
We also show that even two-sided testers require $Omega(n)$ queries when $k = 2$.
arXiv Detail & Related papers (2020-03-29T10:12:32Z) - A closer look at the approximation capabilities of neural networks [6.09170287691728]
A feedforward neural network with one hidden layer is able to approximate any continuous function $f$ to any given approximation threshold $varepsilon$.
We show that this uniform approximation property still holds even under seemingly strong conditions imposed on the weights.
arXiv Detail & Related papers (2020-02-16T04:58:43Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.