Search

There are several classical characterisations of the valuative dimension of a commutative ring. Constructive versions of this dimension have been given and proven to be equivalent to the classical notion within classical mathematics, and they can be used for the usual examples of commutative rings. To the contrary of the classical versions, the constructive versions have a clear computational content. This paper investigates the computational relationship between three possible constructive definitions of the valuative dimension of a commutative ring. In doing so, it proves these constructive versions to be equivalent within constructive mathematics. [ABSTRACT FROM AUTHOR]

In this paper, we focus on Hitting-Set , a fundamental problem in combinatorial optimization, through the lens of sublinear time algorithms. Given access to the hypergraph through a subset query oracle in the query model, we give sublinear time algorithms for Hitting-Set with almost tight parameterized query complexity. In parameterized query complexity , we estimate the number of queries to the oracle based on the parameter k , the size of the Hitting-Set. The subset query oracle we use in this paper is called Generalized d -partite Independent Set query oracle (GPIS) and it was introduced by Bishnu et al. (ISAAC'18). GPIS is a generalization to hypergraphs of the Bipartite Independent Set query oracle (BIS) introduced by Beame et al. (ITCS'18 and TALG'20) for estimating the number of edges in graphs. Since its introduction GPIS query oracle has been used for estimating the number of hyperedges independently by Dell et al. (SODA'20 and SICOMP'22) and Bhattacharya et al. (STACS'22), and for estimating the number of triangles in a graph by Bhattacharya et al. (ISAAC'19 and TOCS'21). Formally, GPIS is defined as follows: GPIS oracle for a d-uniform hypergraph H takes as input d pairwise disjoint non-empty subsets A 1 , ... , A d of vertices in H and answers whether there is a hyperedge in H that intersects each set A i , where i ∈ { 1 , 2 , ... , d }. For d = 2 , the GPIS oracle is nothing but BIS oracle. We show that d - Hitting-Set , the hitting set problem for d -uniform hypergraphs, can be solved using O ˜ d (k d log ⁡ n) GPIS queries. Additionally, we also showed that d - Decision-Hitting-Set , the decision version of d - Hitting-Set can be solved with O ˜ d (min ⁡ { k d log ⁡ n , k 2 d 2 }) GPIS queries. We complement these parameterized upper bounds with an almost matching parameterized lower bound that states that any algorithm that solves d - Decision-Hitting-Set requires Ω (( k + d d )) GPIS queries. [ABSTRACT FROM AUTHOR]

Many studies have shown that long-chain noncoding RNAs (lncRNAs) are involved in a variety of biological processes such as post-transcriptional gene regulation, splicing, and translation by combining with corresponding proteins. Predicting lncRNA-protein interactions is an effective approach to infer the functions of lncRNAs. The paper proposes a new computational model named LPI-IBWA. At first, LPI-IBWA uses similarity kernel fusion (SKF) to integrate various types of biological information to construct lncRNA and protein similarity networks. Then, a bounded matrix completion model and a weighted k -nearest known neighbors algorithm are utilized to update the initial sparse lncRNA-protein interaction matrix. Based on the updated lncRNA-protein interaction matrix, the lncRNA similarity network and the protein similarity network are integrated into a heterogeneous network. Finally, an improved Bi-Random walk algorithm is used to predict novel latent lncRNA-protein interactions. 5-fold cross-validation experiments on a benchmark dataset showed that the AUC and AUPR of LPI-IBWA reach 0.920 and 0.736, respectively, which are higher than those of other state-of-the-art methods. Furthermore, the experimental results of case studies on a novel dataset also illustrated that LPI-IBWA could efficiently predict potential lncRNA-protein interactions. • LPI-IBWA is an effective computational model to predict lncRNA-protein interactions. • Similarity kernel fusion is used to integrate heterogenous biological similarities. • Bounded matrix completion updates lncRNA-protein interaction matrix. • Bi-Random walk on lncRNA-protein interactions network predicts novel interactions. [ABSTRACT FROM AUTHOR]

In this paper, we present an algorithm that, given a differential operator of order 2, detects if this operator comes from a simpler operator under a non-trivial change of variables. [ABSTRACT FROM AUTHOR]

With this paper we present an extension of our recent ISSAC paper about computations of Gröbner(-Shirshov) bases over free associative algebras Z 〈 X 〉. We present all the needed proofs in details, add a part on the direct treatment of the ring Z / m Z as well as new examples and applications to e.g. Iwahori-Hecke algebras. The extension of Gröbner bases concept from polynomial algebras over fields to polynomial rings over rings allows to tackle numerous applications, both of theoretical and of practical importance. Gröbner and Gröbner-Shirshov bases can be defined for various non-commutative and even non-associative algebraic structures. We study the case of associative rings and aim at free algebras over principal ideal rings. We concentrate on the case of commutative coefficient rings without zero divisors (i.e. a domain). Even working over Z allows one to do computations, which can be treated as universal for fields of arbitrary characteristic. By using the systematic approach, we revisit the theory and present the algorithms in the implementable form. We show drastic differences in the behaviour of Gröbner bases between free algebras and algebras, which are close to commutative. Even the process of the formation of critical pairs has to be reengineered, together with implementing the criteria for their quick discarding. We present an implementation of algorithms in the Singular subsystem called Letterplace , which internally uses Letterplace techniques (and Letterplace Gröbner bases), due to La Scala and Levandovskyy. Interesting examples and applications accompany our presentation. [ABSTRACT FROM AUTHOR]

This paper introduces an algorithmic approach to the analysis of bifurcation of limit cycles from the centers of nonlinear continuous differential systems via the averaging method. We develop three algorithms to implement the averaging method. The first algorithm allows one to transform the considered differential systems to the normal form of averaging. Here, we restricted the unperturbed term of the normal form of averaging to be identically zero. The second algorithm is used to derive the computational formulae of the averaged functions at any order. The third algorithm is based on the first two algorithms and determines the exact expressions of the averaged functions for the considered differential systems. The proposed approach is implemented in Maple and its effectiveness is shown by several examples. Moreover, we report some incorrect results in published papers on the averaging method. [ABSTRACT FROM AUTHOR]

This paper presents a study of the LLL algorithm from the perspective of statistical physics. Based on our experimental and theoretical results, we suggest that interpreting LLL as a sandpile model may help understand much of its mysterious behavior. In the language of physics, our work presents evidence that LLL and certain 1-d sandpile models with simpler toppling rules belong to the same universality class. This paper consists of three parts. First, we introduce sandpile models whose statistics imitate those of LLL with compelling accuracy, which leads to the idea that there must exist a meaningful connection between the two. Indeed, on those sandpile models, we are able to prove the analogues of some of the most desired statements for LLL, such as the existence of the gap between the theoretical and the experimental RHF bounds. Furthermore, we test the formulas from finite-size scaling theory (FSS) against the LLL algorithm itself, and find that they are in excellent agreement. This in particular explains and refines the geometric series assumption (GSA), and allows one to extrapolate various quantities of interest to the dimension limit. In particular, we obtain the estimate that the empirical average RHF converges to ≈1.02265 as the dimension goes to infinity. [ABSTRACT FROM AUTHOR]

