Multi-signatures have seen renewed interest due to their application to blockchains, e.g., BIP 340 (one of the Bitcoin improvement proposals), which has triggered the proposals of several new schemes with improved efficiency. However, many previous works have a “loose” security reduction (a large gap between the difficulty of the security assumption and breaking the scheme) or depend on strong idealized assumptions such as the algebraic group model (AGM). This makes the achieved level of security uncertain when instantiated in groups typically used in practice, and it becomes unclear for developers how secure a given scheme is for a given choice of security parameters. Thus, this leads to the question “what kind of schemes can we construct that achieves tight security based on standard assumptions?”. In this paper, we show a simple two-round tightly-secure pairing-based multi-signature scheme based on the computation Diffie-Hellman problem in the random oracle model. This proposal is the first two-round multi-signature scheme that achieves tight security based on a computational assumption and supports key aggregation. Furthermore, our scheme reduce the signature bit size by 19% compared with the shortest existing tightly-secure DDH-based multi-signature scheme. Moreover, we implemented our scheme in C++ and confirmed that it is efficient in practice; to complete the verification takes less than 1[ms] with a total (computational) signing time of 13[ms] for under 100 signers. The source code of the implementation is published as OSS.

Recently, multivariate time-series data has been generated in various environments, such as sensor networks and IoT, making anomaly detection in time-series data an essential research topic. Unsupervised learning anomaly detectors identify anomalies by training a model on normal data and producing high residuals for abnormal observations. However, a fundamental issue arises as anomalies do not consistently result in high residuals, necessitating a focus on the time-series patterns of residuals rather than individual residual sizes. In this paper, we present a novel framework comprising two serialized anomaly detectors: the first model calculates residuals as usual, while the second one evaluates the time-series pattern of the computed residuals to determine whether they are normal or abnormal. Experiments conducted on real-world time-series data demonstrate the effectiveness of our proposed framework.

Pedestrian attribute recognition (PAR) aims to recognize a series of a person's semantic attributes, e.g., age, gender, which plays an important role in video surveillance. This paper proposes a multi-correlation graph convolutional network named MCGCN for PAR, which includes a semantic graph, visual graph, and synthesis graph. We construct a semantic graph by using attribute features with semantic constraints. A graph convolution is employed, based on prior knowledge of the dataset, to learn the semantic correlation. 2D features are projected onto visual graph nodes and each node corresponds to the feature region of each attribute group. Graph convolution is then utilized to learn regional correlation. The visual graph nodes are connected to the semantic graph nodes to form a synthesis graph. In the synthesis graph, regional and semantic correlation are embedded into each other through inter-graph edges, to guide each other's learning and to update the visual and semantic graph, thereby constructing semantic and regional correlation. On this basis, we use a better loss weighting strategy, the suit_polyloss, to address the imbalance of pedestrian attribute datasets. Experiments on three benchmark datasets show that the proposed approach achieves superior recognition performance compared to existing technologies, and achieves state-of-the-art performance.

Composing choreography is challenging because it involves numerous iterative refinements. According to our video analysis and interviews, choreographers typically need to imagine dancers' movements to revise drafts on paper since testing new movements and formations with actual dancers takes time. To address this difficulty, we present an interactive group-dance simulation interface, DanceUnisoner, that assists choreographers in composing a group dance in a simulated environment. With DanceUnisoner, choreographers can arrange excerpts from solo-dance videos of dancers throughout a three-dimensional space. They can adjust various parameters related to the dancers in real time, such as each dancer's position and size and each movement's timing. To evaluate the effectiveness of the system's parametric, visual, and interactive interface, we asked seven choreographers to use it and compose group dances. Our observations, interviews, and quantitative analysis revealed their successful usage in iterative refinements and visual checking of choreography, providing insights to facilitate further computational creativity support for choreographers.

