This paper presents a new approach to precompute points [3]P, [5]P,..., [2k-1]P, for some k ≥ 2 on an elliptic curve over Fp. Those points are required for the efficient evaluation of a scalar multiplication, the most important operation in elliptic curve cryptography. The proposed method precomputes the points in affine coordinates and needs only one single field inversion for the computation. The new method is superior to all known methods that also use one field inversion, if the required memory is taken into consideration. Compared to methods that require several field inversions for the precomputation, the proposed method is faster for a broad range of ratios of field inversions and field multiplications. The proposed method benefits especially from ratios as they occur on smart cards.

There is evidence in favor of a relationship between the presence of 1/f noise and computational universality in cellular automata. To confirm the relationship, we search for two-dimensional cellular automata with a 1/f power spectrum by means of genetic algorithms. The power spectrum is calculated from the evolution of the state of the cell, starting from a random initial configuration. The fitness is estimated by the power spectrum with consideration of the spectral similarity to the 1/f spectrum. The result shows that the rule with the highest fitness over the most runs exhibits a 1/f type spectrum and its transition function and behavior are quite similar to those of the Game of Life, which is known to be a computationally universal cellular automaton. These results support the relationship between the presence of 1/f noise and computational universality.

Consider a client who intends to perform a massive computing task comprsing a number of sub-tasks, while both storage and computation are outsourced by a third-party service provider. How could the client ensure the integrity and completeness of the computation result? Meanwhile, how could the assurance mechanism incur no disincentive, e.g., excessive communication cost, for any service provider or client to participate in such a scheme? We detail this problem and present a general model of execution assurance for massive computing tasks. A series of key features distinguish our work from existing ones: a) we consider the context wherein both storage and computation are provided by untrusted third parties, and client has no data possession; b) we propose a simple yet effective assurance model based on a novel integration of the machineries of data authentication and computational private information retrieval (cPIR); c) we conduct an analytical study on the inherent trade-offs among the verification accuracy, and the computation, storage, and communication costs.

We exhibit a simple procedure to find how classical signals should be processed in cluster-state quantum computation. Using stabilizers characterizing a cluster state, we can easily find a precise classical signal-flow that is required in performing cluster-state computation.

The establishment of inter-domain traffic engineered paths is a requisite to accomplishing an end-to-end bandwidth guarantee and end-to-end resource optimization. Though the inter-domain paths must be reliable, it is difficult to compute suitable backup inter-domain paths in advance when the traffic engineering information is not disclosed outside of each domain. This means that the inter-domain path computation must satisfy the severe requirement of path establishment delay, since all inter-domain paths traversing the links in failure need to be computed after the failure occurs. Though several inter-domain path computation schemes have been proposed, their relative characteristics remain unknown. First, this paper classifies the conventional inter-domain path computation schemes into two types, i.e. end-to-end and per-domain schemes, and compares their performances under various traffic loads. Based on results of the comparisons, this paper proposes an adaptive inter-domain path computation scheme that can satisfy the severe requirement of the path establishment delay. In this scheme, the domain sequence from the source node to the destination node is divided into multiple sub-domain sequences according to the traffic load in each domain. The end-to-end path computation scheme is applied to the sub-domain sequences under heavy traffic loads, while the per-domain path computation scheme is applied to those under normal traffic loads. The simulation results show that the proposed scheme can adaptively satisfy the requirement for the path establishment delay while it maintains the optimality of path computation, even if the traffic load applied to each domain changes.

Introducing adaptive online data compression at network-internal nodes is considered for alleviating traffic congestion on the network. In this paper, we assume that advanced relay nodes, which possess both a relay function (network resource) and a processing function (computational and storage resources), are placed inside the network, and we propose an adaptive online lossless packet compression scheme utilized at these nodes. This scheme selectively compresses a packet according to its waiting time in the queue during congestion. Through preliminary investigation using actual traffic datasets, we investigate the compression ratio and processing time of packet-by-packet compression in actual network environments. Then, by means of computer simulations, we show that the proposed scheme reduces the packet delay time and discard rate and investigate factors necessary in achieving efficient packet relay.

A virtualized optical network (VON) is proposed as a key to implementing increased agility and flexibility into the future Internet and applications by providing any-to-any connectivity with the appropriate optical bandwidth at the appropriate time. The VON is enabled by introducing optical transparentization and optical fine granular grooming based on optical orthogonal frequency division multiplexing.

