The Game of Life, a two-dimensional computationally universal cellular automaton, is known to exhibits 1/f noise in the evolutions starting from random configurations. In this paper we perform the spectral analysis on the computation process by a Turing machine constructed on the array of the Game of Life. As a result, the power spectrum averaged over the whole array has almost flat line at low frequencies and a lot of sharp peaks at high frequencies although some regions in which complicated behavior such as frequent memory rewriting occurs exhibit 1/f noise. This singular power spectrum is, however, easily turned into 1/f by slightly deforming the initial configuration of the Turing machine. These results emphasize the peculiarity of the computation process on the Game of Life that is never shared with the evolutions from random configurations. The Lyapunov exponents have positive values in three out of six trials and zero or negative values in other three trails. That means the computation process is essentially chaotic but it has capable of recovering a slight error in the configuration of the Turing machine.

Two points x, y inside a simple polygon P are said to be mutually link-2 visible if there exists the third point z ∈ P such that z is visible from both x and y. The polygon P is link-2 LR-visible if there are two points s, t on the boundary of P such that every point on the clockwise boundary of P from s to t is link-2 visible from some point of the other boundary of P from t to s and vice versa. We give a characterization of link-2 LR-visibility polygons by generalizing the known result on LR-visibility polygons. A new idea is to extend the concepts of ray-shootings and components to those under notion of link-2 visibility. Then, we develop an O(n log n) time algorithm to determine whether a given polygon is link-2 LR-visible. Using the characterization of link-2 LR-visibility polygons, we further present an O(n log n) time algorithm for determining whether a polygonal region is searchable by a k-searcher, k ≥ 2. This improves upon the previous O(n2) time bound [9]. A polygonal region P is said to be searchable by a searcher if the searcher can detect (or see) an unpredictable intruder inside the region, no matter how fast the intruder moves. A k-searcher holds k flashlights and can see only along the rays of the flashlights emanating from his position.

In terms of spatial online aggregation, traditional stand-alone serial methods gradually become limited. Although parallel computing is widely studied nowadays, there scarcely has research conducted on the index-based parallel online aggregation methods, specifically for spatial data. In this letter, a parallel multilevel indexing method is proposed to accelerate spatial online aggregation analyses, which contains two steps. In the first step, a parallel aR tree index is built to accelerate aggregate query locally. In the second step, a multilevel sampling data pyramid structure is built based on the parallel aR tree index, which contribute to the concurrent returned query results with certain confidence degree. Experimental and analytical results verify that the methods are capable of handling billion-scale data.

We propose a parallel precomputation method for real-time model predictive control. The key idea is to use predicted input values produced by model predictive control to solve an optimal control problem in advance. It is well known that control systems are not suitable for multi- or many-core processors because feedback-loop control systems are inherently based on sequential operations. However, since the proposed method does not rely on conventional thread-/data-level parallelism, it can be easily applied to such control systems without changing the algorithm in applications. A practical evaluation using three real-world model predictive control system simulation programs demonstrates drastic performance improvement without degrading control quality offered by the proposed method.

This paper proposes a novel environmental monitoring strategy, incremental environmental monitoring, that enables scientists to reveal the ecology of wild animals in the field. We applied this strategy to the habitat of endangered freshwater fish. Specifically, we designed and implemented a network-based system using distributed sensors to continuously monitor and record the habitat of endangered fish. Moreover, we developed a set of analytical tools to exploit a variety of sensor data, including environmental time-series data such as amount of dissolved oxygen, as well as underwater video capturing the interaction of fish and their environment. We also describe the current state of monitoring the behavior and habitat of endangered fish and discuss solutions for making such environmental monitoring more efficient in the field.

We consider a device-to-device (D2D) underlaid cellular network where D2D communications are allowed to share the same radio spectrum with cellular uplink communications for improving spectral efficiency. However, to protect the cellular uplink communications, the interference level received at a base station (BS) from the D2D communications needs to be carefully maintained below a certain threshold, and thus the BS coordinates the transmit power of the D2D links. In this paper, we investigate on-off power control for the D2D links, which is known as a simple but effective technique due to its low signaling overhead. We first investigate the optimal on-off power control algorithm to maximize the sum-rate of the D2D links, while satisfying the interference constraint imposed by the BS. The computational complexity of the optimal algorithm drastically increases with D2D link number. Thus, we also propose an on-off power control algorithm to significantly reduce the computational complexity, compared to the optimal on-off power control algorithm. Extensive simulations validate that the proposed algorithm significantly reduces the computational complexity with a marginal sum-rate offset from the optimal algorithm.