In this paper we study a recently proposed variant of the r-gathering problem. An r-gathering of customers C to facilities F is an assignment A of C to open facilities F' ⊂ F such that r or more customers are assigned to each open facility. (Each facility needs enough number of customers to open.) Given an opening cost op(f) for each f∈F, and a connecting cost co(c,f) for each pair of c∈C and f∈F, the cost of an r-gathering A is max{maxc∈C{co(c, A(c))}, maxf∈F'{op(f)}}. The r-gathering problem consists of finding an r-gathering having the minimum cost. Assume that F is a set of locations for emergency shelters, op(f) is the time needed to prepare a shelter f∈F, and co(c,f) is the time needed for a person c∈C to reach assigned shelter f=A(c)∈F. Then an r-gathering corresponds to an evacuation plan such that each open shelter serves r or more people, and the r-gathering problem consists of finding an evacuation plan minimizing the evacuation time span. However in a solution above some person may be assigned to a farther open shelter although it has a closer open shelter. It may be difficult for the person to accept such an assignment for an emergency situation. Therefore, Armon considered the problem with one more additional constraint, that is, each customer should be assigned to a closest open facility, and gave a 9-approximation polynomial-time algorithm for the problem. We have designed a simple 3-approximation algorithm for the problem. The running time is O(r|C||F|).

A user wearing a Head-Mounted Display (HMD) is likely to feel isolated when sharing virtual reality (VR) experiences with Non-HMD users in the same physical space due to not being able to see the real space outside the virtual world. This research proposes a method for an HMD user to recognize the Non-HMD users' gaze and attention via a projector attached to the HMD. In the proposed approach, the projected HMD user's view is filtered darker than default, and when Non-HMD users point controllers towards the projected view, the filter is removed from a circular area for both HMD and Non-HMD users indicating which region the Non-HMD users are viewing. We conducted two user studies showing that the Non-HMD users' gaze can be recognized with the proposed method, and investigated the preferred range for the alpha value and the size of the area for removing the filter for the HMD user.

Text-based communication, such as text chat, is commonly employed in various contexts, both professional and personal. However, it lacks the rich emotional cues present in verbal and visual forms of communication, such as facial expressions and tone of voice, making it more challenging to convey emotions and increasing the likelihood of misunderstandings. In this study, we focused on typefaces as emotional cues employed in text-based communication and investigated the influence of font design on impression formation and decision-making through two experiments. The results of the experiments revealed the relationship between Japanese typeface design and impression formation, and indicated that advice presented in a font evoking an impression of high confidence was more likely to be accepted than advice presented in a font evoking an impression of low confidence.

This study discusses the feasibility to estimate the concentration level of Japanese document workers using computer. Based on the previous findings that dual-task scenarios increase reaction time, we hypothesized that the Kana-Kanji conversion confirmation time (KKCCT) would increase due to the decrease in cognitive resources allocated to the document task, i.e. the level of concentration on the task at hand. To examine this hypothesis, we conducted a set of experiments in which sixteen participants copied Kana text by typing and concurrently converted it into Kanji under three conditions: Normal, Dual-task, and Mental-fatigue. The results suggested the feasibility that KKCCT increased when participants were less concentrated on the task due to subtask or mental fatigue. These findings imply the potential utility of using confirmation time as a measure of concentration level in Japanese document workers.

This paper proposes graph linear notations and an extension of them with regular expressions. Graph linear notations are a set of strings to represent labeled general graphs. They are extended with regular expressions to represent sets of graphs by specifying chosen parts for selections and repetitions of certain induced subgraphs. Methods for the conversion between graph linear notations and labeled general graphs are shown. The NP-completeness of the membership problem for graph regular expressions is proved.

