The enumeration of all outputs of a given multivariate polynomial is a fundamental mathematical problem and is incorporated in some algebraic attacks on multivariate public key cryptosystems. For a degree-d polynomial...
详细信息
ISBN:
(纸本)9783031400025;9783031400032
The enumeration of all outputs of a given multivariate polynomial is a fundamental mathematical problem and is incorporated in some algebraic attacks on multivariate public key cryptosystems. For a degree-d polynomial in n variables over the finite field with q elements, solving the enumeration problem classically requires O ((n+d/d) . q(n)) operations. At CHES 2010, Bouillaguet et al. proposed a fast enumeration algorithm over the binary field F-2. Their proposed algorithm covers all the inputs of a given polynomial following the order of Gray codes and is completed by O(d . 2(n)) bit operations. However, to the best of our knowledge, a result achieving the equivalent efficiency in general finite fields is yet to be proposed. In this study, we propose a novel algorithm that enumerates all the outputs of a degree-d polynomial in n variables over F-q with a prime number q by O(d . q(n)) operations. The proposed algorithm is constructed by using a lexicographic order instead of Gray codes to cover all the inputs. This result can be seen as an extension of the result of Bouillaguet et al. to general finite fields and is almost optimal in terms of time complexity. We can naturally apply the proposed algorithm to the case where q is a prime power. Notably, our enumeration algorithm differs from the algorithm by Bouillaguet et al. even in the case of q = 2.
From social to biological networks, prior research in complex networks have demonstrated the importance of the frequency and distribution of different types of motifs to important network functions and properties. A n...
详细信息
From social to biological networks, prior research in complex networks have demonstrated the importance of the frequency and distribution of different types of motifs to important network functions and properties. A network motif (or graphlet) is defined as a small connected sub-pattern which is over-represented in a network. Network motifs have been widely applied in a wide range of applications, namely biological, social, and technical networks. The counting of the network motif involves expensive enumeration of graph sub-patterns along with the detection of graph isomorphism. In general, network motif detection algorithms are computationally expensive and often designed to operate over static networks, which is infeasible for dynamic network structures. While significant work has been conducted to improve the efficiency of motif enumeration algorithms for complex networks, it is generally accepted that for most applications where dynamic network structure is important, the use of such algorithms is very limited and often impractical. In this dissertation, we emphasize on providing an exact count of a selected set of motifs in dynamic networks. We propose, develop, and demonstrate an efficient and robust algorithmic approach to achieve fast enumeration of motif distribution based on localized changes in network structure. The proposed technique will enable the tracking of motif distributions in large scale dynamic networks. We show how our algorithm can quickly update the frequency of different network motifs in dynamic networks. Starting from an initial frequency of network motif types, the proposed algorithmic approach monitors local network changes. Then, it efficiently updates the motif distribution at run-time without requiring the re-evaluation of the complete network, thereby avoiding redundant searches. The experimental results show that our approach is successful in reducing the computational time by eliminating the overlapped sub-patterns. Run-time monit
This paper develops an enumeration algorithm for the no-wait flow shop scheduling problem with due date constraints. In this problem, waiting time is not allowed between successive operations of jobs. Plus, each job i...
详细信息
This paper develops an enumeration algorithm for the no-wait flow shop scheduling problem with due date constraints. In this problem, waiting time is not allowed between successive operations of jobs. Plus, each job is accompanied by a due date which is dealt with as a hard constraint The considered performance criterion is makespan. The problem is strongly NP-hard. In this research, a new modelling approach is developed for the problem. This new modelling technique and the resulting observations are incorporated into a new exact algorithm to solve the problem to optimality. To investigate the performance of the algorithm, a number of test problems arc solved and the results are reported. Computational results demonstrate that the developed algorithm is significantly faster than the mathematical models. (C) 2016, IFAC (International Federation of Automatic Control) Hosting by Elsevier Ltd. All rights reserved.
In this paper, we propose an algorithm for enumerating all integers nonrepresentable by a given set of positive integers. We say that a positive integer n is nonrepresentable by positive integers a(0), a(1),..., a(d-1...
详细信息
In this paper, we propose an algorithm for enumerating all integers nonrepresentable by a given set of positive integers. We say that a positive integer n is nonrepresentable by positive integers a(0), a(1),..., a(d-1) if there exist no nonnegative integers x(0), x(1),..., x(d-1) such that Sigma(d-1)(i=0) x(i)a(i) = n. In this paper, we prove that the new algorithm runs in O (t(2)s) time, where t and s denote the input and output sizes, respectively;i.e. we prove that the algorithm can enumerate all the integers nonrepresentable by a given set of positive integers in amortized polynomial-time delay. (C) 2014 Elsevier B.V. All rights reserved.
The security of lattice-based cryptosystems is generally based on the hardness of the Shortest Vector Problem (SVP). There are two common categories of lattice algorithms to solve SVP: search algorithms and reduction ...
详细信息
ISBN:
(纸本)9783031088964;9783031088957
The security of lattice-based cryptosystems is generally based on the hardness of the Shortest Vector Problem (SVP). There are two common categories of lattice algorithms to solve SVP: search algorithms and reduction algorithms. The original enumeration algorithm (ENUM) is one of the former algorithms which run in exponential time due to the exhaustive search. Further, ENUM is used as a subroutine for the BKZ algorithm, which is one of the most practical reduction algorithms. It is a critical issue to reduce the computational complexity of ENUM. In this paper, first, we improve the mechanism in the so-called reordering method proposed by Wang in ACISP 2018. We call this improvement Primal Projective Reordering (PPR) method which permutates the projected vectors by decreasing norms;therefore it performs better to reduce the number of search nodes in ENUM. Then, we propose a Dual Projective Reordering (DPR) method permutating the projected vectors in its dual lattice. In addition, we propose a condition to decide whether the reordering method should be adopted or not. Preliminary experimental results show that our proposed reordering methods can successfully reduce the number of ENUM search nodes comparing to the predecessor, e.g., PPR reduces around 9.6% on average in 30-dimensional random lattices, and DPR reduces around 32.8% on average in 45-dimensional random lattices. Moreover, our simulation shows that the higher the lattice dimension, the more the proposed reordering method can reduce ENUM search nodes.
A compatible Euler trail (tour) in an edge-colored graph is an Euler trail (tour) in which each two edges traversed consecutively along the Euler trail (tour) have distinct colors. In this paper, we show that the prob...
详细信息
A compatible Euler trail (tour) in an edge-colored graph is an Euler trail (tour) in which each two edges traversed consecutively along the Euler trail (tour) have distinct colors. In this paper, we show that the problem of counting compatible Euler trails in edge-colored graphs is #P-complete, and develop O(m N) time algorithms for enumerating compatible Euler trails (tours) in edge-colored graphs with m edges and N compatible Euler trails (tours). It is worth mentioning that our algorithms can run in O(N) time when there is no vertex v with degree 4 and maximum monochromatic degree 2.
Finding, Counting, and Enumerating different structural patterns in a large graph is a fundamental task in graph mining and forms the basis of many disciplines such as social network analysis, computational epidemiolo...
详细信息
ISBN:
(纸本)9789819612413;9789819612420
Finding, Counting, and Enumerating different structural patterns in a large graph is a fundamental task in graph mining and forms the basis of many disciplines such as social network analysis, computational epidemiology, etc. Clique is one such structural pattern which is basically a subset of the vertices such that every pair of vertices in this subset is an edge in the graph. In practice, many graphs that we deal with are time-varying, i.e., the edge set of the graph is changing over time. To analyze the structural patterns of such graphs, the notion of temporal clique has been introduced. In this paper, we define the concept of alpha-Persistent Temporal Clique (alpha-PT Clique) in a binary node-attributed temporal network and propose an enumeration strategy for such cliques present in a given temporal network. The correctness of the proposed methodology has been illustrated and the complexity analysis has been done. Several experiments have been conducted with real-world temporal network datasets to illustrate the efficiency and effectiveness of the proposed solution approach. We have also demonstrated that alpha-PT Clique enumeration will be useful to choose Top-k people to be vaccinated to reduce the propagation of pandemic.
A set of objects and a binary relation among them is often represented by a graph or network. Most of the networks that we deal with in practice (e.g., social networks, human contact networks, financial transaction ne...
详细信息
ISBN:
(纸本)9783031706288;9783031706264
A set of objects and a binary relation among them is often represented by a graph or network. Most of the networks that we deal with in practice (e.g., social networks, human contact networks, financial transaction networks, etc.) are time-varying in nature, i.e., the relationship changes over time. Such networks are often modeled as Temporal Networks. In this paper, we study the problem of enumerating cohesive sub-structures present in a given temporal network. We call such substructure as (Delta, gamma)-clique, which is a tuple of vertex subset and time interval, such that every pair of vertices in the vertex subset has at least gamma edges in every Delta duration of the time interval. We propose a recursive solution approach to enumerate all the maximal (Delta, gamma)-cliques. The proposed approach is divided into two parts. First, it initializes all the cliques of size 2 with maximum duration satisfying the (Delta, gamma)-clique property, and recursively, adds vertices till it becomes maximal. The correctness of the proposed method has been established, and the complexity analysis has also been done. Several experiments are carried out using real-world temporal network datasets to highlight the efficiency of the proposed approach. The reported results show that the proposed solution approach is approximately six times faster and more space-efficient than the best existing method.
We study linear bilevel programming problems whose lower-level objective is given by a random cost vector with known distribution. We consider the case where this distribution is nonatomic, allowing to reformulate the...
详细信息
We study linear bilevel programming problems whose lower-level objective is given by a random cost vector with known distribution. We consider the case where this distribution is nonatomic, allowing to reformulate the problem of the leader using the Bayesian approach in the sense of Salas and Svensson (SIAM J Optim 33(3):2311-2340, 2023), with a decision-dependent distribution that concentrates on the vertices of the feasible set of the follower's problem. We call this a vertex-supported belief. We prove that this formulation is piecewise affine over the so-called chamber complex of the feasible set of the high-point relaxation. We propose two algorithmic approaches to solve general problems enjoying this last property. The first one is based on enumerating the vertices of the chamber complex. This approach is not scalable, but we present it as a computational baseline and for its theoretical interest. The second one is a Monte-Carlo approximation scheme based on the fact that randomly drawn points of the domain lie, with probability 1, in the interior of full-dimensional chambers, where the problem (restricted to this chamber) can be reduced to a linear program. Finally, we evaluate these methods through computational experiments showing both approaches' advantages and challenges.
In the monotone integer dualization problem, we are given two sets of vectors in an integer box such that no vector in the first set is dominated by a vector in the second. The question is to check if the two sets of ...
详细信息
In the monotone integer dualization problem, we are given two sets of vectors in an integer box such that no vector in the first set is dominated by a vector in the second. The question is to check if the two sets of vectors cover the entire integer box by upward and downward domination, respectively. It is known that the problem is (quasi-)polynomially equivalent to that of enumerating all maximal feasible solutions of a given monotone system of linear/separable/supermodular inequalities over integer vectors. The equivalence is established via showing that the dual family of minimal infeasible vectors has size bounded by a (quasi-)polynomial in the sizes of the family to be generated and the input description. Continuing in this line of work, in this paper, we consider systems of polynomial, second-order cone, and semidefinite inequalities. We give sufficient conditions under which such bounds can be established and highlight some applications.
暂无评论