This note investigates the characterizing properties of the level sets of an M-convex function introduced by Murota.

A reallocation problem is defined as determining whether blocks can be moved from their current boxes to their destination boxes in the number of moves less than or equal to a given positive integer. This problem is defined simply and has many practical applications. We previously proved the following results: The reallocation problem such that the block volume is restricted to one volume unit for all blocks can be solved in linear time. But the reallocation problem such that the block volume is not restricted is NP-complete, even if no blocks have bypass boxes. But the computational complexity of the reallocation problems such that the range of the block volume is restricted has not yet been known. We prove that the reallocation problem is NP-complete even if the block volume is restricted to one or two volume units for all blocks and no blocks have bypass boxes. Furthermore, we prove that the reallocation problem is NP-complete, even if there are only two blocks such that each block has the volume units of fixed positive integer greater or equal than two, the volume of the other blocks is restricted to one volume unit, and no blocks have bypass boxes. Next, we consider such a block that must stays in a same box both in the initial state and in the final state but can be moved to another box for making room for other blocks. We prove that the reallocation problem such that an instance has such blocks is also NP-complete even if the block volume is restricted to one volume unit for all blocks.

This paper presents a non-interactive and optimally resilient distributed multiplication scheme. By non-interactive we mean that the players need to use outgoing communication channels only once without the need to synchronize with the other players as long as no disruption occurs. Our protocol withstands corrupt players up to less than the half of the players, so it provides optimal resiliency. Furthermore, the shared secrets are secure even against infinitely powerful adversaries. The security is proven under the intractability assumption of the discrete logarithm problem. Those properties are achieved by using an information theoretically secure non-interactive verifiable secret sharing as a kind of non-interactive proof system between a single prover and distributed verifiers. Compared to a former interactive solution in the same setting, the cost is an increase in local computation and communication complexity that is determined by the factor of the threshold used in the verifiable secret sharing.

The minimum distance of a linear code C is a useful metric property for estimating the error correction upper bound of C and the maximum likelihood decoding of a linear code C is also of practical importance and of theoretical interest. These problems are known to be NP-hard to approximate within any constant relative error to the optimum. As a problem related to the above, we consider the maximization problem MAX-WEIGHT: Given a generator matrix of a linear code C, find a codeword c C with its weight as close to the maximum weight of C as possible. It is shown that MAX-WEIGHT PTAS unless P=NP, however, no nontrivial approximation upper and lower bounds are known. In this paper, we investigate the complexity of MAX-WEIGHT to make the approximation upper and lower bounds more precise, and show that (1) MAX-WEIGHT is APX-complete; (2) MAX-WEIGHT is approximable within relative error 1/2 to the optimum; (3) MAX-WEIGHT is not approximable within relative error 1/10 to the optimum unless P=NP.

There are many public key cryptosystems that require random inputs to encrypt messages and their security is always discussed assuming that random objects are ideally generated. Since cryptosystems run on computers, it is quite natural that these random objects are computationally generated. One theoretical solution is the use of pseudorandom generators in the Yao's sense. Informally saying, the pseudorandom generators are polynomial-time algorithms whose outputs are computationally indistinguishable from the uniform distribution. Since if we use the Yao's generators then it takes much more time to generate pseudorandom objects than to encrypt messages in public key cryptosystems, we relax the conditions of pseudorandom generators to fit public key cryptosystems and give a minimal requirement for pseudorandom generators within public key cryptosystems. As an example, we discuss the security of the ElGamal cryptosystem with some well-known generators (e. g. , the linear congruential generator). We also propose a new pseudorandom number generator, for random inputs to the ElGamal cryptosystem, that satisfies the minimal requirement. The newly proposed generator is based on the linear congruential generator. We show some evidence that the ElGamal cryptosystem with the proposed generator is secure.

This paper studies the "usefulness" of initial conditions for distributed algorithms on anonymous networks. In the literature, several initial conditions such as making one vertex a leader, giving the number of vertex to each vertices, and so on, have been considered. In this paper, we study a relation between the initial condition by considering transformation algorithm from one initial condition to another. For such transformation algorithms, we consider in this paper, both deterministic and randomized distributed algorithms. For each deterministic and randomized transformation type, we show that the relation induces an infinite lattice structure among equivalence classes of initial conditions.

