Improved generalized Atkin algorithm for computing square roots in finite fields

Recently, S. Müller developed a generalized Atkin algorithm for computing square roots, which requires two exponentiations in finite fields GF(q) when . In this paper, we present a simple improvement to it and the improved algorithm requires only one exponentiation for half of squares in finite fields GF(q) when . Furthermore, in finite fields GF(pm), where and m is odd, we reduce the complexity of the algorithm from O(m³log³p) to O(m²log²p(logm+logp)) using the Frobenius map and normal basis representation.     

External-memory depth-first search algorithm for solid grid graphs

In this paper, we propose an external memory depth first search algorithm for solid grid graphs, a subclass of grid graphs. The I/O-complexity of the algorithm is O(sort(N)), where N=|V|+|E|, is the sorting I/O-complexity, M is the memory size, and B is the block size. Since grid graphs might be nonplanar (if diagonal edges intersect), they are beyond the reach of existing planar depth first search algorithms. The best known algorithm for this class of graph is the standard (internal memory) DFS algorithm with appropriate block (sub-grid) I/O-access. Its I/O-complexity is .     

Pharmacophore and docking-based combined in-silico study of KDR inhibitors

The growth and metastasis of solid tumors is dependent on angiogenesis. The vascular endothelial growth factor (VEGF) and its cell surface receptor in human KDR (kinase domain containing receptor or VEGFR-2) have particular interest because of their importance in angiogenesis. The development of novel inhibitors of VEGFR-2 would be helpful to check the growth of tumors. Quantitative structure activity relationship (QSAR) analyses used to understand the structural factors affecting inhibitory potency of thiazole-substituted pyrazolone derivatives. Several pharmacophore-based models indicated the importance of steric, hydrophobic and hydrogen bond acceptor groups to inhibitory activity. The comparative molecular field analyses (CoMFA) and comparative molecular similarity indices analyses (CoMSIA) based 3D-QSAR models were derived using pharmacophore-based alignment. Both CoMFA (q² = 0.70, r² = 0.97 and ) and CoMSIA (q² = 0.54, r² = 0.82 and ) gave reasonable results. The molecular docking (receptor-guided technique) with a recently reported receptor structure (PDB = 1YWN) were performed. The docked alignment was subsequently used for 3D-QSAR (CoMFA; q² = 0.56, r² = 0.97, , CoMSIA; q² = 0.58 r² = 0.91, ). The overall both studies were indicated, steric, electrostatic and hydrogen bond acceptor effects contribute to the inhibitory activity. CoMFA and CoMSIA models suggested that a positive bulk with hydrophobic effect is desirable around position 4 and 5 and hydrogen bond acceptor groups around pyrazolones ring will be helpful.     

Almost tight upper bound for finding Fourier coefficients of bounded pseudo-Boolean functions

A k-bounded pseudo-Boolean function is a real-valued function on n{0,1} that can be expressed as a sum of functions depending on at most k input bits. The k-bounded functions play an important role in a number of areas including molecular biology, biophysics, and evolutionary computation. We consider the problem of finding the Fourier coefficients of k-bounded functions, or equivalently, finding the coefficients of multilinear polynomials on n{−1,1} of degree k or less. Given a k-bounded function f with m non-zero Fourier coefficients for constant k, we present a randomized algorithm to find the Fourier coefficients of f with high probability in function evaluations. The best known upper bound was , where λ(n,m) is between and n depending on m. Our bound improves the previous bound by a factor of . It is almost tight with respect to the lower bound . In the process, we also consider the problem of finding k-bounded hypergraphs with a certain type of queries under an oracle with one-sided error. The problem is of self interest and we give an optimal algorithm for the problem.     

On the construction of discrete filters for symmetry-preserving regularization models

