Previously, we proposed a probabilistic data generation model represented by an unobservable tree and a sequential updating method to calculate a posterior distribution over a set of trees. The set is called a meta-tree. In this paper, we propose a more efficient batch updating method.

The context tree model has the property that the occurrence probability of symbols is determined from a finite past sequence and is a broader class of sources that includes i.i.d. or Markov sources. This paper proposes a non-stationary source with context tree models that change from interval to interval. The Bayes code for this source requires weighting of the posterior probabilities of the context tree models and change points, so the computational complexity of it usually increases to exponential order. Therefore, the challenge is how to reduce the computational complexity. In this paper, we propose a special class of prior probability distribution of context tree models and change points and develop an efficient Bayes coding algorithm by combining two existing Bayes coding algorithms. The algorithm minimizes the Bayes risk function of the proposed source in this paper, and the computational complexity of the proposed algorithm is polynomial order. We investigate the behavior and performance of the proposed algorithm by conducting experiments.

In this letter, we present a new lower bound for the treewidth of a graph in terms of the second smallest eigenvalue of its Laplacian matrix. Our bound slightly improves the lower bound given by Chandran and Subramanian [Inf. Process. Lett., 87 (2003)].

In this paper, we explore privacy-preserving techniques in federated learning, including those can be used with both neural networks and decision trees. We begin by identifying how information can be leaked in federated learning, after which we present methods to address this issue by introducing two privacy-preserving frameworks that encompass many existing privacy-preserving federated learning (PPFL) systems. Through experiments with publicly available financial, medical, and Internet of Things datasets, we demonstrate the effectiveness of privacy-preserving federated learning and its potential to develop highly accurate, secure, and privacy-preserving machine learning systems in real-world scenarios. The findings highlight the importance of considering privacy in the design and implementation of federated learning systems and suggest that privacy-preserving techniques are essential in enabling the development of effective and practical machine learning systems.

Technological devices have become deeply embedded in people's lives, and their demand is growing every year. It has been indicated that outsourcing the design and manufacturing of integrated circuits, which are essential for technological devices, may lead to the insertion of malicious circuitry, called hardware Trojans (HTs). This paper proposes an HT detection method at gate-level netlists based on XGBoost, one of the best gradient boosting decision tree models. We first propose the optimal set of HT features among many feature candidates at a netlist level through thorough evaluations. Then, we construct an XGBoost-based HT detection method with its optimized hyperparameters. Evaluation experiments were conducted on the netlists from Trust-HUB benchmarks and showed the average F-measure of 0.842 using the proposed method. Also, we newly propose a Trojan probability propagation method that effectively corrects the HT detection results and apply it to the results obtained by XGBoost-based HT detection. Evaluation experiments showed that the average F-measure is improved to 0.861. This value is 0.194 points higher than that of the existing best method proposed so far.

The existing literature focuses on the applications of fast filter bank due to its excellent frequency responses with low complexity. However, the topic is not addressed related to the general transfer function expressions of the corresponding subfilters for a specific channel. To do this, in this paper, general closed-form transfer function expressions for fast filter bank are derived. Firstly, the cascaded structure of fast filter bank is modelled by a binary tree, with which the index of the subfilter at each stage within the channel can be determined. Then the transfer functions for the two outputs of a subfilter are expressed in a unified form. Finally, the general closed-form transfer functions for the channel and its corresponding subfilters are obtained by variables replacement if the prototype lowpass filters for the stages are given. Analytical results and simulations verify the general expressions. With such closed-form expressions lend themselves easily to analysis and direct computation of the transfer functions and the frequency responses without the structure graph.

The latest versatile video coding (VVC) introduces some novel techniques such as quadtree with nested multi-type tree (QTMT), multiple transform selection (MTS) and multiple reference line (MRL). These tools improve compression efficiency compared with the previous standard H.265/HEVC, but they suffer from very high computational complexity. One of the most time-consuming parts of VVC intra coding is the coding tree unit (CTU) structure decision. In this paper, we propose a low-complexity multi-type tree (MT) pruning method for VVC intra coding. This method consists of lookahead search and MT pruning. The lookahead search process is performed to derive the approximate rate-distortion (RD) cost of each MT node at depth 2 or 3. Subsequently, the improbable MT nodes are pruned by different strategies under different cost errors. These strategies are designed according to the priority of the node. Experimental results show that the overall proposed algorithm can achieve 47.15% time saving with only 0.93% Bjøntegaard delta bit rate (BDBR) increase over natural scene sequences, and 45.39% time saving with 1.55% BDBR increase over screen content sequences, compared with the VVC reference software VTM 10.0. Such results demonstrate that our method achieves a good trade-off between computational complexity and compression quality compared to recent methods.

