Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userPolynomial Expressions of Carries in p-ary Arithmetics
143
0
0.0
(
0
)
Added by
Koji Nuida
Publication date
2015
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
It is known that any $n$-variable function on a finite prime field of characteristic $p$ can be expressed as a polynomial over the same field with at most $p^n$ monomials. However, it is not obvious to determine the polynomial for a given concrete function. In this paper, we study the concrete polynomial expressions of the carries in addition and multiplication of $p$-ary integers. For the case of addition, our result gives a new family of symmetric polynomials, which generalizes the known result for the binary case $p = 2$ where the carries are given by elementary symmetric polynomials. On the other hand, for the case of multiplication of $n$ single-digit integers, we give a simple formula of the polynomial expression for the carry to the next digit using the Bernoulli numbers, and show that it has only $(n+1)(p-1)/2 + 1$ monomials, which is significantly fewer than the worst-case number $p^n$ of monomials for general functions. We also discuss applications of our results to cryptographic computation on encrypted data.
rate research
Read More
Let $mathbb{F}_p$ be the finite field of prime order $p$. For any function $f colon mathbb{F}_p{}^n to mathbb{F}_p$, there exists a unique polynomial over $mathbb{F}_p$ having degree at most $p-1$ with respect to each variable which coincides with $f$. We call it the minimal polynomial of $f$. It is in general a non-trivial task to find a concrete expression of the minimal polynomial of a given function, which has only been worked out for limited classes of functions in the literature. In this paper, we study minimal polynomial expressions of several functions that are closely related to some practically important procedures such as auction and voting.
Let $mathcal{T}^{(p)}_n$ be the set of $p$-ary labeled trees on ${1,2,dots,n}$. A maximal decreasing subtree of an $p$-ary labeled tree is defined by the maximal $p$-ary subtree from the root with all edges being decreasing. In this paper, we study a new refinement $mathcal{T}^{(p)}_{n,k}$ of $mathcal{T}^{(p)}_n$, which is the set of $p$-ary labeled trees whose maximal decreasing subtree has $k$ vertices.
Let f be a function mapping an n dimensional vector space over GF(p) to GF(p). When p is 2, Bernasconi et al. have shown that there is a correspondence between certain properties of f (e.g., if it is bent) and properties of its associated Cayley graph. Analogously, but much earlier, Dillon showed that f is bent if and only if the level curves of f had certain combinatorial properties (again, only when p is 2). The attempt is to investigate an analogous theory when p is greater than 2 using the (apparently new) combinatorial concept of a weighted partial difference set. More precisely, we try to investigate which properties of the Cayley graph of f can be characterized in terms of function-theoretic properties of f, and which function-theoretic properties of f correspond to combinatorial properties of the set of level curves, i.e., the inverse map of f. While the natural generalizations of the Bernasconi correspondence and Dillon correspondence are not true in general, using extensive computations, we are able to determine a classification in some small cases. Our main conjecture is Conjecture 67.
Outsourcing neural network inference tasks to an untrusted cloud raises data privacy and integrity concerns. To address these challenges, several privacy-preserving and verifiable inference techniques have been proposed based on replacing the non-polynomial activation functions such as the rectified linear unit (ReLU) function with polynomial activation functions. Such techniques usually require polynomials with integer coefficients or polynomials over finite fields. Motivated by such requirements, several works proposed replacing the ReLU activation function with the square activation function. In this work, we empirically show that the square function is not the best degree-$2$ polynomial that can replace the ReLU function even when restricting the polynomials to have integer coefficients. We instead propose a degree-$2$ polynomial activation function with a first order term and empirically show that it can lead to much better models. Our experiments on the CIFAR-$10$ and CIFAR-$100$ datasets on various architectures show that our proposed activation function improves the test accuracy by up to $9.4%$ compared to the square function.
A connected graph $G$ is called strongly Menger (edge) connected if for any two distinct vertices $x,y$ of $G$, there are $min {{rm deg}_G(x), {rm deg}_G(y)}$ vertex(edge)-disjoint paths between $x$ and $y$. In this paper, we consider strong Menger (edge) connectedness of the augmented $k$-ary $n$-cube $AQ_{n,k}$, which is a variant of $k$-ary $n$-cube $Q_n^k$. By exploring the topological proprieties of $AQ_{n,k}$, we show that $AQ_{n,3}$ for $ngeq 4$ (resp. $AQ_{n,k}$ for $ngeq 2$ and $kgeq 4$) is still strongly Menger connected even when there are $4n-9$ (resp. $4n-8$) faulty vertices and $AQ_{n,k}$ is still strongly Menger edge connected even when there are $4n-4$ faulty edges for $ngeq 2$ and $kgeq 3$. Moreover, under the restricted condition that each vertex has at least two fault-free edges, we show that $AQ_{n,k}$ is still strongly Menger edge connected even when there are $8n-10$ faulty edges for $ngeq 2$ and $kgeq 3$. These results are all optimal in the sense of the maximum number of tolerated vertex (resp. edge) faults.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
