Permutation polynomials over finite fields are fundamental objects as they are used in various theoretical and practical applications in cryptography, coding theory, combinatorial design, and related topics. This family of polynomials constitutes an active research area in which advances are being made constantly. In particular, constructing infinite classes of permutation polynomials over finite fields with good differential properties (namely, low) remains an exciting problem despite much research in this direction for many years. This article exhibits low differentially uniform power permutations over finite fields of odd characteristic. Specifically, its objective is twofold concerning the power functions $F(x)=x^{\frac{p^n+3}{2}}$ defined over the finite field $F_{p^n}$ of order $p^n$, where $p$ is an odd prime, and $n$ is a positive integer. The first is to complement some former results initiated by Helleseth and Sandberg in \cite{HS} by solving the open problem left open for more than twenty years concerning the determination of the differential spectrum of $F$ when $p^n\equiv3\pmod 4$ and $p\neq 3$. The second is to determine the exact value of its differential uniformity. Our achievements are obtained firstly by evaluating some exponential sums over $F_{p^n}$ (which amounts to evaluating the number of $F_{p^n}$-rational points on some related curves and secondly by computing the number of solutions in $(F_{p^n})^4$ of a system of equations presented by Helleseth, Rong, and Sandberg in ["New families of almost perfect nonlinear power mappings," IEEE Trans. Inform. Theory, vol. 45. no. 2, 1999], naturally appears while determining the differential spectrum of $F$. We show that in the considered case ($p^n\equiv3\pmod 4$ and $p\neq 3$), $F$ is an APN power permutation when $p^n=11$, and a differentially $4$-uniform power permutation otherwise.
相關內容
In this paper, a high-order semi-implicit (SI) asymptotic preserving (AP) and divergence-free finite difference weighted essentially nonoscillatory (WENO) scheme is proposed for magnetohydrodynamic (MHD) equations. We consider the sonic Mach number $\varepsilon$ ranging from $0$ to $\mathcal{O}(1)$. High-order accuracy in time is obtained by SI implicit-explicit Runge-Kutta (IMEX-RK) time discretization. High-order accuracy in space is achieved by finite difference WENO schemes with characteristic-wise reconstructions. A constrained transport method is applied to maintain a discrete divergence-free condition. We formally prove that the scheme is AP. Asymptotic accuracy (AA) in the incompressible MHD limit is obtained if the implicit part of the SI IMEX-RK scheme is stiffly accurate. Numerical experiments are provided to validate the AP, AA, and divergence-free properties of our proposed approach. Besides, the scheme can well capture discontinuities such as shocks in an essentially non-oscillatory fashion in the compressible regime, while it is also a good incompressible solver with uniform large-time step conditions in the low sonic Mach limit.
We establish higher-order nonasymptotic expansions for a difference between probability distributions of sums of i.i.d. random vectors in a Euclidean space. The derived bounds are uniform over two classes of sets: the set of all Euclidean balls and the set of all half-spaces. These results allow to account for an impact of higher-order moments or cumulants of the considered distributions; the obtained error terms depend on a sample size and a dimension explicitly. The new inequalities outperform accuracy of the normal approximation in existing Berry-Esseen inequalities under very general conditions. Under some symmetry assumptions on the probability distribution of random summands, the obtained results are optimal in terms of the ratio between the dimension and the sample size. The new technique which we developed for establishing nonasymptotic higher-order expansions can be interesting by itself. Using the new higher-order inequalities, we study accuracy of the nonparametric bootstrap approximation and propose a bootstrap score test under possible model misspecification. The results of the paper also include explicit error bounds for general elliptic confidence regions for an expected value of the random summands, and optimality of the Gaussian anti-concentration inequality over the set of all Euclidean balls.
We study the formula complexity of the word problem $\mathsf{Word}_{S_n,k} : \{0,1\}^{kn^2} \to \{0,1\}$: given $n$-by-$n$ permutation matrices $M_1,\dots,M_k$, compute the $(1,1)$-entry of the matrix product $M_1\cdots M_k$. An important feature of this function is that it is invariant under action of $S_n^{k-1}$ given by \[ (\pi_1,\dots,\pi_{k-1})(M_1,\dots,M_k) = (M_1\pi_1^{-1},\pi_1M_2\pi_2^{-1},\dots,\pi_{k-2}M_{k-1}\pi_{k-1}^{-1},\pi_{k-1}M_k). \] This symmetry is also exhibited in the smallest known unbounded fan-in $\{\mathsf{AND},\mathsf{OR},\mathsf{NOT}\}$-formulas for $\mathsf{Word}_{S_n,k}$, which have size $n^{O(\log k)}$. In this paper we prove a matching $n^{\Omega(\log k)}$ lower bound for $S_n^{k-1}$-invariant formulas computing $\mathsf{Word}_{S_n,k}$. This result is motivated by the fact that a similar lower bound for unrestricted (non-invariant) formulas would separate complexity classes $\mathsf{NC}^1$ and $\mathsf{Logspace}$. Our more general main theorem gives a nearly tight $n^{d(k^{1/d}-1)}$ lower bound on the $G^{k-1}$-invariant depth-$d$ $\{\mathsf{MAJ},\mathsf{AND},\mathsf{OR},\mathsf{NOT}\}$-formula size of $\mathsf{Word}_{G,k}$ for any finite simple group $G$ whose minimum permutation representation has degree~$n$. We also give nearly tight lower bounds on the $G^{k-1}$-invariant depth-$d$ $\{\mathsf{AND},\mathsf{OR},\mathsf{NOT}\}$-formula size in the case where $G$ is an abelian group.
Difference-based methods have been attracting increasing attention in nonparametric regression, in particular for estimating the residual variance.To implement the estimation, one needs to choose an appropriate difference sequence, mainly between {\em the optimal difference sequence} and {\em the ordinary difference sequence}. The difference sequence selection is a fundamental problem in nonparametric regression, and it remains a controversial issue for over three decades. In this paper, we propose to tackle this challenging issue from a very unique perspective, namely by introducing a new difference sequence called {\em the optimal-$k$ difference sequence}. The new difference sequence not only provides a better balance between the bias-variance trade-off, but also dramatically enlarges the existing family of difference sequences that includes the optimal and ordinary difference sequences as two important special cases. We further demonstrate, by both theoretical and numerical studies, that the optimal-$k$ difference sequence has been pushing the boundaries of our knowledge in difference-based methods in nonparametric regression, and it always performs the best in practical situations.
This paper is motivated by the need to quantify human immune responses to environmental challenges. Specifically, the genome of the selected cell population from a blood sample is amplified by the well-known PCR process of successive heating and cooling, producing a large number of reads. They number roughly 30,000 to 300,000. Each read corresponds to a particular rearrangement of so-called V(D)J sequences. In the end, the observation consists of a set of numbers of reads corresponding to different V(D)J sequences. The underlying relative frequencies of distinct V(D)J sequences can be summarized by a probability vector, with the cardinality being the number of distinct V(D)J rearrangements present in the blood. Statistical question is to make inferences on a summary parameter of the probability vector based on a single multinomial-type observation of a large dimension. Popular summary of the diversity of a cell population includes clonality and entropy, or more generally, is a suitable function of the probability vector. A point estimator of the clonality based on multiple replicates from the same blood sample has been proposed previously. After obtaining a point estimator of a particular function, the remaining challenge is to construct a confidence interval of the parameter to appropriately reflect its uncertainty. In this paper, we have proposed to couple the empirical Bayes method with a resampling-based calibration procedure to construct a robust confidence interval for different population diversity parameters. The method has been illustrated via extensive numerical study and real data examples.
We prove essentially optimal fine-grained lower bounds on the gap between a data structure and a partially retroactive version of the same data structure. Precisely, assuming any one of three standard conjectures, we describe a problem that has a data structure where operations run in $O(T(n,m))$ time per operation, but any partially retroactive version of that data structure requires $T(n,m) \cdot m^{1-o(1)}$ worst-case time per operation, where $n$ is the size of the data structure at any time and $m$ is the number of operations. Any data structure with operations running in $O(T(n,m))$ time per operation can be converted (via the "rollback method") into a partially retroactive data structure running in $O(T(n,m) \cdot m)$ time per operation, so our lower bound is tight up to an $m^{o(1)}$ factor common in fine-grained complexity.
We propose to model longer-term future human behavior by jointly predicting action labels and 3D characteristic poses (3D poses representative of the associated actions). While previous work has considered action and 3D pose forecasting separately, we observe that the nature of the two tasks is coupled, and thus we predict them together. Starting from an input 2D video observation, we jointly predict a future sequence of actions along with 3D poses characterizing these actions. Since coupled action labels and 3D pose annotations are difficult and expensive to acquire for videos of complex action sequences, we train our approach with action labels and 2D pose supervision from two existing action video datasets, in tandem with an adversarial loss that encourages likely 3D predicted poses. Our experiments demonstrate the complementary nature of joint action and characteristic 3D pose prediction: our joint approach outperforms each task treated individually, enables robust longer-term sequence prediction, and outperforms alternative approaches to forecast actions and characteristic 3D poses.
It is well known that second order homogeneous linear ordinary differential equations with slowly varying coefficients admit slowly varying phase functions. This observation underlies the Liouville-Green method and many other techniques for the asymptotic approximation of the solutions of such equations. It is also the basis of a recently developed numerical algorithm that, in many cases of interest, runs in time independent of the magnitude of the equation's coefficients and achieves accuracy on par with that predicted by its condition number. Here we point out that a large class of second order inhomogeneous linear ordinary differential equations can be efficiently and accurately solved by combining phase function methods for second order homogeneous linear ordinary differential equations with a variant of the adaptive Levin method for evaluating oscillatory integrals.
We present a new construction of high dimensional expanders based on covering spaces of simplicial complexes. High dimensional expanders (HDXs) are hypergraph analogues of expander graphs. They have many uses in theoretical computer science, but unfortunately only few constructions are known which have arbitrarily small local spectral expansion. We give a randomized algorithm that takes as input a high dimensional expander $X$ (satisfying some mild assumptions). It outputs a sub-complex $Y \subseteq X$ that is a high dimensional expander and has infinitely many simplicial covers. These covers form new families of bounded-degree high dimensional expanders. The sub-complex $Y$ inherits $X$'s underlying graph and its links are sparsifications of the links of $X$. When the size of the links of $X$ is $O(\log |X|)$, this algorithm can be made deterministic. Our algorithm is based on the groups and generating sets discovered by Lubotzky, Samuels and Vishne (2005), that were used to construct the first discovered high dimensional expanders. We show these groups give rise to many more ``randomized'' high dimensional expanders. In addition, our techniques also give a random sparsification algorithm for high dimensional expanders, that maintains its local spectral properties. This may be of independent interest.
We consider an infinite family of exponents $e(l,k)$ with two parameters, $l$ and $k$, and derive sufficient conditions for $e(l,k)$ to be 0-APN over $\mathbb{F}_{2^n}$. These conditions allow us to generate, for each choice of $l$ and $k$, an infinite list of dimensions $n$ where $x^{e(l,k)}$ is 0-APN much more efficiently than in general. We observe that the Gold and Inverse exponents, as well as the inverses of the Gold exponents can be expressed in the form $e(l,k)$ for suitable $l$ and $k$. We characterize all cases in which $e(l,k)$ can be cyclotomic equivalent to a representative from the Gold, Kasami, Welch, Niho, and Inverse families of exponents. We characterize when $e(l,k)$ can lie in the same cyclotomic coset as the Dobbertin exponent (without considering inverses) and provide computational data showing that the Dobbertin inverse is never equivalent to $e(l,k)$. We computationally test the APN-ness of $e(l,k)$ for small values of $l$ and $k$ over $\mathbb{F}_{2^n}$ for $n \le 100$, and sketch the limits to which such tests can be performed using currently available technology. We conclude that there are no APN monomials among the tested functions, outside of known classes.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191