Register automaton (RA), register context-free grammar (RCFG) and register tree automaton (RTA) are computational models with registers which deal with data values. This paper shows pumping lemmas for the classes of languages expressed by RA, RCFG and RTA. Among them, the first lemma was already proved in terms of nominal automata, which is an abstraction of RA. We define RTA in a deterministic and bottom-up manner. For these languages, the notion of ‘pumped word’ must be relaxed in such a way that a pumped subword is not always the same as the original subword, but is any word equivalent to the original subword in terms of data type defined in this paper. By using the lemmas, we give examples of languages that do not belong to the above-mentioned classes of languages.

On an overlay network where a number of nodes work autonomously in a decentralized way, the efficiency of broadcasts has a significant impact on the performance of distributed systems built on the network. While a broadcast method using a spanning tree produces a small number of messages, the routing path lengths are prone to be relatively large. Moreover, when multiple nodes can be source nodes, inefficient broadcasts often occur because the efficient tree topology differs for each node. To address this problem, we propose a novel protocol in which a source node selects an efficient tree from multiple spanning trees when broadcasting. Our method shortens routing paths while maintaining a small number of messages. We examined path lengths and the number of messages for broadcasts on various topologies. As a result, especially for a random graph, our proposed method shortened path lengths by approximately 28% compared with a method using a spanning tree, with almost the same number of messages.

Multiparty computation (MPC) is a cryptographic method that enables a set of parties to compute an arbitrary joint function of the private inputs of all parties and does not reveal any information other than the output. MPC based on a secret sharing scheme (SS-MPC) and garbled circuit (GC) is known as the most common MPC schemes. Another cryptographic method, homomorphic encryption (HE), computes an arbitrary function represented as a circuit by using ciphertexts without decrypting them. These technologies are in a trade-off relationship for the communication/round complexities, and the computation cost. The private decision tree evaluation (PDTE) is one of the key applications of these technologies. There exist several constant-round PDTE protocols based on GC, HE, or the hybrid schemes that are secure even if a malicious adversary who can deviate from protocol specifications corrupts some parties. There also exist other protocols based only on SS-MPC that are secure only if a semi-honest adversary who follows the protocol specification corrupts some parties. However, to the best of our knowledge, there are currently no constant-round PDTE protocols based only on SS-MPC that are secure against a malicious adversary. In this work, we propose a constant-round four-party PDTE protocol that achieves malicious security. Our protocol provides the PDTE securely and efficiently even when the communication environment has a large latency.

In this paper, we address the problem of finding a representation of a subtree distance, which is an extension of a tree metric. We show that a minimal representation is uniquely determined by a given subtree distance, and give an O(n2) time algorithm that finds such a representation, where n is the size of the ground set. Since a lower bound of the problem is Ω(n2), our algorithm achieves the optimal time complexity.

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, a spanning tree with a non-terminal set VNT, denoted by STNT, is a connected and acyclic spanning subgraph of G that contains all vertices of V where each vertex in a non-terminal set is not a leaf. On general graphs, the problem of finding an STNT of G is known to be NP-hard. In this paper, we show that if G is a circular-arc graph then finding an STNT of G is polynomially solvable with respect to the number of vertices.

AlphaSeq is a new paradigm to design sequencess with desired properties based on deep reinforcement learning (DRL). In this work, we propose a new metric function and a new reward function, to design an improved version of AlphaSeq. We show analytically and also through numerical simulations that the proposed algorithm can discover sequence sets with preferable properties faster than that of the previous algorithm.

Real-time and scalable multicast services are of paramount importance to Industrial Internet of Things (IIoT) applications. To realize these services, the multicast algorithm should, on the one hand, ensure the maximum delay of a multicast session not exceeding its upper delay bound. On the other hand, the algorithm should minimize session costs. As an emerging networking paradigm, Software-defined Networking (SDN) can provide a global view of the network to multicast algorithms, thereby bringing new opportunities for realizing the desired multicast services in IIoT environments. Unfortunately, existing SDN-based multicast (SDM) algorithms cannot meet the real-time and scalable requirements simultaneously. Therefore, in this paper, we focus on SDM algorithm design for IIoT environments. To be specific, the paper first converts the multicast tree construction problem for SDM in IIoT environments into a delay-bounded least-cost shared tree problem and proves that it is an NP-complete problem. Then, the paper puts forward a shared tree (ST) algorithm called SDM4IIoT to compute suboptimal solutions to the problem. The algorithm consists of five steps: 1) construct a delay-optimal shared tree; 2) divide the tree into a set of subpaths and a subtree; 3) optimize the cost of each subpath by relaxing the delay constraint; 4) optimize the subtree cost in the same manner; 5) recombine them into a shared tree. Simulation results show that the algorithm can provide real-time support that other ST algorithms cannot. In addition, it can achieve good scalability. Its cost is only 20.56% higher than the cost-optimal ST algorithm. Furthermore, its computation time is also acceptable. The algorithm can help to realize real-time and scalable multicast services for IIoT applications.

