Search

The combination of chain-mapping and tensor-network techniques provides a powerful tool for the numerically exact simulation of open quantum systems interacting with structured environments. However, these methods suffer from a quadratic scaling with the physical simulation time, and therefore, they become challenging in the presence of multiple environments. This is particularly true when fermionic environments, well-known to be highly correlated, are considered. In this work, we first illustrate how a thermo-chemical modulation of the spectral density allows replacing the original fermionic environments with equivalent, but simpler, ones. Moreover, we show how this procedure reduces the number of chains needed to model multiple environments. We then provide a derivation of the fermionic Markovian closure construction, consisting of a small collection of damped fermionic modes undergoing a Lindblad-type dynamics and mimicking a continuum of bath modes. We describe, in particular, how the use of the Markovian closure allows for a polynomial reduction of the time complexity of chain-mapping based algorithms when long-time dynamics are needed. [ABSTRACT FROM AUTHOR]

Multivariate multipoint evaluation is the problem of evaluating a multivariate polynomial, given as a coefficient vector, simultaneously at multiple evaluation points. In this work, we show that there exists a deterministic algorithm for multivariate multipoint evaluation over any finite field \(\mathbb {F}\) that outputs the evaluations of an m-variate polynomial of degree less than d in each variable at N points in time, \(\begin{equation*} (d^m+N)^{1+o(1)}\cdot {{\sf poly}}(m,d,\log |\mathbb {F}|), \end{equation*}\) for all \(m\in \mathbb {N}\) and all sufficiently large \(d\in \mathbb {N}\). A previous work of Kedlaya and Umans (FOCS 2008 and SICOMP 2011) achieved the same time complexity when the number of variables m is at most \(d^{o(1)}\) and had left the problem of removing this condition as an open problem. A recent work of Bhargava, Ghosh, Kumar, and Mohapatra (STOC 2022) answered this question when the underlying field is not too large and has characteristic less than \(d^{o(1)}\). In this work, we remove this constraint on the number of variables over all finite fields, thereby answering the question of Kedlaya and Umans over all finite fields. Our algorithm relies on a non-trivial combination of ideas from three seemingly different previously known algorithms for multivariate multipoint evaluation, namely the algorithms of Kedlaya and Umans, that of Björklund, Kaski, and Williams (IPEC 2017 and Algorithmica 2019), and that of Bhargava, Ghosh, Kumar, and Mohapatra, together with a result of Bombieri and Vinogradov from analytic number theory about the distribution of primes in an arithmetic progression. We also present a second algorithm for multivariate multipoint evaluation that is completely elementary and, in particular, avoids the use of the Bombieri–Vinogradov theorem. However, it requires a mild assumption that the field size is bounded by an exponential tower in d of bounded height. More specifically, our second algorithm solves the multivariate multipoint evaluation problem over a finite field \(\mathbb {F}\) in time, \(\begin{equation*} (d^m+N)^{1+o(1)}\cdot {{\sf poly}}(m,d,\log |\mathbb {F}|), \end{equation*}\) for all \(m\in \mathbb {N}\) and all sufficiently large \(d\in \mathbb {N}\) , provided that the size of the finite field \(\mathbb {F}\) is at most \((\exp (\exp (\exp (\cdots (\exp (d)))))\) , where the height of this tower of exponentials is fixed. [ABSTRACT FROM AUTHOR]

Multipoint evaluation is the computational task of evaluating a polynomial given as a list of coefficients at a given set of inputs. Besides being a natural and fundamental question in computer algebra on its own, fast algorithms for this problem are also closely related to fast algorithms for other natural algebraic questions such as polynomial factorization and modular composition. And while nearly linear time algorithms have been known for the univariate instance of multipoint evaluation for close to five decades due to a work of Borodin and Moenck [7], fast algorithms for the multivariate version have been much harder to come by. In a significant improvement to the state-of-the-art for this problem, Umans [25] and Kedlaya & Umans [16] gave nearly linear time algorithms for this problem over field of small characteristic and over all finite fields, respectively, provided that the number of variables n is at most do(1) where the degree of the input polynomial in every variable is less than d. They also stated the question of designing fast algorithms for the large variable case (i.e., n x do(1)) as an open problem. In this work, we show that there is a deterministic algorithm for multivariate multipoint evaluation over a field Fq of characteristic p, which evaluates an n-variate polynomial of degree less than d in each variable on N inputs in time provided that p is at most do(1), and q is at most (exp(exp(exp(· · · (exp(d))))), where the height of this tower of exponentials is fixed. When the number of variables is large (e.g., n x do(1)), this is the first nearly linear time algorithm for this problem over any (large enough) field. Our algorithm is based on elementary algebraic ideas, and this algebraic structure naturally leads to the following two independently interesting applications: --We show that there is an algebraic data structure for univariate polynomial evaluation with nearly linear space complexity and sublinear time complexity over finite fields of small characteristic and quasipolynomially bounded size. This provides a counterexample to a conjecture of Miltersen [21] who conjectured that over small finite fields, any algebraic data structure for polynomial evaluation using polynomial space must have linear query complexity. We also show that over finite fields of small characteristic and quasipolynomially bounded size, Vandermonde matrices are not rigid enough to yield size-depth tradeoffs for linear circuits via the current quantitative bounds in Valiant's program [26]. More precisely, for every fixed prime p, we show that for every constant e > 0, and large enough n, the rank of any n × n Vandermonde matrix V over the field Fpa can be reduced to (n/exp(O(poly(e)log0.53 n))) by changing at most nT(e) entries in every row of V, provided a = poly(logn). Prior to this work, similar upper bounds on rigidity were known only for special Vandermonde matrices. For instance, the Discrete Fourier Transform matrices and Vandermonde matrices with generators in a geometric progression [9]. [ABSTRACT FROM AUTHOR]

Summary: Fault‐tolerance and self‐organization are critical properties in modern distributed systems. Self‐stabilization is a class of fault‐tolerant distributed algorithms which has the ability to recover from any kind and any finite number of transient faults and topology changes. In this article, we propose a self‐stabilizing distributed algorithm for the 1‐MIS problem under the unfair central daemon assuming the distance‐3 model. Here, in the distance‐3 model, each process can refer to the values of local variables of processes within three hops. Intuitively speaking, the 1‐MIS problem is a variant of the maximal independent set (MIS) problem with improved local optimizations. The time complexity (convergence time) of our algorithm is O(n)$$ O(n) $$ steps and the space complexity is O(logn)$$ O\left(\log n\right) $$ bits, where n$$ n $$ is the number of processes. Finally, we extend the notion of 1‐MIS to p$$ p $$‐MIS for each nonnegative integer p$$ p $$, and compare the set sizes of p$$ p $$‐MIS (p=0,1,2,...$$ p=0,1,2,\dots $$) and the maximum independent set. [ABSTRACT FROM AUTHOR]

Certificateless public key infrastructure (PKI) avoids the key escrow problem associated with identity-based PKI and has recently been widely employed in anonymous communication schemes for vehicular adhoc networks (VANETs). In existing certificateless anonymous signcryption schemes for VANETs, vulnerabilities such as potential attacks involving the substitution of pseudonyms and the forging of pseudonymous public-private key pairs exist due to the lack of "identity-key binding" and "non-linearity processing of public-private key pairs." To address this issue, we propose an improved certificateless anonymous signcryption scheme based on elliptic curve cryptography. The scheme incorporates bilinear pairing as one of the authentication mechanisms, designs pseudonym generation algorithms and public-private key pair structures, and introduces a pseudonym verification mechanism. The correctness of the scheme is proven under the random oracle model, and its security is extensively demonstrated through detailed discussions on its confidentiality, authentication, unforgeability, anonymity, and traceability. Furthermore, the time and space complexity of the scheme are calculated. By comparing with recently published certificateless signcryption schemes, it is shown that the proposed scheme offers higher security with smaller computational and communication overheads. This certificateless vehicular network signcryption algorithm provides an efficient encryption solution for anonymous communication in vehicular networks, thereby ensuring the rapid development of secure technology for intelligent connected vehicle super terminals. [ABSTRACT FROM AUTHOR]

Despite the urgent need for accurate and robust observations of microplastics in the marine environment to assess current and future environmental risks, existing procedures remain labour-intensive, especially for smaller-sized microplastics. In addition to this, microplastic analysis faces challenges due to environmental weathering, impacting the reliability of research relying on pristine plastics. This study addresses these knowledge gaps by testing the robustness of two automated analysis techniques which combine machine learning algorithms with fluorescent colouration of Nile red (NR)-stained particles. Heterogeneously shaped uncoloured microplastics of various polymers—polyethylene (PE), polyethylene terephthalate (PET), polypropylene (PP), polystyrene (PS), and polyvinyl chloride (PVC)—ranging from 100 to 1000 µm in size and weathered under semi-controlled surface and deep-sea conditions, were stained with NR and imaged using fluorescence stereomicroscopy. This study assessed and compared the accuracy of decision tree (DT) and random forest (RF) models in detecting and identifying these weathered plastics. Additionally, their analysis time and model complexity were evaluated, as well as the lower size limit (2–4 µm) and the interoperability of the approach. Decision tree and RF models were comparably accurate in detecting and identifying pristine plastic polymers (both > 90%). For the detection of weathered microplastics, both yielded sufficiently high accuracies (> 77%), although only RF models were reliable for polymer identification (> 70%), except for PET particles. The RF models showed an accuracy > 90% for particle predictions based on 12–30 pixels, which translated to microplastics sized < 10 µm. Although the RF classifier did not produce consistent results across different labs, the inherent flexibility of the method allows for its swift adaptation and optimisation, ensuring the possibility to fine-tune the method to specific research goals through customised datasets, thereby strengthening its robustness. The developed method is particularly relevant due to its ability to accurately analyse microplastics weathered under various marine conditions, as well as ecotoxicologically relevant microplastic sizes, making it highly applicable to real-world environmental samples. [ABSTRACT FROM AUTHOR]

Recent studies have shown that graph‐based clustering methods are good at processing hyperspectral images (HSIs), while falling short for large‐scale HSIs due to high time complexity. Meanwhile, the performance of these methods relies on the quality of the constructed graph with selected anchor points. More anchor points bring better clustering results for graph‐based methods. Time complexity, however, sees a considerable increase as the number of anchor points grows. Therefore, a method that can obtain efficient clustering accuracy and consumes less time is to be developed. Against this backdrop, a novel algorithm named fast spectral clustering via efficient multilayer anchor graph (FEMAG) is proposed to resolve the accuracy and time‐consuming trade‐off problem. First, FEMAG adopts superpixel principal component analysis (SuperPCA) to extract the low‐dimensional features of HSIs. Then, a multilayer anchor graph is constructed to improve the clustering performance. When constructing the similarity graph, FEMAG takes balanced K‐means‐based hierarchical K‐means (BKHK) to obtain outperforming anchor points efficiently. Extensive experiments validate that FEMAG achieves better clustering accuracy while taking less time compared to previous clustering methods. [ABSTRACT FROM AUTHOR]

Background: The maximal sensitivity for local pairwise alignment makes the Smith-Waterman algorithm a popular choice for protein sequence database search. However, its quadratic time complexity makes it compute-intensive. Unfortunately, current state-of-the-art software tools are not able to leverage the massively parallel processing capabilities of modern GPUs with close-to-peak performance. This motivates the need for more efficient implementations. Results: CUDASW++4.0 is a fast software tool for scanning protein sequence databases with the Smith-Waterman algorithm on CUDA-enabled GPUs. Our approach achieves high efficiency for dynamic programming-based alignment computation by minimizing memory accesses and instructions. We provide both efficient matrix tiling, and sequence database partitioning schemes, and exploit next generation floating point arithmetic and novel DPX instructions. This leads to close-to-peak performance on modern GPU generations (Ampere, Ada, Hopper) with throughput rates of up to 1.94 TCUPS, 5.01 TCUPS, 5.71 TCUPS on an A100, L40S, and H100, respectively. Evaluation on the Swiss-Prot, UniRef50, and TrEMBL databases shows that CUDASW++4.0 gains over an order-of-magnitude performance improvements over previous GPU-based approaches (CUDASW++3.0, ADEPT, SW#DB). In addition, our algorithm demonstrates significant speedups over top-performing CPU-based tools (BLASTP, SWIPE, SWIMM2.0), can exploit multi-GPU nodes with linear scaling, and features an impressive energy efficiency of up to 15.7 GCUPS/Watt. Conclusion: CUDASW++4.0 changes the standing of GPUs in protein sequence database search with Smith-Waterman alignment by providing close-to-peak performance on modern GPUs. It is freely available at https://github.com/asbschmidt/CUDASW4. [ABSTRACT FROM AUTHOR]

This article proposes an optimal approach of improving the dynamic stability in power system by using hybrid method based power system-stabiliser. The proposed hybrid approach is an integration of Owl Search algorithm (OSA) and Improved Grey Wolf Optimizer (IGWO); hence, it is known as OSA-IGWO method. The objective of the proposed method is to enhance the power system's dynamic stability. This notion offers a singular approach to design the sturdy Power System Stabiliser (PSS) and enhance the dynamic energy machine balance. The Modified Heffron-Phillip's version can be evolved through generator facet transformer voltage because endless bus voltage and connection are considered to lessen the complexity with computational time. An energy machine stabiliser is referred to as Modified Power System Stabiliser (MPSS) that can be evolved and incorporated with PID controller; the usage of proposed approach in a Single-Machine-Infinity Bus-System uses Modified Heffron-Phillips (MHP) version. The OSA-IGWO approach may be used to select the benefit sets of PID-MPSS. The proposed version complements the dynamic overall performance of machine via the way of means of growing the damping ratio of the energy machine below diverse running conditions. The OSA-IGWO method is done in MATLABplatform, and its performance is compared with existing methods. [ABSTRACT FROM AUTHOR]

In recent years, the occurrence of task failures are becoming prevalent in cloud computing due to various factors such as the increasing complexity of cloud environments, heterogeneity of resources, resource limitations and inadequate allocation. Task failure due to insufficient allocation poses a significant challenge in cloud computing. When tasks are not allocated effectively, they may not be completed within their deadlines which ultimately leads to failure. Hence, effective allocation strategies combined with appropriate fault tolerance measures are vital for addressing these challenges and mitigating the risk of task failures. This paper proposes a fault-tolerant task allocation algorithm (FTTA) for independent tasks with deadline through preemptive migration in heterogeneous cloud environments to reduce task failure. The proposed algorithm involves three phases: the initial phase decides the priority of tasks in the ready list to minimize the execution time and meet task deadlines, the second phase includes the selection of a suitable virtual machine with minimum execution time and the last phase assigns task on available or non-available (which may available in future) virtual machines to find the best execution time within the deadline limit. During the task allocation process, the algorithm adopts fault-tolerant strategy that includes preemptive migration if necessary which allows the migration of tasks to identify the best suitable virtual machine. An analysis of the proposed algorithm reveals that the overall time complexity is O (n log n + n m 2) where n is the number of tasks and m is the number of virtual machines. Further, the performance of the algorithm is evaluated for different sets of tasks (small to large) while varying the number of virtual machines. The experimental results demonstrate that FTTA outperforms First Come First Served (FCFS), Priority based algorithm, Shortest Job First (SJF), Dynamic Maximum Minimum (Dy max min) and RADL algorithms in terms of number of rejected tasks, makespan, speedup and efficiency. [ABSTRACT FROM AUTHOR]

Crater identification aims to match the craters of a planetary body observed in an image to the corresponding entries in a catalogue of known craters of the same body. It is a key step in crater-based navigation algorithms for planetary missions. Many crater identification methods extract descriptors from the observed craters and compare them to an index of descriptors constructed a priori from the crater catalogue. The need for viewpoint invariance motivates descriptors defined over crater tuples (e.g. , crater triads for projective invariance). However, this implies a descriptor index that grows rapidly (e.g. , cubically) with the size of the catalogue, which practically limits the spatial resolution and/or coverage of the catalogue. Another serious drawback is the sensitivity of the descriptors and the matching accuracy to noise and outliers in the crater detection result, which are inevitable due to imperfect crater detection algorithms. In this paper, we propose a novel descriptorless crater identification technique. At its core, our method solves the perspective cone alignment problem with geometric verification iteratively over the crater catalogue. We show that our simple algorithm, with time and space complexities that are linear in the catalogue size, is substantially more accurate than state-of-the-art descriptor-based methods in the presence of noise. Moreover, the availability of multi-core onboard processors raises the prospect of speeding up our method through parallelisation. • This paper introduces the first descriptor-less crater identification method. • It comprises a perspective cone alignment solver and a geometric verification scheme. • It achieves 2–3 orders of magnitude memory improvement over descriptor-based methods. • It demonstrated superior robustness against input noise and challenging conditions. [ABSTRACT FROM AUTHOR]

In this paper, the approximate parallel prefix adders with minimizing hardware and timing complexities are proposed. Moreover, an approximate multiplier based on these adders is designed. The approximate structures include two approximate Sklansky adders, one approximate Ladner-Fischer adder, and one approximate Kogge-Stone adder. The proposed adders are free from carry rippling. The main strategy for approximate design is primarily based on rearranging and deleting sub-blocks and secondary reducing the critical path delay and area in the adders. In this case, we have a trade-off between accuracy, delay, and area. The proposed approximate multiplier has a serial structure that is designed based on using one approximate parallel prefix adder. The proposed approximate adders and multiplier are compared from hardware and accuracy point of view such as gate count, delay, area delay product, error rate, mean error distance, mean relative error distance, and normalized error distance. The efficacy of proposed structures in image processing applications such as image smoothing (low-pass filter) and image multiplication is performed using MATLAB. The results show the proposed approximate structures are comparable in terms of area, delay, PSNR, and mean structural similarity index metric parameters with other works. [ABSTRACT FROM AUTHOR]

Diagnosis of depression is based on tests performed by psychiatrists and information provided by patients or their relatives. In the field of machine learning (ML), numerous models have been devised to detect depression automatically through the analysis of speech audio signals. While deep learning approaches often achieve superior classification accuracy, they are notably resource-intensive. This research introduces an innovative, multilevel hybrid feature extraction-based classification model, specifically designed for depression detection, which exhibits reduced time complexity. MODMA dataset consisting of 29 healthy and 23 Major depressive disorder audio signals was used. The constructed model architecture integrates multilevel hybrid feature extraction, iterative feature selection, and classification processes. During the Hybrid Handcrafted Feature (HHF) generation stage, a combination of textural and statistical methods was employed to extract low-level features from speech audio signals. To enhance this process for high-level feature creation, a Multilevel Discrete Wavelet Transform (MDWT) was applied. This technique produced wavelet subbands, which were then input into the hybrid feature extractor, enabling the extraction of both high and low-level features. For the selection of the most pertinent features from these extracted vectors, Iterative Neighborhood Component Analysis (INCA) was utilized. Finally, in the classification phase, a one-dimensional nearest neighbor classifier, augmented with ten-fold cross-validation, was implemented to achieve detailed, results. The HHF-based speech audio signal classification model attained excellent performance, with the 94.63 % classification accuracy. The findings validate the remarkable proficiency of the introduced HHF-based model in depression classification, underscoring its computational efficiency. • The research introduces a novel depression detection model using multilevel hybrid feature extraction from speech audio signals. • The study employs the MODMA dataset, containing audio signals from individuals with and without Major Depressive Disorder. • Advanced techniques like Hybrid Handcrafted Feature generation and Multilevel Discrete Wavelet Transform are used for effective feature extraction. • The model achieves a high classification accuracy of 94.63%, demonstrating both effectiveness and computational efficiency in depression diagnosis. [ABSTRACT FROM AUTHOR]

The geospatial domain increasingly relies on data-driven methodologies to extract actionable insights from the growing volume of available data. Despite the effectiveness of tree-based models in capturing complex relationships between features and targets, they fall short when it comes to considering spatial factors. This limitation arises from their reliance on univariate, axis-parallel splits that result in rectangular areas on a map. To address this issue and enhance both performance and interpretability, we propose a solution that introduces two novel bivariate splits: an oblique and Gaussian split designed specifically for geographic coordinates. Our innovation, called Geospatial Random Forest (geoRF), builds upon Geospatial Regression Trees (GeoTrees) to effectively incorporate geographic features and extract maximum spatial insights. Through an extensive benchmark, we show that our geoRF model outperforms traditional spatial statistical models, other spatial RF variations, machine learning and deep learning methods across a range of geospatial tasks. Furthermore, we contextualize our method's computational time complexity relative to baseline approaches. Our prediction maps illustrate that geoRF produces more robust and intuitive decision boundaries compared to conventional tree-based models. Utilizing impurity-based feature importance measures, we validate geoRF's effectiveness in highlighting the significance of geographic coordinates, especially in data sets exhibiting pronounced spatial patterns. [ABSTRACT FROM AUTHOR]

3D printing technology proves itself to be effective in the field of medical industry due to processing potential of titanium alloys. Nonetheless it also has its drawbacks, the most severe being high roughness of printed elements’ area as well as the need to remove support structures created following the printing. Mechanical processing is commonly used for said parameters being enhanced. The completion of that process, however, takes a lot of time and prevents hard-to-reach elements from being reached. The task of this article is to provide a new method of firming the print’s surface and removing load-bearing structures. To achieve this, selective laser melting (SLM) technology will be used along with bathing prints in HF/HNO3 solution, all of which are supported by ultrasound. This process will enhance the material fatigue processing while reducing the postprocessing time and complexity. [ABSTRACT FROM AUTHOR]

Meta-heuristic algorithms, especially evolutionary algorithms, have been frequently used to find near optimal solutions to combinatorial optimization problems. The evaluation of such algorithms is often conducted through comparisons with other algorithms on a set of benchmark problems. However, even if one algorithm is the best among all those compared, it still has difficulties in determining the true quality of the solutions found because the true optima are unknown, especially in dynamic environments. It would be desirable to evaluate algorithms not only relatively through comparisons with others, but also in absolute terms by estimating their quality compared to the true global optima. Unfortunately, true global optima are normally unknown or hard to find since the problems being addressed are NP-hard. In this paper, instead of using true global optima, lower bounds are derived to carry out an objective evaluation of the solution quality. In particular, the first approach capable of deriving a lower bound for dynamic capacitated arc routing problem (DCARP) instances is proposed, and two optimization algorithms for DCARP are evaluated based on such a lower bound approach. An effective graph pruning strategy is introduced to reduce the time complexity of our proposed approach. Our experiments demonstrate that our approach provides tight lower bounds for small DCARP instances. Two optimization algorithms are evaluated on a set of DCARP instances through the derived lower bounds in our experimental studies, and the results reveal that the algorithms still have room for improvement for large complex instances. [ABSTRACT FROM AUTHOR]

Self-sufficient sensors scattered over different regions of the world comprise distributed wireless sensor networks (DWSNs), which track a range of environmental and physical factors such as pressure, temperature, vibration, sound, motion, and pollution. The use of data fusion becomes essential for combining information from various sensors and system performance. In this study, we suggested the multi-class support vector machine (SDF-MCSVM) with synthetic minority over-sampling techniques (SMOTE) data fusion for wireless sensor network (WSN) performance. The dataset includes 1,334 instances of hourly averaged answers for 12 variables from an AIR quality chemical multisensor device. To create a balanced dataset, the unbalanced data was first pre-processed using the SMOTE. The grey wolf optimization (GWO) approach is then used to reduce features in an effort to improve the efficacy and efficiency of feature selection procedures. This method is applied to classify the fused feature vectors into multiple categories at once to improve classification performance in WSNs and address unbalance datasets. The result shows the proposed method reaches high precision, accuracy, F1-score, recall, and specificity. The computational complexity and processing time were decreased in the study by using the proposed method. This is great potential for accurate and timely data fusion in dispersed WSNs with the successful integration of data fusion technologies. [ABSTRACT FROM AUTHOR]

Large fingerprint databases can make the automated search process tedious and time‐consuming. Fingerprint pattern classification is a significant step in the identification system's complexity in terms of time and speed. Although several fingerprint algorithms have been developed for classification tasks, further improvements in performance and efficiency are still required. Most of the fingerprint algorithms use deep learning techniques. However, some deep learning techniques can be resource‐intensive and computationally expensive, while others can disregard the spatial relationships between the features used in classifying fingerprint patterns. This study proposes using lightweight deep learning models (i.e., MobileNet and EfficientNet‐B0) integrated with attention modules to classify fingerprint patterns. The two lightweight models are modified, yielding MobileNet+ and EfficientNet‐B0+ models. The lightweight deep learning models can help achieve optimal performance and reduce computational complexity. The attention modules focus on distinctive features for classification. Our proposed approach integrates four attention modules for fingerprint pattern classification into two lightweight deep learning models, that is, MobileNet+ and EfficientNet‐B0+. To evaluate our approach, we use two publicly available fingerprint datasets, that is, the NIST special database 301 dataset and the LivDet dataset. The evaluation results show that the EfficientNet‐B0+ model achieves the highest classification accuracy of 97% with only 854,086 training parameters. As a conclusion, we consider the training parameters small enough for the EfficientNet‐B0+ model to be deployed on low‐resource devices. [ABSTRACT FROM AUTHOR]

Linear cryptanalysis is one of the most classical cryptanalysis methods for block ciphers. Some critical techniques of the key-recovery phase are developed for enhancing linear cryptanalysis. Collard et al. improved the time complexity for last-round key-recovery attacks by using FWT. A generalized key-recovery algorithm for an arbitrary number of rounds with an associated time complexity formula is further provided by Flórez-Gutiérrez and Naya-Plasencia based on FWT in Eurocrypt 2020. However, the previous generalized algorithms are mainly applied to block ciphers with SPN structures, where the round-keys in the first and last round XORed to the state can be easily defined as outer keys. In Asiacrypt 2021, Leurent et al. applied the algorithm by Flórez-Gutiérrez et al. to Feistel structure ciphers. However, for other structures, such as NLFSR-based, the outer keys can not be directly deduced to utilize the previous algorithms. This paper extends the algorithm by Flórez-Gutiérrez et al. for more complicated structures, including but not limited to NLFSR-based, Feistel, ARX, and SPN. We also use the dependency relationships between ciphertext, plaintext and key information bits to eliminate the redundancy calculation and the improve analysis phase. We apply the algorithm with the improved analysis phase to KATAN (NLFSR-based) and SPARX (ARX). We obtain significantly improved results. The linear results we find for SPARX-128/128 beat other cryptanalytic techniques, becoming the best key recovery attacks on this cipher. The previous best linear attacks on KATAN32, KATAN48 and KATAN64 are improved by 9, 4, and 14 rounds, respectively. [ABSTRACT FROM AUTHOR]

Quantum algorithms have demonstrated extraordinary potential across numerous fields, offering significant advantages in solving practical problems. Power Quality Disturbances (PQDs) have always been a critical factor affecting the stability and safety of electrical power systems, and accurately detecting and identifying PQDs is crucial for ensuring reliable system operation. This paper explores the application of quantum algorithms in the field of power quality and proposes a novel method using Quantum Support Vector Machines (QSVM) to detect and identify PQDs, which marks the first application of QSVM in PQD analysis. The QSVM model employed involves three main stages: quantum feature mapping, quantum kernel computation, and model training. Quantum feature mapping uses quantum circuits to map classical data into a high-dimensional Hilbert space, enhancing feature separability. Quantum kernel computation calculates the inner products between features for model training. Rigorous theoretical and experimental analyses validate our approach. This method achieves a time complexity of O (N 2 log (N)) , superior to classical SVM algorithms. Simulation results show high accuracy in PQDs detection, achieving a 100% detection rate and a 96.25% accuracy rate in single PQD identification. Experimental outcomes demonstrate robustness, maintaining over 87% accuracy even with increased noise levels, confirming its effectiveness in PQDs detection and identification. [ABSTRACT FROM AUTHOR]

Currently, specialists and researchers are focusing their efforts on information security, while frequently exchanged data is increasingly vulnerable to cyberattacks and threats. They use cryptography and watermarking methods to ensure copyright ownership protection, authenticity and integrity by hiding secret data within encrypted images. Most existing watermarking schemes are unable to ensure a good balance between imperceptibility, robustness, time processing, blindness and security. To address these problems, we propose a novel blind watermarking scheme for color images based on chaotic sequence, A-start algorithm and DCT. First, we apply DCT transform on the host image to produce DCT weights. The image block sequences are then slightly updated and scrambled from the obtained DCT weights using A-start algorithm and Arnold chaotic map. Finally, the embedded bits are extracted using the same embedding steps. Optimized image block sequences result in imperceptible, secure and robust watermark bits while reducing processing time. Experimental results show that the proposed approach outperforms other similar works when it comes to imperceptibility exceeding 74 dB and execution time less than 1.5 s for both watermark embedding and extraction. It has exceptional robustness to filtering, rotation and JPEG compression attacks with normalized correlations exceeding 0.8. [ABSTRACT FROM AUTHOR]

Physical unclonable functions (PUFs) have emerged as a favorable hardware security primitive, they exploit the process variations to provide unique signatures or secret keys amidst other critical cryptographic applications. CMOS-based PUFs are the most popular type, they generate unique bit strings using process variations in semiconductor fabrication. However, most existing CMOS PUFs are found to be vulnerable to modeling attacks based on machine learning (ML) algorithms. Memristors leveraging nanotechnology fabrication processes and highly nonlinear behavior became an interesting alternative to the existing CMOS-based PUF technology, introducing cryptographic and resilient random outputs. Memristor-based PUFs are emerging due to the inherent randomness at both the memristor level due to the cycle-to-cycle (C2C) programming variation of the device and the fabrication process level such as the cross-sectional area and variations. Our study focuses on building a machine learning analysis and attack framework of tools on C u / H f O 2 - x / p + + S i memristor-based PUF (MR-PUF). Our objective is to test the resiliency of the security margins of the presented PUF using machine learning analysis tools, on-top of holistic NIST cryptographic randomness testing initially provided, to provide a high level of certainty in predicting the randomness output of the verified Memrister-based PUF. Our main contribution is a holistic study that focuses on attacking the randomness output resiliency based on building randomness predictors using Logistic Regression (LR), Support Vector Machine (SVM), Gaussian Mixture Models (GMM), K-means, K-means + + , Random Forest, XGBoost and LSTM, within efficient time, and data complexity. Our results yield low accuracy and ROC results of within 0.49 - 0.52 and 0.49 - 0.52 respectively, indicating failure in predicting random data demonstrates efficient randomness prediction resiliency of the MR-PUF. The efficient time and data complexities of these attacks illustrated in this study are yielded to be linear and quadratic resulting in attack execution time in seconds and 5032 training samples combined with 2157 testing samples to verify the randomness of PUF. [ABSTRACT FROM AUTHOR]

Min–max programming problems with addition–min constraints have been studied in the literature to model data transfer in BitTorrent-like peer-to-peer file-sharing systems. It is well known that the class of overlap functions contains various operators, including the "min" operator. The aim of this paper is to generalize the above min–max programming problem with addition–overlap function constraints. We demonstrate that this new optimization problem can be transformed into a simplified single-variable optimization problem, which makes it easier to find an optimal solution. The bisection method will be used to find this optimal solution. In addition, when the overlap function is explicitly specified, an iterative method is given to compute the optimal objective value with a polynomial time complexity. A numerical example is provided to illustrate the procedures. [ABSTRACT FROM AUTHOR]

In this paper, we study covert communications in a hybrid decode-and-forward (DF)/ amplify-and-forward (AF) relay system. The considered relay in normal operation forwards messages from a source node to a destination node in either DF or AF mode on request. Meanwhile, the source and destination nodes also attempt to secretly exchange covert messages such as confidential or sensitive information and avoid detection by the covert message detector embedded on the relay. We first establish an optimal DF/AF mode selection criterion to maximize the covert rate based on the analyses of delay-aware achievable covert rates of individual DF and AF modes. To further reduce the time complexity, we propose a low-complexity selection criterion as well for practical use. The numerical results demonstrate the covert rate gain as high as 50% and running time gain as high as 20% for particular system parameters, which verify the effectiveness of the proposed criteria. [ABSTRACT FROM AUTHOR]

In order to perform emotion prediction in music quickly and accurately, we have proposed a muscular and tall neural network architecture for music emotion classification. Specifically, during the audio pre-processing stage, we converge mel-scale frequency cepstral coefficients features and residual phase features with weighting, enabling the extraction of more comprehensive music emotion characteristics. Additionally, to enhance the accuracy of predicting musical emotion while reducing computational complexity during training phase, we consolidate Long short term memory network with Broad learning system network. We employ long short term memory structure as the feature mapping node of broad learning system structure, leveraging the advantages of both network models. This novel Neural Network architecture, called BLNN (Broad-Long Neural Network), achieves higher prediction accuracy. i.e., 66.78%, than single network models and other benchmark with/without consolidation methods. Moreover, it achieves lower time complexity than other excellent models, i.e., 169.32 s of training time and 507.69 ms of inference time, and achieves the optimal balance between efficiency and performance. In short, the extensive experimental results demonstrate that the proposed BLNN architecture effectively predicts music emotion, surpassing other models in terms of accuracy while reducing computational demands. In addition, the detailed description of the related work, along with an analysis of its advantages and disadvantages, and its future prospects, can serve as a valuable reference for future researchers. [ABSTRACT FROM AUTHOR]

Although existing in situ oceanographic data are sparse, such data still play an important role in submarine monitoring and forecasting. Considering budget limitations, an efficient spatial sampling scheme is critical to obtain data with much information from as few sampling stations as possible. This study improved existing sampling methods based on the Quadtree (QT) algorithm. In the first-phase sampling, the gradient-based QT (GQT) algorithm is recommended since it avoids the repeated calculation of variance in the Variance QT (VQT) algorithm. In addition, based on the GQT algorithm, we also propose the algorithm considering the change in variation (the GGQT algorithm) to alleviate excessive attention to the area with large changes. In second-phase sampling, QT decomposition and the greedy algorithm are combined (the BG algorithm). QT decomposition is used to divide the region into small blocks first, and then within the small blocks, the greedy algorithm is applied to sampling simultaneously. In terms of sampling efficiency, both the GQT (GGQT) algorithm and the BG algorithm are close to the constant time complexity, which is much lower than the time consumption of the VQT algorithm and the dynamic greedy (DG) algorithm and conducive to large-scale sampling tasks. At the same time, the algorithms recommend above share similar qualities with the VQT algorithm and the dynamic greedy algorithm. [ABSTRACT FROM AUTHOR]

The N-Queens problem is a fundamental challenge in combinatorial optimization, commonly used as a benchmark for assessing the efficiency of algorithms. Traditional algorithms, such as Backtracking with Forward Checking (BFC), constraint satisfaction problem (CSP) techniques, Lookahead algorithms, and heuristic-based methods, often face challenges with exponential time complexity, making them less practical for large-scale instances. This paper introduces a novel algorithm, non-sequential conflict resolution (NSCR), which improves performance over traditional algorithms through dynamic conflict resolution. The NSCR algorithm iteratively resolves conflicts among queens by adjusting their positions, aiming to optimize both time complexity and memory usage. While NSCR also operates within exponential time bounds, it demonstrates improved scalability and efficiency compared to traditional methods. A significant strength of the NSCR algorithm lies in its space complexity, which is O(n), and a time complexity that, while typically lower than traditional methods, can reach O(n3) in the worst-case scenario. This linear space complexity is highly advantageous, particularly when dealing with large problem sizes, as it ensures efficient use of memory resources. Comparative analysis with the aforementioned algorithms shows that NSCR offers superior resource management, using up to 60% less memory and reducing runtime by approximately 50%, making it an efficient option for large-scale instances of the N-Queens problem. The algorithm's performance, evaluated on problem sizes ranging from 8 to 1000 queens, highlights its ability to manage computational resources effectively, despite the inherent challenges of exponential time complexity. [ABSTRACT FROM AUTHOR]

Recent studies have shown the potential of transformer-based neural networks in increasing prediction capacity. However, classical transformers present several problems such as computational time complexity and high memory requirements, which make Long Sequence Time-Series Forecasting (LSTF) challenging. The contribution to the prediction of time series of flood events using deep learning techniques is examined, with a particular focus on evaluating the performance of the Informer model (a particular implementation of transformer architecture), which attempts to address the previous issues. The predictive capabilities of the Informer model are explored and compared to statistical methods, stochastic models and traditional deep neural networks. The accuracy, efficiency as well as the limits of the approaches are demonstrated via numerical benchmarks relating to real river streamflow applications. Using daily flow data from the River Test in England as the main case study, we conduct a rigorous evaluation of the Informer efficacy in capturing the complex temporal dependencies inherent in streamflow time series. The analysis is extended to encompass diverse time series datasets from various locations (>100) in the United Kingdom, providing insights into the generalizability of the Informer. The results highlight the superiority of the Informer model over established forecasting methods, especially regarding the LSTF problem. For a forecast horizon of 168 days, the Informer model achieves an NSE of 0.8 and maintains a MAPE below 10%, while the second-best model (LSTM) only achieves −0.63 and 25%, respectively. Furthermore, it is observed that the dependence structure of time series, as expressed by the climacogram, affects the performance of the Informer network. [ABSTRACT FROM AUTHOR]

In this study, we analyze the changes over time in the complexity and structure of words used in article titles and the connections between articles in citation networks, focusing on the topic of artificial intelligence (AI) up to 2020. By measuring unpredictability in word usage and changes in the connections between articles, we gain insights into shifts in research focus and diversity of themes. Our investigation reveals correspondence between fluctuations in word complexity and changes in the structure of citation networks, highlighting links between thematic evolution and network dynamics. This approach not only enhances our understanding of scientific progress but also may help in anticipating emerging fields and fostering innovation, providing a quantitative lens for studying scientific domains beyond AI. [ABSTRACT FROM AUTHOR]

Accurate forecasting of ship encounter positions is crucial for preventing collisions at sea. This paper presents a framework for predicting a ship's trajectory using a sparse Gaussian process. The proposed method effectively addresses the limitations of existing full Gaussian processes, specifically the significant storage requirements and time complexity associated with data training. The model is trained using Automatic Identification System (AIS) data on trajectories, with hyperparameters optimized through a genetic algorithm. Experimental analysis demonstrates that the proposed model reduces average time complexity by 61.3 s and improves average prediction error to 9.2 m compared to full Gaussian-process-based models. [ABSTRACT FROM AUTHOR]

The graph theory is one of the fundamental structures in computer science used to model various scientific and engineering problems. Many problems within the graph theory are categorized as NP-hard and NP-complete. One such problem is the minimum dominating set (MDS) problem, which seeks to identify the minimum possible subsets in a graph such that every other node in the subset is directly connected to a node in this subset. Due to its inherent complexity, developing an efficient polynomial-time method to address the MDS problem remains a significant challenge in graph theory. This paper introduces a novel algorithm that utilizes a centrality measure known as the Malatya Centrality to effectively address the MDS problem. The proposed algorithm, called the Malatya Dominating Set Algorithm (MDSA), leverages centrality values to identify dominating sets within a graph. It extends the Malatya centrality by incorporating a second-level centrality measure, which enhances the identification of dominating nodes. Through a systematic and algorithmic approach, these centrality values are employed to pinpoint the elements of the dominating set. The MDSA uniquely integrates greedy and dynamic programming strategies. At each step, the algorithm selects the most optimal (or near-optimal) node based on the centrality values (greedy approach) while updating the neighboring nodes' criteria to influence subsequent decisions (dynamic programming). The proposed algorithm demonstrates efficient performance, particularly in large-scale graphs, with time and space requirements scaling proportionally with the size of the graph and its average degree. Experimental results indicate that our algorithm outperforms existing methods, especially in terms of time complexity when applied to large datasets, showcasing its effectiveness in addressing the MDS problem. [ABSTRACT FROM AUTHOR]

At the vanguard of quantum computation and quantum machine learning, the role of convolutional operations is pivotal, serving as the linchpin of image processing techniques. Currently, various quantum convolutional circuits have been proposed, but they are all based on non-ground state encoding. Quantum convolution methods based on ground state encoding, particularly NEQR, have not yet been studied. To address the aforementioned issues, a novel quantum convolutional circuit has been designed based on arithmetic operation modules and quantum amplitude estimation modules. This circuit performs convolution operations on NEQR encoded quantum images. Furthermore, considering the limitations of existing neighborhood pixel extraction methods in quantum image processing, this quantum convolutional circuit has been utilized to design a quantum neighborhood pixel extraction circuit. Neighborhood pixels from a specified pixel in NEQR encoded quantum images are accurately extracted by this circuit, providing a novel solution. Through comparative analysis, our research results show certain advantages in time and space complexity over existing technologies. [ABSTRACT FROM AUTHOR]

Recommending products to users with intuitive explanations helps improve the system in transparency, persuasiveness, and satisfaction. Existing interpretation techniques include post hoc methods and interpretable modeling. The former category could quantitatively analyze input contribution to model prediction but has limited interpretation faithfulness, while the latter could explain model internal mechanisms but may not directly attribute model predictions to input features. In this study, we propose a novel Dual Interpretable Recommendation model called DIRECT, which integrates ideas of the two interpretation categories to inherit their advantages and avoid limitations. Specifically, DIRECT makes use of item descriptions as explainable evidence for recommendation. First, similar to the post hoc interpretation, DIRECT could attribute the prediction of a user preference score to textual words of the item descriptions. The attribution of each word is related to its sentiment polarity and word importance, where a word is important if it corresponds to an item aspect that the user is interested in. Second, to improve the interpretability of embedding space, we propose to extract high-level concepts from embeddings, where each concept corresponds to an item aspect. To learn discriminative concepts, we employ a concept bottleneck layer and maximize the coding rate reduction on word-aspect embeddings by leveraging a word–word affinity graph extracted from a pre-trained language model. In this way, DIRECT simultaneously achieves faithful attribution and usable interpretation of embedding space. We also show that DIRECT achieves linear inference time complexity regarding the length of item reviews. We conduct experiments including ablation studies on five real-world datasets. Quantitative analysis, visualizations, and case studies verify the interpretability of DIRECT. Our code is available at: https://github.com/JacksonWuxs/DIRECT. [ABSTRACT FROM AUTHOR]

Given trajectories with gaps (i.e., missing data), we investigate algorithms to identify abnormal gaps in trajectories which occur when a given moving object did not report its location, but other moving objects in the same geographic region periodically did. The problem is important due to its societal applications, such as improving maritime safety and regulatory enforcement for global security concerns, such as illegal fishing, illegal oil transfers, and trans-shipments. The problem is challenging due to the difficulty of bounding the possible locations of the moving object during a trajectory gap, and the very high computational cost of detecting gaps in such a large volume of location data. The current literature on anomalous trajectory detection assumes linear interpolation within gaps, which may not be able to detect abnormal gaps since objects within a given region may have traveled away from their shortest path. In preliminary work, we introduced an abnormal gap measure that uses a classical space-time prism model to bound an object's possible movement during the trajectory gap and provided a scalable memoized gap detection algorithm (Memo-AGD). In this article, we propose a space time-aware gap detection (STAGD) approach to leverage space-time indexing and merging of trajectory gaps. We also incorporate a dynamic region merge-based (DRM) approach to efficiently compute gap abnormality scores. We provide theoretical proofs that both algorithms are correct and complete and also provide analysis of asymptotic time complexity. Experimental results on synthetic and real-world maritime trajectory data show that the proposed approach substantially improves computation time over the baseline technique. [ABSTRACT FROM AUTHOR]

The early work of Wei et al. has shown that it is possible to do the computation in constant time for quantum search in quantum local adiabatic evolution framework if the system Hamiltonian has an extra enlarged factor proportional to the square-root of the size of the problem. Also in our prior work, we have shown that it is possible to apply a linear interpolating path in the system Hamiltonian to achieve an O(1) time complexity for a quantum global adiabatic computation. In this paper, we discuss the issues when implementing these two quantum algorithms on the quantum circuit model, and find that to our surprise, the time slices produced does not equal to the time complexity of the algorithm in each case. This is in contrast to the previous related results, because there these two quantities always coincide. When taking into account of the whole energy-level increase of the system compared with that of the usual quantum adiabatic evolutions and the corresponding time complexity simultaneously, we find that the time slices needed always consist of the two quantities multiplying together. This result is new, and may be hopeful to find application in designing quantum adiabatic algorithm for problems beyond quantum search. [ABSTRACT FROM AUTHOR]

Complex networks describe a broad range of systems in nature and society. As a fundamental concept of graph theory, the path connecting nodes and edges plays a crucial role in network science, where the computation of shortest path lengths and numbers has garnered substantial focus. It is well known that powers of the adjacency matrix can calculate the number of walks, specifying their corresponding lengths. However, developing methodologies to quantify both the number and length of shortest paths through the adjacency matrix remains a challenge. Here, we extend powers of the adjacency matrix from walks to shortest paths. We address the all-pairs shortest path count problem and propose a fast algorithm based on powers of the adjacency matrix that counts both the number and the length of all shortest paths. Numerous experiments on synthetic and real-world networks demonstrate that our algorithm is significantly faster than the classical algorithms across various network types and sizes. Moreover, we verified that the time complexity of our proposed algorithm significantly surpasses that of the current state-of-the-art algorithms. The superior property of the algorithm allows for rapid calculation of all shortest paths within large-scale networks, offering significant potential applications in traffic flow optimization and social network analysis. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the learning abilities of linear recurrent neural networks (RNNs) trained using Gradient Descent. We present a theoretical guarantee demonstrating that these linear RNNs can effectively learn any stable linear dynamical system with polynomial complexity. Importantly, our derived generalization error bound is independent of the episode length. For any stable linear system with a transition matrix C characterized by a parameter ρ C related to the spectral radius, we prove that despite the non-convexity of the parameter optimization loss, a linear RNN can learn the system with polynomial sample and time complexity in 1 1 - ρ C , provided that the RNN has sufficient width. Notably, the required width of the hidden layers does not depend on the length of the input sequence. This work provides the first rigorous theoretical foundation for learning linear RNNs. Our findings suggest that linear RNNs are capable of efficiently learning complex dynamical systems, paving the way for further research into the learning capabilities of more general RNN architectures. [ABSTRACT FROM AUTHOR]

Glaucoma represents a significant global contributor to blindness. Accurately segmenting the optic disc (OD) and optic cup (OC) to obtain precise CDR is essential for effective screening. However, existing convolutional neural network (CNN)-based segmentation techniques are often limited by high computational demands and long inference times. This paper proposes an efficient end-to-end method for OD and OC segmentation, utilizing the lightweight MobileNetv3 network as the core feature-extraction module. Our approach combines boundary branches with adversarial learning, to achieve multi-label segmentation of the OD and OC. We validated our proposed approach across three public available datasets: Drishti-GS, RIM-ONE-r3, and REFUGE. The outcomes reveal that the Dice coefficients for the segmentation of OD and OC within these datasets are 0.974/0.900, 0.966/0.875, and 0.962/0.880, respectively. Additionally, our method substantially lowers computational complexity and inference time, thereby enabling efficient and precise segmentation of the optic disc and optic cup. [ABSTRACT FROM AUTHOR]

Objectives: Three dimensional buffer analysis is a spatial analysis function widely used in geographic information systems, which is of great significance in underwater submersible terrain matching navigation, submarine engineering construction planning, submarine pollution source diffusion analysis and other bathymetric research fields. The traditional buffer surface construction algorithm has limitations in the application of triangulated irregular network digital depth model (TIN-DDM) model accuracy and modeling efficiency. Therefore, taking the rolling ball acceleration optimization model with controllable accuracy threshold as the analysis object, we propose a fast TIN-DDM buffer surface construction algorithm based on the efficient determination of key sampling points. Methods: The main research contents are as follows: (1) Based on the spatial distribution characteristic analysis of alternative point sets, through the numerical convergence analysis of the critical rolling ball radius, the trial iteration strategy of critical rolling sphere radius is designed, then a new criterion for determining key sampling points is given. (2) The spatial data block index modeling is applied to the rapid positioning of adjacent alternative points, and an efficient judgment model of key sampling points for rapid positioning of spatial index is established. Results: From the statistical results of the key data link list parameters and the actual buffer surface construction images, the proposed method can be used to build the buffer surface, and is consistent with the construction accuracy of the rolling ball accelerated optimization model. From the results of buffer surface construction time consuming of different TIN-DDM water depth data, the time consuming of this method is obviously better than that of the rolling ball accelerated optimization model. Conclusions: The experimental results show that in the face of massive TIN-DDM data, the proposed algorithm can effectively improve the construction efficiency of buffer surface on the basis of ensuring the construction accuracy of buffer surface, and reduce the time complexity of overall buffer surface construction. [ABSTRACT FROM AUTHOR]

The amortized step complexity of an implementation measures its performance as a whole, rather than the performance of individual operations. Specifically, the amortized step complexity of an implementation is the average number of steps performed by invoked operations, in the worst case, taken over all possible executions. The point contention of an execution, denoted by c ˙ , measures the maximal number of precesses simultaneously active in the execution. Ruppert (2016) showed that the amortized step complexity of known lock-free implementations for many shared data structures includes an additive factor linear in the point contention c ˙ . This paper shows that there is no lock-free implementation with o (min { c ˙ , log log n }) amortized RMR complexity of queues, stacks or heaps from reads, writes, comparison primitives (such as compare &swap) and LL/SC, where n is the total number of the processes in the system. In addition, the paper shows a Ω (min { c ˙ , log log n }) lower bound on the amortized step complexity for shared linked lists, skip lists, search trees and other pointer-based data structures. These lower bounds mean that the additive factor linear in c ˙ is inherent for these implementations, provided that the point contention is small compared to the number of processes in the system (i.e. c ˙ ∈ O (log log n) or c ˙ ∈ O (log log n) ). [ABSTRACT FROM AUTHOR]

In this paper, we address the challenge of creating candidate sets for large-scale Traveling Salesman Problem (TSP) instances, where choosing a subset of edges is crucial for efficiency. Traditional methods for improving tours, such as local searches and heuristics, depend greatly on the quality of these candidate sets but often struggle in large-scale situations due to insufficient edge coverage or high time complexity. We present a new heuristic based on fuzzy clustering, designed to produce high-quality candidate sets with nearly linear time complexity. Thoroughly tested on benchmark instances, including VLSI and Euclidean types with up to 316,000 nodes, our method consistently outperforms traditional and current leading techniques for large TSPs. Our heuristic's tours encompass nearly all edges of optimal or best-known solutions, and its candidate sets are significantly smaller than those produced with the POPMUSIC heuristic. This results in faster execution of subsequent improvement methods, such as Helsgaun's Lin–Kernighan heuristic and evolutionary algorithms. This substantial enhancement in computation time and solution quality establishes our method as a promising approach for effectively solving large-scale TSP instances. [ABSTRACT FROM AUTHOR]

Existing methods to obtain position from inertial sensors typically use a combination of multiple sensors and orientation modeling; thus, obtaining position from a single inertial sensor is highly desirable given the decreased setup time and reduced complexity. The dead reckoning method is commonly chosen to obtain position from acceleration; however, when applied to upper limb tracking, the accuracy of position estimates are questionable, which limits feasibility. A new method of obtaining position estimates through the use of zero velocity updates is reported, using a commercial IMU, a push-to-make momentary switch, and a 3D printed object to house the sensors. The generated position estimates can subsequently be converted into sound through sonification to provide audio feedback on reaching movements for rehabilitation applications. An evaluation of the performance of the generated position estimates from a system labeled 'Soniccup' is presented through a comparison with the outputs from a Vicon Nexus system. The results indicate that for reaching movements below one second in duration, the Soniccup produces positional estimates with high similarity to the same movements captured through the Vicon system, corresponding to comparable audio output from the two systems. However, future work to improve the performance of longer-duration movements and reduce the system latency to produce real-time audio feedback is required to improve the acceptability of the system. [ABSTRACT FROM AUTHOR]

This paper proposed an aggregate signature scheme based on the SM9 algorithm to address the issue of excessive storage space occupied by the signatures of n messages generated by the conventional SM9 signature scheme. This scheme reduced the time cost of verifying multiple signatures compared to the original SM9 scheme, with a space cost of about 66.7% of the original SM9 scheme. Furthermore, the scheme introduced a locally verifiable approach based on the SM9 aggregate signature to tackle the problem where validators need only verify the correctness of specific messages when verifying signatures in current aggregate signature algorithms but still require knowledge of the complete message list. For the aggregated signatures S of a messages generated by a single user, the signer generated verification tags for a specific message m, enabling the verifier to verify the correctness of the message's signature without knowledge of the complete message list. Theoretical and experimental analysis confirm that the proposed scheme achieves a time complexity of O(1) for verifying specific messages given an aggregated signature. [ABSTRACT FROM AUTHOR]

The imaging quality of ultrasonic phased array technology significantly affects the quantification of small defects inside metals. Moreover, traditional manual evaluation methods require a substantial amount of manpower and time, and they are easily influenced by subjective factors. To mitigate the impact of imaging quality on the automated quantification of defects, this study proposes an improved gcForest algorithm (AWGA-gcForest, Adaptive window genetic algorithm- gcForest). Firstly, the acquired ultrasonic full matrix data from the phased array is processed using full focusing A-scan technique. Additionally, a window averaging weighting method is introduced for ultrasound signal processing to eliminate the interference from incident waves and backwall echoes. Subsequently, a multi-scale adaptive sliding window adjustment strategy based on Mean Absolute Deviation (MAD) is employed to reduce the computational time complexity of the gcForest algorithm. Furthermore, a weighted approach optimised with a genetic algorithm is utilised in the cascade forest to improve the classification accuracy and generalisation capability. Experimental results demonstrate that the proposed method achieves an accuracy of 97.50%, precision of 97.26%, recall rate of 96.63%, and F1 score of 96.92, exhibiting higher detection accuracy compared to other models while also reducing time costs. [ABSTRACT FROM AUTHOR]

Plant Leaf Disease (PLD) detection is helpful for several fields like Agriculture Institute and Biological Research. The country’s economic growth depends on the productivity of the agricultural field. Recently developed models based on deep learning give more accurate and precise results over the detection and classification of PLD while evolving through image processing approaches. Many image-processing approaches are used for the identification and classification of PLD. The quality of agricultural products is mainly affected by several factors like fungi, bacteria, and viruses. These factors severely destroy the entire growth of the plant. Hence, some outperformed models are needed to detect and identify the severity level of plant diseases yet, the identification requires more time and has a struggle to identify the appropriate type of disease based on its symptoms. Therefore, several automatic detection and classification models are developed to avoid the time complexity. Computerized image processing approaches are utilized for crop protection, which analyzes the color information of leaves from the collected images. Hence, image processing techniques play an important role in the identification and classification of PLD. It gives more advantages by lowering the task of illustrating crops on large farms and detecting the leaf diseases at the initial stage itself based on the symptoms of the plant leaves. While implementing a new model, there is a need to study various machine and deep learning-based structures for PLD detection approaches. This research work provides an overview of various heuristic approaches, machine learning, and deep learning models for the detection and classification of PLD. This research work also covers the various constraints like PLD detection tools, performance measures, datasets used, and chronological review. Finally, the research work explores the research findings and also the research gaps with future scope. [ABSTRACT FROM AUTHOR]

By considering maps and routes as sequences of line segments, their intersections can be computed to find out useful information like the possibility of collision in a military area where the parties do not trust each other. At the first glance, finding the coordinates of the intersections is seemed impossible to be solved securely since having coordinates of two intersection points on the same line reveals the passing line. In this paper, we solve this problem by suggesting a secure two-party protocol in presence of passive adversaries. Additionally, regarding the fact that in some cases, the fixedness of the inputs of the parties in classic security models is an unrealistic assumption, we define the new concept of input-adaptive security and show that our method is secure against such an adversary who is able to select his inputs adaptively. In addition to serve different approaches like oblivious transfer and sometimes homomorphic encryption, we also employ some tricks to prevent the distribution of harmful information between specific parties to achieve our intended security level. We provide formal proofs to show the security of our protocol. Time complexity analysis and implementations show that our protocol finds the intersections in feasible time of O (n log n) and indicate that our protocol is as good as the unsecure optimal method of line segment intersection computation. In comparison, previous methods require O (n 2) to only detect the existence of intersection between two sets of n line segments and are unable to find the coordinates of the intersections. [ABSTRACT FROM AUTHOR]

In a market, there are many groups caused by geographical location or other reasons, and consumers in groups have their own brand preferences for a type of products. The diversity of consumers' brand preferences will avoid the phenomenon of brand simplification and monopoly caused by consistent brand reference of consumers, and to some extent, promote the prosperity and development of various brands in each group. For brand diversification in a market, we hope the brand preferences of consumers in each groups are as equilibrious as possible, so Influence Maximization under Equilibrious Groups (IMEG) is proposed to select k nodes to maximize the number of equilibrious groups after information diffusion. This paper proves that the IMEG is NP-hard, and computing the objective function is #P-hard. It also proves that the objective function is neither submodular nor supermodular under Independent Cascade (IC) model and Linear Threshold (LT) model. Then, the Equilibrious Groups Maximization Solution (EGMS) algorithm is presented to solve our problem. And by comparing with baseline algorithms using different datasets (dolphins, wildbird, weaver and hamsterster), it can be found that the EGMS has obvious advantages in time complexity and spatial complexity. In particular, the running time of EGMS is about 3.7 × 10 - 2 , 2.4 × 10 - 2 , 1.1 × 10 - 1 and 1.8 × 10 - 3 times that of the fastest baseline algorithm in dolphins, wildbird, weaver and hamsterster respectively. And the experiments in small-world, scale-free, random and regular network verify the robustness of EGMS with the varying parameters, such as the number of nodes, the probability of adding edges and the number of adjacencies. [ABSTRACT FROM AUTHOR]

Although the density peak clustering (DPC) algorithm can effectively distribute samples and quickly identify noise points, it lacks adaptability and cannot consider the local data structure. In addition, clustering algorithms generally suffer from high time complexity. Prior research suggests that clustering algorithms grounded in P systems can mitigate time complexity concerns. Within the realm of membrane systems (P systems), spiking neural P systems (SN P systems), inspired by biological nervous systems, are third-generation neural networks that possess intricate structures and offer substantial parallelism advantages. Thus, this study first improved the DPC by introducing the maximum nearest neighbor distance and K-nearest neighbors (KNN). Moreover, a method based on delayed spiking neural P systems (DSN P systems) was proposed to improve the performance of the algorithm. Subsequently, the DSNP-ANDPC algorithm was proposed. The effectiveness of DSNP–ANDPC was evaluated through comprehensive evaluations across four synthetic datasets and 10 real-world datasets. The proposed method outperformed the other comparison methods in most cases. [ABSTRACT FROM AUTHOR]

Analog circuits composed by large number of nodes in a tightly coupled structure pose significant challenges due to their prohibitive CPU simulation time. This work describes a method to speed up the simulation of such circuits by means of the combination of space state formulation of circuit equations with explicit integration methods parallelized over a many-core processor such as a GPU. Although stability of explicit techniques require smaller integration steps compared to implicit methods, the proposed method employs a fast estimate of the maximum allowed step size to guarantee numerical stability, which yields a shorter simulation time for increasing complexity circuit architectures. Moreover, the proposed technique can be straightforward parallelized on a many core architecture. The proposed method is demonstrated with two examples using constant and variable coefficients respectively: an RLC interconnect and a MOS-C network to perform Gaussian filtering of medium resolution images. The results obtained have been compared to a parallel version of SPICE and show improvements up to two orders of magnitude for transient simulations depending of the circuit size. [ABSTRACT FROM AUTHOR]