We study a new reconfiguration problem inspired by classic mechanical puzzles: a colored token is placed on each vertex of a given graph; we are also given a set of distinguished cycles on the graph. We are tasked with rearranging the tokens from a given initial configuration to a final one by using cyclic shift operations along the distinguished cycles. We call this a cyclic shift puzzle. We first investigate a large class of graphs, which generalizes several classic cyclic shift puzzles, and we give a characterization of which final configurations can be reached from a given initial configuration. Our proofs are constructive, and yield efficient methods for shifting tokens to reach the desired configurations. On the other hand, when the goal is to find a shortest sequence of shifting operations, we show that the problem is NP-hard, even for puzzles with tokens of only two different colors.

The construction of a Huffman code can be understood as the problem of finding a full binary tree such that each leaf is associated with a linear function of the depth of the leaf and the sum of the function values is minimized. Fujiwara and Jacobs extended this to a general function and proved the extended problem to be NP-hard. The authors also showed the case where the functions associated with leaves are each non-decreasing and convex is solvable in polynomial time. However, the complexity of the case of non-decreasing non-convex functions remains unknown. In this paper we try to reveal the complexity by considering non-decreasing non-convex functions each of which takes the smaller value of either a linear function or a constant. As a result, we provide a polynomial-time algorithm for two subclasses of such functions.

Hansen, Kaplan, Zamir and Zwick (STOC 2019) introduced a systematic way to use “bias” for predicting an assignment to a Boolean variable in the process of PPSZ and showed that their biased PPSZ algorithm achieves a relatively large success probability improvement of PPSZ for Unique 3SAT. We propose an additional way to use “bias” and show by numerical analysis that the improvement gets increased further.

We study the gathering problem requiring a team of mobile agents to gather at a single node in arbitrary networks. The team consists of k agents with unique identifiers (IDs), and f of them are weakly Byzantine agents, which behave arbitrarily except falsifying their identifiers. The agents move in synchronous rounds and cannot leave any information on nodes. If the number of nodes n is given to agents, the existing fastest algorithm tolerates any number of weakly Byzantine agents and achieves gathering with simultaneous termination in O(n4·|Λgood|·X(n)) rounds, where |Λgood| is the length of the maximum ID of non-Byzantine agents and X(n) is the number of rounds required to explore any network composed of n nodes. In this paper, we ask the question of whether we can reduce the time complexity if we have a strong team, i.e., a team with a few Byzantine agents, because not so many agents are subject to faults in practice. We give a positive answer to this question by proposing two algorithms in the case where at least 4f2+9f+4 agents exist. Both the algorithms assume that the upper bound N of n is given to agents. The first algorithm achieves gathering with non-simultaneous termination in O((f+|&Lambdagood|)·X(N)) rounds. The second algorithm achieves gathering with simultaneous termination in O((f+|&Lambdaall|)·X(N)) rounds, where |&Lambdaall| is the length of the maximum ID of all agents. The second algorithm significantly reduces the time complexity compared to the existing one if n is given to agents and |&Lambdaall|=O(|&Lambdagood|) holds.

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).

This paper proposes a network tomography scheme for information-centric networking (ICN), which we call ICN tomography. When content is received over a conventional IP network, the communication occurs after converting the content name into an IP address, which is the locator, so as to identify the position of the network. By contrast, in ICN, communication is achieved by directly specifying the content name or content ID. The content is sent to the requesting user by a nearby node having the content or cache, making it difficult to apply a conventional network tomography that uses end-to-end quality of service (QoS) measurements and routing information between the source and destination node pairs as input to the ICN. This is because, in ICN, the end-to-end flow for an end host receiving some content can take various routes; therefore, the intermediate and source nodes can vary. In this paper, we first describe the technical challenges of applying network tomography to ICN. We then propose ICN tomography, where we use the content name as an endpoint to define an end-to-end QoS measurement and a routing matrix. In defining the routing matrix, we assume that the end-to-end flow follows a probabilistic routing. Finally, the effectiveness of the proposed method is evaluated through a numerical analysis and simulation.

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.

In this paper, we propose the first private decision tree evaluation (PDTE) schemes which are suitable for use in Machine Learning as a Service (MLaaS) scenarios. In our schemes, a user and a model owner send the ciphertexts of a sample and a decision tree model, respectively, and a single server classifies the sample without knowing the sample nor the decision tree. Although many PDTE schemes have been proposed so far, most of them require to reveal the decision tree to the server. This is undesirable because the classification model is the intellectual property of the model owner, and/or it may include sensitive information used to train the model, and therefore the model also should be hidden from the server. In other PDTE schemes, multiple servers jointly conduct the classification process and the decision tree is kept secret from the servers under the assumption they do not collude. Unfortunately, this assumption may not hold because MLaaS is usually provided by a single company. In contrast, our schemes do not have such problems. In principle, fully homomorphic encryption allows us to classify an encrypted sample based on an encrypted decision tree, and in fact, the existing non-interactive PDTE scheme can be modified so that the server classifies only handling ciphertexts. However, the resulting scheme is less efficient than ours. We also show the experimental results for our schemes.

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.

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.

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.

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.

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.