Since direct numerical simulations cannot be computed at high Reynolds numbers, a dynamically less complex formulation is sought. In the quest for such a formulation, we consider regularizations of the convective term that preserve the symmetry and conservation properties exactly. This requirement yielded a novel class of regularizations [Verstappen R. On restraining the production of small scales of motion in a turbulent channel flow. Comput Fluids 2008;37:887–97.] that restrains the convective production of smaller and smaller scales of motion in an unconditionally stable manner, meaning that the velocity cannot blow up in the energy-norm (in 2D also: enstrophy-norm). The numerical algorithm used to solve the governing equations must preserve the symmetry and conservation properties too. To do so, one of the most critical issues is the discrete filtering. The method requires a list of properties that, in general, is not preserved by classical filters for LES unless they are imposed a posteriori. In the present paper, we propose a novel class of discrete filters that preserves such properties per se. They are based on polynomial functions of the discrete diffusive operator, , with the general form . Then, the coefficients, d_m, follow from the requirement that, at the smallest grid scale k_c, the amount by which the interactions between the wavevector-triples (k_c, k_c − q, q) are damped must become virtually independent of the qth Fourier-mode. This allows an optimal control of the subtle balance between convection and diffusion at the smallest grid scale to stop the vortex-stretching. Finally, the resulting filters are successfully tested for the Burgers’ equation.     

An iterative algorithm for solving a pair of matrix equations over generalized centro-symmetric matrices

A matrix is said to be a symmetric orthogonal matrix if . A matrix is said to be generalized centro-symmetric (generalized central anti-symmetric) with respect to P, if A=PAP (A=−PAP). The generalized centro-symmetric matrices have wide applications in information theory, linear estimate theory and numerical analysis. In this paper, we propose a new iterative algorithm to compute a generalized centro-symmetric solution of the linear matrix equations . We show, when the matrix equations are consistent over generalized centro-symmetric matrix Y, for any initial generalized centro-symmetric matrix Y₁, the sequence {Y_k} generated by the introduced algorithm converges to a generalized centro-symmetric solution of matrix equations . The least Frobenius norm generalized centro-symmetric solution can be derived when a special initial generalized centro-symmetric matrix is chosen. Furthermore, the optimal approximation generalized centro-symmetric solution to a given generalized centro-symmetric matrix can be derived. Several numerical examples are given to show the efficiency of the presented method.     

Stabilization of some fractional delay systems of neutral type

In this note, we give new stability tests which enable one to fully characterize the H_∞-stability of systems with transfer function , where h>0 and p,q,r are real polynomials in the variable s^μ for 0<μ<1.As an application of this, in the case r(s)=1 and degp=degq=1, families of H_∞-stabilizing controllers are given and a complete parametrization of all H_∞-stabilizing controllers is obtained when .     

The Kolmogorov Expression Complexity of Logics

The purpose of the paper is to propose a completely new notion of complexity of logics in finite-model theory. It is the Kolmogorov variant of the Vardi'sexpression complexity. We define it by considering the value of the Kolmogorov complexityC(L[]) of the infinite stringL[] of all truth values of sentences ofLin . The higher is this value, the more expressive is the logicLin . If is a class of finite models, then the value ofC(L[]) over all ∈ is a measure of expressive power ofLin . Unboundedness ofC(L[])−C(L′[]) for ∈ implies nonexistence of a recursive interpretation ofLinL′. A version of this statement with complexities modulo oracles implies the nonexistence of any interpretation ofLinL′. Thus the valuesC(L[]) modulo oracles constitute an invariant of the expressive power of logics over finite models, depending on their real (absolute) expressive power, and not on the syntax. We investigate our notion for fragments of the infinitary logic ^ω_∞ω: least fixed point logic (LFP) and partial fixed point logic (PFP). We prove a precise characterization of 0–1 laws for these logics in terms of a certain boundedness condition placed onC(L[]). We get an extension of the notion of a 0–1 law by imposing an upper bound on the value ofC(L[]) growing not too fast with cardinality of , which still implies inexpressibility results similar to those implied by 0–1 laws. We also discuss classes in whichC(PFP^k[]) is very high. It appears that then PFP or its simple extension can define all the PSPACE subsets of .     

Combining OWL ontologies using -Connections