Betweenness centrality is one of the most significant and commonly used centralities, where centrality is a notion of measuring the importance of nodes in networks. In 2001, Brandes proposed an algorithm for computing betweenness centrality efficiently, and it can compute those values for all nodes in O(nm) time for unweighted networks, where n and m denote the number of nodes and links in networks, respectively. However, even Brandes' algorithm is not fast enough for recent large-scale real-world networks, and therefore, much faster algorithms are expected. The objective of this research is to theoretically improve the efficiency of Brandes' algorithm by introducing graph decompositions, and to verify the practical effectiveness of our approaches by implementing them as computer programs and by applying them to various kinds of real-world networks. A series of computational experiments shows that our proposed algorithms run several times faster than the original Brandes' algorithm, which are guaranteed by theoretical analyses.

Multiparty computation (MPC) is the technology that computes an arbitrary function represented as a circuit without revealing input values. Typical MPC uses secret sharing (SS) schemes, garbled circuit (GC), and homomorphic encryption (HE). These cryptographic technologies have a trade-off relationship for the computation cost, communication cost, and type of computable circuit. Hence, the optimal choice depends on the computing resources, communication environment, and function related to applications. The private decision tree evaluation (PDTE) is one of the important applications of secure computation. There exist several PDTE protocols with constant communication rounds using GC, HE, and SS-MPC over the field. However, to the best of our knowledge, PDTE protocols with constant communication rounds using MPC based on SS over the ring (requiring only lower computation costs and communication complexity) are non-trivial and still missing. In this paper, we propose a PDTE protocol based on a three-party computation (3PC) protocol over the ring with one corruption. We also propose another three-party PDTE protocol over the field with one corruption that is more efficient than the naive construction.

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.

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.

This paper introduces our work on a Movie Map, which will enable users to explore a given city area using 360° videos. Visual exploration of a city is always needed. Nowadays, we are familiar with Google Street View (GSV) that is an interactive visual map. Despite the wide use of GSV, it provides sparse images of streets, which often confuses users and lowers user satisfaction. Forty years ago, a video-based interactive map was created - it is well-known as Aspen Movie Map. Movie Map uses videos instead of sparse images and seems to improve the user experience dramatically. However, Aspen Movie Map was based on analog technology with a huge effort and never built again. Thus, we renovate the Movie Map using state-of-the-art technology. We build a new Movie Map system with an interface for exploring cities. The system consists of four stages; acquisition, analysis, management, and interaction. After acquiring 360° videos along streets in target areas, the analysis of videos is almost automatic. Frames of the video are localized on the map, intersections are detected, and videos are segmented. Turning views at intersections are synthesized. By connecting the video segments following the specified movement in an area, we can watch a walking view along a street. The interface allows for easy exploration of a target area. It can also show virtual billboards in the view.

Blockchain-based voting, including liquid voting, has been extensively studied in recent years. However, it remains challenging to implement liquid voting on blockchain using Ethereum smart contract. The challenge comes from the gas limit, which is that the number of instructions for processing a ballot cannot exceed a certain amount. This restricts the application scenario with respect to algorithms whose time complexity is linear to the number of voters, i.e., O(n). As the blockchain technology can well share and reuse the resources, we study a model of liquid voting on blockchain and propose a fast algorithm, named Flash, to eliminate the restriction. The key idea behind our algorithm is to shift some on-chain process to off-chain. In detail, we first construct a Merkle tree off-chain which contains all voters' properties. Second, we use Merkle proof and interval tree to process each ballot with O(log n) on-chain time complexity. Theoretically, the algorithm can support up to 21000 voters with respect to the current gas limit on Ethereum. Experimentally, the result implies that the consumed gas fee remains at a very low level when the number of voters increases. This means our algorithm makes liquid voting on blockchain practical even for massive voters.