Metabolic networks represent the relationship between chemical reactions and compounds in cells. In useful metabolite production using microorganisms, it is often required to calculate reaction deletion strategies from the original network to result in growth coupling, which means the target metabolite production and cell growth are simultaneously achieved. Although simple elementary flux mode (EFM)-based methods are useful for listing such reaction deletions strategies, the number of cases to be considered is often proportional to the exponential function of the size of the network. Therefore, it is desirable to develop methods of narrowing down the number of reaction deletion strategy candidates. In this study, the author introduces the idea of L1 norm minimal modes to consider metabolic flows whose L1 norms are minimal to satisfy certain criteria on growth and production, and developed a fast metabolic design listing algorithm based on it (minL1-FMDL), which works in polynomial time. Computational experiments were conducted for (1) a relatively small network to compare the performance of minL1-FMDL with that of the simple EFM-based method and (2) a genome-scale network to verify the scalability of minL1-FMDL. In the computational experiments, it was seen that the average value of the target metabolite production rates of minL1-FMDL was higher than that of the simple EFM-based method, and the computation time of minL1-FMDL was fast enough even for genome-scale networks. The developed software, minL1-FMDL, implemented in MATLAB, is available on https://sunflower.kuicr.kyoto-u.ac.jp/~tamura/software, and can be used for genome-scale metabolic network design for metabolite production.

Scalable networking for scientific research data transfer is a vital factor in the progress of data-intensive research, such as collaborative research on observation of black hole. In this paper, investigations of the nature of practical research traffic allow us to introduce optical flow switching (OFS) and contents delivery network (CDN) technologies into a wide area network (WAN) to realize highly scalable networking. To measure the scalability of networks, energy consumption in the WAN is evaluated by considering the practical networking equipment as well as reasonable assumptions on scientific research data transfer networks. In this study, we explore the energy consumption performance of diverse Japan and US topologies and reveal that the energy consumption of a routing and wavelength assignment algorithm in an OFS scheduler becomes the major hurdle when the number of nodes is high, for example, as high as that of the United States of America layer 1 topology. To provide computational scalability of a network dimensioning algorithm for the CDN based WAN, a simple heuristic algorithm for a surrogate location problem is proposed and compared with an optimal algorithm. This paper provides intuitions and design rules for highly scalable research data transfer networks, and thus, it can accelerate technology advancements against the encountering big-science problems.

In this paper, in order to avoid the cascading failure by increasing the number of links in the physical network in D2D-based SNS, we propose an autonomous device placement algorithm. In this method, some relay devices are placed so as to increase the number of links in the physical network. Here, relay devices can be used only for relaying data and those are not SNS users. For example, unmanned aerial vehicles (UAV) with D2D communication capability and base stations with D2D communication capability are used as the relay devices. In the proposed method, at first, an optimization problem for minimizing node resilience which is a performance metric in order to place relay devices. Then, we investigate how relay devices should be placed based on some approximate optimal solutions. From this investigation, we propose an autonomous relay device placement in the physical network. In our proposed algorithm, relay devices can be placed without the complete information on network topology. We evaluate the performance of the proposed method with simulation, and investigate the effectiveness of the proposed method. From numerical examples, we show the effectiveness of our proposed algorithm.

Approximate Simultaneous Diagonalization (ASD) is a problem to find a common similarity transformation which approximately diagonalizes a given square-matrix tuple. Many data science problems have been reduced into ASD through ingenious modelling. For ASD, the so-called Jacobi-like methods have been extensively used. However, the methods have no guarantee to suppress the magnitude of off-diagonal entries of the transformed tuple even if the given tuple has an exact common diagonalizer, i.e., the given tuple is simultaneously diagonalizable. In this paper, to establish an alternative powerful strategy for ASD, we present a novel two-step strategy, called Approximate-Then-Diagonalize-Simultaneously (ATDS) algorithm. The ATDS algorithm decomposes ASD into (Step 1) finding a simultaneously diagonalizable tuple near the given one; and (Step 2) finding a common similarity transformation which diagonalizes exactly the tuple obtained in Step 1. The proposed approach to Step 1 is realized by solving a Structured Low-Rank Approximation (SLRA) with Cadzow's algorithm. In Step 2, by exploiting the idea in the constructive proof regarding the conditions for the exact simultaneous diagonalizability, we obtain an exact common diagonalizer of the obtained tuple in Step 1 as a solution for the original ASD. Unlike the Jacobi-like methods, the ATDS algorithm has a guarantee to find an exact common diagonalizer if the given tuple happens to be simultaneously diagonalizable. Numerical experiments show that the ATDS algorithm achieves better performance than the Jacobi-like methods.