Synthesis problems on multiplayer non-zero-sum games (MG) with multiple environment players that behave rationally are the problems to find a good strategy of the system and have been extensively studied. This paper concerns the synthesis problems on stochastic MG (SMG), where a special controller other than players, called nature, which chooses a move in its turn randomly, may exist. Two types of synthesis problems on SMG exist: cooperative rational synthesis problem (CRSP) and non-cooperative rational synthesis problem (NCRSP). The rationality of environment players is modeled by Nash equilibria, and CRSP is the problem to decide whether there exists a Nash equilibrium that gives the system a payoff not less than a given threshold. Ummels et al. studied the complexity of CRSP for various classes of objectives and strategies of players. CRSP fits the situation where the system can make a suggestion of a strategy profile (a tuple of strategies of all players) to the environment players. However, in real applications, the system may rarely have an opportunity to make suggestions to the environment, and thus CRSP is optimistic. NCRSP is the problem to decide whether there exists a strategy σ0 of the system satisfying that for every strategy profile of the environment players that forms a 0-fixed Nash equilibrium (a Nash equilibrium where the system's strategy is fixed to σ0), the system obtains a payoff not less than a given threshold. In this paper, we investigate the complexity of NCRSP for positional (i.e. pure memoryless) strategies. We consider ω-regular objectives as the model of players' objectives, and show the complexity results of the problem for several subclasses of ω-regular objectives. In particular, the problem for terminal reachability (TR) objectives is shown to be Σp2-complete.

In Variant 4 of the one-way trading game [El-Yaniv, Fiat, Karp, and Turpin, 2001], a player has one dollar at the beginning and wants to convert it to yen only by one-way conversion. The exchange rate is guaranteed to fluctuate between m and M, and only the maximum fluctuation ratio φ = M/m is informed to the player in advance. The performance of an algorithm for this game is measured by the competitive ratio. El-Yaniv et al. derived the best possible competitive ratio over all algorithms for this game. However, it seems that the behavior of the best possible algorithm itself has not been explicitly described. In this paper we reveal the behavior of the best possible algorithm by solving a linear optimization problem. The behavior turns out to be quite different from that of the best possible algorithm for Variant 2 in which the player knows m and M in advance.

Software development companies must consider employees' job satisfaction and turnover intentions. To explain the related factors, this study focused on future perspective index (FPI). FPI was assumed to relate positively to satisfaction and negatively to turnover. In the analysis, we compared the FPI with existing factors that are considered to be related to job satisfaction. We discovered that the FPI was promising for enhancing explanatory power, particularly when analyzing satisfaction.

Code search is a task to retrieve the most relevant code given a natural language query. Several recent studies proposed deep learning based methods use multi-encoder model to parse code into multi-field to represent code. These methods enhance the performance of the model by distinguish between similar codes and utilizing a relation matrix to bridge the code and query. However, these models require more computational resources and parameters than single-encoder models. Furthermore, utilizing the relation matrix that solely relies on max-pooling disregards the delivery of word alignment information. To alleviate these problems, we propose a combined alignment model for code search. We concatenate the multi-code fields into one sequence to represent code and use one encoding model to encode code features. Moreover, we transform the relation matrix using trainable vectors to avoid information losses. Then, we combine intra-modal and cross-modal attention to assign the salient words while matching the corresponding code and query. Finally, we apply the attention weight to code/query embedding and compute the cosine similarity. To evaluate the performance of our model, we compare our model with six previous models on two popular datasets. The results show that our model achieves 0.614 and 0.687 Top@1 performance, outperforming the best comparison models by 12.2% and 9.3%, respectively.

The Linux kernel has been applied in various security-sensitive fields, so ensuring its security is crucial. Vulnerabilities in the Linux kernel are usually caused by undefined behaviors of the C programming language, the most threatening of which are memory safety vulnerabilities. Both the software-based and hardware approaches to memory safety have disadvantages of poor performance, false positives, and poor compatibility. This paper explores the feasibility of using the safe programming language Rust to reconstruct a Linux kernel component and open-source the component's code. We leverage the Rust FFI mechanism to design a safe foreign interface layer to enable the reconstructed component to invoke other Linux functionalities, and then use Rust to reconstruct the component, during which we leverage Rust's type-safety and ownership mechanisms to improve its security, and finally export the C interface of the component to enable the invocation by the Linux kernel. The performance and memory overhead of the reconstructed component, referred to as “rOOM”, were evaluated, revealing a performance overhead of 8.9% in kernel mode, 5% in user mode, 3% in real time, and a memory overhead of 0.06%. These results suggest that it is possible to develop key components of the Linux kernel using Rust in terms of functionality, performance, and memory overhead.

This paper presents the design of a capacitive coupler for underwater wireless power transfer focused on the landing direction of a drone. The main design feature is the relative position of power feeding/receiving points on the coupler electrodes, which depends on the landing direction of the drone. First, the maximum power transfer efficiencies of coupled lines with different feeding positions are derived in a uniform dielectric environment, such as that realized underwater. As a result, these are formulated by the coupling coefficient of the capacitive coupler, the unloaded qualify factor of dielectrics, and hyperbolic functions with complex propagation constants. The hyperbolic functions vary depending on the relative positions and whether these are identical or opposite couplers, and the efficiencies of each coupler depend on the type of water, such as seawater and tap water. The design method was demonstrated and achieved the highest efficiencies of 95.2%, 91.5%, and 85.3% in tap water at transfer distances of 20, 50, and 100 mm, respectively.

This paper proposes a non-linear overloaded MIMO detector that outperforms the conventional soft-input maximum likelihood detector (MLD) with less computational complexity. We propose iterative log-likelihood ratio (LLR) estimation and multi stage LLR estimation for the proposed detector to achieve such superior performance. While the iterative LLR estimation achieves better BER performance, the multi stage LLR estimation makes the detector less complex than the conventional soft-input maximum likelihood detector (MLD). The computer simulation reveals that the proposed detector achieves about 0.6dB better BER performance than the soft-input MLD with about half of the soft-input MLD's complexity in a 6×3 overloaded MIMO OFDM system.

This paper proposes a network design model, considering data consistency for a delay-sensitive distributed processing system. The data consistency is determined by collating the own state and the states of slave servers. If the state is mismatched with other servers, the rollback process is initiated to modify the state to guarantee data consistency. In the proposed model, the selected servers and the master-slave server pairs are determined to minimize the end-to-end delay and the delay for data consistency. We formulate the proposed model as an integer linear programming problem. We evaluate the delay performance and computation time. We evaluate the proposed model in two network models with two, three, and four slave servers. The proposed model reduces the delay for data consistency by up to 31 percent compared to that of a typical model that collates the status of all servers at one master server. The computation time is a few seconds, which is an acceptable time for network design before service launch. These results indicate that the proposed model is effective for delay-sensitive applications.

A circular string formed by connecting the first and the last symbols of a string is one of the simplest sequence forms, and it has been used for many applications such as data compression and fragment assembly problem. A sufficient condition on the lengths of substrings with frequencies for reconstruction of an input circular binary string is shown. However, there are no detailed descriptions on the proof of the sufficient condition and reconstruction algorithm. In this paper, we prove a necessary and sufficient condition on the lengths of substrings with frequencies for reconstruction of the circular string. We show the length is shorter than that of previous study for some circular strings. For improving the length, we use minimal absent words (MAWs) for given substrings of length k, and we propose a new construction algorithm of MAWs of length h(>k) while a conventional construction algorithm of MAWs can construct MAWs of length l(≤k). Moreover, we propose reconstruction algorithm of an input circular string for given substrings satisfying the new condition.

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

Facial Beauty Prediction (FBP) is a significant pattern recognition task that aims to achieve consistent facial attractiveness assessment with human perception. Currently, Convolutional Neural Networks (CNNs) have become the mainstream method for FBP. The training objective of most conventional CNNs is usually to learn static convolution kernels, which, however, makes the network quite difficult to capture global attentive information, and thus usually ignores the key facial regions, e.g., eyes, and nose. To tackle this problem, we devise a new convolution manner, Dynamic Attentive Convolution (DyAttenConv), which integrates the dynamic and attention mechanism into convolution in kernel-level, with the aim of enforcing the convolution kernels adapted to each face dynamically. DyAttenConv is a plug-and-play module that can be flexibly combined with existing CNN architectures, making the acquisition of the beauty-related features more globally and attentively. Extensive ablation studies show that our method is superior to other fusion and attention mechanisms, and the comparison with other state-of-the-arts also demonstrates the effectiveness of DyAttenConv on facial beauty prediction task.