We describe a practical algorithm for computing normal forms for semigroups and monoids with finite presentations satisfying so-called small overlap conditions. Small overlap conditions are natural conditions on the relations in a presentation, which were introduced by J. H. Remmers and subsequently studied extensively by M. Kambites. Presentations satisfying these conditions are ubiquitous; Kambites showed that a randomly chosen finite presentation satisfies the C (4) condition with probability tending to 1 as the sum of the lengths of relation words tends to infinity. Kambites also showed that several key problems for finitely presented semigroups and monoids are tractable in C (4) monoids: the word problem is solvable in O (min ⁡ { | u | , | v | }) time in the size of the input words u and v ; the uniform word problem for 〈 A | R 〉 is solvable in O (N 2 min ⁡ { | u | , | v | }) where N is the sum of the lengths of the words in R ; and a normal form for any given word u can be found in O (| u |) time. Although Kambites' algorithm for solving the word problem in C (4) monoids is highly practical, it appears that the coefficients in the linear time algorithm for computing normal forms are too large in practice. In this paper, we present an algorithm for computing normal forms in C (4) monoids that has time complexity O (| u | 2) for input word u , but where the coefficients are sufficiently small to allow for practical computation. Additionally, we show that the uniform word problem for small overlap monoids can be solved in O (N min ⁡ { | u | , | v | }) time. [ABSTRACT FROM AUTHOR]

The problem of deletion of vertices to a hereditary graph class is a well-studied problem in parameterized complexity. Recently, a natural extension of the problem was initiated where we are given a finite set of hereditary graph classes and we determine whether k vertices can be deleted from a given graph so that the connected components of the resulting graph belong to one of the given hereditary graph classes. The problem is shown to be fixed parameter tractable (FPT) when the deletion problem to each of the given hereditary graph classes is fixed-parameter tractable, and the property of being in any of the graph classes is expressible in the counting monodic second order (CMSO) logic. This paper focuses on pairs of specific graph classes (Π 1 , Π 2) in which we would like the connected components of the resulting graph to belong to, and design simpler and more efficient FPT algorithms. [ABSTRACT FROM AUTHOR]

Unambiguous automata are nondeterministic automata in which every word has at most one accepting run. In this paper we give a polynomial-time algorithm for model checking discrete-time Markov chains against ω -regular specifications represented as unambiguous automata. We furthermore show that the complexity of this model checking problem lies in NC: the subclass of P comprising those problems solvable in poly-logarithmic parallel time. These complexity bounds match the known bounds for model checking Markov chains against specifications given as deterministic automata, notwithstanding the fact that unambiguous automata can be exponentially more succinct than deterministic automata. We report on an implementation of our procedure, including an experiment in which the implementation is used to model check LTL formulas on Markov chains. [ABSTRACT FROM AUTHOR]

Over the past few decades, a large body of works studied the (in)tractability of various computational problems on grid graphs, which often yield substantially faster algorithms than general graphs. Unfortunately, the recognition of a grid graph is hard—it was shown to be NP-hard already in 1987. In this paper, we provide several positive results in this regard in the framework of parameterized complexity. Specifically, our contribution is threefold. First, we show that the problem is FPT parameterized by k + mcc where mcc is the maximum size of a connected component of G. Second, we present a new parameterization, denoted a G , relating graph distance to geometric distance. We show that the problem is para-NP-hard parameterized by a G , but FPT parameterized by a G on trees, as well as FPT parameterized by k + a G. Third, we show that the recognition of k × r grid graphs is NP-hard on graphs of pathwidth 2 where k = 3. [ABSTRACT FROM AUTHOR]

Crop row detection is an important part of precision agriculture. Therefore, an unmanned agricultural machine crop row detection method based on YOLO-R is proposed. This method can solve the problem that traditional image processing methods are easily affected by weeds, light and other factors when extracting crop feature points. First, the YOLO-R object detection algorithm was used to obtain the crop position information, and then, the number of crop rows in the image and the crop in each crop row were obtained by the DBSCAN clustering algorithm. Finally, the function expression for each crop row was obtained by using the least squares method. The experimental results show that the AP values of YOLO-R are 91.69%, 95.34% and 89.13% on the seven-day, 14-day, and 21-day rice datasets, respectively. When the proposed algorithm's number of parameters was only 12.31% of that of YOLOv4 and the FPS was 17.54 higher than that of YOLOv4, the AP value was only 2.2% lower. The accuracy values of crop row detection algorithm are 93.91%, 95.87% and 89.87% on the seven-day, 14-day, and 21-day rice datasets, respectively, which indicates that the algorithm in this paper can effectively identify crop lines. • Proposing a crop row detection method based on YOLO-R object detection algorithm. • Ghostnet and Focal Loss are used in YOLO-R to perform better and faster. • Use channel attention module to coordinate the importance between each channel. • Incremental ablation study on all network designs. [ABSTRACT FROM AUTHOR]

The paper aims at mitigating hot-spots during Offline Scheduling in IaaS (Infrastructure-as-a-Service) cloud systems. Unlike previous studies, the research focuses on identifying and resolving hot-spots not at servers, but at server racks. A two-phase algorithm for performing power-aware offline scheduling is proposed. The first phase aims at identifying and mitigating hot-spots at racks, while the second phase performs VM consolidation, i.e. minimization of the number of occupied servers while maintaining a feasible VM mapping and low migration costs. The proposed algorithm takes into account the dynamic nature of VM's resource consumption: it does not only resolve detected hot-spots, but also tries to avoid hot-spots in a reasonable future time period. The algorithm was tested with the data from a real IaaS cloud with different sets of algorithm's parameters. Experimental evaluation showed that the statistical estimates of the future VM's resource consumption provide the most reliable mapping, which is a result of minimization of the number of new hot-spot occurrences. • A server rack is a hot-spot if it exceeds the upper bound of power consumption. • Hot-spot identification, mitigation, and avoidance is crucial for IaaS systems. • An algorithm is proposed for rack hot-spot mitigation and consolidation of VMs. • Considering future CPU utilization values is associated with migrating more memory. • Ignoring future CPU utilization values leads to more new hot-spots happening shortly. [ABSTRACT FROM AUTHOR]

