Shinichiro OHNUKI Kenichiro KOBAYASHI Seiya KISHIMOTO Tsuneki YAMASAKI
Electromagnetic scattering problems of canonical 2D structures can be analyzed with a high degree of accuracy by using the point matching method with mode expansion. In this paper, we will extend our previous method to 3D electromagnetic scattering problems and investigate the radar cross section of spherical shells and the computational accuracy.
Ying YAN Xunwang ZHAO Yu ZHANG Changhong LIANG Zhewang MA
In this paper, a novel hybrid technique for analyzing complex antennas around the coated object is proposed, which is termed as “iterative vector fields with Physical Optics (PO)”. A closed box is used to enclose the antennas and the complex field vectors on the box' surfaces can then be obtained using Huygens principle. The equivalent electromagnetic currents on Huygens surfaces are computed by Higher-order Method of Moments (HOB-MoM) and the fields scattered from the coated object are calculated by PO method. In addition, the parallel technique based on Message Passing Interface (MPI) and Scalable Linear Algebra Package (ScaLAPACK) is employed so as to accelerate the computation. Numerical examples are presented to validate and to show the effectiveness of the proposed method on solving the practical engineering problem.
Raissa RELATOR Yoshihiro HIROHASHI Eisuke ITO Tsuyoshi KATO
Classification tasks in computer vision and brain-computer interface research have presented several applications such as biometrics and cognitive training. However, like in any other discipline, determining suitable representation of data has been challenging, and recent approaches have deviated from the familiar form of one vector for each data sample. This paper considers a kernel between vector sets, the mean polynomial kernel, motivated by recent studies where data are approximated by linear subspaces, in particular, methods that were formulated on Grassmann manifolds. This kernel takes a more general approach given that it can also support input data that can be modeled as a vector sequence, and not necessarily requiring it to be a linear subspace. We discuss how the kernel can be associated with the Projection kernel, a Grassmann kernel. Experimental results using face image sequences and physiological signal data show that the mean polynomial kernel surpasses existing subspace-based methods on Grassmann manifolds in terms of predictive performance and efficiency.
This paper covers new architectures, technologies, and performance benchmarking together with prospects for high productivity and high performance computing enabled by photonics. The exponential and sustained increases in computing and data center needs are driving the demands for exascale computing in the future. Power-efficient and parallel computing with balanced system design is essential for reaching that goal as should support ∼billion total concurrencies and ∼billion core interconnections with ∼exabyte/second bisection bandwidth. Photonic interconnects offer a disruptive technology solution that fundamentally changes the computing architectural design considerations. Optics provide ultra-high throughput, massive parallelism, minimal access latencies, and low power dissipation that remains independent of capacity and distance. In addition to the energy efficiency and many of the fundamental physical problems, optics will bring high productivity computing where programmers can ignore locality between billions of processors and memory where data resides. Repeaterless interconnection links across the entire computing system and all-to-all massively parallel interconnection switch will significantly transform not only the hardware aspects of computing but the way people program and harness the computing capability. This impacts programmability and productivity of computing. Benchmarking and optimization of the configuration of the computing system is very important. Practical and scalable deployment of photonic interconnected computing systems are likely to be aided by emergence of athermal silicon photonics and hybrid integration technologies.
Liang LI Lingjiang KONG Xiaobo YANG
We consider the method of evaluating the detection performance of a single pulse monostatic radar for a fluctuating target in compound-Gaussian clutter plus noise background. The system uses a coded pulse compression waveform as its transmitting signal and the linear minimum mean square error (LMMSE) based reiterated filtering, also known as the adaptive pulse compression (APC). We study the theoretical statistical characteristics of the amplitude of the APC estimation for infinite iterations in this scenario. Based on this theory, we derive both the theoretical probability of false alarm and the probability of detection for the ‘ideal constant false alarm rate (CFAR)’ detector that uses amplitude of the APC estimation as the test statistics. Finaly, we verify the validity of the theoretical detection performance calculations with Monte Carlo simulations. The simulations include three different compound-Gaussian clutter models and all theoretical results well fit the simulated ones.
Honggyu JUNG Kwang-Yul KIM Yoan SHIN
We propose a cooperative compressed spectrum sensing scheme for correlated signals in wideband cognitive radio networks. In order to design a reconstruction algorithm which accurately recover the wideband signals from the compressed samples in low SNR (Signal-to-Noise Ratio) environments, we consider the multiple measurement vector model exploiting a sequence of input signals and propose a cooperative sparse Bayesian learning algorithm which models the temporal correlation of the input signals. Simulation results show that the proposed scheme outperforms existing compressed sensing algorithms for low SNRs.
Dajuan FAN Zhiqiu HUANG Lei TANG
One of the most important problems in web services application is the integration of different existing services into a new composite service. Existing work has the following disadvantages: (i) developers are often required to provide a composite service model first and perform formal verifications to check whether the model is correct. This makes the synthesis process of composite services semi-automatic, complex and inefficient; (ii) there is no assurance that composite services synthesized by using the fully-automatic approaches are correct; (iii) some approaches only handle simple composition problems where existing services are atomic. To address these problems, we propose a correct assurance approach for automatically synthesizing composite services based on finite state machine model. The syntax and semantics of the requirement model specifying composition requirements is also proposed. Given a set of abstract BPEL descriptions of existing services, and a composition requirement, our approach automatically generate the BPEL implementation of the composite service. Compared with existing approaches, the composite service generated by utilizing our proposed approach is guaranteed to be correct and does not require any formal verification. The correctness of our approach is proved. Moreover, the case analysis indicates that our approach is feasible and effective.
Ryuichi HARASAWA Yutaka SUEYOSHI Aichi KUDO
In the paper [4], the authors generalized the Cipolla-Lehmer method [2][5] for computing square roots in finite fields to the case of r-th roots with r prime, and compared it with the Adleman-Manders-Miller method [1] from the experimental point of view. In this paper, we compare these two methods from the theoretical point of view.
Hiroshi FUJIWARA Yasuhiro KONNO Toshihiro FUJITO
The multislope ski-rental problem is an extension of the classical ski-rental problem, where the player has several options of paying both of a per-time fee and an initial fee, in addition to pure renting and buying options. Damaschke gave a lower bound of 3.62 on the competitive ratio for the case where arbitrary number of options can be offered. In this paper we propose a scheme that for the number of options given as an input, provides a lower bound on the competitive ratio, by extending the method of Damaschke. This is the first to establish a lower bound for each of the 5-or-more-option cases, for example, a lower bound of 2.95 for the 5-option case, 3.08 for the 6-option case, and 3.18 for the 7-option case. Moreover, it turns out that our lower bounds for the 3- and 4-option cases respectively coincide with the known upper bounds. We therefore conjecture that our scheme in general derives a matching lower and upper bound.
Erik D. DEMAINE Yoshio OKAMOTO Ryuhei UEHARA Yushi UNO
Shakashaka is a pencil-and-paper puzzle proposed by Guten and popularized by the Japanese publisher Nikoli (like Sudoku). We determine the computational complexity by proving that Shakashaka is NP-complete, and furthermore that counting the number of solutions is #P-complete. Next we formulate Shakashaka as an integer-programming (IP) problem, and show that an IP solver can solve every instance from Nikoli's website within a second.
This paper proposes a new approach to defining and expressing algorithms: the notion of task logical algorithms. This notion allows the user to define an algorithm for a task T as a set of agents who can collectively perform T. This notion considerably simplifies the algorithm development process and can be seen as an integration of the sequential pseudocode and logical algorithms. This observation requires some changes to algorithm development process. We propose a two-step approach: the first step is to define an algorithm for a task T via a set of agents that can collectively perform T. The second step is to translate these agents into (higher-order) computability logic.
In this paper, we show a connection between #P and computing the (real) value of the high order derivative at the origin. Consider, as a problem instance, an integer b and a sufficiently often differentiable function F(x) that is given as a string. Then we consider computing the value F(b)(0) of the b-th derivative of F(x) at the origin. By showing a polynomial as an example, we show that we have FP = #P if we can compute log 2F(b)(0) up to certain precision. The previous statement holds even if F(x) is limited to a function that is analytic at any x ∈ R. It implies the hardness of computing the b-th value of a number sequence from the closed form of its generating function.
Wentao LV Junfeng WANG Wenxian YU Zhen TAN
In compressed sensing, the design of the measurement matrix is a key work. In order to achieve a more precise reconstruction result, the columns of the measurement matrix should have better orthogonality or linear incoherence. A random matrix, like a Gaussian random matrix (GRM), is commonly adopted as the measurement matrix currently. However, the columns of the random matrix are only statistically-orthogonal. By substituting an orthogonal basis into the random matrix to construct a semi-random measurement matrix and by optimizing the mutual coherence between dictionary columns to approach a theoretical lower bound, the linear incoherence of the measurement matrix can be greatly improved. With this optimization measurement matrix, the signal can be reconstructed from its measures more precisely.
Atsushi FUJIOKA Eiichiro FUJISAKI Keita XAGAWA
We study non-malleability of multiple public-key encryption (ME) schemes. The main difference of ME from the threshold public-key encryption schemes is that there is no dealer to share a secret among users; each user can independently choose their own public-keys; and a sender can encrypt a message under ad-hoc multiple public keys of his choice. In this paper we tackle non-malleability of ME. We note that the prior works only consider confidentiality of messages and treat the case that all public keys are chosen by honest users. In the multiple public-key setting, however, some application naturally requires non-malleability of ciphertexts under multiple public keys including malicious users'. Therefore, we study the case and have obtained the following results:·We present three definitions of non-malleability of ME, simulation-based, comparison-based, and indistinguishability-based ones. These definitions can be seen as an analogue of those of non-malleable public-key encryption (PKE) schemes. Interestingly, our definitions are all equivalent even for the “invalid-allowing” relations. We note that the counterparts of PKE are not equivalent for the relations.·The previous strongest security notion for ME, “indistinguishability against strong chosen-ciphertext attacks (sMCCA)” [1], does not imply our notion of non-malleability against chosen-plaintext attacks.·Non-malleability of ME guarantees that the single message indistinguishability-based notion is equivalent to the multiple-message simulation-based notion, which provides designers a fundamental benefit.·We define new, stronger decryption robustness for ME. A non-malleable ME scheme is meaningful in practice if it also has the decryption robustness.·We present a constant ciphertext-size ME scheme (meaning that the length of a ciphertext is independent of the number of public-keys) that is secure in our strongest security notion of non-malleability. Indeed, the ciphertext overhead (i.e., the length of a ciphertext minus that of a plaintext) is the combined length of two group elements plus one hash value, regardless of the number of public keys. Then, the length of the partial decryption of one user consists of only two group elements, regardless of the length of the plaintext.
Tamaki NAKAJIMA Yuuki TANAKA Toru ARAKI
A twin dominating set of a digraph D is a subset S of vertices if, for every vertex u ∉ S, there are vertices x,y ∈ S such that ux and yu are arcs of D. A digraph D is round if the vertices can be labeled as v0,v1,...,vn-1 so that, for each vertex vi, the out-neighbors of vi appear consecutively following vi and the in-neighbors of vi appear consecutively preceding vi. In this paper, we give polynomial time algorithms for finding a minimum weight twin dominating set and a minimum weight total twin dominating set for a weighted round digraph. Then we show that there is a polynomial time algorithm for deciding whether a locally semicomplete digraph has an independent twin dominating set. The class of locally semicomplete digraphs contains round digraphs as a special case.
Atsushi FUJIOKA Taiichi SAITO Keita XAGAWA
This paper proposes a generic construction of hierarchical identity-based identification (HIBI) protocols secure against impersonation under active and concurrent attacks in the standard model. The proposed construction converts a digital signature scheme existentially unforgeable against chosen message attacks, where the scheme has a protocol for showing possession of a signing key, not a signature. Our construction is based on the so-called certificate-based construction of hierarchical identity-based cryptosystems, and utilizes a variant of the well-known OR-proof technique to ensure the security against impersonation under active and concurrent attacks. We also present several concrete examples of our construction employing the Waters signature (EUROCRYPT 2005), and other signatures. As results, its concurrent security of each instantiation is proved under the computational Diffie-Hellman (CDH) assumption, the RSA assumption, or their variants in the standard model. Chin, Heng, and Goi proposed an HIBI protocol passively and concurrently secure under the CDH and one-more CDH assumption, respectively (FGIT-SecTech 2009). However, its security is proved in the random oracle model.
Keishi TSUBAKI Tetsuya HIROSE Yuji OSAKI Seiichiro SHIGA Nobutaka KUROKI Masahiro NUMA
A fully on-chip CMOS relaxation oscillator (ROSC) with a PVT variation compensation circuit is proposed in this paper. The circuit is based on a conventional ROSC and has a distinctive feature in the compensation circuit that compensates for comparator's non-idealities caused by not only offset voltage, but also delay time. Measurement results demonstrated that the circuit can generate a stable clock frequency of 6.66kHz. The current dissipation was 320nA at 1.0-V power supply. The measured line regulation and temperature coefficient were 0.98%/V and 56ppm/°C, respectively.
Tatsuya FUJIMOTO Tsunehiro YOSHINAGA Makoto SAKAMOTO
A cooperating system of finite automata (CS-FA) has more than one finite automata (FA's) and an input tape. These FA's operate independently on the input tape and can communicate with each other on the same cell of the input tape. For each k ≥ 1, let L[CS-1DFA(k)] (L[CS-1UFA(k)]) be the class of sets accepted by CS-FA's with k one-way deterministic finite automata (alternating finite automata with only universal states). We show that L[CS-1DFA(k+1)] - L[CS-1UFA(k)] ≠ ∅ and L[CS-1UFA(2)] - ∪1≤k<∞L[CS-1DFA(k)] ≠ ∅.
In this paper we apply angle recoding to the CORDIC-based processing elements in a scalable architecture for complex matrix inversion. We extend the processing elements from the scalable real matrix inversion architecture to the complex domain and obtain the novel scalable complex matrix inversion architecture, which can significantly reduce computational complexity. We rearrange the CORDIC elements to make one half of the processing elements simple and compact. For the other half of the processing elements, the efficient use of angler recoding reduces the number of microrotation steps of the CORDIC elements to 3/4. Consequently, only 3 CORDIC elements are required for the processing elements with full utilization.
Collaborative business has been increasingly developing with the environment of globalization and advanced information technologies. In a collaboration environment with multiple organizations, participants from different organizations always have different views about modeling the overall business process due to different knowledge and cultural backgrounds. Moreover, flexible support, privacy preservation and process reuse are important issues that should be considered in business process management across organizational boundaries. This paper presents a novel approach of modeling interorganizational business process for collaboration. Our approach allows for modeling loosely coupled interorganizational business process considering different views of organizations. In the proposed model, organizations have their own local process views of modeling business process instead of sharing pre-defined global processes. During process cooperation, local process of an organization can be invisible to other organizations. Further, we propose the coordination mechanisms for different local process views to detect incompatibilities among organizations. We illustrate our proposed approach by a case study of interorganizational software development collaboration.