Card-based cryptographic protocols provide secure multi-party computations using a deck of physical cards. The most important primitive of those protocols is the shuffling operation, and most of the existing protocols rely on uniform cyclic shuffles (such as the random cut and random bisection cut) in which each possible outcome is equally likely and all possible outcomes constitute a cyclic subgroup. However, a couple of protocols with non-uniform and/or non-cyclic shuffles were proposed by Koch, Walzer, and Härtel at Asiacrypt 2015. Compared to the previous protocols, their protocols require fewer cards to securely produce a hidden AND value, although to implement of such unconventional shuffles appearing in their protocols remains an open problem. This paper introduces “pile-shifting scramble,” which can be a secure implementation of those shuffles. To implement such unconventional shuffles, we utilize physical cases that can store piles of cards, such as boxes and envelopes. Therefore, humans are able to perform the shuffles using these everyday objects. Furthermore, we show that a certain class of non-uniform and/or non-cyclic shuffles having two possible outcomes can be implemented by the pile-shifting scramble. This also implies that we can improve upon the known COPY protocol using three card cases so that the number of cases required can be reduced to two.

Although Wolf Pack Algorithm (WPA) is a novel optimal algorithm with good performance, there is still room for improvement with respect to its convergence. In order to speed up its convergence and strengthen the search ability, we improve WPA with the Differential Evolution (DE) elite set strategy. The new proposed algorithm is called the WPADEES for short. WPADEES is faster than WPA in convergence, and it has a more feasible adaptability for various optimizations. Six standard benchmark functions are applied to verify the effects of these improvements. Our experiments show that the performance of WPADEES is superior to the standard WPA and other intelligence optimal algorithms, such as GA, DE, PSO, and ABC, in several situations.

Response property is a kind of liveness property. Response property problem is defined as follows: Given two activities α and β, whenever α is executed, is β always executed after that? In this paper, we tackled the problem in terms of Workflow Petri nets (WF-nets for short). Our results are (i) the response property problem for acyclic WF-nets is decidable, (ii) the problem is intractable for acyclic asymmetric choice (AC) WF-nets, and (iii) the problem for acyclic bridge-less well-structured WF-nets is solvable in polynomial time. We illustrated the usefulness of the procedure with an application example.

Many of affine motion compensation techniques proposed thus far employ least-square-based techniques in estimating affine parameters, which requires a hardware structure different from conventional block-matching-based one. This paper proposes a new affine motion estimation/compensation framework friendly to block-matching-based parameter estimation, and applies it to an HEVC encoder to demonstrate its coding efficiency and computation cost. To avoid a nest of search loops, a new affine motion model is first introduced by decomposing the conventional 4-parameter affine model into two 3-parameter ones. Then, a block-matching-based fast parameter estimation technique is proposed for the models. The experimental results given in this paper show that our approach is advantageous over conventional techniques.

A cograph (complement reducible graph) is a graph which can be generated by disjoint union and complement operations on graphs, starting with a single vertex graph. Cographs arise in many areas of computer science and are studied extensively. With the goal of developing an effective data mining method for graph structured data, in this paper we introduce a graph pattern expression, called a cograph pattern, which is a special type of cograph having structured variables. Firstly, we show that a problem whether or not a given cograph pattern g matches a given cograph G is NP-complete. From this result, we consider the polynomial time learnability of cograph pattern languages defined by cograph patterns having variables labeled with mutually different labels, called linear cograph patterns. Secondly, we present a polynomial time matching algorithm for linear cograph patterns. Next, we give a polynomial time algorithm for obtaining a minimally generalized linear cograph pattern which explains given positive data. Finally, we show that the class of linear cograph pattern languages is polynomial time inductively inferable from positive data.

With the popularity of cloud computing services, outsourcing computation has entered a period of rapid development. Modular exponentiation is one of the most expensive operations in public key cryptographic systems, but the current outsourcing algorithms for modular exponentiations (MExps) with single server are inefficient or have small checkability. In this paper, we propose an efficient and fully verifiable algorithm for outsourcing multiple MExps with single untrusted server where the errors can be detected by an outsourcer with a probability of 1. The theory analysis and experimental evaluations also show that the proposed algorithm is the most efficient one compared with the previous work. Finally, we present the outsourcing schemes of digital signature algorithm (DSA) and attribute based encryption (ABE) as two applications of the proposed algorithm.

The performance of secret-sharing (SS)-based multiparty computation (MPC) has recently increased greatly, and several efforts to implement and use it have been put into practice. Authentication of clients is one critical mechanism for implementing SS-based MPC successfully in practice. We propose a password-based authentication protocol for SS-based MPC. Our protocol is secure in the presence of secure channels, and it is optimized for practical use with SS-based MPC in the following ways. Threshold security: Our protocol is secure in the honest majority, which is necessary and sufficient since most practical results on SS-based MPC are secure in the same environment. Establishing distinct channels: After our protocol, a client has distinct secure and two-way authenticated channels to each server. Ease of implementation: Our protocol consists of SS, operations involving SS, and secure channels, which can be reused from an implementation of SS-based MPC. Furthermore, we implemented our protocol with an optimization for the realistic network. A client received the result within 2 sec even when the network delay was 200 ms, which is almost the delay that occurs between Japan and Europe.