• The adaptive bulk search is a QUBO solver alternative to quantum annealing. • The cyclic-min algorithm is a SA-like algorithm without random number generation. • The bit permutated cyclic-min algorithm provides near-optimal solutions for QUBO. • Our scalable implementation attains linear improvement of the search rate. A wide range of combinatorial optimization problems can be reduced to the Ising model, and equivalently the quadratic unconstrained binary optimization (QUBO) problem. Thus, in recent years, researchers have proposed to solve QUBO on FPGAs, GPUs, and special-purpose processors. The adaptive bulk search (ABS) is a previously-proposed framework for solving QUBO in parallel on multiple GPUs. In the ABS, a CPU host performs a GA-based global search while GPUs asynchronously perform many local searches in parallel. An original ABS adopts a simple local search algorithm called a cyclic-min algorithm, which does not use pseudo random numbers. However, the lack of randomness may cause a potential drawback of restricted bit-flipping operations in a local search. To avoid this drawback, this paper proposes a cyclic-min algorithm with randomly-generated multiple bit permutations, which enables a more effective local search with random number generation in CPUs (not in GPUs). Furthermore, this paper introduces a scalable implementation of the ABS with MPI and OpenMP. Our experimental results on TSUBAME3.0 show that the solution quality improves and the throughput linearly increases as the number of GPUs increases; with 256 GPUs, it evaluates 20.1 × 10 12 solutions per second. [ABSTRACT FROM AUTHOR]

• A novel positivity-preserving algorithm for implicit NS solver. • A residual correction to compute the correction factor. • A flux correction to enforce the positivity of the solution conservatively. • Positivity-preserving combined with implicit iterations. • Numerical experiments to verify the positivity-preserving capability. This paper presents a general positivity-preserving algorithm for implicit high-order finite volume schemes that solve compressible Euler and Navier-Stokes equations to ensure the positivity of density and internal energy (or pressure). Previous positivity-preserving algorithms are mainly based on the slope limiting or flux limiting technique, which rely on the existence of low-order positivity-preserving schemes. This dependency poses serious restrictions on extending these algorithms to temporally implicit schemes since it is difficult to know if a low-order implicit scheme is positivity-preserving. In the present paper, a new positivity-preserving algorithm is proposed in terms of the flux correction technique. And the factors of the flux correction are determined by a residual correction procedure. For a finite volume scheme that is capable of achieving a converged solution, we show that the correction factors are in the order of unity with additional high-order terms corresponding to the spatial and temporal rates of convergence. Therefore, the proposed positivity-preserving algorithm is accuracy-reserving and asymptotically consistent. The notable advantage of this method is that it does not rely on the existence of low-order positivity-preserving baseline schemes. Therefore, it can be applied to the implicit schemes solving Euler and especially Navier-Stokes equations. In the present paper, the proposed technique is applied to an implicit dual time-stepping finite volume scheme with temporal second-order and spatial high-order accuracy. The present positivity-preserving algorithm is implemented in an iterative manner to ensure that the dual time-stepping iteration will converge to the positivity-preserving solution. Another similar correction technique is also proposed to ensure that the solution remains positivity-preserving at each sub-iteration. Numerical results demonstrate that the proposed algorithm preserves positive density and internal energy in all test cases and significantly improves the robustness of the numerical schemes. [ABSTRACT FROM AUTHOR]

