This paper reports on the details of the International Competition on Graph Counting Algorithms (ICGCA) held in 2023. The graph counting problem is to count the subgraphs satisfying specified constraints on a given graph. The problem belongs to #P-complete, a computationally tough class. Since many essential systems in modern society, e.g., infrastructure networks, are often represented as graphs, graph counting algorithms are a key technology to efficiently scan all the subgraphs representing the feasible states of the system. In the ICGCA, contestants were asked to count the paths on a graph under a length constraint. The benchmark set included 150 challenging instances, emphasizing graphs resembling infrastructure networks. Eleven solvers were submitted and ranked by the number of benchmarks correctly solved within a time limit. The winning solver, TLDC, was designed based on three fundamental approaches: backtracking search, dynamic programming, and model counting or #SAT (a counting version of Boolean satisfiability). Detailed analyses show that each approach has its own strengths, and one approach is unlikely to dominate the others. The codes and papers of the participating solvers are available: https://afsa.jp/icgca/.

A rectangle-of-influence drawing of a plane graph G is a straight-line planar drawing of G such that there is no vertex in the proper inside of the axis-parallel rectangle defined by the two ends of any edge. In this paper, we show that any given 5-connected plane graph G with five or more vertices on the outer face has a rectangle-of-influence drawing in an integer grid such that W + H ≤ n - 2, where n is the number of vertices in G, W is the width and H is the height of the grid.

The dispersion problem is a variant of facility location problems, that has been extensively studied. Given a polygon with n edges on a plane we want to find k points in the polygon so that the minimum pairwise Euclidean distance of the k points is maximized. We call the problem the k-dispersion problem in a polygon. Intuitively, for an island, we want to locate k drone bases far away from each other in flying distance to avoid congestion in the sky. In this paper, we give a polynomial-time approximation scheme (PTAS) for this problem when k is a constant and ε < 1 (where ε is a positive real number). Our proposed algorithm runs in O(((1/ε)² + n/ε)^k) time with 1/(1 + ε) approximation, the first PTAS developed for this problem. Additionally, we consider three variations of the dispersion problem and design a PTAS for each of them.

As a multi-receiver variant of public key encryption with keyword search (PEKS), broadcast encryption with keyword search (BEKS) has been proposed (Attrapadung et al. at ASIACRYPT 2006/Chatterjee-Mukherjee at INDOCRYPT 2018). Unlike broadcast encryption, no receiver anonymity is considered because the test algorithm takes a set of receivers as input and thus a set of receivers needs to be contained in a ciphertext. In this paper, we propose a generic construction of BEKS from anonymous and weakly robust 3-level hierarchical identity-based encryption (HIBE). The proposed generic construction provides outsider anonymity, where an adversary is allowed to obtain secret keys of outsiders who do not belong to the challenge sets, and provides sublinear-size ciphertext in terms of the number of receivers. Moreover, the proposed construction considers security against chosen-ciphertext attack (CCA) where an adversary is allowed to access a test oracle in the searchable encryption context. The proposed generic construction can be seen as an extension to the Fazio-Perera generic construction of anonymous broadcast encryption (PKC 2012) from anonymous and weakly robust identity-based encryption (IBE) and the Boneh et al. generic construction of PEKS (EUROCRYPT 2004) from anonymous IBE. We run the Fazio-Perera construction employs on the first-level identity and run the Boneh et al. generic construction on the second-level identity, i.e., a keyword is regarded as a second-level identity. The third-level identity is used for providing CCA security by employing one-time signatures. We also introduce weak robustness in the HIBE setting, and demonstrate that the Abdalla et al. generic transformation (TCC 2010/JoC 2018) for providing weak robustness to IBE works for HIBE with an appropriate parameter setting. We also explicitly introduce attractive concrete instantiations of the proposed generic construction from pairings and lattices, respectively.

In 2005, Nandi introduced a class of double-block-length compression functions h^π(x) := (h(x), h(π(x))), where h is a random oracle with an n-bit output and π is a non-cryptographic public permutation. Nandi demonstrated that the collision resistance of h^π is optimal if π has no fixed point in the classical setting. Our study explores the collision resistance of h^π and the Merkle-Damgård hash function using h^π in the quantum random oracle model. Firstly, we reveal that the quantum collision resistance of h^π may not be optimal even if π has no fixed point. If π is an involution, then a colliding pair of inputs can be found for h^π with only O(2^n/2) queries by the Grover search. Secondly, we present a sufficient condition on π for the optimal quantum collision resistance of h^π. This condition states that any collision attack needs Ω(2^2n/3) queries to find a colliding pair of inputs. The proof uses the recent technique of Zhandry’s compressed oracle. Thirdly, we show that the quantum collision resistance of the Merkle-Damgård hash function using h^π can be optimal even if π is an involution. Finally, we discuss the quantum collision resistance of double-block-length compression functions using a block cipher.

