This paper deals with the problem of minimizing roundoff noise and pole sensitivity simultaneously subject to l2-scaling constraints for state-space digital filters. A novel measure for evaluating roundoff noise and pole sensitivity is proposed, and an efficient technique for minimizing this measure by jointly optimizing state-space realization and error feedback is explored, namely, the constrained optimization problem at hand is converted into an unconstrained problem and then the resultant problem is solved by employing a quasi-Newton algorithm. A numerical example is presented to demonstrate the validity and effectiveness of the proposed technique.

We consider the problem of placing arrows, which indicate the direction of each edge in directed graph drawings, without making them overlap other arrows, vertices and edges as much as possible. The following two methods have been proposed for this problem. One is an exact algorithm for the case in which the position of each arrow is restricted to some discrete points. The other is a heuristic algorithm for the case in which the arrow is allowed to move continuously on each edge. In this paper, we assume that the arrow positions are not restricted to discrete points and propose an exact algorithm for the problem of finding an arrow placement such that (a) the weighted sum of the numbers of overlaps with edges, vertices and other arrows is minimized and (b) the sum of the distances between the arrows and their edges' terminal vertices is minimized as a secondary objective. The proposed method solves this problem by reducing it to a mixed integer linear programming problem. Since this is an exponential time algorithm, we add a simple procedure as preprocessing to reduce the running time. Experimental results show that the proposed method can find a better arrow placement than the previous methods and the procedure for reducing the running time is effective.

We numerically investigate that optimal robust onion-like networks can emerge even with the constraint of surface growth in supposing a spatially embedded transportation or communication system. To be onion-like, moderately long links are necessary in the attachment through intermediations inspired from a social organization theory.

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.

Due to its simplicity and efficiency, differential evolution (DE) has gained the interest of researchers from various fields for solving global optimization problems. However, it is prone to premature convergence at local minima. To overcome this drawback, a novel hybrid dragonfly algorithm with differential evolution (Hybrid DA-DE) for solving global optimization problems is proposed. Firstly, a novel mutation operator is introduced based on the dragonfly algorithm (DA). Secondly, the scaling factor (F) is adjusted in a self-adaptive and individual-dependent way without extra parameters. The proposed algorithm combines the exploitation capability of DE and exploration capability of DA to achieve optimal global solutions. The effectiveness of this algorithm is evaluated using 30 classical benchmark functions with sixteen state-of-the-art meta-heuristic algorithms. A series of experimental results show that Hybrid DA-DE outperforms other algorithms significantly. Meanwhile, Hybrid DA-DE has the best adaptability to high-dimensional problems.

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.

Boolean functions and vectorial Boolean functions are the most important components of stream ciphers. Their cryptographic properties are crucial to the security of the underlying ciphers. And how to construct such functions with good cryptographic properties is a nice problem that worth to be investigated. In this paper, using two small nonlinear functions with t-1 resiliency, we provide a method on constructing t-resilient n variables Boolean functions with strictly almost optimal nonlinearity >2n-1-2n/2 and optimal algebraic degree n-t-1. Based on the method, we give another construction so that a large class of resilient vectorial Boolean functions can be obtained. It is shown that the vectorial Boolean functions also have strictly almost optimal nonlinearity and optimal algebraic degree.

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.

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.

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.

Boolean functions used in the filter model of stream ciphers should have balancedness, large nonlinearity, optimal algebraic immunity and high algebraic degree. Besides, one more criterion called strict avalanche criterion (SAC) can be also considered. During the last fifteen years, much work has been done to construct balanced Boolean functions with optimal algebraic immunity. However, none of them has the SAC property. In this paper, we first present a construction of balanced Boolean functions with SAC property by a slight modification of a known method for constructing Boolean functions with SAC property and consider the cryptographic properties of the constructed functions. Then we propose an infinite class of balanced functions with optimal algebraic immunity and SAC property in odd number of variables. This is the first time that such kind of functions have been constructed. The algebraic degree and nonlinearity of the functions in this class are also determined.

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.

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

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.

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.

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.

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.

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.