Considering a multivariate polynomial ideal over a given field as a vector space, we investigate for such an ideal a particular linear basis, a so-called staggered linear basis, which contains a Gröbner basis as well. In this paper, we present a simple and efficient algorithm to compute a staggered linear basis. The new framework is equipped with some novel criteria (including both Buchberger's criteria) to detect superfluous reductions. The proposed algorithm has been implemented in Maple, and we provide an illustrative example to show how it works. Finally, the efficiency of this algorithm compared to the existing methods is discussed via a set of benchmark polynomials. [ABSTRACT FROM AUTHOR]

Resource provisioning plays a pivotal role in determining the right amount of infrastructure resource to run applications and reduce the monetary cost. A significant portion of production clusters is now dedicated to long-running applications (LRAs), which are typically in the form of microservices and executed in the order of hours or even months. It is therefore practically important to plan ahead the placement of LRAs in a shared cluster for the minimized number of compute nodes required by them. Existing works on LRA scheduling are often application-agnostic, without particularly addressing the constraining requirements imposed by LRAs, such as co-location affinity constraints and time-varying resource requirements. In this paper, we present an affinity-aware resource provisioning approach for deploying large-scale LRAs in a shared cluster subject to multiple constraints, with the objective of minimizing the number of compute nodes in use. We investigate a broad range of solution algorithms which fall into three main categories: Application-Centric, Node-Centric, and Multi-Node approaches, and tune them for typical large-scale real-world scenarios. Experimental studies driven by the Alibaba Tianchi dataset show that our algorithms can achieve competitive scheduling effectiveness and running time, as compared with the heuristics used by the latest work including Medea and Lra Sched. Best results are obtained by the Application-Centric algorithms, if the algorithm's running time is of primary concern, and by Multi-Node algorithms, if the solution quality is of primary concern. • Resource provisioning for long-running applications is studied in shared clusters. • Temporal resource requests and application-level affinity are considered. • Application-Centric algorithms win if the running time is of primary concern. • Node-Centric Algorithms offer a trade-off between solution quality and time. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem of recovery of a burst-like forcing term in an initial value problem (IVP) in the framework of dynamical sampling. We introduce an idea of using two particular classes of samplers that allow one to predict the solution of the IVP over a time interval without a burst. This leads to two different algorithms that stably and accurately approximate the burst-like forcing term even in the presence of a measurement acquisition error and a large background source. [ABSTRACT FROM AUTHOR]

One of the key objectives in many fields in machine learning is to discover causal relationships among a set of variables from observational data. In linear non-Gaussian acyclic models (LiNGAM), it can be shown that the true underlying causal structure can be identified uniquely from merely observational data. The DirectLiNGAM algorithm is a well-known solution to learn the true causal structure in a high dimensional setting. DirectLiNGAM algorithm executes in a sequence of iterations and it performs a set of comparisons between pairs of variables in each iteration. Unfortunately, the runtime of this algorithm grows significantly as the number of variables increases. In this paper, we propose a parallel algorithm, called ParaLiNGAM, to learn casual structures based on DirectLiNGAM algorithm. We propose a threshold mechanism that can reduce the number of comparisons remarkably compared with the sequential solution. Moreover, in order to further reduce runtime, we employ a messaging mechanism between workers. We also present an implementation of ParaLiNGAM on GPU, considering hardware constraints. Experimental results on synthetic and real data show that our proposed solution outperforms DirectLiNGAM by a factor up to 4788X, and by a median of 2344X. • A scalable algorithm for learning causal structures in linear non-Gaussian models. • Significant speedup by selecting the necessary computations judiciously. • Speedup ratio of up to 4788 on GPUs in real-world and synthetic datasets. [ABSTRACT FROM AUTHOR]

Holonomic sequences are widely studied as many objects interesting to mathematicians and computer scientists are in this class. In the univariate case, these are the sequences satisfying linear recurrences with polynomial coefficients and also referred to as D -finite sequences. A subclass are C -finite sequences satisfying a linear recurrence with constant coefficients. We investigate the set of sequences which satisfy linear recurrence equations with coefficients that are C -finite sequences and call them C 2 -finite sequences. These sequences are a natural generalization of holonomic sequences. In this paper, we show that C 2 -finite sequences form a difference ring and provide methods to compute in this ring. Furthermore, we provide an analogous construction for D 2 -finite sequences, i.e., sequences satisfying a linear recurrence with holonomic coefficients. We show that these constructions can be iterated and obtain an increasing chain of difference rings. [ABSTRACT FROM AUTHOR]

In edge computing, application components can be placed over a range of computational devices from cloud data centers to nodes at the network edge. Application placement can have significant impact on important metrics like latency and resource utilization. Thus, application placement is an important optimization problem. In edge computing, the characteristics of both the infrastructure and the application may change over time, which may require the dynamic re-optimization of the application placement. Most algorithms suggested so far for the dynamic re-optimization of edge application placement are centralized, i.e., they rely on one entity collecting information from the whole infrastructure and making decisions centrally. However, centralized approaches suffer from limited scalability and are vulnerable to failures. In this paper, we present a decentralized approach for the dynamic re-optimization of edge application placement. We adopt an algorithm of Malek et al. for distributed systems and modify it to make it applicable to edge computing. In this approach, each node makes decisions autonomously, using auctions for coordination. Our empirical results demonstrate that the proposed algorithm is very effective in optimizing edge application placement. In an edge system with 637 edge nodes and 563 end devices, our algorithm achieves 54% higher reduction of application latency than a previous decentralized algorithm. • Optimized placement of application components on cloud and edge devices. • Decentralized optimization algorithm using local knowledge and local modifications. • Auctions and distributed locking for synchronization. • Minimization of application latency. [ABSTRACT FROM AUTHOR]

Flagged Schur modules generalize the irreducible representations of the general linear group under the action of the Borel subalgebra. Their characters include many important generalizations of Schur polynomials, such as Demazure characters, flagged skew Schur polynomials, and Schubert polynomials. In this paper, we prove the characters of flagged Schur modules can be computed using a simple combinatorial algorithm due to Kohnert if and only if the indexing diagram is northwest. This gives a new proof that characters of flagged Schur modules are nonnegative sums of Demazure characters and gives a representation theoretic interpretation for Kohnert polynomials. [ABSTRACT FROM AUTHOR]

In this paper, we describe the first parallel Branch-and-Bound (B&B) algorithm with a history-based domination technique. Although history-based domination substantially speeds up a B&B search, it makes parallelization much more challenging. Our algorithm is the first parallel exact algorithm for the Sequential Ordering Problem using a pure B&B approach. To effectively explore the solution space, we have developed three novel parallelization techniques: thread restart, parallel history domination, and history-table memory management. The proposed algorithm was experimentally evaluated using the SOPLIB and TSPLIB benchmarks on multi-core processors. Using 32 threads with a time limit of one hour, the algorithm gives geometric-mean speedups of 72x and 20x on the medium-difficulty SOPLIB and TSPLIB instances, respectively. On the hard instances, it solves 12 instances that the sequential algorithm does not solve, with geometric-mean speedups of 16x on SOPLIB and 32x on TSPLIB. Super-linear speedups up to 366x are seen on 16 instances. • We propose the first parallel B&B algorithm that involves a history-based domination technique. • The proposed algorithm includes three novel parallelization techniques: thread restart, parallel history-based domination, and history-table memory management. • The proposed algorithm is the first parallel B&B algorithm for the Sequential Ordering Problem, which is an NP-hard sequencing problem with precedence constraints. • We present a thorough experimental evaluation of the proposed parallel algorithm on SOPLIB and TSPLIB. The results show that super-linear speedup is not an anomaly; it can be achieved on many instances. We report a speedup ratio as high as 285 on a 32-core processor. [ABSTRACT FROM AUTHOR]

This paper presents a theoretical study on the implementation of a self-tuning vibration absorber for tonal vibration control. The study considers a tuneable vibration absorber, composed by a spring-mass-damper system with variable stiffness and damping components, which is attached to a single degree of freedom mechanical system subjected to a harmonic excitation. The online tuning of the absorber stiffness and damping parameters is performed using an extremum seeking algorithm set to minimise the vibration kinetic energy of the hosting system. The paper proposes a two-paths tuning approach, which, starting from initial estimates of the stiffness and damping parameters of the absorber, searches for their optimal values along constant-damping and constant-stiffness paths respectively. The study presents a comprehensive analysis on the implementation of the algorithm at off-resonance and at resonance frequencies of the hosting system. Also, it investigates how the intrinsic parameters of the algorithm influence the convergence to the optimal stiffness and damping values. The proposed tuning methodology does not require a reference signal for the tonal excitation and, thus, can be suitably implemented both for fixed and time-varying tonal disturbances. [ABSTRACT FROM AUTHOR]

In this paper we analyze the computational costs of various operations and algorithms in algebraic number fields using exact arithmetic. Let K be an algebraic number field. In the first half of the paper, we calculate the running time and the size of the output of many operations in K in terms of the size of the input and the parameters of K. We include some earlier results about these, but we go further than them, e.g. we also analyze some R -specific operations in K like less-than comparison. In the second half of the paper, we analyze two algorithms: the Bareiss algorithm, which is an integer-preserving version of the Gaussian elimination, and the LLL algorithm, which is for lattice basis reduction. In both cases, we extend the algorithm from Z n to K n , and give a polynomial upper bound on the running time when the computations in K are performed exactly (as opposed to floating-point approximations). [ABSTRACT FROM AUTHOR]

• An adaptive HEVC video steganography algorithm is designed, which can effectively resist the PU shift-based steganalysis. • The introduction of multivariate STC allows for smaller modifications with the same embedding capacity. • The superiority of this algorithm over the state-of-the-art video steganography algorithm is verified through extensive experiments. Calibration-based steganalysis methods are a fatal threat to current HEVC steganography algorithms. The current steganography algorithms based on prediction unit (PU) still lack resistance to this type of steganalysis. The reason is that the improvements in HEVC codec provide more potential steganographic space as well as introduce more detectable distortion. Therefore, a HEVC video steganography method that has resistance to PU shift-based steganalysis is proposed in this paper. First, the PU shift phenomenon that exists in PU-based steganography is introduced. Then the existing calibration-based steganalysis method is enhanced. According to the encoding rules of HEVC, the distortion cost function according to the difference of rate distortion cost (RD cost) during recompression is designed, which aims to obtain better resistance to calibration-based steganalysis. Experimental results demonstrate that the steganography algorithm designed in this paper provides excellent resistance ability for calibration-based steganalysis. [ABSTRACT FROM AUTHOR]

• Formulate a non-cooperative game with both UEs and MECs as players. • Prove the existence of and convergence to a Nash equilibrium. • Develop a set of algorithms to find the Nash equilibrium. • Demonstrate numerical examples of non-cooperative games with and without MECs' participation. In a newly emerged fog computing environment, various user equipments (UE) enhance their computing power and extend their battery lifetime by computation offloading to mobile edge cloud (MEC) servers. Such an environment is distributed and competitive in nature. In this paper, we take a game theoretical approach to computation offloading optimization in a fog computing environment. Such an approach captures and characterizes the nature of a competitive environment. The main contributions of the paper can be summarized as follows. First, we formulate a non-cooperative game with both UEs and MECs as players. Each UE attempts to minimize the execution time of its tasks with an energy constraint. Each MEC attempts to minimize the product of its power consumption for computation and execution time for allocated tasks. Second, we develop a heuristic algorithm for a UE to determine its "heuristically" best response to the current situation, an algorithm for an MEC to determine its best response to the current situation, and an iterative algorithm to find the Nash equilibrium. Third, we prove that our iterative algorithm converges to a Nash equilibrium. We demonstrate numerical examples of our non-cooperative games with and without MECs' participation. We observe that our iterative algorithm always quickly converges to a Nash equilibrium. The uniqueness of our non-cooperative games is that the strategy set of a player can be discrete and the payoff function of a player can be obtained by a heuristic algorithm for combinatorial optimization. To the best of the author's knowledge, there has been no such investigation of non-cooperative games based on combinatorial optimization for computation offloading optimization in a fog computing environment. [ABSTRACT FROM AUTHOR]

The paper presents a new method of optimization by the Layered Algorithm (LA). The proposed algorithm reduces the initial area to the sub-area containing the optimum. The proposed technique is based on the classification of the optimized function values (data sampled by sensors). The classification method uses a two-dimensional three-state Cellular Automata (CA). The CA classifies all area points ascribed to the CA cells based on their values. Specification of the categorization layers to the data gives a possibility to identify the different levels areas. Consequently, after analysis, a sub-area containing the optimum can be designated. In this paper, the proposed algorithm is applied to find the location of the airborne contaminant source by analyzing the concentration of released substances reported by mobile sensors distributed over the domain of interest. The Gaussian dispersion model simulation of the contaminant dispersion in the urbanized area is applied to generate the data used to verify the efficiency of the proposed Layered Algorithm. The LA successfully estimates the sub-area of the considered domain where the contamination source is located, taking to account data from sensors solely. • Optimization method reducing the initial area to the sub-area containing the optimum. • Verification of the Layered Algorithm (LA) with Selected Benchmark Functions. • Analysis of the LA efficiency to localize the airborne contaminant source. • LA results assessment by the measures: classification and accuracy error, relevance. [ABSTRACT FROM AUTHOR]

• A network flow model of the VLSI processor array is constructed under row and column rerouting. • A new strategy for selecting the bottleneck row in the logic array using the minimum cutting technique is proposed. • The proposed schemes significantly reduce the interconnect redundancy of the logical subarray. The reconfiguration algorithms have been extensively investigated to ensure the reliability and stability for the processor arrays with faults. It is important to reduce the power consumption, capacitance and communication costs in the processors by reducing the interconnection length of the VLSI array. This paper discusses the reconfiguration problem of the high-performance VLSI processor array under the row and column rerouting constraints. A novel method, making use the idea of network flow, is proposed in this paper. Firstly, a network flow model of the VLSI processor array is constructed, such that the high-performance VLSI target array can be obtained by utilizing the minimal cost flow algorithm. Secondly, we propose a new strategy for bottleneck row selection in the logical array using the minimum cut technique, which can find a more suitable bottleneck row. Finally, we conducted reliable experiments to clearly reveal the efficiency of the new rerouting scheme and algorithm in reducing the number of long interconnects. The experimental results show that, for a host array with size of 256×256, the number of long interconnects in the subarray can be reduced by up to 79.22% and 55.88% without performance penalty for random faults with density of 1% and 25% respectively, when compared with state-of-the-art. In addition, the proposed scheme improves existing algorithm in terms of subarray size. On a 256×256 host array with 25% faulty density, the average improvement in subarray size is up to 3.77% compared with state-of-the-art. [ABSTRACT FROM AUTHOR]

Structural plasticity of the brain describes the creation of new and the deletion of old synapses over time. Rinke et al. (JPDC 2018) introduced a scalable algorithm that simulates structural plasticity for up to one billion neurons on current hardware using a variant of the Barnes–Hut algorithm. They demonstrate good scalability and prove a runtime complexity of O (n log 2 ⁡ n). In this comment paper, we show that with careful consideration of the algorithm and a rigorous proof, the theoretical runtime can even be classified as O (n log ⁡ n). • Improved serial runtime bound for the adapted Barnes–Hut algorithm to Θ(n*log(n)). • Improved the parallel runtime bound to Θ(n/p*log(n)+p). • Mathematical justification that the given runtime bound is sharp. [ABSTRACT FROM AUTHOR]

For any fixed field K ∈ { Q 2 , Q 3 , Q 5 , ... } , we prove that all univariate polynomials f with exactly 3 (resp. 2) monomial terms, degree d , and all coefficients in { ± 1 , ... , ± H } , can be solved over K within deterministic time log 4 + o (1) ⁡ (d H) log 3 ⁡ d (resp. log 2 + o (1) ⁡ (d H)) in the classical Turing model: Our underlying algorithm correctly counts the number of roots of f in K , and for each such root generates an approximation in Q with logarithmic height O (log 2 ⁡ (d H) log ⁡ d) that converges at a rate of O ((1 / p) 2 i ) after i steps of Newton iteration. We also prove significant speed-ups in certain settings, a minimal spacing bound of p − O (p log p 2 ⁡ (d H) log ⁡ d) for distinct roots in C p , and even stronger root repulsion when there are nonzero degenerate roots in C p : p -adic distance p − O (log p ⁡ (d H)). On the other hand, we prove that there is an explicit family of tetranomials with distinct nonzero roots in Z p indistinguishable in their first Ω (d log p ⁡ H) most significant base- p digits. So speed-ups for t -nomials with t ≥ 4 will require evasion or amortization of such worst-case instances. For a video summary of this paper, please visit https://youtu.be/npfdxLk04MY. [ABSTRACT FROM AUTHOR]

The aim of this paper is to present an explicit reduction algorithm for Hilbert modular groups over arbitrary totally real number fields. An implementation of the algorithm is available to download from [20]. The exposition is self-contained and sufficient details are given for the reader to understand how it works and implement their own version if desired. [ABSTRACT FROM AUTHOR]

Path planning is an NP-hard problem that is aimed to satisfy multi-constraint optimization requirements. In autonomous robotics applications, path planning together with collision avoidance presents a challenging task. It necessitates the generation of possible search directions from a designated point to a fixed varying destination location satisfying spatial constraints. This paper presents a framework for the design of an intelligent multi-objective robotic path planning algorithm. The algorithm relies on the generation of way-points by hybridizing two meta-heuristics techniques, namely Grey Wolf Algorithm (GWO) and Particle Swarm Optimization (PSO). A frequency-based modification in GWO search operators is introduced to fasten the search process. An improvised search strategy is employed for collision detection and avoidance, which converts non-desired points into the desired point. Sensors are deployed around the robot vicinity for search optimization. Mutation operators are then introduced to improve path length by smoothing out the trajectory. The proposed algorithm's effectivity is then validated through extensive simulations, in which different condition environments are simulated. To validate the effectiveness of the proposed methodology, the results are compared with contemporary algorithms namely Minimum Angle Artificial Bee Colony (MAABC) algorithms, Hybrid Cuckoo Search-Bat Algorithm (BA-CSA), Bacterial Bolony (BC) and Genetic Algorithm (GA) algorithms. The results conclusively demonstrated that the proposed algorithm ensures effective performance in path smoothness and safety under a wide range of conditions. • A novel intelligent multi-objective framework for robotic path planning algorithm. • A hybridizing two meta-heuristics techniques to solve the path planning. • An improvised search strategy is employed for collision detection and avoidance. • The proposed algorithm's effectively validated through extensive simulations. [ABSTRACT FROM AUTHOR]

Communication overhead is the key challenge for distributed training. Gradient compression is a widely used approach to reduce communication traffic. When combined with a parallel communication mechanism method like pipeline, gradient compression technique can greatly alleviate the impact of communication overhead. However, there exist two problems of gradient compression technique to be solved. Firstly, gradient compression brings in extra computation cost, which will delay the next training iteration. Secondly, gradient compression usually leads to a decrease in convergence accuracy. In this paper, we combine parallel mechanism with gradient quantization and periodic full-gradient compensation, and propose a new distributed optimization method named CP-SGD, which can hide the overhead of gradient compression, overlap part of the communication and obtain high convergence accuracy. The local update operation in CP-SGD allows the next iteration to be launched quickly without waiting for the completion of gradient compression and the current communication process. Besides, the accuracy loss caused by gradient compression is solved by k-step correction method introduced in CP-SGD, which provides a gradient correction every k iterations. We prove that CP-SGD has a convergence guarantee and it achieves at least O (1 K + 1 K) convergence rate, where K is the number of iterations. We conduct extensive experiments on MXNet to verify the convergence properties and scaling performance of CP-SGD. Experimental results on a 32-GPU cluster show that convergence accuracy of CP-SGD is close to or even slightly better than that of S-SGD, and its end-to-end time is 30% less than 2-bit gradient compression under a 56Gbps bandwidth environment. In addition, we analyze the performance of CP-SGD when training on 8, 16 and 32 GPUs. It is found that CP-SGD is suitable for most compression-supported update algorithms, and its scalability is approximately linear. • CP-SGD: Distributed Stochastic Gradient Descent with Compression and Periodic Compensation. • CP-SGD help distributed deep learning train with high-accuracy and friendly-communication simultaneously. • Combining the advantages of parallel mechanism and gradient compression. • K-step correction technique makes CP-SGD achieve codesign optimizations and improve compression-based methods greatly. • CP-SGD suits most compression-supported update algorithms and gradient compression strategies. [ABSTRACT FROM AUTHOR]

Hard-thresholding-based algorithms have seen various advantages for sparse optimization in controlling the sparsity and allowing for fast computation. Recent research shows that when techniques of the Newton-type methods are integrated, their numerical performance can be improved surprisingly. This paper develops a gradient projection Newton pursuit algorithm that mainly adopts the hard-thresholding operator and employs the Newton pursuit only when certain conditions are satisfied. The proposed algorithm is capable of converging globally and quadratically under the standard assumptions. When it comes to compressive sensing problems, the imposed assumptions are much weaker than those for many state-of-the-art algorithms. Moreover, extensive numerical experiments have demonstrated its high performance in comparison with the other leading solvers. [ABSTRACT FROM AUTHOR]

Approximate polynomial GCD (greatest common divisor) of polynomials with a priori errors on their coefficients, is one of interesting problems in Symbolic-Numeric Computations. In fact, there are many known algorithms: QRGCD, UVGCD, STLN based methods, Fastgcd and so on. The fundamental question of this paper is "which is the best?" from the practical point of view, and subsequently "is there any better way?" by any small extension, any effect by pivoting, and any combination of sub-routines along the algorithms. In this paper, we consider a framework that covers those algorithms and their sub-routines, and makes their sub-routines being interchangeable between the algorithms (i.e. disassembling the algorithms and reassembling their parts). By this framework along with/without small new extensions and a newly adapted refinement sub-routine, we have done many performance tests and found the current answer. In summary, 1) UVGCD is the best way to get smaller tolerance, 2) modified Fastgcd is better for GCD that has one or more clusters of zeros with large multiplicity, and 3) modified ExQRGCD is better for GCD that has no cluster of zeros. [ABSTRACT FROM AUTHOR]