Sieve algorithms are regarded as the best algorithms to solve the shortest vector problem (SVP) on account of its good asymptotical quality, which could make it outperform enumeration algorithms in solving SVP of high dimension. However, due to its large memory requirement, sieve algorithms are not practical as expected, especially on high dimension lattice. To overcome this bottleneck, TupleSieve algorithm was proposed to reduce memory consumption by a trade-off between time and memory. In this work, aiming to make TupleSieve algorithm more practical, we combine TupleSieve algorithm with SubSieve technique and obtain a sub-exponential gain in running time. For 2-tuple sieve, 3-tuple sieve and arbitrary k-tuple sieve, when selecting projection index d appropriately, the time complexity of our algorithm is O(20.415(n-d)), O(20.566(n-d)) and $O(2^{rac{kmathrm{log}_2p}{1-k}(n-d)})$ respectively. In practice, we propose a practical variant of our algorithm based on GaussSieve algorithm. Experimental results show that our algorithm implementation is about two order of magnitude faster than FPLLL's GuassSieve algorithm. Moreover, techniques such as XOR-POPCNT trick, progressive sieving and appropriate projection index selection can be exploited to obtain a further acceleration.

The PCHS (Park-Chang-Hong-Seo) algorithm is a varied Karatsuba algorithm (KA) that utilizes a different splitting strategy with no overlap module. Such an algorithm has been applied to develop efficient hybrid GF(2m) multipliers for irreducible trinomials and pentanomials. However, compared with KA-based hybrid multipliers, these multipliers usually match space complexity but require more gates delay. In this paper, we proposed a new design of hybrid multiplier using PCHS algorithm for irreducible all-one polynomial. The proposed scheme skillfully utilizes redundant representation to combine and simplify the subexpressions computation, which result in a significant speedup of the implementation. As a main contribution, the proposed multiplier has exactly the same space and time complexities compared with the KA-based scheme. It is the first time to show that different splitting strategy for KA also can develop the same efficient multiplier.

To reduce peak-to-average power ratio, we propose a method of choosing suitable vectors in a partial transmit sequence technique. Conventional approaches require that a suitable vector be selected from a large number of candidates. By contrast, our method does not include such a selecting procedure, and instead generates random vectors from the Gaussian distribution whose covariance matrix is a solution of a relaxed problem. The suitable vector is chosen from the random vectors. This yields lower peak-to-average power ratio than a conventional method.

The performance of online algorithms for the bin packing problem is usually measured by the asymptotic approximation ratio. However, even if an online algorithm is explicitly described, it is in general difficult to obtain the exact value of the asymptotic approximation ratio. In this paper we show a theorem that gives the exact value of the asymptotic approximation ratio in a closed form when the item sizes and the online algorithm satisfy some conditions. Moreover, we demonstrate that our theorem serves as a powerful tool for the design of online algorithms combined with mathematical optimization.

This paper deals with the problem of enumerating 3-edge-connected spanning subgraphs of an input plane graph. In 2018, Yamanaka et al. proposed two enumeration algorithms for such a problem. Their algorithm generates each 2-edge-connected spanning subgraph of a given plane graph with n vertices in O(n) time, and another one generates each k-edge-connected spanning subgraph of a general graph with m edges in O(mT) time, where T is the running time to check the k-edge connectivity of a graph. This paper focuses on the case of the 3-edge-connectivity in a plane graph. We give an algorithm which generates each 3-edge-connected spanning subgraph of the input plane graph in O(n2) time. This time complexity is the same as the algorithm by Yamanaka et al., but our algorithm is simpler than theirs.

