This paper proposes a method of estimating computational complexity of problem through analyzing its input condition for N-vehicle exploration problem. The N-vehicle problem is firstly formulated to determine the opti...This paper proposes a method of estimating computational complexity of problem through analyzing its input condition for N-vehicle exploration problem. The N-vehicle problem is firstly formulated to determine the optimal replacement in the set of permutations of 1 to N. The complexity of the problem is factorial of N （input scale of problem）. To balance accuracy and efficiency of general algorithms, this paper mentions a new systematic algorithm design and discusses correspondence between complexity of problem and its input condition, other than just putting forward a uniform approximation algorithm as usual. This is a new technique for analyzing computation of NP problems. The method of corresponding is then presented. We finally carry out a simulation to verify the advantages of the method： 1） to decrease computation in enumeration; 2） to efficiently obtain computational complexity for any N-vehicle case; 3） to guide an algorithm design for any N-vehicle case according to its complexity estimated by the method.展开更多
In this note, we first derive an exponential generating function of the alternating run polynomials. We then deduce an explicit formula of the alternating run polynomials in terms of the partial Bell polynomials.
In this work we propose efficient codec algorithms for watermarking images that are intended for uploading on the web under intellectual property protection. Headed to this direction, we recently suggested a way in wh...In this work we propose efficient codec algorithms for watermarking images that are intended for uploading on the web under intellectual property protection. Headed to this direction, we recently suggested a way in which an integer number w which being transformed into a self-inverting permutation, can be represented in a two dimensional (2D) object and thus, since images are 2D structures, we have proposed a watermarking algorithm that embeds marks on them using the 2D representation of w in the spatial domain. Based on the idea behind this technique, we now expand the usage of this concept by marking the image in the frequency domain. In particular, we propose a watermarking technique that also uses the 2D representation of self-inverting permutations and utilizes marking at specific areas thanks to partial modifications of the image’s Discrete Fourier Transform (DFT). Those modifications are made on the magnitude of specific frequency bands and they are the least possible additive information ensuring robustness and imperceptiveness. We have experimentally evaluated our algorithms using various images of different characteristics under JPEG compression. The experimental results show an improvement in comparison to the previously obtained results and they also depict the validity of our proposed codec algorithms.展开更多
A highly practical parallel signcrypUon scheme named PLSC from trapdoor permutations （TDPs for short） was built to perform long messages directly. The new scheme follows the Idea ＂scramble all, and encrypt small＂,...A highly practical parallel signcrypUon scheme named PLSC from trapdoor permutations （TDPs for short） was built to perform long messages directly. The new scheme follows the Idea ＂scramble all, and encrypt small＂, using some scrambling operation on message m along with the user＇s Identities, and then passing, In paraliel, small parts of the scrambling result through corresponding TOPs. This design enables the scheme to flexibly perform long messages of arbitrary length while avoid repeatedly invoking TDP operations such as the CBC mode, or verbosely black-box composing symmetric encryption and slgncryption, resulting in noticeable practical sevlngs in both message bandwidth and efficiency. Concretely, the signcryptlon scheme requires exactly one computation of the ＂receiver＇s TDP＂ （for ＂encryptlon＂） and one Inverse computation of the ＂sender＇s TDP＂ （for ＂authentication＂）, which Is of great practical significance in directly performing long messages, since the major bottleneck for many public encryptlon schemes is the excessive computational overhead of performing TDP operations. Cutting out the verbosely repeated padding, the newly proposed scheme Is more efficient than a black-box hybrid scheme. Most importantly, the proposed scheme has been proven to be tightly semanUcaiiy secure under adaptive chosen clphertext attacks （iND-CCA2） and to provide integrity of clphertext （INT-CTXT） as well as non-repudiation in the random oracle model. All of these security guarantees are provided in the full multi-user, insider-security setting. Moreover, though the scheme is designed to perform long messages, it may also be appropriate for settings where It is Impractical to perform large block of messages （i.e. extremely low memory environments such as smart cards）.展开更多
A property(C) for permutation pairs is introduced. It is shown that if a pair{π_1, π_2} of permutations of(1,2,…,n) has property(C),then the D-type map Φ_(π_1,π_2) on n× n complex matrices constructed from ...A property(C) for permutation pairs is introduced. It is shown that if a pair{π_1, π_2} of permutations of(1,2,…,n) has property(C),then the D-type map Φ_(π_1,π_2) on n× n complex matrices constructed from {π_1,π_2} is positive. A necessary and sufficient condition is obtained for a pair {π_1,π_2} to have property(C),and an easily checked necessary and sufficient condition for the pairs of the form {π~p,π~q} to have property(C) is given, whereπ is the permutation defined by π(i) = i + 1 mod n and 1≤ p < q≤ n.展开更多
We generalize the Eulerian numbers ?to sets of numbers Eμ(k,l), (μ=0,1,2,···) where the Eulerian numbers appear as the special case μ=1. This can be used for the evaluation of generalizations Eμ(k,Z...We generalize the Eulerian numbers ?to sets of numbers Eμ(k,l), (μ=0,1,2,···) where the Eulerian numbers appear as the special case μ=1. This can be used for the evaluation of generalizations Eμ(k,Z) of the Geometric series G0(k;Z)=G1(0;Z) by splitting an essential part (1-Z)-(μK+1) where the numbers Eμ(k,l) are then the coefficients of the remainder polynomial. This can be extended for non-integer parameter k to the approximative evaluation of generalized Geometric series. The recurrence relations and for the Generalized Eulerian numbers E1(k,l) are derived. The Eulerian numbers are related to the Stirling numbers of second kind S(k,l) and we give proofs for the explicit relations of Eulerian to Stirling numbers of second kind in both directions. We discuss some ordering relations for differentiation and multiplication operators which play a role in our derivations and collect this in Appendices.展开更多
High throughput gene expression analysis is swiftly becoming the focal point for deciphering molecular mechanisms underlying various dif-ferent biological questions. Testament to this is the fact that vast volumes of ...High throughput gene expression analysis is swiftly becoming the focal point for deciphering molecular mechanisms underlying various dif-ferent biological questions. Testament to this is the fact that vast volumes of expression profiles are being generated rapidly by scientists worldwide and subsequently stored in publicly available data repositories such as ArrayEx-press and the Gene Expression Omnibus (GEO). Such wealth of biological data has motivated biologists to compare expression profiles gen-erated from biologically-related microarray ex-periments in order to unravel biological mecha-nisms underlying various states of diseases. However, without the availability of appropriate software and tools, they are compelled to use manual or labour-intensive methods of com-parisons. A scrutiny of current literature makes it apparent that there is a soaring need for such bioinformatics tools that cater for the multiple analyses of expression profiles. In order to contribute towards this need, we have developed an efficient software pipeline for the analysis of multiple gene expression data-sets, called Micropath, which implements three principal functions;1) it searches for common genes amongst n number of datasets using a number crunching method of comparison as well as applying the principle of permutations and combinations in the form of a search strat-egy, 2) it extracts gene expression patterns both graphically and statistically, and 3) it streams co-expressed genes to all molecular pathways belonging to KEGG in a live fashion. We sub-jected MicroPath to several expression datasets generated from our tolerance-related in-house microarray experiments as well as published data and identified a set of 31 candidate genes that were found to be co-expressed across all interesting datasets. Pathway analysis revealed their putative roles in regulating immune toler-ance. MicroPath is freely available to download from: www.1066technologies.co.uk/micropath.展开更多
The main purpose of this paper is to solve the class equation in an alternating group, (i.e. find the solutions set ) and find the number of these solutions where ranges over the conjugacy class in and d is a positive...The main purpose of this paper is to solve the class equation in an alternating group, (i.e. find the solutions set ) and find the number of these solutions where ranges over the conjugacy class in and d is a positive integer. In this paper we solve the class equation in where , for all . is the complement set of where { of , with all parts of are different and odd}. is conjugacy class of and form class depends on the cycle type of its elements If and , then splits into the two classes of .展开更多
Secure computing paradigms impose new architectural challenges for general-purpose processors. Cryptographic processing is needed for secure communications, storage, and computations. We identify two categories of ope...Secure computing paradigms impose new architectural challenges for general-purpose processors. Cryptographic processing is needed for secure communications, storage, and computations. We identify two categories of operations in symmetric-key and public-key cryptographic algorithms that are not common in previous general-purpose workloads： advanced bit operations within a word and multi-word operations. We define MOMR （Multiple Operands Multiple Results） execution or datarich execution as a unified solution to both challenges. It allows arbitrary n-bit permutations to be achieved in one or two cycles, rather than O（n） cycles as in existing RISC processors. It also enables significant acceleration of multiword multiplications needed by public-key ciphers. We propose two implementations of MOMR： one employs only hardware changes while the other uses Instruction Set Architecture （ISA） support. We show that MOMR execution leverages available resources in typical multi-issue processors with minimal additional cost. Multi-issue processors enhanced with MOMR units provide additional speedup over standard multi-issue processors with the same datapath. MOMR is a general architectural solution for word-oriented processor architectures to incorporate datarich operations.展开更多
Let n be a positive integer. A permutation a of the symmetric group of permutations of is called a derangement if for each . Suppose that x and y are two arbitrary permutations of . We say that...Let n be a positive integer. A permutation a of the symmetric group of permutations of is called a derangement if for each . Suppose that x and y are two arbitrary permutations of . We say that a permutation a is a double derangement with respect to x and y if and for each . In this paper, we give an explicit formula for , the number of double derangements with respect to x and y. Let and let and be two subsets of with and . Suppose that denotes the number of derangements x such that . As the main result, we show that if and z is a permutation such that for and for , then where .展开更多
Simple formulas for the number of different cyclic and dihedral necklaces containing nj beads of the j-th color, and , are derived, using the Pólya enumeration theorem.
This paper introduces the concept of Latin arrays, discusses the general property on their enumeration, and gives formulae of numbers for (2,k)- and (3,k)-Latin arrays and for their isotopy classes.
基金supported by the State 973 Program(2006CB701306) and Key Laboratory of Management,Decision and Information Systems,CAS
文摘This paper proposes a method of estimating computational complexity of problem through analyzing its input condition for N-vehicle exploration problem. The N-vehicle problem is firstly formulated to determine the optimal replacement in the set of permutations of 1 to N. The complexity of the problem is factorial of N （input scale of problem）. To balance accuracy and efficiency of general algorithms, this paper mentions a new systematic algorithm design and discusses correspondence between complexity of problem and its input condition, other than just putting forward a uniform approximation algorithm as usual. This is a new technique for analyzing computation of NP problems. The method of corresponding is then presented. We finally carry out a simulation to verify the advantages of the method： 1） to decrease computation in enumeration; 2） to efficiently obtain computational complexity for any N-vehicle case; 3） to guide an algorithm design for any N-vehicle case according to its complexity estimated by the method.
文摘In this note, we first derive an exponential generating function of the alternating run polynomials. We then deduce an explicit formula of the alternating run polynomials in terms of the partial Bell polynomials.
文摘In this work we propose efficient codec algorithms for watermarking images that are intended for uploading on the web under intellectual property protection. Headed to this direction, we recently suggested a way in which an integer number w which being transformed into a self-inverting permutation, can be represented in a two dimensional (2D) object and thus, since images are 2D structures, we have proposed a watermarking algorithm that embeds marks on them using the 2D representation of w in the spatial domain. Based on the idea behind this technique, we now expand the usage of this concept by marking the image in the frequency domain. In particular, we propose a watermarking technique that also uses the 2D representation of self-inverting permutations and utilizes marking at specific areas thanks to partial modifications of the image’s Discrete Fourier Transform (DFT). Those modifications are made on the magnitude of specific frequency bands and they are the least possible additive information ensuring robustness and imperceptiveness. We have experimentally evaluated our algorithms using various images of different characteristics under JPEG compression. The experimental results show an improvement in comparison to the previously obtained results and they also depict the validity of our proposed codec algorithms.
基金Supported by the National Basic Research Program (Grant No. 2004CB318004)the National Natural Science Foundation of China (Grant Nos. 60373047 and 90604036)
文摘A highly practical parallel signcrypUon scheme named PLSC from trapdoor permutations （TDPs for short） was built to perform long messages directly. The new scheme follows the Idea ＂scramble all, and encrypt small＂, using some scrambling operation on message m along with the user＇s Identities, and then passing, In paraliel, small parts of the scrambling result through corresponding TOPs. This design enables the scheme to flexibly perform long messages of arbitrary length while avoid repeatedly invoking TDP operations such as the CBC mode, or verbosely black-box composing symmetric encryption and slgncryption, resulting in noticeable practical sevlngs in both message bandwidth and efficiency. Concretely, the signcryptlon scheme requires exactly one computation of the ＂receiver＇s TDP＂ （for ＂encryptlon＂） and one Inverse computation of the ＂sender＇s TDP＂ （for ＂authentication＂）, which Is of great practical significance in directly performing long messages, since the major bottleneck for many public encryptlon schemes is the excessive computational overhead of performing TDP operations. Cutting out the verbosely repeated padding, the newly proposed scheme Is more efficient than a black-box hybrid scheme. Most importantly, the proposed scheme has been proven to be tightly semanUcaiiy secure under adaptive chosen clphertext attacks （iND-CCA2） and to provide integrity of clphertext （INT-CTXT） as well as non-repudiation in the random oracle model. All of these security guarantees are provided in the full multi-user, insider-security setting. Moreover, though the scheme is designed to perform long messages, it may also be appropriate for settings where It is Impractical to perform large block of messages （i.e. extremely low memory environments such as smart cards）.
基金partially supported by National Natural Science Foundation of China(11671294)
文摘A property(C) for permutation pairs is introduced. It is shown that if a pair{π_1, π_2} of permutations of(1,2,…,n) has property(C),then the D-type map Φ_(π_1,π_2) on n× n complex matrices constructed from {π_1,π_2} is positive. A necessary and sufficient condition is obtained for a pair {π_1,π_2} to have property(C),and an easily checked necessary and sufficient condition for the pairs of the form {π~p,π~q} to have property(C) is given, whereπ is the permutation defined by π(i) = i + 1 mod n and 1≤ p < q≤ n.
文摘We generalize the Eulerian numbers ?to sets of numbers Eμ(k,l), (μ=0,1,2,···) where the Eulerian numbers appear as the special case μ=1. This can be used for the evaluation of generalizations Eμ(k,Z) of the Geometric series G0(k;Z)=G1(0;Z) by splitting an essential part (1-Z)-(μK+1) where the numbers Eμ(k,l) are then the coefficients of the remainder polynomial. This can be extended for non-integer parameter k to the approximative evaluation of generalized Geometric series. The recurrence relations and for the Generalized Eulerian numbers E1(k,l) are derived. The Eulerian numbers are related to the Stirling numbers of second kind S(k,l) and we give proofs for the explicit relations of Eulerian to Stirling numbers of second kind in both directions. We discuss some ordering relations for differentiation and multiplication operators which play a role in our derivations and collect this in Appendices.
文摘High throughput gene expression analysis is swiftly becoming the focal point for deciphering molecular mechanisms underlying various dif-ferent biological questions. Testament to this is the fact that vast volumes of expression profiles are being generated rapidly by scientists worldwide and subsequently stored in publicly available data repositories such as ArrayEx-press and the Gene Expression Omnibus (GEO). Such wealth of biological data has motivated biologists to compare expression profiles gen-erated from biologically-related microarray ex-periments in order to unravel biological mecha-nisms underlying various states of diseases. However, without the availability of appropriate software and tools, they are compelled to use manual or labour-intensive methods of com-parisons. A scrutiny of current literature makes it apparent that there is a soaring need for such bioinformatics tools that cater for the multiple analyses of expression profiles. In order to contribute towards this need, we have developed an efficient software pipeline for the analysis of multiple gene expression data-sets, called Micropath, which implements three principal functions;1) it searches for common genes amongst n number of datasets using a number crunching method of comparison as well as applying the principle of permutations and combinations in the form of a search strat-egy, 2) it extracts gene expression patterns both graphically and statistically, and 3) it streams co-expressed genes to all molecular pathways belonging to KEGG in a live fashion. We sub-jected MicroPath to several expression datasets generated from our tolerance-related in-house microarray experiments as well as published data and identified a set of 31 candidate genes that were found to be co-expressed across all interesting datasets. Pathway analysis revealed their putative roles in regulating immune toler-ance. MicroPath is freely available to download from: www.1066technologies.co.uk/micropath.
文摘The main purpose of this paper is to solve the class equation in an alternating group, (i.e. find the solutions set ) and find the number of these solutions where ranges over the conjugacy class in and d is a positive integer. In this paper we solve the class equation in where , for all . is the complement set of where { of , with all parts of are different and odd}. is conjugacy class of and form class depends on the cycle type of its elements If and , then splits into the two classes of .
文摘Secure computing paradigms impose new architectural challenges for general-purpose processors. Cryptographic processing is needed for secure communications, storage, and computations. We identify two categories of operations in symmetric-key and public-key cryptographic algorithms that are not common in previous general-purpose workloads： advanced bit operations within a word and multi-word operations. We define MOMR （Multiple Operands Multiple Results） execution or datarich execution as a unified solution to both challenges. It allows arbitrary n-bit permutations to be achieved in one or two cycles, rather than O（n） cycles as in existing RISC processors. It also enables significant acceleration of multiword multiplications needed by public-key ciphers. We propose two implementations of MOMR： one employs only hardware changes while the other uses Instruction Set Architecture （ISA） support. We show that MOMR execution leverages available resources in typical multi-issue processors with minimal additional cost. Multi-issue processors enhanced with MOMR units provide additional speedup over standard multi-issue processors with the same datapath. MOMR is a general architectural solution for word-oriented processor architectures to incorporate datarich operations.
文摘Let n be a positive integer. A permutation a of the symmetric group of permutations of is called a derangement if for each . Suppose that x and y are two arbitrary permutations of . We say that a permutation a is a double derangement with respect to x and y if and for each . In this paper, we give an explicit formula for , the number of double derangements with respect to x and y. Let and let and be two subsets of with and . Suppose that denotes the number of derangements x such that . As the main result, we show that if and z is a permutation such that for and for , then where .
文摘Simple formulas for the number of different cyclic and dihedral necklaces containing nj beads of the j-th color, and , are derived, using the Pólya enumeration theorem.
基金Project supported by the National Natural Science Foundation of China.
文摘This paper introduces the concept of Latin arrays, discusses the general property on their enumeration, and gives formulae of numbers for (2,k)- and (3,k)-Latin arrays and for their isotopy classes.