This paper newly proposes a fast computation technique on the method of image Green's function for p-characteristic calculations, when a plane wave with the transverse wavenumber p is incident on a periodic rough surface having perfect conductivity. In the computation of p-characteristics, based on a spectral domain periodicity of the periodic image Green's function, the image integral equation for a given incidence p maintains the same form for other particular incidences except for the excitation term. By means of a quadrature method, such image integral equations lead to matrix equations. Once the first given matrix equation is performed by a solution procedure as calculations of its matrix elements and its inverse matrix, the other matrix equations for other particular incidences no longer need such a solution procedure. Thus, the total CPU time for the computation of p-characteristics is largely reduced in complex shaped surface cases, huge roughness cases or large period cases.

A Tikhonov regularized RLS algorithm with an exponential weighting factor, i.e., a leaky RLS (LRLS) algorithm was proposed by the author. A quadratic version of the LRLS algorithm also exists in the literature of adaptive filters. In this letter, a cubic version of the LRLS filter which is computationally efficient is proposed when the length of the adaptive filter is short. The proposed LRLS filter includes only a divide per iteration although its multiplications and additions increase in number. Simulation results show that the proposed LRLS filter is faster for its short length than the existing quadratic version of the LRLS filter.

The main contribution of this paper is to present an efficient GPU implementation of bulk computation of the CKY parsing for a context-free grammar, which determines if a context-free grammar derives each of a lot of input strings. The bulk computation is to execute the same algorithm for a lot of inputs in turn or at the same time. The CKY parsing is to determine if a context-free grammar derives a given string. We show that the bulk computation of the CKY parsing can be implemented in the GPU efficiently using Bitwise Parallel Bulk Computation (BPBC) technique. We also show the rule minimization technique and the dynamic scheduling method for further acceleration of the CKY parsing on the GPU. The experimental results using NVIDIA TITAN X GPU show that our implementation of the bitwise-parallel CKY parsing for strings of length 32 takes 395µs per string with 131072 production rules for 512 non-terminal symbols.

In this letter, we investigate the computation offloading problem in cloud based multi-robot systems, in which user weights, communication interference and cloud resource limitation are jointly considered. To minimize the system cost, two offloading selection and resource allocation algorithms are proposed. Numerical results show that the proposed algorithms both can greatly reduce the overall system cost, and the greedy selection based algorithm even achieves near-optimal performance.

Rational proofs, introduced by Azar and Micali (STOC 2012), are a variant of interactive proofs in which the prover is rational, and may deviate from the protocol for increasing his reward. Guo et al. (ITCS 2014) demonstrated that rational proofs are relevant to delegation of computation. By restricting the prover to be computationally bounded, they presented a one-round delegation scheme with sublinear verification for functions computable by log-space uniform circuits with logarithmic depth. In this work, we study rational proofs in which the verifier is also rational, and may deviate from the protocol for decreasing the prover's reward. We construct a three-message delegation scheme with sublinear verification for functions computable by log-space uniform circuits with polylogarithmic depth in the random oracle model.

A fast parameter estimation method with a coarse estimation and a fine estimation for polyphase P coded signals is proposed. For a received signal with N sampling points, the proposed method has an improved performance when the signal-to-noise ratio (SNR) is larger than 2dB and a lower computational complexity O(N logs N) compared with the latest time-frequency rate estimation method whose computational complexity is O(N2).

A bi-dimensional empirical mode decomposition (BEMD) is one of the powerful methods for decomposing non-linear and non-stationary signals without a prior function. It can be applied in many applications such as feature extraction, image compression, and image filtering. Although modified BEMDs are proposed in several approaches, computational cost and quality of their bi-dimensional intrinsic mode function (BIMF) still require an improvement. In this paper, an iteration-free computation method for bi-dimensional empirical mode decomposition, called iBEMD, is proposed. The locally partial correlation for principal component analysis (LPC-PCA) is a novel technique to extract BIMFs from an original signal without using extrema detection. This dramatically reduces the computation time. The LPC-PCA technique also enhances the quality of BIMFs by reducing artifacts. The experimental results, when compared with state-of-the-art methods, show that the proposed iBEMD method can achieve the faster computation of BIMF extraction and the higher quality of BIMF image. Furthermore, the iBEMD method can clearly remove an illumination component of nature scene images under illumination change, thereby improving the performance of text localization and recognition.