This paper presents a new proof to a polynomial-time algorithm for determining whether a given embedded graph is a Delaunay graph, i. e. , whether it is topologically equivalent to a Delaunay triangulation. The problem of recognizing the Delaunay graph had long been open. Recently Hodgson et al. gave a combinatorial characterization of the Delaunay graph, and thus constructed the polynomial-time algorithm for recognizing the Delaunay graphs. Their proof is based on sophisticated discussions on hyperbolic geometry. On the other hand, this paper gives another and simpler proof based on primitive arguments on Euclidean geometry. Moreover, the algorithm is applied to study the distribution of non-Delaunay graphs.

The three dimensional (3D) packing problem is to arrange given rectangular boxes in a rectangular box of the minimum volume without overlapping each other. As an approach, this paper introduces the system of three sequences of the box labels, the sequence-triple, to encode the topology of the 3D-packing. The topology is the system of relative relations in pairs of boxes such as right-of, above, front-of, etc. It will be proved that the sequence-triple represents the topology of the tractable 3D-packings which is a 3D-packing such that there is an order of the boxes along which all the boxes are extracted one by one in a certain fixed direction without disturbing other remaining boxes. The idea is extended to the system of five ordered sequences, the sequence-quintuple. A decoding rule is given by which any 3D-packing is represented. These coding systems are applied to design heuristic algorithms by simulated annealing which search the codes for better 3D-packings. Experimental results were very convincing its usefulness as automated packing algorithms.

A min-wise independent permutation family is known to be an efficient tool to estimate similarity of documents. Toward good understanding of min-wise independence, we present a characterization of exactly min-wise independent permutation families by size uniformity, which represents certain symmetry of the string representation of a family. Also, we present a general construction strategy which produce any exactly min-wise independent permutation family using this characterization.

The classical game of peg solitaire has uncertain origins, but was certainly popular by the time of Louis XIV, and was described by Leibniz in 1710. One of the classical problems concerning peg solitaire is the feasibility issue. An early tool used to show the infeasibility of various peg games is the rule-of-three [Suremain de Missery 1841]. In the 1960s the description of the solitaire cone [Boardman and Conway] provides necessary conditions: valid inequalities over this cone, known as pagoda functions, were used to show the infeasibility of various peg games. In this paper, we recall these necessary conditions and present new developments: the lattice criterion, which generalizes the rule-of-three; and results on the strongest pagoda functions, the facets of the solitaire cone.

Designing a protocol to exchange a secret key is one of the most fundamental subjects in cryptography. Using a random deal of cards, pairs of card players (agents) can share secret keys that are information-theoretically secure against an eavesdropper. A key set protocol, which uses a random deal of cards, can perform an Eulerian secret key exchange, in which the pairs of players sharing secret keys form an Eulerian circuit passing through all players. Along the Eulerian circuit any designated player can send a message to the rest of players and the message can be finally sent back to the sender. Checking the returned message with the original one, the sender can know whether the message circulation has not been influenced by a possible single transmission error or false alteration. It has been known that any Eulerian circuit formed by the protocol has length at most 3/2k, where k is the number of players. Note that the length corresponds to the time required to send the message to all players and acknowledge the secure receipt. In this paper, we show that the average length of Eulerian circuits is approximately k+ln k.

Let l be a positive integer, and let G be a graph with nonnegative integer weights on edges. Then a generalized vertex-coloring, called an l-coloring of G, is an assignment of colors to the vertices of G in such a way that any two vertices u and v get different colors if the distance between u and v in G is at most l. In this paper we give an algorithm to find an l-coloring of a given graph G with the minimum number of colors. The algorithm takes polynomial time if G is a partial k-tree and both l and k are bounded integers.

A new elliptic curve scalar multiplication algorithm is proposed. The algorithm offers about twice the throughput of some conventional OEF-base algorithms because it combines the Frobenius map with the table reference method based on base-φ expansion. Furthermore, since this algorithm suits conventional computational units such as 16, 32 and 64 bits, its base field F_p^m is expected to enhance elliptic curve operation efficiency more than F_q (q is a prime) or F_2ⁿ.