For a simply connected connected simple algebraic group G , a cell B w 0 − = B − ∩ U w 0 ‾ U is a geometric crystal with a positive structure θ i − : (C ×) l (w 0) → B w 0 −. Applying the tropicalization functor to a rational function Φ B K h = ∑ i ∈ I Δ w 0 Λ i , s i Λ i called the half decoration on B w 0 − , one can realize the crystal B (∞) in Z l (w 0). By computing Φ B K h , we get an explicit form of B (∞) in Z l (w 0). In this paper, we give an algorithm to compute Δ w 0 Λ i , s i Λ i ∘ θ i − explicitly for i ∈ I such that V (Λ i) is a minuscule representation of g = Lie (G). In particular, the algorithm works for all i ∈ I if g is of type A n. The algorithm computes a directed graph DG , called a decoration graph , whose vertices are labelled by all monomials in Δ w 0 Λ i , s i Λ i ∘ θ i − (t 1 , ⋯ , t l (w 0)). The decoration graph has some properties similar to crystal graphs of minuscule representations. We also verify that the algorithm works in some other cases, for example, the case g is of type G 2 though V (Λ i) is non-minuscule. [ABSTRACT FROM AUTHOR]

• A parallel scalable DBSCAN algorithm which outperforms other implementations. • Optimizations for data partitioning, spatial indexing, and cluster merging. • Exploiting hybrid parallelization to take advantage of modern HPC architectures. • Demonstrating accuracy, performance and scalability of our algorithm. Dbscan is a density-based clustering algorithm which is well known for its ability to discover clusters of arbitrary shape as well as to distinguish noise. As it is computationally expensive for large datasets, research studies on the parallelization of Dbscan have been received a considerable amount of attention. In this paper we present an exact, efficient and scalable parallel Dbscan algorithm which we call Hy-Dbscan. It employs three major techniques to enable scalable data clustering on distributed-memory computers i) a modified kd-tree for domain decomposition, ii) a spatial indexing approach based on grid and inference, and iii) a cluster merging scheme based on distributed Rem's Union-Find algorithm. Moreover, Hy-Dbscan exploits process level and thread level parallelization. In experiments, we have demonstrated performance and scalability using two scientific datasets on up to 2048 cores of a distributed-memory computer. Through extensive evaluation, we show that Hy-Dbscan significantly outperforms previous state-of-the-art Dbscan implementations. [ABSTRACT FROM AUTHOR]

