Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn Functions of Markov Random Fields
104
0
0.0
(
0
)
Added by
Bernhard C. Geiger
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We derive two sufficient conditions for a function of a Markov random field (MRF) on a given graph to be a MRF on the same graph. The first condition is information-theoretic and parallels a recent information-theoretic characterization of lumpability of Markov chains. The second condition, which is easier to check, is based on the potential functions of the corresponding Gibbs field. We illustrate our sufficient conditions at the hand of several examples and discuss implications for practical applications of MRFs. As a side result, we give a partial characterization of functions of MRFs that are information-preserving.
rate research
Read More
Differential uniformity is a significant concept in cryptography as it quantifies the degree of security of S-boxes respect to differential attacks. Power functions of the form $F(x)=x^d$ with low differential uniformity have been extensively studied in the past decades due to their strong resistance to differential attacks and low implementation cost in hardware. In this paper, we give an affirmative answer to a recent conjecture proposed by Budaghyan, Calderini, Carlet, Davidova and Kaleyski about the differential uniformity of $F(x)=x^d$ over $mathbb{F}_{2^{4n}}$, where $n$ is a positive integer and $d=2^{3n}+2^{2n}+2^{n}-1$, and we completely determine its differential spectrum.
Let $mathbb{F}_{p^{n}}$ be the finite field with $p^n$ elements and $operatorname{Tr}(cdot)$ be the trace function from $mathbb{F}_{p^{n}}$ to $mathbb{F}_{p}$, where $p$ is a prime and $n$ is an integer. Inspired by the works of Mesnager (IEEE Trans. Inf. Theory 60(7): 4397-4407, 2014) and Tang et al. (IEEE Trans. Inf. Theory 63(10): 6149-6157, 2017), we study a class of bent functions of the form $f(x)=g(x)+F(operatorname{Tr}(u_1x),operatorname{Tr}(u_2x),cdots,operatorname{Tr}(u_{tau}x))$, where $g(x)$ is a function from $mathbb{F}_{p^{n}}$ to $mathbb{F}_{p}$, $taugeq2$ is an integer, $F(x_1,cdots,x_n)$ is a reduced polynomial in $mathbb{F}_{p}[x_1,cdots,x_n]$ and $u_iin mathbb{F}^{*}_{p^n}$ for $1leq i leq tau$. As a consequence, we obtain a generic result on the Walsh transform of $f(x)$ and characterize the bentness of $f(x)$ when $g(x)$ is bent for $p=2$ and $p>2$ respectively. Our results generalize some earlier works. In addition, we study the construction of bent functions $f(x)$ when $g(x)$ is not bent for the first time and present a class of bent functions from non-bent Gold functions.
While two hidden Markov process (HMP) resp. quantum random walk (QRW) parametrizations can differ from one another, the stochastic processes arising from them can be equivalent. Here a polynomial-time algorithm is presented which can determine equivalence of two HMP parametrizations $cM_1,cM_2$ resp. two QRW parametrizations $cQ_1,cQ_2$ in time $O(|S|max(N_1,N_2)^{4})$, where $N_1,N_2$ are the number of hidden states in $cM_1,cM_2$ resp. the dimension of the state spaces associated with $cQ_1,cQ_2$, and $S$ is the set of output symbols. Previously available algorithms for testing equivalence of HMPs were exponential in the number of hidden states. In case of QRWs, algorithms for testing equivalence had not yet been presented. The core subroutines of this algorithm can also be used to efficiently test hidden Markov processes and quantum random walks for ergodicity.
We consider learning a sparse pairwise Markov Random Field (MRF) with continuous-valued variables from i.i.d samples. We adapt the algorithm of Vuffray et al. (2019) to this setting and provide finite-sample analysis revealing sample complexity scaling logarithmically with the number of variables, as in the discrete and Gaussian settings. Our approach is applicable to a large class of pairwise MRFs with continuous variables and also has desirable asymptotic properties, including consistency and normality under mild conditions. Further, we establish that the population version of the optimization criterion employed in Vuffray et al. (2019) can be interpreted as local maximum likelihood estimation (MLE). As part of our analysis, we introduce a robust variation of sparse linear regression a` la Lasso, which may be of interest in its own right.
In this work we establish some new interleavers based on permutation functions. The inverses of these interleavers are known over a finite field $mathbb{F}_q$. For the first time M{o}bius and Redei functions are used to give new deterministic interleavers. Furthermore we employ Skolem sequences in order to find new interleavers with known cycle structure. In the case of Redei functions an exact formula for the inverse function is derived. The cycle structure of Redei functions is also investigated. The self-inverse and non-self-inver
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