We consider the problem of finding a minimum weight k-connected spanning subgraph of a given edge-weighted graph G for k=3. The problem is known to be NP-hard for k 2, and there are an O(n²m) time 3-approximation algorithm due to Nutov and Penn and an O(n⁸) time 2-approximation algorithm due to Dinitz and Nutov, where n and m are the numbers of vertices and edges in G, respectively. In this paper, we present a 7/3-approximation algorithm which runs in O(n²m) time.

We consider the performance of hyperelliptic curve cryptosystems over the fields F_p vs. F_2n. We analyze the complexity of the group law of the jacobians J_C(F_p) and J_C(F_2n) and compare their performance taking into consideration the effectiveness of the word size (32-bit or 64-bit) of the applied CPU (Alpha and Pentium) on the arithmetic of the definition field. Our experimental results show that J_C(F_2n) is faster than J_C(F_p) on an Alpha, whereas J_C(F_p) is faster than J_C(F_2n) on a Pentium. Moreover, we investigate the algorithm of the jacobian and the definition-field arithmetic to clarify our results from a practical point of view, with theoretical analysis.

For a given graph G=(V, E), edge capacities c(e) for edges e E, and flow-demands d(v) for nodes v V, a problem of finding the minimum size source-set S V such that the maximum flow-amount between S and v is greater than or equal to d(v) for every v V is called generalized plural cover problem (GPC). For this problem, O(np s(n,m)) time algorithm is presented, where n, m, and p is the number of nodes, edges, and different values of d(v), respectively, and s(n,m) is the time required to solve the maximum flow problem of a graph with n nodes and m edges. This algorithm also constructs a set of optimal solutions in the same time. This property is convenient for applying it to real problems, because other constraints can also be taken into account.

In this paper, we propose a method for detecting conserved domains from a set of amino acid sequences that belong to a protein family. This method detects the domains as follows: first, generate fixed-length subsequences from the sequences; second, construct a weighted graph that connects any two of the subsequences (vertices) having higher similarity than a pre-defined threshold; third, search for the maximum-density subgraph for each connected component of the graph; finally, explore conserved domains in the sequences by combining the results of the previous step. From the performance results obtained by applying the method to several protein families that have complex conserved domains, we found that our method was able to detect those domains even though some domains were weakly conserved.

Let S be a set of n points in the plane and CH(S) be the convex hull of S. We consider the problem of constructing an approximate convex hull which contains CH(S) with strong convexity. An ε-convex δ-superhull of S is a convex polygon P satisfying the following conditions: (1) P has at most O(n) vertices, (2) P contains S, (3) no vertex of P lies farther than δ outside CH(S), and (4) P remains convex even if its vertices are perturbed by as much as ε. The parameters ε and δ represent the strength of convexity of P and the degree of approximation of P to CH(S), respectively. This paper presents the first parallel method for the problem. We show that an ε-convex (8+42)ε-superhull of S can be constructed in O(log n) time using O(n) processors, or in O(log n) time using O(n/log n) processors if S is sorted, in the EREW-PRAM model. We implement the algorithm and find that the average performance is even much better: the results are more strongly convex and much more approximate to CH(S) than the theoretical analysis shows.

Higher order delta-sigma (ΔΣ) modulator with one bit quantizer is known as one of the easiest method to gain a high resolution A/D converter without the need of accurately matched components. However, stability of higher order ΔΣ modulator is still a problem during the design and implementation process. Stabilizing higher order modulator requires the proper choice of integrator gains. In this paper, a new approach on ΔΣ modulator stability analysis which based on the system auto-correlation function is proposed, and equation of NTF power integration is derived out. The specification of equation related to input signal amplitude and output quantization level is discussed. Combining with system control theory, the stability of higher order modulator (2nd and 3rd order) is evaluated. Matlab simulation confirm the proposed method. It offers an evaluation method for the choice of the in-loop integrator gains which ensure the modulator operates under the stable status, and is able to be used for designing stable higher order ΔΣ analog-to-digital converters.