Choco Banana is one of Nikoli’s pencil puzzles. We study the computational complexity of Choco Banana. It is shown that deciding whether a given instance of the Choco Banana puzzle has a solution is NP-complete.

Latin squares are a classical and well-studied topic of discrete mathematics, and recently Takeuti and Adachi (IACR ePrint, 2023) proposed (2, n)-threshold secret sharing based on mutually orthogonal Latin squares (MOLS). Hence efficient constructions of as large sets of MOLS as possible are also important from practical viewpoints. In this letter, we determine the maximum number of MOLS among a known class of Latin squares defined by weighted sums. We also mention some known property of Latin squares interpreted via the relation to secret sharing and a connection of Takeuti-Adachi’s scheme to Shamir’s secret sharing scheme.

Images with rich color information are an important source of information that people obtain from the objective world. Occasionally, it is difficult for people with red-green color vision deficiencies to obtain color information from color images. We propose a method of color correction for dichromats based on the physiological characteristics of dichromats, considering hue information. First, the hue loss of color pairs under normal color vision was defined, an objective function was constructed on its basis, and the resultant image was obtained by minimizing it. Finally, the effectiveness of the proposed method is verified through comparison tests. Red-green color vision deficient people fail to distinguish between partial red and green colors. When the red and green connecting lines are parallel to the a* axis of CIE L*a*b*, red and green perception defectives cannot distinguish the color pair, but can distinguish the color pair parallel to the b* axis. Therefore, when two colors are parallel to the a* axis, their color correction yields good results. When color correction is performed on a color, the hue loss between the two colors under normal color vision is supplemented with b* so that red-green color vision-deficient individuals can distinguish the color difference between the color pairs. The magnitude of the correction is greatest when the connecting lines of the color pairs are parallel to the a* axis, and no color correction is applied when the connecting lines are parallel to the b* axis. The objective evaluation results show that the method achieves a higher score, indicating that the proposed method can maintain the naturalness of the image while reducing confusing colors.

Minutiae pattern extraction plays a crucial role in fingerprint registration and identification for electronic applications. However, the extraction accuracy is seriously compromised by the presence of contaminated ridge lines and complex background scenarios. General image processing-based methods, which rely on many prior hypotheses, fail to effectively handle minutiae extraction in complex scenarios. Previous works have shown that CNN-based methods can perform well in object detection tasks. However, the deep neural networks (DNNs)-based methods are restricted by the limitation of public labeled datasets due to legitimate privacy concerns. To address these challenges comprehensively, this paper presents a fully automated minutiae extraction method leveraging DNNs. Firstly, we create a fingerprint minutiae dataset using a semi-automated minutiae annotation algorithm. Subsequently, we propose a minutiae extraction model based on Residual Networks (Resnet) that enables end-to-end prediction of minutiae. Moreover, we introduce a novel non-maximal suppression (NMS) procedure, guided by the Generalized Intersection over Union (GIoU) metric, during the inference phase to effectively handle outliers. Experimental evaluations conducted on the NIST SD4 and FVC 2004 databases demonstrate the superiority of the proposed method over existing state-of-the-art minutiae extraction approaches.

Multi-object tracking (MOT) algorithms are typically classified as one-shot or two-step algorithms. The one-shot MOT algorithm is widely studied and applied due to its fast inference speed. However, one-shot algorithms include two sub-tasks of detection and re-ID, which have conflicting directions for model optimization, thus limiting tracking performance. Additionally, MOT algorithms often suffer from serious ID switching issues, which can negatively affect the tracking effect. To address these challenges, this study proposes the DETrack algorithm, which consists of feature decomposition and feature enhancement modules. The feature decomposition module can effectively exploit the differences and correlations of different tasks to solve the conflict problem. Moreover, it can effectively mitigate the competition between the detection and re-ID tasks, while simultaneously enhancing their cooperation. The feature enhancement module can improve feature quality and alleviate the problem of target ID switching. Experimental results demonstrate that DETrack has achieved improvements in multi-object tracking performance, while reducing the number of ID switching. The designed method of feature decomposition and feature enhancement can significantly enhance target tracking effectiveness.