In the present paper, we propose an evolutionary P2P networking technique that dynamically and adaptively optimizes several P2P network topologies, in which all of the nodes are included at the same time, in an evolutionary manner according to given evaluation criteria. In addition, through simulations, we examine whether the proposed evolutionary P2P networking technique can provide reliable search capability in dynamic P2P environments. In simulations, we assume dynamic P2P environments in which each node leaves and joins the network with its own probability and in which search objects vary with time. The simulation results show that topology reconstruction by the evolutionary P2P networking technique is better than random topology reconstruction when only a few types of search objects are present in the network at any moment and these search objects are not replicated. Moreover, for the scenario in which the evolutionary P2P networking technique is more effective, we show through simulations that when each node makes several links with other nodes in a single network topology, the evolutionary P2P networking technique improves the reliable search capability. Finally, the number of links that yields more reliable search capability appears to depend on how often nodes leave and join the network.

This paper introduces a new computational problem on a two-dimensional vector space, called the vector decomposition problem (VDP), which is mainly defined for designing cryptosystems using pairings on elliptic curves. We first show a relation between the VDP and the computational Diffie-Hellman problem (CDH). Specifically, we present a sufficient condition for the VDP on a two-dimensional vector space to be at least as hard as the CDH on a one-dimensional subspace. We also present a sufficient condition for the VDP with a fixed basis to have a trapdoor. We then give an example of vector spaces which satisfy both sufficient conditions and on which the CDH is assumed to be hard in previous work. In this sense, the intractability of the VDP is a reasonable assumption as that of the CDH.

This paper focuses on fusion estimation algorithms weighted by matrices and scalars, and relationship between them is considered. We present new algorithms that address the computation of matrix weights arising from multidimensional estimation problems. The first algorithm is based on the Cholesky factorization of a cross-covariance block-matrix. This algorithm is equivalent to the standard composite fusion estimation algorithm however it is low-complexity. The second fusion algorithm is based on an approximation scheme which uses special steady-state approximation for local cross-covariances. Such approximation is useful for computing matrix weights in real-time. Subsequent analysis of the proposed fusion algorithms is presented, in which examples demonstrate the low-computational complexity of the new fusion estimation algorithms.

Petri net is a powerful modeling tool for concurrent systems. Liveness, which is a problem to verify there exists no local deadlock, is one of the most important properties of Petri net to analyze. Computational complexity of liveness of a general Petri net is deterministic exponential space. Liveness is studied for subclasses of Petri nets to obtain necessary and sufficient conditions that need less computational cost. These are mainly done using a subset of places called siphons. CS-property, which denotes that every siphon has token(s) in every reachable marking, in one of key properties in liveness analysis. On the other hand, normal Petri net is a subclass of Petri net whose reachability set can be effectively calculated. This paper studies computational complexity of liveness problem of normal Petri nets. First, it is shown that liveness of a normal Petri net is equivalent to cs-property. Then we show this problem is co-NP complete by deriving a nondeterministic algorithm for non-liveness which is similar to the algorithm for liveness suggested by Howell et al. Lastly, we study structural feature of bounded Petri net where liveness and cs-property are equivalent. From this consideration, liveness problem of bounded normal Petri net is shown to be deterministic polynomial time complexity.

This paper presents a gate-block selection algorithm, which can synthesize a proper parameter extractor of the pre-computation-based content-addressable memory (PB-CAM) to enhance power efficiency for specific applications such as embedded systems, microprocessor and SOC, etc. Furthermore, a novel CAM cell design with single bit-line is proposed. The proposed CAM cell design requires only one heavy loading bit-line and merely is constructed with eight transistors. The whole PB-CAM design was described in Spice with TSMC 0.35 µm double-poly quadruple-metal CMOS process. We used Synopsys Nanosim to estimate power consumption. With a 128 words by 32 bits CAM size, the experimental results showed that our proposed PB-CAM effectively reduces 18.21% of comparison operations in the CAM and saves 16.75% in power reduction by synthesizing a proper parameter extractor of the PB-CAM compared with the 1's count PB-CAM. This implies that our proposed PB-CAM is more flexible and adaptive for specific applications.

In this paper, we propose a new approximate algorithm for the model predictive control (MPC) problem with a time-varying reference of hybrid systems. The proposed algorithm consists of an offline computation and an online computation. In the offline computation, candidates of mode sequences are derived. In the online computation, after the mode sequence is uniquely decided among candidates, the finite-time optimal control problem, i.e., the quadratic programming problem, is solved. So by applying the proposed algorithm, the computational amount of the online computation is decreased. First, the MPC problem with a time-varying reference is formulated. Next, the proposed algorithm is explained, and the accuracy of the obtained approximate solution is discussed. Finally, the effectiveness of the proposed method is shown by a numerical example.