The standardization of the Web Ontology Language (OWL) leaves (at least) two crucial issues for Web-based ontologies unsatisfactorily resolved, namely how to represent and reason with multiple distinct, but linked ontologies, and how to enable effective knowledge reuse and sharing on the Semantic Web.In this paper, we present a solution for these fundamental problems based on -Connections. We aim to use -Connections to provide modelers with suitable means for developing Web ontologies in a modular way and to provide an alternative to the owl:imports construct.With such motivation, we present in this paper a syntactic and semantic extension of the Web Ontology language that covers -Connections of OWL-DL ontologies. We show how to use such an extension as an alternative to the owl:imports construct in many modeling situations. We investigate different combinations of the logics , and for which it is possible to design and implement reasoning algorithms, well-suited for optimization.Finally, we provide support for -Connections in both an ontology editor, SWOOP, and an OWL reasoner, Pellet.     

Elementary approximation algorithms for prize collecting Steiner tree problems

This paper deals with approximation algorithms for the prize collecting generalized Steiner forest problem, defined as follows. The input is an undirected graph G=(V,E), a collection T={T₁,…,T_k}, each a subset of V of size at least 2, a weight function , and a penalty function . The goal is to find a forest F that minimizes the cost of the edges of F plus the penalties paid for subsets T_i whose vertices are not all connected by F. Our main result is a -approximation for the prize collecting generalized Steiner forest problem, where n2 is the number of vertices in the graph. This obviously implies the same approximation for the special case called the prize collecting Steiner forest problem (all subsets T_i are of size 2). The approximation algorithm is obtained by applying the local ratio method, and is much simpler than the best known combinatorial algorithm for this problem.Our approach gives a -approximation for the prize collecting Steiner tree problem (all subsets T_i are of size 2 and there is some root vertex r that belongs to all of them). This latter algorithm is in fact the local ratio version of the primal-dual algorithm of Goemans and Williamson [M.X. Goemans, D.P. Williamson, A general approximation technique for constrained forest problems, SIAM Journal on Computing 24 (2) (April 1995) 296–317]. Another special case of our main algorithm is Bar-Yehuda's local ratio -approximation for the generalized Steiner forest problem (all the penalties are infinity) [R. Bar-Yehuda, One for the price of two: a unified approach for approximating covering problems, Algorithmica 27 (2) (June 2000) 131–144]. Thus, an important contribution of this paper is in providing a natural generalization of the framework presented by Goemans and Williamson, and later by Bar-Yehuda.     

MGR Hash Functions

Abstract

GOST-R 34.11-94 is a Russian standard cryptographic hash function that was introduced in 1994 by the Russian Federal Agency for the purposes of information processing, information security, and digital signature. Mendel et al. (2008 Mendel, F., N. Pramstaller, C. Rechberger, M. Kontak, and J. Szmidt. 2008. Cryptanalysis of the GOST hash function, Advances in Cryptology – CRYPTO 2008, vol. 5157, 162–178. [Google Scholar]) and Courtois and Mourouzis (2011 Courtois, N., and T. Mourouzis. 2011. Black-box collision attacks on the compression function of the GOST hash function. SECRYPT. Proceedings of the International Conference on Security and Cryptography, 325–332, IEEE. [Google Scholar]) found attacks on the compression function of the GOST-R structure that were basically weaknesses of the GOST-R block cipher (GOST 28147–89, 1989 GOST 28147-89. 1989. Systems of the information treatment, cryptographic security, algorithms of the cryptographic transformation (in Russian). [Google Scholar]). Hence in 2012, it was updated to GOST-R 34.11-2012, which replaced the older one for all its applications from January 2013. GOST-R 34.11-2012 is based on a modified Merkle-Damgård construction. Here we present a modified version of GOST-R 34.11-2012 (Modified GOST-R (MGR) hash). The design of the MGR hash is based on wide-pipe construction, which is also a modified Merkle-Damgård construction. MGR is much more secure as well as three times faster than GOST-R 34.11-2012. Advanced Encryption Standard (AES)-like block ciphers have been used in designing the compression function of MGR because AES is one of the most efficient and secure block ciphers and has been evaluated for more than 14?years. A detailed statistical analysis with a few other attacks on MGR is incorporated into this paper.     

Spectral radius minimization for optimal average consensus and output feedback stabilization

