Using linear programming (LP) decoding based on alternating direction method of multipliers (ADMM) for low-density parity-check (LDPC) codes shows lower complexity than the original LP decoding. However, the development of the ADMM-LP decoding algorithm could still be limited by the computational complexity of Euclidean projections onto parity check polytope. In this paper, we proposed a bisection method iterative algorithm (BMIA) for projection onto parity check polytope avoiding sorting operation and the complexity is linear. In addition, the convergence of the proposed algorithm is more than three times as fast as the existing algorithm, which can even be 10 times in the case of high input dimension.

We design a new oblivious routing algorithm for two-dimensional mesh-based Networks-on-Chip (NoCs) called LEF (Long Edge First) which offers high throughput with low design complexity. LEF's basic idea comes from conventional wisdom in choosing the appropriate dimension-order routing (DOR) algorithm for supercomputers with asymmetric mesh or torus interconnects: routing longest dimensions first provides better performance than other strategies. In LEF, we combine the XY DOR and the YX DOR. When routing a packet, which DOR algorithm is chosen depends on the relative position between the source node and the destination node. Decisions of selecting the appropriate DOR algorithm are not fixed to the network shape but instead made on a per-packet basis. We also propose an efficient deadlock avoidance method for LEF in which the use of virtual channels is more flexible than in the conventional method. We evaluate LEF against O1TURN, another effective oblivious routing algorithm, and a minimal adaptive routing algorithm based on the odd-even turn model. The evaluation results show that LEF is particularly effective when the communication is within an asymmetric mesh. In a 16×8 NoC, LEF even outperforms the adaptive routing algorithm in some cases and delivers from around 4% up to around 64.5% higher throughput than O1TURN. Our results also show that the proposed deadlock avoidance method helps to improve LEF's performance significantly and can be used to improve O1TURN's performance. We also examine LEF in large-scale NoCs with thousands of nodes. Our results show that, as the NoC size increases, the performance of the routing algorithms becomes more strongly influenced by the resource allocation policy in the network and the effect is different for each algorithm. This is evident in that results of middle-scale NoCs with around 100 nodes cannot be applied directly to large-scale NoCs.

Unmanned aerial vehicle mounted base stations (UAV-BSs) can provide wireless cellular service to ground users in a variety of scenarios. The efficient deployment of such UAV-BSs while optimizing the coverage area is one of the key challenges. We investigate the deployment of UAV-BS to maximize the coverage of ground users, and further analyzes the impact of the deployment of UAV-BS on the fairness of ground users. In this paper, we first calculated the location of the UAV-BS according to the QoS requirements of the ground users, and then the fairness of ground users is taken into account by calculating three different fairness indexes. The performance of two genetic algorithms, namely Standard Genetic Algorithm (SGA) and Multi-Population Genetic Algorithm (MPGA) are compared to solve the optimization problem of UAV-BS deployment. The simulations are presented showing that the performance of the two algorithms, and the fairness performance of the ground users is also given.

A passively mobile system is an abstract notion of mobile ad-hoc networks. It is a collection of agents with computing devices. Agents move in a region, but the algorithm cannot control their physical behavior (i.e., how they move). The population protocol model is one of the promising models in which the computation proceeds by the pairwise communication between two agents. The communicating agents update their states by a specified transition function (algorithm). In this paper, we consider a general form of the aggregation problem with a base station. The base station is a special agent having the computational power more powerful than others. In the aggregation problem, the base station has to sum up for inputs distributed to other agents. We propose an algorithm that solves the aggregation problem in sub-linear parallel time using a relatively small number of states per agent. More precisely, our algorithm solves the aggregation problem with input domain X in O(√n log2 n) parallel time and O(|X|2) states per agent (except for the base station) with high probability.

Miller [9] proposed a linear-time algorithm for computing small separators for 2-connected planar graphs. We explain his algorithm and present a way to modify it to a space efficient version. Our algorithm can be regarded as a log-space reduction from the separator construction to the breadth first search tree construction.

The Shortest Vector Problem (SVP) is one of the most important lattice problems in computer science and cryptography. The LLL lattice basis reduction algorithm runs in polynomial time and can compute an LLL-reduced basis that provably contains an approximate solution to the SVP. On the other hand, the LLL algorithm in practice tends to solve low-dimensional exact SVPs with high probability, i.e., >99.9%. Filling this theoretical-practical gap would lead to an understanding of the computational hardness of the SVP. In this paper, we try to fill the gap in 3,4 and 5 dimensions and obtain two results. First, we prove that given a 3,4 or 5-dimensional LLL-reduced basis, the shortest vector is one of the basis vectors or it is a limited integer linear combination of the basis vectors. In particular, we construct explicit representations of the shortest vector by using the LLL-reduced basis. Our analysis yields a necessary and sufficient condition for checking whether the output of the LLL algorithm contains the shortest vector or not. Second, we estimate the failure probability that a 3-dimensional random LLL-reduced basis does not contain the shortest vector. The upper bound seems rather tight by comparison with a Monte Carlo simulation.