Quantum random access coding (QRAC) is one of the basic tools in quantum computing. It uses a quantum state for encoding the sender's bit string so that the receiver can recover any single bit of the bit string with high probability. This article surveys recent developments of QRAC, with some concrete examples of QRAC using one quantum bit, and its applications, focusing on communication complexity and locally decodable codes.

The first part of this paper contains an introduction to Bell inequalities and Tsirelson's theorem for the non-specialist. The next part gives an explicit optimum construction for the "hard" part of Tsirelson's theorem. In the final part we describe how upper bounds on the maximal quantum violation of Bell inequalities can be obtained by an extension of Tsirelson's theorem, and survey very recent results on how exact bounds may be obtained by solving an infinite series of semidefinite programs.

An elementary formal system, EFS for short, is a kind of logic program over strings, and regarded as a set of rules to generate a language. For an EFS Γ, the language L(Γ) denotes the set of all strings generated by Γ. We consider a new form of EFS, called a restricted two-clause EFS, and denote by rEFS the set of all restricted two-clause EFSs. Then we study the learnability of rEFS in the exact learning model. The class rEFS contains the class of regular patterns, which is extensively studied in Learning Theory. Let Γ* be a target EFS in rEFS of learning. In the exact learning model, an oracle for superset queries answers "yes" for an input EFS Γ in rEFS if L(Γ) is a superset of L(Γ*), and outputs a string in L(Γ*)-L(Γ), otherwise. An oracle for membership queries answers "yes" for an input string w if w is included in L(Γ*), and answers "no", otherwise. We show that any EFS in rEFS is exactly identifiable in polynomial time using membership and superset queries. Moreover, for other types of queries, we show that there exists no polynomial time learning algorithm for rEFS by using the queries. This result indicates the hardness of learning the class rEFS in the exact learning model, in general.

Two-Terminal Series Parallel (TTSP, for short) graphs are used as data models in applications for electric networks and scheduling problems. We propose a TTSP term graph which is a TTSP graph having structured variables, that is, a graph pattern over a TTSP graph. Let TGTTSP be the set of all TTSP term graphs whose variable labels are mutually distinct. For a TTSP term graph g in TGTTSP, the TTSP graph language of g, denoted by L(g), is the set of all TTSP graphs obtained from g by substituting arbitrary TTSP graphs for all variables in g. Firstly, when a TTSP graph G and a TTSP term graph g are given as inputs, we present a polynomial time matching algorithm which decides whether or not L(g) contains G. The minimal language problem for the class LTTSP={L(g) | g ∈ TGTTSP} is, given a set S of TTSP graphs, to find a TTSP term graph g in TGTTSP such that L(g) is minimal among all TTSP graph languages which contain all TTSP graphs in S. Secondly, we give a polynomial time algorithm for solving the minimal language problem for LTTSP. Finally, we show that LTTSP is polynomial time inductively inferable from positive data.

Trust negotiation is an authorizing technique based on digital credentials, in which both a user and a server gradually establish trust in each other by repeatedly exchanging their credentials. A trust negotiation strategy is a function that answers a set of credentials to disclose to the other party, depending on policies and the set of already disclosed credentials. The disclosure tree strategy (DTS), proposed by Yu et al., is one of the strategies that satisfies preferable properties. DTS in a simple implementation requires exponential time and space; however, neither an efficient algorithm nor the lower-bound of its complexity was known. In this paper, we investigate the computational complexity of DTS. We formulate subproblems of DTS as problems on derivation trees of a context-free grammar (CFG), and analyze the computational complexity of the subproblems using the concepts of CFGs. As a result, we show that two subproblems EVL and MSET of DTS are NP-complete and NP-hard, respectively, while both are solvable in polynomial time if we modify EVL not to require non-redundancy and MSET not to answer any subset useless for leading the negotiation to success.

This paper introduces a new timetabling problem on universities, called interview timetabling. In this problem, some constant number, say three, of referees are assigned to each of 2n graduate students. Our task is to construct a presentation timetable of these 2n students using n timeslots and two rooms, so that two students evaluated by the same referee must be assigned to different timeslots. The optimization goal is to minimize the total number of movements of all referees between two rooms. This problem comes from the real world in the interview timetabling in Kyoto University. We propose two restricted models of this problem, and investigate their time complexities.

A graph is an interval graph if and only if each vertex in the graph can be associated with an interval on the real line such that any two vertices are adjacent in the graph exactly when the corresponding intervals have a nonempty intersection. A number of interesting applications for interval graphs have been found in the literature. In order to find structural features common to structural data which can be represented by intervals, this paper proposes new interval graph structured patterns, called linear interval graph patterns, and a polynomial time algorithm for finding a minimally generalized linear interval graph pattern explaining a given finite set of interval graphs.