Protein–protein interactions (PPIs) are crucial for various biological processes, and predicting PPIs is a major challenge. To solve this issue, the most common method is link prediction. Currently, the link prediction methods based on network Paths of Length Three (L3) have been proven to be highly effective. In this paper, we propose a novel link prediction algorithm, named SMS, which is based on L3 and protein similarities. We first design a mixed similarity that combines the topological structure and attribute features of nodes. Then, we compute the predicted value by summing the product of all similarities along the L3. Furthermore, we propose the Max Similarity Multiplied Similarity (maxSMS) algorithm from the perspective of maximum impact. Our computational prediction results show that on six datasets, including S. cerevisiae, H. sapiens, and others, the maxSMS algorithm improves the precision of the top 500, area under the precision–recall curve, and normalized discounted cumulative gain by an average of 26.99%, 53.67%, and 6.7%, respectively, compared to other optimal methods. [Display omitted] • A mixed similarity combining sequence and topological structure is introduced. • A link prediction algorithm based on complementarity and similarity is proposed. • The proposed method performs better than existing L3, Sim and other methods. [ABSTRACT FROM AUTHOR]

In recent years there has been increased use of machine learning (ML) techniques within mathematics, including symbolic computation where it may be applied safely to optimise or select algorithms. This paper explores whether using explainable AI (XAI) techniques on such ML models can offer new insight for symbolic computation, inspiring new implementations within computer algebra systems that do not directly call upon AI tools. We present a case study on the use of ML to select the variable ordering for cylindrical algebraic decomposition. It has already been demonstrated that ML can make the choice well, but here we show how the SHAP tool for explainability can be used to inform new heuristics of a size and complexity similar to those human-designed heuristics currently commonly used in symbolic computation. [ABSTRACT FROM AUTHOR]