PID control schemes have been widely used in most of process control systems. Most of these processes are often treated as first-order systems with dead times. And also, in many cases, PID parameters are usually tuned based on the process parameters, i. e. , the time constant, the dead time and the process gain. However, since these process parameters can not be obtained exactly, it is well known that it is difficult to find the suitable PID parameters in practice. In this paper, we propose a genetic tuning scheme of PID parameters for first-order systems with large dead times. The authors have already proposed a tuning method of PID parameters using a genetic algorithm (GA), which was based on the relationship between PID control and generalized minimum variance control(GMVC) laws. In practice, for large dead time systems, first-order low pass pre-filters are often used. The proposed method is an extended version of the previously proposed method mentioned above to the system with a pre-filter due to the large dead time, i. e. , a tuning method of both PID parameters and the pre-filter using a GA. The proposed control scheme is numerically evaluated on some simulation examples.

A family C of min-wise independent permutations is known to be a useful tool of indexing replicated documents on the Web. For any integer n>0, a family C of permutations on [n]={1,2,. . . ,n} is said to be min-wise independent if for any (nonempty) X [n] and any x X, Pr ( min {π(X)} = π(x))= ||X||^-1 when π is chosen uniformly at random from C, where ||A|| is the cardinality of a finite set A. For any integer n>0, it has been known that (1) ||C|| lcm(n,n-1,. . . ,2,1) = e^n-o(n) for any family C of min-wise independent permutations on [n]; (2) there exists a polynomial time samplable C family of min-wise independent permutations on [n] such that ||C|| 4ⁿ. However, it has been unclear whether there exists a min-wise independent family C such that ||C|| = lcm(n,n-1,. . . ,2,1) for each integer n>0 and how to construct such a family C of min-wise independent permutations for each integer n>0 if it exists. In this paper, we shall construct a family F_n of permutations for each integer n>0 and show that F_n is min-wise independent and ||F_n|| = lcm(n,n-1,. . . ,2,1). Moreover, we present a polynomial time sampling algorithm for the family. Thus the family F_n of min-wise independent permutations is optimal in the sense of family size and is easy to implement because of its polynomial time samplability.

The problem we consider in this paper is whether the Menezes-Okamoto-Vanstone (MOV) reduction for attacking elliptic curve cryptosystems can be realized for genera elliptic curves. In realizing the MOV reduction, the base field F_q is extended so that the reduction to the discrete logarithm problem in a finite field is possible. Recent results by Balasubramanian and Koblitz suggest that, if l q-1, such a minimum extension degree is the minimum k such that l|q^k-1, which is equivalent to the condition under which the Frey-Ruck (FR) reduction can be applied, where l is the order of the group in the elliptic curve discrete logarithm problem. Our point is that the problem of finding an l-torsion point required in evaluating the Weil pairing should be considered as well from an algorithmic point of view. In this paper, we actually propose a method which leads to a solution of the problem. In addition, our contribution allows us to draw the conclusion that the MOV reduction is indeed as powerful as the FR reduction under l q-1 not only from the viewpoint of the minimum extension degrees but also from that of the effectiveness of algorithms.

This letter analyses the convergence behaviour of the transform domain least mean square (TDLMS) adaptive filtering algorithm which is based on a well known interpretation of the variable stepsize algorithm. With this interpretation, the analysis is considerably simplified. The time varying stepsize is implemented by the modified power estimator to redistribute the spread power after transformation. The main contribution of this letter is the statistical performance analysis in terms of mean and mean squared error of the weight error vector and the decorrelation property of the TDLMS is presented by the lower and upper bound of eigenvalue spread ratio. The theoretical analysis results are validated by Monte Carlo simulation.

In this letter, a novel built-in self-test (BIST) structure based on operational transconductance amplifiers and grounded capacitors (OTA-Cs) for the fault diagnosis of analog circuits is proposed. The proposed analog BIST structure, namely ABIST, can be used to increase the number of test points, sampling and controlling of all test points with voltage data, and making less time for test signal observable. Experimental measurements have been made to verify that the proposed ABIST structure is effective.

Several methods have be proposed or used to optimize the phase distribution of a kinoform. In this paper, we proposed a fast algorithm for optimization of the kinoform based on simulated annealing to reduce the large computation cost. This method uses a simplified equation to calculate the energy function after perturbation.