In this paper, a Proof-of-Concept (PoC) architecture is constructed, and the effectiveness of mmWave overlay heterogeneous network (HetNet) with mesh backhaul utilizing route-multiplexing and Multi-access Edge Computing (MEC) utilizing prefetching algorithm is verified by measuring the throughput and the download time of real contents. The architecture can cope with the intensive mobile data traffic since data delivery utilizes multiple backhaul routes based on the mesh topology, i.e. route-multiplexing mechanism. On the other hand, MEC deploys the network edge contents requested in advance by nearby User Equipment (UE) based on pre-registered context information such as location, destination, demand application, etc. to the network edge, which is called prefetching algorithm. Therefore, mmWave access can be fully exploited even with capacity-limited backhaul networks by introducing the proposed algorithm. These technologies solve the problems in conventional mmWave HetNet to reduce mobile data traffic on backhaul networks to cloud networks. In addition, the proposed architecture is realized by introducing wireless Software Defined Network (SDN) and Network Function Virtualization (NFV). In our architecture, the network is dynamically controlled via wide-coverage microwave band links by which UE's context information is collected for optimizing the network resources and controlling network infrastructures to establish backhaul routes and MEC servers. In this paper, we develop the hardware equipment and middleware systems, and introduce these algorithms which are used as a driver of IEEE802.11ad and open source software. For 5G and beyond, the architecture integrated in mmWave backhaul, MEC and SDN/NFV will support some scenarios and use cases.

The circuit satisfiability problem has been intensively studied since Ryan Williams showed a connection between the problem and lower bounds for circuit complexity. In this letter, we present a #SAT algorithm for synchronous Boolean circuits of n inputs and s gates in time $2^{nleft(1 - rac{1}{2^{O(s/n)}} ight)}$ if s=o(n log n).

Shape matching with local descriptors is an underlying scheme in shape analysis. We can visually confirm the matching results and also assess them for shape classification. Generally, shape matching is implemented by determining the correspondence between shapes that are represented by their respective sets of sampled points. Some matching methods have already been proposed; the main difference between them lies in their choice of matching cost function. This function measures the dissimilarity between the local distribution of sampled points around a focusing point of one shape and the local distribution of sampled points around a referring point of another shape. A local descriptor is used to describe the distribution of sampled points around the point of the shape. In this paper, we propose an extended scheme for shape matching that can compensate for errors in existing local descriptors. It is convenient for local descriptors to adopt our scheme because it does not require the local descriptors to be modified. The main idea of our scheme is to consider the correspondence of neighboring sampled points to a focusing point when determining the correspondence of the focusing point. This is useful because it increases the chance of finding a suitable correspondence. However, considering the correspondence of neighboring points causes a problem regarding computational feasibility, because there is a substantial increase in the number of possible correspondences that need to be considered in shape matching. We solve this problem using a branch-and-bound algorithm, for efficient approximation. Using several shape datasets, we demonstrate that our scheme yields a more suitable matching than the conventional scheme that does not consider the correspondence of neighboring sampled points, even though our scheme requires only a small increase in execution time.

In this paper, we clarify the importance of performance evaluation using a plurality of smartphones in a positioning system based on radio waves. Specifically, in a positioning system using bluetooth low energy, the positioning performance of two types of positioning algorithms is performed using a plurality of smartphones. As a result, we confirmed that the fingerprint algorithm does not always provide sufficient positioning performance. It depends on the model of the smartphone used. On the other hand, the hybrid algorithm that the authors have already proposed is robust in the difference of the received signal characteristics of the smartphone. Consequently, we spotlighted that the use of multiple devices is essential for providing high-quality location-based services in real environments in the performance evaluation of radio wave-based positioning systems using smartphones.

Diffusion least-mean-square (LMS) is a method to estimate and track an unknown parameter at multiple nodes in a network. When the unknown vector has sparsity, the sparse promoting version of diffusion LMS, which utilizes a sparse regularization term in the cost function, is known to show better convergence performance than that of the original diffusion LMS. This paper proposes a novel choice of the coefficients involved in the updates of sparse diffusion LMS using the idea of message propagation. Moreover, we optimize the proposed coefficients with respect to mean-square-deviation at the steady-state. Simulation results demonstrate that the proposed method outperforms conventional methods in terms of the convergence performance.