In this paper, we consider two problems which can be posed as spectral radius minimization problems. Firstly, we consider the fastest average agreement problem on multi-agent networks adopting a linear information exchange protocol. Mathematically, this problem can be cast as finding an optimal such that x(k+1)=Wx(k), , and W∈S(E). Here, is the value possessed by the agents at the kth time step, is an all-one vector and S(E) is the set of real matrices in with zeros at the same positions specified by a network graph G(V,E), where V is the set of agents and E is the set of communication links between agents. The optimal W is such that the spectral radius is minimized. To this end, we consider two numerical solution schemes: one using the qth-order spectral norm (2-norm) minimization (q-SNM) and the other gradient sampling (GS), inspired by the methods proposed in [Burke, J., Lewis, A., & Overton, M. (2002). Two numerical methods for optimizing matrix stability. Linear Algebra and its Applications, 351-352, 117-145; Xiao, L., & Boyd, S. (2004). Fast linear iterations for distributed averaging. Systems & Control Letters, 53(1), 65-78]. In this context, we theoretically show that when E is symmetric, i.e. no information flow from the ith to the jth agent implies no information flow from the jth to the ith agent, the solution from the 1-SNM method can be chosen to be symmetric and is a local minimum of the function . Numerically, we show that the q-SNM method performs much better than the GS method when E is not symmetric. Secondly, we consider the famous static output feedback stabilization problem, which is considered to be a hard problem (some think NP-hard): for a given linear system (A,B,C), find a stabilizing control gain K such that all the real parts of the eigenvalues of A+BKC are strictly negative. In spite of its computational complexity, we show numerically that q-SNM successfully yields stabilizing controllers for several benchmark problems with little effort.     

Periodically switched stability induces exponential stability of discrete-time linear switched systems in the sense of Markovian probabilities

The conjecture that periodically switched stability implies absolute asymptotic stability of random infinite products of a finite set of square matrices, has recently been disproved under the guise of the finiteness conjecture. In this paper, we show that this conjecture holds in terms of Markovian probabilities. More specifically, let S_k∈C^n×n,1≤k≤K, be arbitrarily given K matrices and , where n,K≥2. Then we study the exponential stability of the following discrete-time switched dynamics S: where can be an arbitrary switching sequence.For a probability row-vector and an irreducible Markov transition matrix with , we denote by the Markovian probability on corresponding to . By using symbolic dynamics and ergodic-theoretic approaches, we show that, if S possesses the periodically switched stability then, (i) it is exponentially stable -almost surely; (ii) the set of stable switching sequences has the same Hausdorff dimension as . Thus, the periodically switched stability of a discrete-time linear switched dynamics implies that the system is exponentially stable for “almost” all switching sequences.     

Implicit B-trees: a new data structure for the dictionary problem

An implicit data structure for the dictionary problem maintains n data values in the first n locations of an array in such a way that it efficiently supports the operations insert, delete and search. No information other than that in O(1) memory cells and in the input data is to be retained; and the only operations performed on the data values (other than reads and writes) are comparisons. This paper describes the implicit B-tree, a new data structure supporting these operations in block transfers like in regular B-trees, under the realistic assumption that a block stores keys, so that reporting r consecutive keys in sorted order has a cost of block transfers. En route a number of space efficient techniques for handling segments of a large array in a memory hierarchy are developed. Being implicit, the proposed data structure occupies exactly ⌈n/B⌉ blocks of memory after each update, where n is the number of keys after each update and B is the number of keys contained in a memory block. In main memory, the time complexity of the operations is , disproving a conjecture of the mid 1980s.     

Fast multiplication of matrices over a finitely generated semiring

In this paper we show that n×n matrices with entries from a semiring R which is generated additively by q generators can be multiplied in time O(q²nω), where nω is the complexity for matrix multiplication over a ring (Strassen: ω<2.807, Coppersmith and Winograd: ω<2.376).We first present a combinatorial matrix multiplication algorithm for the case of semirings with q elements, with complexity , matching the best known methods in this class.Next we show how the ideas used can be combined with those of the fastest known boolean matrix multiplication algorithms to give an O(q²nω) algorithm for matrices of, not necessarily finite, semirings with q additive generators.For finite semirings our combinatorial algorithm is simple enough to be a practical algorithm and is expected to be faster than the O(q²nω) algorithm for matrices of practically relevant sizes.