In this paper, we investigate the maximum induced matching problem (MaxIM) on C5-free d-regular graphs. The previously known best approximation ratio for MaxIM on C5-free d-regular graphs is $left(rac{3d}{4}-rac{1}{8}+rac{3}{16d-8} ight)$. In this paper, we design a $left(rac{2d}{3}+rac{1}{3} ight)$-approximation algorithm, whose approximation ratio is strictly smaller/better than the previous one when d≥6.

Revisiting the Sekine-Imai-Tani top-down algorithm to compute the BDD of all spanning trees and the Tutte polynomial of a given graph, we explicitly analyze the Fixed-Parameter Tractable (FPT) time complexity with respect to its (proper) pathwidth, pw (ppw), and obtain a bound of O*(Bellmin{pw}+1,ppw}), where Belln denotes the n-th Bell number, defined as the number of partitions of a set of n elements. We further investigate the case of complete graphs in terms of Bell numbers and related combinatorics, obtaining a time complexity bound of Belln-O(n/log n).

In this paper, we consider the problem of enumerating spanning subgraphs with high edge-connectivity of an input graph. Such subgraphs ensure multiple routes between two vertices. We first present an algorithm that enumerates all the 2-edge-connected spanning subgraphs of a given plane graph with n vertices. The algorithm generates each 2-edge-connected spanning subgraph of the input graph in O(n) time. We next present an algorithm that enumerates all the k-edge-connected spanning subgraphs of a given general graph with m edges. The algorithm generates each k-edge-connected spanning subgraph of the input graph in O(mT) time, where T is the running time to check the k-edge-connectivity of a graph.

In this paper, we investigate computational complexity of pipe puzzles. A pipe puzzle is a kind of tiling puzzle; the input is a set of cards, and a part of a pipe is drawn on each card. For a given set of cards, we arrange them and connect the pipes. We have to connect all pipes without creating any local loop. While ordinary tiling puzzles, like jigsaw puzzles, ask to arrange the tiles with local consistency, pipe puzzles ask to join all pipes. We first show that the pipe puzzle is NP-complete in general even if the goal shape is quite restricted. We also investigate restricted cases and show some polynomial-time algorithms.

At PQCrypto 2016, Szepieniec et al. proposed a new type of trapdoor called Extension Field Cancellation (EFC) for constructing secure multivariate encryption cryptosystems. They also specifically suggested two schemes EFCp- and EFCpt2- that apply this trapdoor and some modifiers. Although both of them seem to avoid all attacks used for cryptanalysis on multivariate cryptography, their decryption efficiency has room for improvement. On the other hand, their security was analyzed mainly through an algebraic attack of computing the Gröbner basis of the public key, and there possibly exists more effective attacks. In this paper, we introduce a more efficient decryption approach for EFCp- and EFCpt2-, which manages to avoid all redundant computation involved in the original decryption algorithms without altering their public key. In addition, we estimate the secure parameters for EFCp- and EFCpt2- through a hybrid attack of algebraic attack and exhaustive search.

This study proposes a Peak-to-Average Power Ratio (PAPR) reduction method using an adaptive Finite Impulse Response (FIR) filter in Orthogonal Frequency Division Multiplexing systems. At the transmitter, an iterative algorithm that minimizes the p-norm of a transmitted signal vector is used to update the weight coefficients of the FIR filter to reduce PAPR. At the receiver, the FIR filter used at the transmitter is estimated using pilot symbols, and its effect can be compensated for by using an equalizer for proper demodulation. Simulation results show that the proposed method is superior to conventional methods in terms of the PAPR reduction and computational complexity. It also shows that the proposed method has a trade-off between PAPR reduction and bit error rate performance.

Accurate estimation of the state-of-charge is a crucial need for the battery, which is the most important power source in electric vehicles. To achieve better estimation result, an accurate battery model with optimum parameters is required. In this paper, a gradient-free optimization technique, namely tree seed algorithm (TSA), is utilized to identify specific parameters of the battery model. In order to strengthen the search ability of TSA and obtain more quality results, the original algorithm is improved. On one hand, the DE/rand/2/bin mechanism is employed to maintain the colony diversity, by generating mutant individuals in each time step. On the other hand, the control parameter in the algorithm is adaptively updated during the searching process, to achieve a better balance between the exploitation and exploration capabilities. The battery state-of-charge can be estimated simultaneously by regarding it as one of the parameters. Experiments under different dynamic profiles show that the proposed method can provide reliable and accurate estimation results. The performance of conventional algorithms, such as genetic algorithm and extended Kalman filter, are also compared to demonstrate the superiority of the proposed method in terms of accuracy and robustness.

