Qihua NIU Tongjiang YAN Yuhua SUN Chun'e ZHAO Fei TANG
The concept of witness hiding was proposed by Feige and Shamir as a natural relaxation of zero-knowledge. Prior constructions of witness hiding protocol for general hard distribution on NP language consist of at least three rounds. In this paper we construct a two-round witness hiding protocol for all hard distributions on NP language. Our construction is based on two primitives: point obfuscation and adaptive witness encryption scheme.
Daisuke GOTO Fumihiro YAMASHITA Kouhei SUZAKI Hideya SO Yoshinori SUZUKI Kiyoshi KOBAYASHI Naoki KITA
We target the estimation of antenna patterns of distributed array antenna (DAA) systems for satellite communications. Measuring DAA patterns is very difficult because of the large antenna separations involved, more than several tens of wavelengths. Our goal is to elucidate the accuracy of the DAA pattern estimation method whose inputs are actual antenna pattern data and array factors by evaluating their similarity to actually measured DAA radiation patterns. Experiments on two Ku band parabolic antennas show that their patterns can be accurately estimated even if we change the conditions such as frequency, antenna arrangement and polarization. Evaluations reveal that the method has high estimation accuracy since its errors are better than 1dB. We conclude the method is useful for the accurate estimation of DAA patterns.
Yo UMEKI Taichi YOSHIDA Masahiro IWAHASHI
In this paper, we propose a method of salient object detection based on distributed seeds and a co-propagation of seed information. Salient object detection is a technique which estimates important objects for human by calculating saliency values of pixels. Previous salient object detection methods often produce incorrect saliency values near salient objects in the case of images which have some objects, called the leakage of saliencies. Therefore, a method based on a co-propagation, the scale invariant feature transform, the high dimensional color transform, and machine learning is proposed to reduce the leakage. Firstly, the proposed method estimates regions clearly located in salient objects and the background, which are called as seeds and resultant seeds, are distributed over images. Next, the saliency information of seeds is simultaneously propagated, which is then referred as a co-propagation. The proposed method can reduce the leakage caused because of the above methods when the co-propagation of each information collide with each other near the boundary. Experiments show that the proposed method significantly outperforms the state-of-the-art methods in mean absolute error and F-measure, which perceptually reduces the leakage.
Liang CHEN Dongyi CHEN Xiao CHEN
Operations, such as text entry and zooming, are simple and frequently used on mobile touch devices. However, these operations are far from being perfectly supported. In this paper, we present our prototype, BackAssist, which takes advantage of back-of-device input to augment front-of-device touch interaction. Furthermore, we present the results of a user study to evaluate whether users can master the back-of-device control of BackAssist or not. The results show that the back-of-device control can be easily grasped and used by ordinary smart phone users. Finally, we present two BackAssist supported applications - a virtual keyboard application and a map application. Users who tried out the two applications give positive feedback to the BackAssist supported augmentation.
Mohamad Sabri bin SINAL Eiji KAMIOKA
Automatic detection of heart cycle abnormalities in a long duration of ECG data is a crucial technique for diagnosing an early stage of heart diseases. Concretely, Paroxysmal stage of Atrial Fibrillation rhythms (ParAF) must be discriminated from Normal Sinus rhythms (NS). The both of waveforms in ECG data are very similar, and thus it is difficult to completely detect the Paroxysmal stage of Atrial Fibrillation rhythms. Previous studies have tried to solve this issue and some of them achieved the discrimination with a high degree of accuracy. However, the accuracies of them do not reach 100%. In addition, no research has achieved it in a long duration, e.g. 12 hours, of ECG data. In this study, a new mechanism to tackle with these issues is proposed: “Door-to-Door” algorithm is introduced to accurately and quickly detect significant peaks of heart cycle in 12 hours of ECG data and to discriminate obvious ParAF rhythms from NS rhythms. In addition, a quantitative method using Artificial Neural Network (ANN), which discriminates unobvious ParAF rhythms from NS rhythms, is investigated. As the result of Door-to-Door algorithm performance evaluation, it was revealed that Door-to-Door algorithm achieves the accuracy of 100% in detecting the significant peaks of heart cycle in 17 NS ECG data. In addition, it was verified that ANN-based method achieves the accuracy of 100% in discriminating the Paroxysmal stage of 15 Atrial Fibrillation data from 17 NS data. Furthermore, it was confirmed that the computational time to perform the proposed mechanism is less than the half of the previous study. From these achievements, it is concluded that the proposed mechanism can practically be used to diagnose early stage of heart diseases.
Xiaoli ZENG Longye WANG Hong WEN Gaoyuan ZHANG
By interleaving known Z-periodic complementary (ZPC) sequence set, a new ZPC sequence set is constructed with multiple ZPC sequence subsets based on an orthogonal matrix in this work. For this novel ZPC sequence set, which refer to as asymmetric ZPC (AZPC) sequence set, its inter-subset zero cross-correlation zone (ZCCZ) is larger than intra-subset zero correlation zone (ZCZ). In particular, if select a periodic perfect complementary (PC) sequence or PC sequence set and a discrete Fourier transform (DFT) matrix, the resultant sequence set is an inter-group complementary (IGC) sequence set. When a suitable shift sequence is chosen, the obtained IGC sequence set will be optimal in terms of the corresponding theoretical bound. Compared with the existing constructions of IGC sequence sets, the proposed method can provide not only flexible ZCZ width but also flexible choice of basic sequences, which works well in both synchronous and asynchronous operational modes. The proposed AZPC sequence sets are suitable for multiuser environments.
In this paper, we present a hybrid message logging protocol consisting of three modules for two-level hierarchical and distributed architectures to address the drawbacks of sender-based message logging. The first module reduces the number of in-group control messages and, the rest, the number of inter-group control messages while localizing recovery. In addition, it can distribute the load of logging and keeping inter-group messages to group members as evenly as possible. The simulation results show the proposed protocol considerably outperforms the traditional protocol in terms of message logging overhead and scalability.
Hiroyuki ASAHARA Takuji KOUSAKA
In this research, we propose an effective stability analysis method to impacting systems with periodically moving borders (periodic borders). First, we describe an n-dimensional impacting system with periodic borders. Subsequently, we present an algorithm based on a stability analysis method using the monodromy matrix for calculating stability of the waveform. This approach requires the state-transition matrix be related to the impact phenomenon, which is known as the saltation matrix. In an earlier study, the expression for the saltation matrix was derived assuming a static border (fixed border). In this research, we derive an expression for the saltation matrix for a periodic border. We confirm the performance of the proposed method, which is also applicable to systems with fixed borders, by applying it to an impacting system with a periodic border. Using this approach, we analyze the bifurcation of an impacting system with a periodic border by computing the evolution of the stable and unstable periodic waveform. We demonstrate a discontinuous change of the periodic points, which occurs when a periodic point collides with a border, in the one-parameter bifurcation diagram.
Feifei ZHAO Wenping MA Momiao ZHOU Chengli ZHANG
Based on Bezout's theorem, the feasibility condition for interference alignment (IA) is established in a two-way small cell network where part of cells transmit in downlink while the others in uplink. Moreover, the sufficient and necessary condition for the two-way network to achieve as many degrees of freedom (DoFs) as the traditional one-way network is presented. We find that in certain cases every small cell can independently decide to work in either downlink mode or uplink mode as needed without causing performance degradation of IA.
Yoojin KIM Yongwoon SONG Hyukjun LEE
An accurate but energy-efficient estimation of a position is important as the number of mobile computing systems grow rapidly. A challenge is to develop a highly accurate but energy efficient estimation method. A particle filter is a key algorithm to estimate and track the position of an object which exhibits non-linear movement behavior. However, it requires high usage of computation resources and energy. In this paper, we propose a scheme which can dynamically adjust the number of particles according to the accuracy of the reference signal for positioning and reduce the energy consumption by 37% on Cortex A7.
Atsushi OOKA Suyong EUM Shingo ATA Masayuki MURATA
Information-centric networking (ICN) has gained attention from network research communities due to its capability of efficient content dissemination. In-network caching function in ICN plays an important role to achieve the design motivation. However, many researchers on in-network caching due to its ability to efficiently disseminate content. The in-network caching function in ICN plays an important role in realizing the design goals. However, many in-network caching researchers have focused on where to cache rather than how to cache: the former is known as content deployment in the network and the latter is known as cache replacement in an ICN router. Although the cache replacement has been intensively researched in the context of web-caching and content delivery network previously, networks, the conventional approaches cannot be directly applied to ICN due to the fine granularity of chunks in ICN, which eventually changes the access patterns. In this paper, we argue that ICN requires a novel cache replacement algorithm to fulfill the requirements in the design of a high performance ICN router. Then, we propose a novel cache replacement algorithm to satisfy the requirements named Compact CLOCK with Adaptive Replacement (Compact CAR), which can reduce the consumption of cache memory to one-tenth compared to conventional approaches. In this paper, we argue that ICN requires a novel cache replacement algorithm to fulfill the requirements set for high performance ICN routers. Our solution, Compact CLOCK with Adaptive Replacement (Compact CAR), is a novel cache replacement algorithm that satisfies the requirements. The evaluation result shows that the consumption of cache memory required to achieve a desired performance can be reduced by 90% compared to conventional approaches such as FIFO and CLOCK.
Suyan LIU Yuanan LIU Fan WU Puning ZHANG
The tens of billions of devices expected to be connected to the Internet will include so many sensors that the demand for sensor-based services is rising. The task of effectively utilizing the enormous numbers of sensors deployed is daunting. The need for automatic sensor identification has expanded the need for research on sensor similarity searches. The Internet of Things (IoT) features massive non-textual dynamic data, which is raising the critical challenge of efficiently and effectively searching for and selecting the sensors most related to a need. Unfortunately, single-attribute similarity searches are highly inaccurate when searching among similar attribute values. In this paper, we propose a group-fitting correlation calculation algorithm (GFC) that can identify the most similar clusters of sensors. The GFC method considers multiple attributes (e.g., humidity, temperature) to calculate sensor similarity; thus, it performs more accurate searches than do existing solutions.
Jae-Gon LEE Taek-Sun KWON Bo-Hee CHOI Jeong-Hae LEE
In this paper, a compact controlled reception pattern antenna (CRPA) array based on a mu-zero resonance (MZR) antenna is proposed for a global positioning system (GPS). The MZR antenna can be minimized by designing structure based in mu-negative (MNG) transmission line. The MNG transmission line can be implemented by a gap structure for the series capacitance and a shorting via for a short-ended boundary condition. The CRPA array, which operates in L1 (1.57542GHz) and L2 (1.2276GHz) bands, is designed as a cylinder with a diameter and a height of 127mm (5 inches) and 20mm, respectively, and is composed of seven radiating elements. To design the compact CRPA array with high performance attributes such as an impedance matching (VSWR) value of less than 2, an isolation between array elements (<-12dB), an axial ratio (<5dB), and a circular polarization (CP) gain (>-1dBic: L1 band and >-3dBic: L2 band), we employ two orthogonal MZR antennas, a superstrate, and chip couplers. The performances of the CRPA antenna are verified and compared by an analytic analysis, a full-wave simulation, and measurements.
Takaaki KISHIGAMI Hidekuni YOMO Naoya YOSOKU Akihiko MATSUOKA Junji SATO
This paper proposes multiple-input multiple-output (MIMO) radar waveforms consisting of Doppler-offset orthogonal complementary codes (DO-OCC) for raising the Doppler resilience of MIMO radar systems. The DO-OCC waveforms have low cross-correlation among multiplexed waves and a low autocorrelation peak sidelobe level (PSL) even in the Doppler shift condition. They are verified by computer simulations and measurements. Computer simulations show that the peak sidelobe ratio (PSR) of the DO-OCC exceeds over 60dB and the desired to undesired signal power ratio (DUR) is over 60dB in the case that the Doppler shift is 0.048 rad per pulse repetition interval (PRI). And through the experimental measurements, it has been verified that the PSR of the DO-OCC is over 40dB and the DUR is over 50dB in the case that Doppler shift is 0.05 rad per PRI and that The DO-OCC waveforms enable to maintain the direction of arrival (DOA) estimation accuracy for moving targets as almost same as the one for static targets. The results prove the effectiveness of the proposed MIMO waveforms in achieving Doppler tolerance while maintaining orthogonality and autocorrelation properties.
Hideki ONO Takasi SIMOYAMA Shigekazu OKUMURA Masahiko IMAI Hiroki YAEGASHI Hironori SASAKI
We report good responsivity at the wavelength of 1600nm in a Ge photodetector which had lateral p-i-n structure and butt-joint coupling structure based on conventional normal complementary metal oxide semiconductor processes. We experimentally verified the responsivity of 0.82A/W and 0.71A/W on the best and the worst polarizations, respectively. The butt joint lateral p-i-n structure is found to be polarization independent as compared with vertical ones. Although cut-off frequency was 2.3-2.4GHz at reverse bias 3V, clearly open eye diagram at 10Gbps was obtained with reverse bias over 12V. These results are promising as optical photodetectors to receive long wavelengths downstream signal wavelengths required for next-generation optical access network systems.
Kenji HASHIMOTO Ryunosuke TAKAYAMA Hiroyuki SEKI
One of the most promising compression methods for XML documents is the one that translates a given document to a tree grammar that generates it. A feature of this compression is that the internal structures are kept in production rules of the grammar. This enables us to directly manipulate the tree structure without decompression. However, previous studies assume that a given XML document does not have data values because they focus on direct retrieval and manipulation of the tree structure. This paper proposes a direct update method for XML documents with data values and shows the effectiveness of the proposed method based on experiments conducted on our implemented tool.
Bao Trung CHU Kenji HASHIMOTO Hiroyuki SEKI
Formal series are a natural extension of formal languages by associating each word with a value called a coefficient or a weight. Among them, recognizable series and algebraic series can be regarded as extensions of regular languages and context-free languages, respectively. The coefficient of a word w can represent quantities such as the cost taken by an operation on w, the probability that w is emitted. One of the possible applications of formal series is the string counting in quantitative analysis of software. In this paper, we define the counting problems for formal series and propose algorithms for the problems. The membership problem for an automaton or a grammar corresponds to the problem of computing the coefficient of a given word in a given series. Accordingly, we define the counting problem for formal series in the following two ways. For a formal series S and a natural number d, we define CC(S,d) to be the sum of the coefficients of all the words of length d in S and SC(S,d) to be the number of words of length d that have non-zero coefficients in S. We show that for a given recognizable series S and a natural number d, CC(S,d) can be computed in O(η log d) time where η is an upper-bound of time needed for a single state-transition matrix operation, and if the state-transition matrices of S are commutative for multiplication, SC(S,d) can be computed in polynomial time of d. We extend the notions to tree series and discuss how to compute them efficiently. Also, we propose an algorithm that computes CC(S,d) in square time of d for an algebraic series S. We show the CPU time of the proposed algorithm for computing CC(S,d) for some context-free grammars as S, one of which represents the syntax of C language. To examine the applicability of the proposed algorithms to string counting for the vulnerability analysis, we also present results on string counting for Kaluza Benchmark.
We have previously introduced the static dependency pair method that proves termination by analyzing the static recursive structure of various extensions of term rewriting systems for handling higher-order functions. The key is to succeed with the formalization of recursive structures based on the notion of strong computability, which is introduced for the termination of typed λ-calculi. To bring the static dependency pair method close to existing functional programs, we also extend the method to term rewriting models in which functional abstractions with patterns are permitted. Since the static dependency pair method is not sound in general, we formulate a class; namely, accessibility, in which the method works well. The static dependency pair method is a very natural reasoning; therefore, our extension differs only slightly from previous results. On the other hand, a soundness proof is dramatically difficult.
Ken-ichiro MORIDOMI Kohei HATANO Eiji TAKIMOTO
We consider online linear optimization over symmetric positive semi-definite matrices, which has various applications including the online collaborative filtering. The problem is formulated as a repeated game between the algorithm and the adversary, where in each round t the algorithm and the adversary choose matrices Xt and Lt, respectively, and then the algorithm suffers a loss given by the Frobenius inner product of Xt and Lt. The goal of the algorithm is to minimize the cumulative loss. We can employ a standard framework called Follow the Regularized Leader (FTRL) for designing algorithms, where we need to choose an appropriate regularization function to obtain a good performance guarantee. We show that the log-determinant regularization works better than other popular regularization functions in the case where the loss matrices Lt are all sparse. Using this property, we show that our algorithm achieves an optimal performance guarantee for the online collaborative filtering. The technical contribution of the paper is to develop a new technique of deriving performance bounds by exploiting the property of strong convexity of the log-determinant with respect to the loss matrices, while in the previous analysis the strong convexity is defined with respect to a norm. Intuitively, skipping the norm analysis results in the improved bound. Moreover, we apply our method to online linear optimization over vectors and show that the FTRL with the Burg entropy regularizer, which is the analogue of the log-determinant regularizer in the vector case, works well.
Naoki FUJIEDA Kiyohiro SATO Ryodai IWAMOTO Shuichi ICHIKAWA
Instruction set randomization (ISR) is a cost-effective obfuscation technique that modifies or enhances the relationship between instructions and machine languages. An Instruction Register File (IRF), a list of frequently used instructions, can be used for ISR by providing the way of indirect access to them. This study examines the IRF that integrates a positional register, which was proposed as a supplementary unit of the IRF, for the sake of tamper resistance. According to our evaluation, with a new design for the contents of the positional register, the measure of tamper resistance was increased by 8.2% at a maximum, which corresponds to a 32.2% increase in the size of the IRF. The number of logic elements increased by the addition of the positional register was 3.5% of its baseline processor.