Online learning is an efficient approach in machine learning and statistics, which iteratively updates models upon the observation of a sequence of training examples. A representative online learning algorithm is the online gradient descent, which has found wide applications due to its low complexity and scalability to large datasets. Kernel-based learning methods have been proven to be quite successful in dealing with nonlinearity in the data and multivariate optimization. In this paper we present a class of kernel-based online gradient descent algorithm for addressing regression problems, which generates sparse estimators in an iterative way to reduce the algorithmic complexity for training streaming datasets and model selection in large-scale learning scenarios. In the setting of support vector regression (SVR), we design the sparse online learning algorithm by introducing a sequence of insensitive distance-based loss functions. We prove consistency and error bounds quantifying the generalization performance of such algorithms under mild conditions. The theoretical results demonstrate the interplay between statistical accuracy and sparsity property during learning processes. We show that the insensitive parameter plays a crucial role in providing sparsity as well as fast convergence rates. The numerical experiments also support our theoretical results. [ABSTRACT FROM AUTHOR]

The selective delayless subband structure stands out as a promising algorithmic choice for the multi-channel active control of vehicle interior noise, particularly in the context of road noise. This type of algorithm reduces the eigenvalue spread of the autocorrelation matrix of the signal by decomposing the signal into subbands, and the desired subbands are activated selectively, thus achieving a significant performance improvement while consuming less computational resources compared with the traditional fullband algorithms. Nevertheless, the effectiveness of the subband algorithm appears to be closely tied to the configuration of the primary disturbance signal. In cases where the primary disturbance signal encompasses both broadband and tonal components, the performance advantage of the subband algorithm becomes constrained. In this paper, we conduct a thorough comparative analysis of two extensively employed subband algorithms, namely the Morgan and the Milani methods, through simulations employing data obtained from a multi-channel active noise control (ANC) headrest system. The results indicate that the Morgan method outperforms the Milani method when configured optimally. Subsequently, we propose an enhanced version of the subband algorithm based on the Morgan method. The enhanced algorithm incorporates an additional sinusoidal noise canceller (SNC) subsystem and a narrowband active noise control (NANC) subsystem based on local secondary path modeling to address tonal components, while the selective subband structure is employed for controlling broadband components. In addition, the computational complexity of the algorithm is analyzed. The effectiveness of the proposed algorithm is validated through numerous simulations and the ANC tests conducted on an actual vehicle utilizing the multi-channel ANC headrest system. The performance of the proposed algorithm surpasses that of traditional selective subband and fullband algorithms, and balanced binaural noise reduction is achieved. [ABSTRACT FROM AUTHOR]

DNA 4 mC plays a crucial role in the genetic expression process of organisms. However, existing deep learning algorithms have shortcomings in the ability to represent DNA sequence features. In this paper, we propose a 4 mC site identification algorithm, DNABert-4mC, based on a fusion of the pruned pre-training DNABert-Pruning model and artificial feature encoding to identify 4 mC sites. The algorithm prunes and compresses the DNABert model, resulting in the pruned pre-training model DNABert-Pruning. This model reduces the number of parameters and removes redundancy from output features, yielding more precise feature representations while upholding accuracy.Simultaneously, the algorithm constructs an artificial feature encoding module to assist the DNABert-Pruning model in feature representation, effectively supplementing the information that is missing from the pre-trained features. The algorithm also introduces the AFF-4mC fusion strategy, which combines artificial feature encoding with the DNABert-Pruning model, to improve the feature representation capability of DNA sequences in multi-semantic spaces and better extract 4 mC sites and the distribution of nucleotide importance within the sequence. In experiments on six independent test sets, the DNABert-4mC algorithm achieved an average AUC value of 93.81%, outperforming seven other advanced algorithms with improvements of 2.05%, 5.02%, 11.32%, 5.90%, 12.02%, 2.42% and 2.34%, respectively. [Display omitted] • Train a new pruning pretraining model on DNA sequences to extract feature information. • The introduction of manually assisted features has expanded the search space for sequence feature. • Attention fusion strategy better promotes the fusion output of features from different dimensions. • The complementary nature of machine features and manual features better fits the target features. [ABSTRACT FROM AUTHOR]

