In the literature, there are many results about permutation polynomials over finite fields. However, very few permutations of vector spaces are constructed although it has been shown that permutations of vector spaces have many applications in cryptography, especially in constructing permutations with low differential and boomerang uniformities. In this paper, motivated by the butterfly structure \cite{perrin2016cryptanalysis} and the work of Qu and Li \cite{qu2023}, we investigate rotatable permutations from $\gf_{2^m}^3$ to itself with $d$-homogenous functions. Based on the theory of equations of low degree, the resultant of polynomials, and some skills of exponential sums, we construct five infinite classes of $3$-homogeneous rotatable permutations from $\gf_{2^m}^3$ to itself, where $m$ is odd. Moreover, we demonstrate that the corresponding permutation polynomials of $\gf_{2^{3m}}$ of our newly constructed permutations of $\gf_{2^m}^3$ are QM-inequivalent to the known ones.
相關內容
Within the framework of Riehl-Shulman's synthetic $(\infty,1)$-category theory, we present a theory of two-sided cartesian fibrations. Central results are several characterizations of the two-sidedness condition \`{a} la Chevalley, Gray, Street, and Riehl-Verity, a two-sided Yoneda Lemma, as well as the proof of several closure properties. Along the way, we also define and investigate a notion of fibered or sliced fibration which is used later to develop the two-sided case in a modular fashion. We also briefly discuss discrete two-sided cartesian fibrations in this setting, corresponding to $(\infty,1)$-distributors. The systematics of our definitions and results closely follows Riehl-Verity's $\infty$-cosmos theory, but formulated internally to Riehl-Shulman's simplicial extension of homotopy type theory. All the constructions and proofs in this framework are by design invariant under homotopy equivalence. Semantically, the synthetic $(\infty,1)$-categories correspond to internal $(\infty,1)$-categories implemented as Rezk objects in an arbitrary given $(\infty,1)$-topos.
We present a computationally efficient algorithm that is suitable for graphic processing unit implementation. This algorithm enables the identification of all weak pseudo-manifolds that meet specific facet conditions, drawn from a given input set. We employ this approach to enumerate toric colorable seeds. Consequently, we achieve a comprehensive characterization of $(n-1)$-dimensional PL spheres with $n+4$ vertices that possess a maximal Buchstaber number. A primary focus of this research is the fundamental categorization of non-singular complete toric varieties of Picard number $4$. This classification serves as a valuable tool for addressing questions related to toric manifolds of Picard number $4$. Notably, we have determined which of these manifolds satisfy equality within an inequality regarding the number of minimal components in their rational curve space. This addresses a question posed by Chen, Fu, and Hwang in 2014 for this specific case.
In minimum power network design problems we are given an undirected graph $G=(V,E)$ with edge costs $\{c_e:e \in E\}$. The goal is to find an edge set $F\subseteq E$ that satisfies a prescribed property of minimum power $p_c(F)=\sum_{v \in V} \max \{c_e: e \in F \mbox{ is incident to } v\}$. In the Min-Power $k$ Edge Disjoint $st$-Paths problem $F$ should contains $k$ edge disjoint $st$-paths. The problem admits a $k$-approximation algorithm, and it was an open question whether it admits approximation ratio sublinear in $k$ even for unit costs. We give a $2\sqrt{2k}$-approximation algorithm for general costs.
We give structural results about bifibrations of (internal) $(\infty,1)$-categories with internal sums. This includes a higher version of Moens' Theorem, characterizing cartesian bifibrations with extensive aka stable and disjoint internal sums over lex bases as Artin gluings of lex functors. We also treat a generalized version of Moens' Theorem due to Streicher which does not require the Beck--Chevalley condition. Furthermore, we show that also in this setting the Moens fibrations can be characterized via a condition due to Zawadowski. Our account overall follows Streicher's presentation of fibered category theory \`{a} la B\'{e}nabou, generalizing the results to the internal, higher-categorical case, formulated in a synthetic setting. Namely, we work inside simplicial homotopy type theory, which has been introduced by Riehl and Shulman as a logical system to reason about internal $(\infty,1)$-categories, interpreted as Rezk objects in any given Grothendieck--Rezk--Lurie $(\infty,1)$-topos.
For a fixed graph $H$, in the graph homomorphism problem, denoted by $Hom(H)$, we are given a graph $G$ and we have to determine whether there exists an edge-preserving mapping $\varphi: V(G) \to V(H)$. Note that $Hom(C_3)$, where $C_3$ is the cycle of length $3$, is equivalent to $3$-Coloring. The question whether $3$-Coloring is polynomial-time solvable on diameter-$2$ graphs is a well-known open problem. In this paper we study the $Hom(C_{2k+1})$ problem on bounded-diameter graphs for $k\geq 2$, so we consider all other odd cycles than $C_3$. We prove that for $k\geq 2$, the $Hom(C_{2k+1})$ problem is polynomial-time solvable on diameter-$(k+1)$ graphs -- note that such a result for $k=1$ would be precisely a polynomial-time algorithm for $3$-Coloring of diameter-$2$ graphs. Furthermore, we give subexponential-time algorithms for diameter-$(k+2)$ and -$(k+3)$ graphs. We complement these results with a lower bound for diameter-$(2k+2)$ graphs -- in this class of graphs the $Hom(C_{2k+1})$ problem is NP-hard and cannot be solved in subexponential-time, unless the ETH fails. Finally, we consider another direction of generalizing $3$-Coloring on diameter-$2$ graphs. We consider other target graphs $H$ than odd cycles but we restrict ourselves to diameter $2$. We show that if $H$ is triangle-free, then $Hom(H)$ is polynomial-time solvable on diameter-$2$ graphs.
Negation is a important perspective of knowledge representation. Existing negation methods are mainly applied in probability theory, evidence theory and complex evidence theory. As a generalization of evidence theory, random permutation sets theory may represent information more precisely. However, how to apply the concept of negation to random permutation sets theory has not been studied. In this paper, the negation of permutation mass function is proposed. Moreover, in the negation process, the convergence of proposed negation method is verified. The trends of uncertainty and dissimilarity after each negation operation are investigated. Numerical examples are used to demonstrate the rationality of the proposed method.
This paper considers correlation clustering on unweighted complete graphs. We give a combinatorial algorithm that returns a single clustering solution that is simultaneously $O(1)$-approximate for all $\ell_p$-norms of the disagreement vector; in other words, a combinatorial $O(1)$-approximation of the all-norms objective for correlation clustering. This is the first proof that minimal sacrifice is needed in order to optimize different norms of the disagreement vector. In addition, our algorithm is the first combinatorial approximation algorithm for the $\ell_2$-norm objective, and more generally the first combinatorial algorithm for the $\ell_p$-norm objective when $1 < p < \infty$. It is also faster than all previous algorithms that minimize the $\ell_p$-norm of the disagreement vector, with run-time $O(n^\omega)$, where $O(n^\omega)$ is the time for matrix multiplication on $n \times n$ matrices. When the maximum positive degree in the graph is at most $\Delta$, this can be improved to a run-time of $O(n\Delta^2 \log n)$.
Path eccentricity of $k$-AT-free graphs and application on graphs with the consecutive ones property
The central path problem is a variation on the single facility location problem. The aim is to find, in a given connected graph $G$, a path $P$ minimizing its eccentricity, which is the maximal distance from $P$ to any vertex of the graph $G$. The path eccentricity of $G$ is the minimal eccentricity achievable over all paths in $G$. In this article we consider the path eccentricity of the class of the $k$-AT-free graphs. They are graphs in which any set of three vertices contains a pair for which every path between them uses at least one vertex of the closed neighborhood at distance $k$ of the third. We prove that they have path eccentricity bounded by $k$. Moreover, we answer a question of G\'omez and Guti\'errez asking if there is a relation between path eccentricity and the consecutive ones property. The latter is the property for a binary matrix to admit a permutation of the rows placing the 1's consecutively on the columns. It was already known that graphs whose adjacency matrices have the consecutive ones property have path eccentricity at most 1, and that the same remains true when the augmented adjacency matrices (with ones on the diagonal) has the consecutive ones property. We generalize these results as follow. We study graphs whose adjacency matrices can be made to satisfy the consecutive ones property after changing some values on the diagonal, and show that those graphs have path eccentricity at most 2, by showing that they are 2-AT-free.
Functional Differential Equations (FDEs) play a fundamental role in many areas of mathematical physics, including fluid dynamics (Hopf characteristic functional equation), quantum field theory (Schwinger-Dyson equation), and statistical physics. Despite their significance, computing solutions to FDEs remains a longstanding challenge in mathematical physics. In this paper we address this challenge by introducing new approximation theory and high-performance computational algorithms designed for solving FDEs on tensor manifolds. Our approach involves approximating FDEs using high-dimensional partial differential equations (PDEs), and then solving such high-dimensional PDEs on a low-rank tensor manifold leveraging high-performance parallel tensor algorithms. The effectiveness of the proposed approach is demonstrated through its application to the Burgers-Hopf FDE, which governs the characteristic functional of the stochastic solution to the Burgers equation evolving from a random initial state.
The discretization of non-local operators, e.g., solution operators of partial differential equations or integral operators, leads to large densely populated matrices. $\mathcal{H}^2$-matrices take advantage of local low-rank structures in these matrices to provide an efficient data-sparse approximation that allows us to handle large matrices efficiently, e.g., to reduce the storage requirements to $\mathcal{O}(n k)$ for $n$-dimensional matrices with local rank $k$, and to reduce the complexity of the matrix-vector multiplication to $\mathcal{O}(n k)$ operations. In order to perform more advanced operations, e.g., to construct efficient preconditioners or evaluate matrix functions, we require algorithms that take $\mathcal{H}^2$-matrices as input and approximate the result again by $\mathcal{H}^2$-matrices, ideally with controllable accuracy. In this manuscript, we introduce an algorithm that approximates the product of two $\mathcal{H}^2$-matrices and guarantees block-relative error estimates for the submatrices of the result. It uses specialized tree structures to represent the exact product in an intermediate step, thereby allowing us to apply mathematically rigorous error control strategies.
小貼士
登錄享
相關主題
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191