In the upcoming Internet of Things era, reducing energy consumption of embedded processors is highly desired. Minimum Energy Point Tracking (MEPT) is one of the most efficient methods to reduce both dynamic and static energy consumption of a processor. Previous works proposed a variety of MEPT methods over the past years. However, none of them incorporate their algorithms with practical real-time operating systems, although edge computing applications often require low energy task execution with guaranteeing real-time properties. The difficulty comes from the time complexity for identifying an MEP and changing voltages, which often prevents real-time task scheduling. The conventional Dynamic Voltage and Frequency Scaling (DVFS) only scales the supply voltage. On the other hand, MEPT needs to adjust the body bias voltage in addition. This additional tuning knob makes MEPT much more complicated. This paper proposes an approximate MEPT algorithm, which reduces the complexity of identifying an MEP down to that of DVFS. The key idea is to linearly approximate the relationship between the processor frequency, supply voltage, and body bias voltage. Thanks to the approximation, optimal voltages for a specified clock frequency can be derived immediately. We also propose a task scheduling algorithm, which adjusts processor performance to the workload and then provides a soft real-time capability to the system. The operating system stochastically adjusts the average response time of the processor to be equal to a specified deadline. MEPT will be performed as a general task, and its overhead is considered in the calculation of the frequency. The experiments using a fabricated test chip and on-chip sensors show that the proposed algorithm is a maximum of 16 times more energy-efficient than DVFS. Also, the energy loss induced by the approximation is only 3% at most, and the algorithm does not sacrifice the fundamental real-time properties.

The growing threat of Hardware Trojans (HT) in the System-on-Chips (SoC) industry has given way to the embedded systems researchers to propose a series of detection methodologies to identify and detect the presence of Trojan circuits or logics inside a host design in the various stages of the chip design and manufacturing process. Many state of the art works propose different techniques for HT detection among which the popular choice remains the Side-Channel Analysis (SCA) based methods that perform differential analysis targeting the difference in consumption of power, change in electromagnetic emanation or the delay in propagation of logic in various paths of the circuit. Even though the effectiveness of these methods are well established, the evaluation is carried out on simplistic models such as AES coprocessors and the analytical approaches used for these methods are limited by some statistical metrics such as direct comparison of EM traces or the T-test coefficients. In this paper, we propose two new detection methodologies based on Machine Learning algorithms. The first method consists in applying the supervised Machine Learning (ML) algorithms on raw EM traces for the classification and detection of HT. It offers a detection rate close to 90% and false negative smaller than 5%. In the second method, we propose an outlier/novelty algorithms based approach. This method combined with the T-test based signal processing technique, when compared with state-of-the-art, offers a better performance with a detection rate close to 100% and a false positive smaller than 1%. In different experiments, the false negative is nearly the same level than the false positive and for that reason the authors only show the false positive value on the results. We have evaluated the performance of our method on a complex target design: RISC-V generic processor. Three HTs with their corresponding sizes: 0.53%, 0.27% and 0.09% of the RISC-V processors are inserted for the experimentation. In this paper we provide elaborative details of our tests and experimental process for reproducibility. The experimental results show that the inserted HTs, though minimalistic, can be successfully detected using our new methodology.

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.

Recent localization methods for wireless networks cannot be applied to dynamic networks with unknown topology. To solve this problem, we propose a localization method based on partial correlation analysis in this paper. We evaluate our proposed localization method in terms of accuracy, which shows that our proposed method can achieve high accuracy localization for dynamic networks with unknown topology.

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.

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.

The efficient implementation strategy for speeding up high-quality clustering algorithms is developed on the basis of general purpose graphic processing units (GPGPUs) in this work. Among various clustering algorithms, a sophisticated Gaussian mixture model (GMM) by estimating parameters through variational Bayesian (VB) mechanism is conducted due to its superior performances. Since the VB-GMM methodology is computation-hungry, the GPGPU is employed to carry out massive matrix-computations. To efficiently migrate the conventional CPU-oriented schemes of VB-GMM onto GPGPU platforms, an entire migration-flow with thirteen stages is presented in detail. The CPU-GPGPU co-operation scheme, execution re-order, and memory access optimization are proposed for optimizing the GPGPU utilization and maximizing the clustering speed. Five types of real-world applications along with relevant data-sets are introduced for the cross-validation. From the experimental results, the feasibility of implementing VB-GMM algorithm by GPGPU is verified with practical benefits. The proposed GPGPU migration achieves 192x speedup in maximum. Furthermore, it succeeded in identifying the proper number of clusters, which is hardly conducted by the EM-algotihm.