This paper expands our previously proposed semi-blind uplink interference suppression scheme for multicell multiuser massive MIMO systems to support multi modulus signals. The original proposal applies the channel state information (CSI) aided blind adaptive array (BAA) interference suppression after the beamspace preprocessing and the decision feedback channel estimation (DFCE). BAA is based on the constant modulus algorithm (CMA) which can fully exploit the degree of freedom (DoF) of massive antenna arrays to suppress both inter-user interference (IUI) and inter-cell interference (ICI). Its effectiveness has been verified under the extensive pilot contamination constraint. Unfortunately, CMA basically works well only for constant envelope signals such as QPSK and thus the proposed scheme should be expanded to cover QAM signals for more general use. This paper proposes to apply the multi modulus algorithm (MMA) and the minimum mean square error weight derivation based on data-aided sample matrix inversion (MMSE-SMI). It can successfully realize interference suppression even with the use of multi-level envelope signals such as 16QAM with satisfactorily outage probability performance below the fifth percentile.

In this paper, we investigate the subcarriers combination selection and the subcarriers activation of OFDM-IM system. Firstly, we propose an algorithm to solve the problem of subcarriers combination selection based on the transmission rate and diversity gain. Secondly, we ropose a more concise algorithm to solve the problem of power allocation and carrier combination activation probability under this combination to improve system capacity. Finally, we verify the robustness of the algorithm and the superiority of the system scheme in the block error rate (BLER) and system capacity by numerical results.

Multivariate public key cryptosystem (MPKC) is one of the major post quantum cryptosystems (PQC), and the National Institute of Standards and Technology (NIST) recently selected four MPKCs as candidates of their PQC. The security of MPKC depends on the hardness of solving systems of algebraic equations over finite fields. In particular, the multivariate quadratic (MQ) problem is that of solving such a system consisting of quadratic polynomials and is regarded as an important research subject in cryptography. In the Fukuoka MQ challenge project, the hardness of the MQ problem is discussed, and algorithms for solving the MQ problem and the computational results obtained by these algorithms are reported. Algorithms for computing Gröbner basis are used as the main tools for solving the MQ problem. For example, the F4 algorithm and M4GB algorithm have succeeded in solving many instances of the MQ problem provided by the project. In this paper, based on the F4-style algorithm, we present an efficient algorithm to solve the MQ problems with dense polynomials generated in the Fukuoka MQ challenge project. We experimentally show that our algorithm requires less computational time and memory for these MQ problems than the F4 algorithm and M4GB algorithm. We succeeded in solving Type II and III problems of Fukuoka MQ challenge using our algorithm when the number of variables was 37 in both problems.

Multiscale retinex is one of the most popular image enhancement methods. However, its control parameters, such as Gaussian kernel sizes, gain, and offset, should be tuned carefully according to the image contents. In this letter, we propose a new method that optimizes the parameters using practical swarm optimization and multi-objective function. The method iteratively verifies the visual quality (i.e. brightness, contrast, and colorfulness) of the enhanced image using a multi-objective function while subtly adjusting the parameters. Experimental results shows that the proposed method achieves better image quality qualitatively and quantitatively compared with other image enhancement methods.

Random network topologies have been proposed as a low-latency network for parallel computers. Although multicast is a common collective-communication operation, multicast algorithms each of which consists of a large number of unicasts are not well optimized for random network topologies. In this study, we firstly apply a two-opt algorithm for building efficient multicast on random network topologies. The two-opt algorithm creates a skilled ordered list of visiting nodes to minimize the total path hops or the total possible contention counts of unicasts that form the target multicast. We secondly extend to apply the two-opt algorithm for the other collective-communication operations, e.g., allreduce and allgather. The SimGrid discrete-event simulation results show that the two-opt multicast outperforms that in typical MPI implementation by up to 22% of the execution time of an MPI program that repeats the MPI_Bcast function. The two-opt allreduce and the two-opt allgather operations also improve by up to 15% and 14% the execution time when compared to those used in typical MPI implementations, respectively.

In this paper we analyze the interval algorithm for random number generation proposed by Han and Hoshi in the case of Markov coin tossing. Using the expression of real numbers on the interval [0,1), we first establish an explicit representation of the interval algorithm with the representation of real numbers on the interval [0,1) based one number systems. Next, using the expression of the interval algorithm, we give a rigorous analysis of the interval algorithm. We discuss the difference between the expected number of the coin tosses in the interval algorithm and their upper bound derived by Han and Hoshi and show that it can be characterized explicitly with the established expression of the interval algorithm.