This paper improves our previously proposed semi-blind uplink interference suppression scheme for multicell multiuser massive MIMO systems by incorporating the beamspace approach. The constant modulus algorithm (CMA), a known blind adaptive array scheme, can fully exploit the degree of freedom (DoF) offered by massive antenna arrays to suppress inter-user interference (IUI) and inter-cell interference (ICI). Unfortunately, CMA wastes a lot of the benefit of DoF for null-steering even when the number of incoming signal is fewer than that of receiving antenna elements. Our new proposal introduces the beamspace method which degenerates the number of array input for CMA from element-space to beamspace. It can control DoF expended for subsequent interference suppression by CMA. Optimizing the array beamforming gain and null-steering ability, can further improve the output signal-to-interference and noise power ratio (SINR). Computer simulation confirmed that our new proposal reduced the required number of data symbols by 34.6%. In addition, the 5th percentile SINR was also improved by 14.3dB.

Machine learning algorithms are becoming more and more popular in current era. Data preprocessing especially feature selection is helpful for improving the performance of those algorithms. A new powerful feature selection algorithm is proposed. It combines the advantages of ant colony optimization and brain storm optimization which simulates the behavior of human beings. Six classical datasets and five state-of-art algorithms are used to make a comparison with our algorithm on binary classification problems. The results on accuracy, percent rate, recall rate, and F1 measures show that the developed algorithm is more excellent. Besides, it is no more complex than the compared approaches.

This study proposes a novel machine learning architecture and various learning algorithms to build-in anti-phishing services for avoiding cyber-phishing attack. For the rapid develop of information technology, hackers engage in cyber-phishing attack to steal important personal information, which draws information security concerns. The prevention of phishing website involves in various aspect, for example, user training, public awareness, fraudulent phishing, etc. However, recent phishing research has mainly focused on preventing fraudulent phishing and relied on manual identification that is inefficient for real-time detection systems. In this study, we used methods such as ANOVA, X2, and information gain to evaluate features. Then, we filtered out the unrelated features and obtained the top 28 most related features as the features to use for the training and evaluation of traditional machine learning algorithms, such as Support Vector Machine (SVM) with linear or rbf kernels, Logistic Regression (LR), Decision tree, and K-Nearest Neighbor (KNN). This research also evaluated the above algorithms with the ensemble learning concept by combining multiple classifiers, such as Adaboost, bagging, and voting. Finally, the eXtreme Gradient Boosting (XGBoost) model exhibited the best performance of 99.2%, among the algorithms considered in this study.

Affine projection sign algorithm (APSA) is an important adaptive filtering method to combat the impulsive noisy environment. However, the performance of APSA is poor, if its regularization parameter is not well chosen. We propose a variable regularization APSA (VR-APSA) approach, which adopts a gradient-based method to recursively reduce the norm of the a priori error vector. The resulting VR-APSA leverages the time correlation of both the input signal matrix and error vector to adjust the value of the regularization parameter. Simulation results confirm that our algorithm exhibits both fast convergence and small misadjustment properties.

Given a graph G=(V,E), where V and E are vertex and edge sets of G, and a subset VNT of vertices called a non-terminal set, the minimum spanning tree with a non-terminal set VNT, denoted by MSTNT, is a connected and acyclic spanning subgraph of G that contains all vertices of V with the minimum weight where each vertex in a non-terminal set is not a leaf. On general graphs, the problem of finding an MSTNT of G is NP-hard. We show that if G is a series-parallel graph then finding an MSTNT of G is linearly solvable with respect to the number of vertices.

Femtocell has been considered as a key promising technology to improve the capacity of a cellular system. However, the femtocells deployed inside a macrocell coverage are potentially suffered from excessive interference. This paper proposes a novel radio resource optimization in closed access femtocell networks based on bat algorithm. Bat algorithm is inspired by the behavior of bats in their echolocation process. While the original bat algorithm is designed to solve the complex optimization problem in continuous search space, the proposed modified bat algorithm extends the search optimization in a discrete search space which is suitable for radio resource allocation problem. The simulation results verify the convergence of the proposed optimization scheme to the global optimal solution and reveal that the proposed scheme based on modified bat algorithm facilitates the improvement of the femtocell network capacity.

This paper investigates the wireless information surveillance in a suspicious millimeter wave (mmWave) wireless communication system via the spoofing relay based proactive eavesdropping approach. Specifically, the legitimate monitor in the system acts as a relay to simultaneously eavesdrop and send spoofing signals to vary the source transmission rate. To maximize the effective eavesdropping rate, an optimization problem for both hybrid precoding design and power distribution is formulated. Since the problem is fractional and non-convex, we resort to the Dinkelbach method to equivalently reduce the original problem into a series of non-fractional problems, which is still coupling. Afterwards, based on the BCD-type method, the non-fractional problem is reduced to three subproblems with two introduced parameters. Then the GS-PDD-based algorithm is proposed to obtain the optimal solution by alternately optimizing the three subproblems and simultaneously updating the introduced parameters. Numerical results verify the effectiveness and superiority of our proposed scheme.