This paper introduces a novel parameter related to bearing degradation, namely the Equivalent Damaged Volume (EDV). An algorithm capable of extracting EDV values from experimental data is detailed. To this end, the proposed technique relies on the comparison between experimental and numerical signals. The former are the result of an extensive campaign of run-to-failure tests performed on a dedicated test rig. On the other hand, the latter are obtained by means of a lumped parameter model that accounts for the angular extent and the depth of either localized or extended defects. The potential of this novel technique is demonstrated by exploiting the values obtained by the algorithm as inputs for a prognostic model. In particular, the developed model aims at predicting the time until a certain threshold on the equivalent damaged volume is crossed, regardless of the applied load and the shaft rotation speed. The advantages and downsides introduced by the proposed approach are thoroughly discussed by providing examples based on real degradation histories. [ABSTRACT FROM AUTHOR]

• A near-field weighted subspace fitting algorithm is proposed for ultrasonic guided wave multi-damage localization. • A near-field multi-dimensional solution search algorithm based on a niche particle swarm optimization is proposed, which effectively improves the efficiency of damage localization. • Algorithm performance comparison, finite element simulation, real point damage and slot damage experiments verify the effectiveness of the proposed method. The ultrasonic guided wave-based method for multi-damage localization has been widely proposed. However, the precision of this method is directly correlated with both the quantity of sensors employed and the intricacy of the implementation process. This relationship poses a challenge in striking a balance between the accuracy and efficiency. To improve the computational efficiency under the premise of ensuring the accuracy of multi-damage localization, this paper proposes a near-field weighted subspace fitting algorithm based on niche-particle swarm optimization. Firstly, the fitting relationship between the signal subspace of the diffraction wave and the array steering vector is established under the uniform linear array. Secondly, a multi-dimensional solution space search algorithm based on niche-particle swarm optimization is proposed to improve the search efficiency of damage. Finally, the algorithm is verified by performance comparison, finite element simulation and experiment. The results show that compared with the same type of method, the algorithm improves the computational efficiency by nearly threefold under the identifiable multi-damage conditions. Additionally, the angle error is 1 ∼ 6°, and the distance error is 1 ∼ 20 mm. [ABSTRACT FROM AUTHOR]

The Chow ring of the moduli space of stable marked curves is generated by Keel's divisor classes. The top graded part of this Chow ring is isomorphic to the integers, generated by the class of a single point. In this paper, we give an equivalent graphical characterization on the monomials in this Chow ring, as well as the characterization on the algebraic reduction on such monomials. Moreover, we provide an algorithm for computing the intersection degree of tuples of Keel's divisor classes — we call it the forest algorithm; the complexity of which is O (n 3) in the worst case, where n refers to the number of marks on the stable curves in the ambient moduli space. Last but not least, we introduce three identities on multinomial coefficients which naturally came into play, showing that they are all equivalent to the correctness of the base case of the forest algorithm. [ABSTRACT FROM AUTHOR]

In this paper we study the Shor relaxation of quadratic programs by fixing a feasible set and considering the space of objective functions for which the Shor relaxation is exact. We first give conditions under which this region is invariant under the choice of generators defining the feasible set. We then describe this region when the feasible set is invariant under the action of a subgroup of the general linear group. We conclude by applying these results to quadratic binary programs. We give an explicit description of objective functions where the Shor relaxation is exact and use this knowledge to design an algorithm that produces candidate solutions for binary quadratic programs. [ABSTRACT FROM AUTHOR]

Algorithmic stability is a fundamental concept in statistical learning theory to understand the generalization behavior of optimization algorithms. Existing high-probability bounds are developed for the generalization gap as measured by function values and require the algorithm to be uniformly stable. In this paper, we introduce a novel stability measure called pointwise uniform stability by considering the sensitivity of the algorithm with respect to the perturbation of each training example. We show this weaker pointwise uniform stability guarantees almost optimal bounds, and gives the first high-probability bound for the generalization gap as measured by gradients. Sharper bounds are given for strongly convex and smooth problems. We further apply our general result to derive improved generalization bounds for stochastic gradient descent. As a byproduct, we develop concentration inequalities for a summation of weakly-dependent vector-valued random variables. [ABSTRACT FROM AUTHOR]

Semi-filterless optical networks (semi-FONs), a novel passive wide area network (WAN) solution, have attracted considerable attention. This paper investigates the dynamic routing, modulation and spectrum assignment (RMSA) problem in semi-FONs, where requests may propagate on unnecessary links due to the broadcast characteristics of semi-FONs, resulting in wastage of spectrum resources. Moreover, the dynamically setup and torn down of requests can lead to significant spectrum fragments. To address these issues, this paper studies semi-FONs based on two metrics: resource consumption M and fragmentation degree N. Resource consumption M refers to reducing spectrum wastage caused by broadcasting and establishing requests using minimal resources, while fragmentation degree N refers to the situation where the remaining available resources after establishing a request are more concentrated. Based on these metrics, we propose the Minimum Resource Consumption and Fragmentation Degree (Min-RCF) algorithm. We conduct simulation experiments on the German-Net and China's Henan-Net network topologies, and the results demonstrate that the proposed Min-RCF algorithm achieves lower blocking probability and spectrum waste rate than the compared algorithms. • In the routing phase, resource consumption and spectrum wastage are reduced. • In the spectrum assignment phase, the spectrum fragmentation is reduced. • Reduced blocking probability and spectrum waste rate in the semi-filterless network. [ABSTRACT FROM AUTHOR]

CSIDH is an isogeny-based key exchange protocol proposed by Castryck et al. in 2018. It is based on the ideal class group action on F p -isomorphism classes of Montgomery curves. The original CSIDH algorithm requires a calculation over F p by representing points as x -coordinate over Montgomery curves. There is a special coordinate on Edwards curves (the w -coordinate) to calculate group operations and isogenies. If we try to calculate the class group action on Edwards curves by using the w -coordinate in a similar way on Montgomery curves, we have to consider points defined over F p 4 . Therefore, calculating the class group action on Edwards curves with w -coordinates over only F p is not a trivial task. In this paper, we prove some theorems about the properties of Edwards curves. We construct the new CSIDH algorithm using these theorems on Edwards curves with w -coordinates over F p. This algorithm is as fast as (or a little bit faster than) the algorithm proposed by Meyer and Reith. This paper is an extended version of [29]. We added the construction of a technique similar to Elligator on Edwards curves. This technique contributes to the efficiency of the constant-time CSIDH algorithm. We also added the construction of new formulas to compute isogenies in O ˜ (ℓ) time on Edwards curves. It is based on formulas on Montgomery curves proposed by Bernstein et al. ( élu's formulas). In our analysis, these formulas on Edwards curves are a little bit faster than those on Montgomery curves. We finally implemented CSIDH, élu's formulas, and CTIDH [3] (faster constant-time CSIDH) on Edwards curves. Each result shows the efficiency of algorithms on Edwards curves. [ABSTRACT FROM AUTHOR]