Radar emitter identification (REI) is a crucial function of electronic radar warfare support systems. The challenge emphasizes identifying and locating unique transmitters, avoiding potential threats, and preparing countermeasures. Due to the remarkable effectiveness of deep learning (DL) in uncovering latent features within data and performing classifications, deep neural networks (DNNs) have seen widespread application in radar emitter identification (REI). In many real-world scenarios, obtaining a large number of annotated radar transmitter samples for training identification models is essential yet challenging. Given the issues of insufficient labeled datasets and abundant unlabeled training datasets, we propose a novel REI method based on a semi-supervised learning (SSL) framework with virtual adversarial training (VAT). Specifically, two objective functions are designed to extract the semantic features of radar signals: computing cross-entropy loss for labeled samples and virtual adversarial training loss for all samples. Additionally, a pseudo-labeling approach is employed for unlabeled samples. The proposed VAT-based SS-REI method is evaluated on a radar dataset. Simulation results indicate that the proposed VAT-based SS-REI method outperforms the latest SS-REI method in recognition performance.

The rapid advancement of cloud-edge-end collaboration offers a feasible solution to realize low-delay and low-energy-consumption data processing for internet of things (IoT)-based smart distribution grid. The major concern of cloud-edge-end collaboration lies on resource management. However, the joint optimization of heterogeneous resources involves multiple timescales, and the optimization decisions of different timescales are intertwined. In addition, burst electromagnetic interference will affect the channel environment of the distribution grid, leading to inaccuracies in optimization decisions, which can result in negative influences such as slow convergence and strong fluctuations. Hence, we propose a cloud-edge-end collaborative multi-timescale multi-service resource management algorithm. Large-timescale device scheduling is optimized by sliding window pricing matching, which enables accurate matching estimation and effective conflict elimination. Small-timescale compression level selection and power control are jointly optimized by disturbance-robust upper confidence bound (UCB), which perceives the presence of electromagnetic interference and adjusts exploration tendency for convergence improvement. Simulation outcomes illustrate the excellent performance of the proposed algorithm.

This paper reports a spatial extrapolation of the sound field with a physics-informed neural network. We investigate the spatial extrapolation of the room impulse responses with physics-informed SIREN architecture. Furthermore, we proposed a noise-robust extrapolation method by introducing a tolerance term to the loss function.

We propose a pre-T event-triggered controller (ETC) for the stabilization of a chain of integrators. Our per-T event-triggered controller is a modified event-triggered controller by adding a pre-defined positive constant T to the event-triggering condition. With this pre-T, the immediate advantages are (i) the often complicated additional analysis regarding the Zeno behavior is no longer needed, (ii) the positive lower bound of interexecution times can be specified, (iii) the number of control input updates can be further reduced. We carry out the rigorous system analysis and simulations to illustrate the advantages of our proposed method over the traditional event-triggered control method.

This study explores adaptive output feedback leader-following in networks of linear systems utilizing switching logic. A local state observer is employed to estimate the true state of each agent within the network. The proposed protocol is based on the estimated states obtained from neighboring agents and employs a switching logic to tune its adaptive gain by utilizing only local neighboring information. The proposed leader-following protocol is fully distributed because it has a distributed adaptive gain and relies on only local information from its neighbors. Consequently, compared to conventional adaptive protocols, the proposed design method provides the advantages of a very simple adaptive law and dynamics with a low dimension.

In this letter, we give a characterization for a generic construction of bent functions. This characterization enables us to obtain another efficient construction of bent functions and to give a positive answer on a problem of bent functions.

This letter proposes a scheme for the backward transmission of the propagation-delay based three-user X channel, which is reciprocal to the forward transmission. The given scheme successfully delivers 10 expected messages in 6 time-slots by cyclic interference alignment without loss of degrees of freedom, which supports efficient bidirectional transmission between the two ends of the three-user X channel.

A novel temporal convolution network-gated recurrent unit (NTCN-GRU) algorithm is proposed for the greatest of constant false alarm rate (GO-CFAR) frequency hopping (FH) prediction, integrating GRU and Bayesian optimization (BO). GRU efficiently captures the semantic associations among long FH sequences, and mitigates the phenomenon of gradient vanishing or explosion. BO improves extracting data features by optimizing hyperparameters besides. Simulations demonstrate that the proposed algorithm effectively reduces the loss in the training process, greatly improves the FH prediction effect, and outperforms the existing FH sequence prediction model. The model runtime is also reduced by three-quarters compared with others FH sequence prediction models.