Chun-e ZHAO Yuhua SUN Tongjiang YAN Xubo ZHAO
Binary sequences with high linear complexity and high 2-adic complexity have important applications in communication and cryptography. In this paper, the 2-adic complexity of a class of balanced Whiteman generalized cyclotomic sequences which have high linear complexity is considered. Through calculating the determinant of the circulant matrix constructed by one of these sequences, the result shows that the 2-adic complexity of this class of sequences is large enough to resist the attack of the rational approximation algorithm (RAA) for feedback with carry shift registers (FCSRs).
Xubo ZHAO Xiaoping LI Runzhi YANG Qingqing ZHANG Jinpeng LIU
In this paper, we study Hermitian linear complementary dual (abbreviated Hermitian LCD) rank metric codes. A class of Hermitian LCD generalized Gabidulin codes are constructed by qm-self-dual bases of Fq2m over Fq2. Moreover, the exact number of qm-self-dual bases of Fq2m over Fq2 is derived. As a consequence, an upper bound and a lower bound of the number of the constructed Hermitian LCD generalized Gabidulin codes are determined.
Some textbooks of formal languages and automata theory implicitly state the structural equality of the binary n-dimensional de Bruijn graph and the state diagram of minimum state deterministic finite automaton which accepts regular language (0+1)*1(0+1)n-1. By introducing special finite automata whose accepting states are refined with two or more colors, we extend this fact to both k-ary versions. That is, we prove that k-ary n-dimensional de Brujin graph and the state diagram for minimum state deterministic colored finite automaton which accepts the (k-1)-tuple of the regular languages (0+1+…+k-1)*1(0+1+…+k-1)n-1,...,and(0+1+…+k-1)*(k-1)(0+1+…+k-1)n-1 are isomorphic for arbitrary k more than or equal to 2. We also investigate the properties of colored finite automata themselves and give computational complexity results on three decision problems concerning color unmixedness of nondeterminisitic ones.
Yasuaki KOBAYASHI Shin-ichi NAKANO Kei UCHIZAWA Takeaki UNO Yutaro YAMAGUCHI Katsuhisa YAMANAKA
Given a set P of n points and an integer k, we wish to place k facilities on points in P so that the minimum distance between facilities is maximized. The problem is called the k-dispersion problem, and the set of such k points is called a k-dispersion of P. Note that the 2-dispersion problem corresponds to the computation of the diameter of P. Thus, the k-dispersion problem is a natural generalization of the diameter problem. In this paper, we consider the case of k=3, which is the 3-dispersion problem, when P is in convex position. We present an O(n2)-time algorithm to compute a 3-dispersion of P.
The effect of provision of “Neither-Good-Nor-Bad” (NGNB) information on the perceived trustworthiness of agents has been investigated in previous studies. The experimental results have revealed several conditions under which the provision of NGNB information works effectively to make users perceive greater trust of agents. However, the experiments in question were carried out in a situation in which a user is able to choose, with the agent's advice, one of a limited number of options. In practical problems, we are often at a loss as to which to choose because there are too many possible options and it is not easy to narrow them down. Furthermore, in the above-mentioned previous studies, it was easy to predict the size of profits that a user would obtain because its pattern was also limited. This prompted us, in this paper, to investigate the effect of provision of NGNB information on the users' trust of agents under conditions where it appears to the users that numerous options are available. Our experimental results reveal that an agent that reliably provides NGNB information tends to gain greater user trust in a situation where it appears to the users that there are numerous options and their consequences, and it is not easy to predict the size of profits. However, in contradiction to the previous study, the results in this paper also reveal that stable provision of NGNB information in the context of numerous options is less effective in a situation where it is harder to obtain larger profits.
Takahito TSUKAMOTO Go OTSURU Yukitoshi SANADA
In this paper, a macro cell switching scheme for distributed antennas is proposed. In conventional distributed antenna transmission (DAT), the macro cell to which each antenna belongs is fixed. Though a cell-free system has been investigated because of its higher system throughput, the implementation cost of front-hauls can be excessive. To increase the flexibility of resource allocation in the DAT with moderate front-haul complexity, we propose the macro cell switching of distributed antennas (DAs). In the proposed scheme, DAs switch their attribution macro cells depending on the amount of pre-assigned connections. Numerical results obtained through computer simulation show that the proposed scheme realizes a better system throughput than the conventional system, especially when the number of user equipments (UEs) is smaller and the distance between DAs are larger.
Tetsunao MATSUTA Tomohiko UYEMATSU
We consider the coding problem for lossy source coding with side information at the decoder, which is known as the Wyner-Ziv source coding problem. The goal of the coding problem is to find the minimum rate such that the probability of exceeding a given distortion threshold is less than the desired level. We give an equivalent expression of the minimum rate by using the chromatic number and notions of covering of a set. This allows us to analyze the coding problem in terms of graph coloring and covering.
Yuki MONMA Kan ARO Muneki YASUDA
In this study, Bayesian image denoising, in which the prior distribution is assumed to be a Gaussian Markov random field (GMRF), is considered. Recently, an effective algorithm for Bayesian image denoising with a standard GMRF prior has been proposed, which can help implement the overall procedure and optimize its parameters in O(n)-time, where n is the size of the image. A new GMRF-type prior, referred to as a hierarchical GMRF (HGMRF) prior, is proposed, which is obtained by applying a hierarchical Bayesian approach to the standard GMRF prior; in addition, an effective denoising algorithm based on the HGMRF prior is proposed. The proposed HGMRF method can help implement the overall procedure and optimize its parameters in O(n)-time, as well as the previous GMRF method. The restoration quality of the proposed method is found to be significantly higher than that of the previous GMRF method as well as that of a non-local means filter in several cases. Furthermore, numerical evidence implies that the proposed HGMRF prior is more suitable for the image prior than the standard GMRF prior.
Toi TOMITA Wakaha OGATA Kaoru KUROSAWA
In this paper, we construct the first efficient leakage-resilient CCA2 (LR-CCA2)-secure attribute-based encryption (ABE) schemes. We also construct the first efficient LR-CCA2-secure identity-based encryption (IBE) scheme with optimal leakage rate. To obtain our results, we develop a new quasi-adaptive non-interactive zero-knowledge (QA-NIZK) argument for the ciphertext consistency of the LR-CPA-secure schemes. Our ABE schemes are obtained by boosting the LR-CPA-security of some existing schemes to the LR-CCA2-security by using our QA-NIZK arguments. The schemes are almost as efficient as the underlying LR-CPA-secure schemes.
Keisuke HARA Takahiro MATSUDA Keisuke TANAKA
In the situation where there are one sender and multiple receivers, a receiver selective opening (RSO) attack for an identity-based encryption (IBE) scheme considers adversaries that can corrupt some of the receivers and get their user secret keys and plaintexts. Security against RSO attacks for an IBE scheme ensures confidentiality of ciphertexts of uncorrupted receivers. In this paper, we formalize a definition of RSO security against chosen ciphertext attacks (RSO-CCA security) for IBE and propose the first RSO-CCA secure IBE schemes. More specifically, we construct an RSO-CCA secure IBE scheme based on an IND-ID-CPA secure IBE scheme and a non-interactive zero-knowledge proof system with unbounded simulation soundness and multi-theorem zero-knowledge. Through our generic construction, we obtain the first pairing-based and lattice-based RSO-CCA secure IBE schemes.
Tatsuma MORI Taito MANABE Yuichiro SHIBATA
The convex hull is the minimum convex surrounding a given set of points. Since the process of finding convex hulls has various practical application fields including embedded real-time systems, efficient acceleration of convex hull algorithms is an important problem in computer geometry. In this paper, we discuss an FPGA acceleration approach to address this problem. In order to compute the convex hull of an unsorted point set, it is necessary to store all the points during the computation, and thus the capacity of a on-chip memory is likely to be a major constraint for efficient FPGA implementation. On the other hand, approximate convex hulls are often sufficient for practical applications. Therefore, we propose a hardware oriented approximate convex hull algorithm, which can process the input points as a stream without storing all the points in the memory. We also propose some computation reduction techniques for efficient FPGA implementation. Then, we present FPGA implementation of the proposed algorithm, which is parallelized both in temporal and spatial domains, and evaluate its effectiveness in terms of performance and accuracy. As a result, we demonstrated 11 to 30 times faster performance compared to the widely-used convex hull software library Qhull. In addition, accuracy assessment revealed that the maximum approximation error normalized to the diameters of point sets was 0.038%, which was reasonably small for practical use cases.
Tianfeng FENG Leonie RYVKIN Jérôme URHAUSEN Giovanni VIGLIETTA
We study the computational complexity of the puzzle game Critter Crunch, where the player has to rearrange Critters on a board in order to eliminate them all. Smaller Critters can be fed to larger Critters, and Critters will explode if they eat too much. Critters come in several different types, sizes, and colors. We prove the NP-hardness of levels that contain Blocker Critters, as well as levels where the player must clear the board in a given number of moves (i.e., “puzzle mode”). We also characterize the complexity of the game, as a function of the number of columns on the board, in two settings: (i) the setting where Critters may have several different colors, but only two possible sizes, and (ii) the setting where Critters come in all three sizes, but with no color variations. In both settings, the game is NP-hard for levels with exactly two columns, and solvable in linear time for levels with only one column or more than two columns.
Masatoshi YAMADA Masaki OHATA Daisuke KAKOI
In ball games, acquiring skills to change the direction becomes necessary. For revealing the mechanism of skill acquisition in terms of the relevant field, it would be necessary to take an approach regarding players' cognition as well as body movements measurable from outside. In the phase of change-of-direction performance that this study focuses on, cognitive factors including the prediction of opposite players' movements and judgements of the situation have significance. The purpose of this study was to reveal cognitive transformation in the skill acquisition process for change-of-direction performance. The survey was conducted for three months from August 29 to November 28, 2020, and those surveyed were seven university freshmen belonging to women's basketball club of M University. The way to analyze verbal reports collected in order to explore the changes in the players' cognition is described in Sect.2. In Sect.3, we made a plot graph showing temporal changes in respective factors based on coding outcomes for verbal reports. Consequently, as cognitive transformation in the skill acquisition process for change-of-direction performance, four items such as (1) goal setting for skill acquisition, (2) experience of change in running direction, (3) experience of speed and acceleration, and (4) experience of the movement of lower extremities such as legs and hip joints were suggested as common cognitive transformation. In addition, cognitive transformation varied by the degree of skill acquisition for change-of-direction performance. It was indicated that paying too much attention to body feelings including the position of and shift in the center of gravity in the body posed an obstacle to the skill acquisition for change-of-direction performance.
Suresh JAGANATHAN Sathya MADHUSUDHANAN
Online feeds are streamed continuously in batches with varied polarities at varying times. The system handling the online feeds must be trained to classify all the varying polarities occurring dynamically. The polarity classification system designed for the online feeds must address two significant challenges: i) stability-plasticity, ii) category-proliferation. The challenges faced in the polarity classification of online feeds can be addressed using the technique of incremental learning, which serves to learn new classes dynamically and also retains the previously learned knowledge. This paper proposes a new incremental learning methodology, ILOF (Incremental Learning of Online Feeds) to classify the feeds by adopting Deep Learning Techniques such as RNN (Recurrent Neural Networks) and LSTM (Long Short Term Memory) and also ELM (Extreme Learning Machine) for addressing the above stated problems. The proposed method creates a separate model for each batch using ELM and incrementally learns from the trained batches. The training of each batch avoids the retraining of old feeds, thus saving training time and memory space. The trained feeds can be discarded when new batch of feeds arrives. Experiments are carried out using the standard datasets comprising of long feeds (IMDB, Sentiment140) and short feeds (Twitter, WhatsApp, and Twitter airline sentiment) and the proposed method showed positive results in terms of better performance and accuracy.
Lige GE Shengming JIANG Xiaowei WANG Yanli XU Ruoyu FENG Zhichao ZHENG
Along with the fast development of blue economy, wireless communication in oceans has received extensive attention in recent years, and opportunistic networks without any aid from fixed infrastructure or centralized management are expected to play an important role in such highly dynamic environments. Here, link prediction can help nodes to select proper links for data forwarding to reduce transmission failure. The existing prediction schemes are mainly based on analytical models with no adaptability, and consider relatively simple and small terrestrial wireless networks. In this paper, we propose a new link prediction algorithm based on machine learning, which is composed of an extractor of convolutional layers and an estimator of long short-term memory to extract useful representations of time-series data and identify effective long-term dependencies. The experiments manifest that the proposed scheme is more effective and flexible compared with the other link prediction schemes.
Beomjin YUK Byeongseol KIM Soohyun YOON Seungbeom CHOI Joonsung BAE
This paper presents a driver status monitoring (DSM) system with body channel communication (BCC) technology to acquire the driver's physiological condition. Specifically, a conductive thread, the receiving electrode, is sewn to the surface of the seat so that the acquired signal can be continuously detected. As a signal transmission medium, body channel characteristics using the conductive thread electrode were investigated according to the driver's pose and the material of the driver's pants. Based on this, a BCC transceiver was implemented using an analog frequency modulation (FM) scheme to minimize the additional circuitry and system cost. We analyzed the heart rate variability (HRV) from the driver's electrocardiogram (ECG) and displayed the heart rate and Root Mean Square of Successive Differences (RMSSD) values together with the ECG waveform in real-time. A prototype of the DSM system with commercial-off-the-shelf (COTS) technology was implemented and tested. We verified that the proposed approach was robust to the driver's movements, showing the feasibility and validity of the DSM with BCC technology using a conductive thread electrode.
Jian PANG Xueting LUO Zheng LI Atsushi SHIRANE Kenichi OKADA
This paper introduces a high-resolution and compact CMOS switch-type phase shifter (STPS) for the 5th generation mobile network (5G) n260 band. In this work, totally four coarse phase shifting stages and a high-resolution tuning stage are included. The coarse stages based on the bridged-T topology is capable of providing 202.5° phase coverage with a 22.5° tuning step. To further improve the phase shifting resolution, a compact fine-tuning stage covering 23° is also integrated with the coarse stages. Sub-degree phase shifting resolution is realized for supporting the fine beam-steering and high-accuracy phase calibration in the 5G new radio. Simplified phase control algorithm and suppressed insertion loss can also be maintained by the proposed fine-tuning stage. In the measurement, the achieved RMS gain errors at 39 GHz are 0.1 dB and 0.4 dB for the coarse stages and fine stage, respectively. The achieved RMS phase errors at 39 GHz are 3.1° for the coarse stages and 0.1° for the fine stage. Within 37 GHz to 40 GHz, the measured return loss within all phase-tuning states is always better than -14 dB. The proposed phase shifter consumes a core area of only 0.12mm2 with 65-nm CMOS process, which is area-efficient.
For a graph G=(V,E), finding a set of disjoint edges that do not share any vertices is called a matching problem, and finding the maximum matching is a fundamental problem in the theory of distributed graph algorithms. Although local algorithms for the approximate maximum matching problem have been widely studied, exact algorithms have not been much studied. In fact, no exact maximum matching algorithm that is faster than the trivial upper bound of O(n2) rounds is known for general instances. In this paper, we propose a randomized $O(s_{max}^{3/2})$-round algorithm in the CONGEST model, where smax is the size of maximum matching. This is the first exact maximum matching algorithm in o(n2) rounds for general instances in the CONGEST model. The key technical ingredient of our result is a distributed algorithms of finding an augmenting path in O(smax) rounds, which is based on a novel technique of constructing a sparse certificate of augmenting paths, which is a subgraph of the input graph preserving at least one augmenting path. To establish a highly parallel construction of sparse certificates, we also propose a new characterization of sparse certificates, which might also be of independent interest.
Wenhao FAN Dong LIU Fan WU Bihua TANG Yuan'an LIU
Android operating system occupies a high share in the mobile terminal market. It promotes the rapid development of Android applications (apps). However, the emergence of Android malware greatly endangers the security of Android smartphone users. Existing research works have proposed a lot of methods for Android malware detection, but they did not make the utilization of apps' functional category information so that the strong similarity between benign apps in the same functional category is ignored. In this paper, we propose an Android malware detection scheme based on the functional classification. The benign apps in the same functional category are more similar to each other, so we can use less features to detect malware and improve the detection accuracy in the same functional category. The aim of our scheme is to provide an automatic application functional classification method with high accuracy. We design an Android application functional classification method inspired by the hyperlink induced topic search (HITS) algorithm. Using the results of automatic classification, we further design a malware detection method based on app similarity in the same functional category. We use benign apps from the Google Play Store and use malware apps from the Drebin malware set to evaluate our scheme. The experimental results show that our method can effectively improve the accuracy of malware detection.
A new adaptive binarization method is proposed for the vehicle state images obtained from the intelligent operation and maintenance system of rail transit. The method can check the corresponding vehicle status information in the intelligent operation and maintenance system of rail transit more quickly and effectively, track and monitor the vehicle operation status in real time, and improve the emergency response ability of the system. The advantages of the proposed method mainly include two points. For decolorization, we use the method of contrast preserving decolorization[1] obtain the appropriate ratio of R, G, and B for the grayscale of the RGB image which can retain the color information of the vehicle state images background to the maximum, and maintain the contrast between the foreground and the background. In terms of threshold selection, the mean value and standard deviation of gray value corresponding to multi-color background of vehicle state images are obtained by using major cluster estimation[2], and the adaptive threshold is determined by the 2 sigma principle for binarization, which can extract text, identifier and other target information effectively. The experimental results show that, regarding the vehicle state images with rich background color information, this method is better than the traditional binarization methods, such as the global threshold Otsu algorithm[3] and the local threshold Sauvola algorithm[4],[5] based on threshold, Mean-Shift algorithm[6], K-Means algorithm[7] and Fuzzy C Means[8] algorithm based on statistical learning. As an image preprocessing scheme for intelligent rail transit data verification, the method can improve the accuracy of text and identifier recognition effectively by verifying the optical character recognition through a data set containing images of different vehicle statuses.