Search

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]

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]

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]

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]

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]

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]

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]

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]

• 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]

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]

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]

• 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]

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]

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]

The use of multiple independent spanning trees (ISTs) for data broadcasting in networks provides a number of advantages, including the increase of fault-tolerance and secure message distribution. Thus, the designs of multiple ISTs on several classes of networks have been widely investigated. Kao et al. (2019) [18] proposed an algorithm to construct independent spanning trees in bubble-sort networks. The algorithm is executed in a recursive function and thus is hard to parallelize. In this paper, we focus on the problem of constructing ISTs in bubble-sort networks B n and present a non-recursive algorithm. Our approach can be fully parallelized, i.e., every vertex can determine its parent in each spanning tree in constant time. This solves the open problem from the paper by Kao et al. Furthermore, we show that the total time complexity O (n ⋅ n !) of our algorithm is asymptotically optimal, where n is the dimension of B n and n ! is the number of vertices of the network. • We present an algorithm for constructing multiple independent spanning trees in bubble-sort networks. • Our approach can be fully parallelized, thus solving an open problem from Kao et al. (2019). • We show that the total time complexity of our algorithm is asymptotically optimal. [ABSTRACT FROM AUTHOR]

The vigorous development and the increasing popularity of cloud computing highlight the necessity of reducing data center energy consumption and the environmental impact of carbon dioxide emissions. For geographically distributed data centers, cloud servers are connected to the conventional power grid and in addition they are supported by an attached renewable energy source. Since the carbon footprint rate of energy consumption has dynamic differences in space, reducing energy consumption does not mean decrease carbon emission, which indicates that energy consumption and carbon footprint need to be synergistically optimized. In this paper, an energy and carbon-aware algorithm for virtual machine placement is proposed. The goal is to obtain a virtual machine allocation scheme that aims to achieve the trade-off between energy consumption and carbon emissions by improving renewable energy utilization. The experimental results show that the proposed approach is more energy-efficient and greener, which can also maximize the renewable energy utilization with 73.11% while ensuring the SLA violation with 0.2% in comparison to the baseline algorithms. • Propose a novel energy-aware VM placement approach in cloud data centers. • Introduce renewable energy for managing energy consumption and carbon footprint. • Design renewable energy generation prediction method based on EEMD and TCN. • Demonstrate the superiority of the proposed algorithm with five baseline algorithms. [ABSTRACT FROM AUTHOR]

The performance of collective communication operations determines the overall performance of MPI applications. Different algorithms have been developed and implemented for each MPI collective operation, but none proved superior in all situations. Therefore, MPI implementations have to solve the problem of selecting the optimal algorithm for the collective operation depending on the platform, the number of processes involved, the message size(s), etc. The current solution method is purely empirical. Recently, an alternative solution method using analytical performance models of collective algorithms has been proposed and proved both accurate and efficient for one-process-per-CPU configurations. The method derives the analytical performance models of algorithms from their code implementation rather than from high-level mathematical definitions, and estimates the parameters of the models separately for each algorithm. The method is network and topology oblivious and uses the Hockney model for point-to-point communications. In this paper, we extend that selection method to the case of clusters of multi-core processors, where each core of the platform runs a process of the MPI application. We present the proposed approach using Open MPI broadcast algorithms, and experimentally validate it on three different clusters of multi-core processors, Grisou, Gros and MareNostrum4. • A novel model-based method for runtime selection of optimal collective algorithms. • Application of the proposed method to the Open MPI broadcast algorithms. • Experimental validation of the method on two modern multi-core clusters. [ABSTRACT FROM AUTHOR]

• Our algorithm is more efficient, has less communication overhead, and has greater throughput than the original PBFT algorithm. • We propose a Vehicle - Service Provider - Roadside Unit architecture to ensure the orderliness and safety of vehicles. • We propose an identity authentication scheme based on blockchain. • Experimental results demonstrate that our solution is better than PBFT, G-PBFT and CPBFT. As an application of Internet of Things (IoT) technology, the Internet of Vehicles (IoV) faces two main security issues: (1) the central server of the IoV may not be powerful enough to support the centralized authentication of the rapidly increasing connected vehicles, (2) the IoV itself may not be robust enough to single-node attacks. To address these issues, in this paper, we propose SG-PBFT (Score Grouping-PBFT), a secure and efficient distributed consensus algorithm for blockchain applications in the IoV. The distributed structure can reduce the pressure on the central server and decrease the risk of single-node attacks. The SG-PBFT consensus algorithm improves the traditional practical Byzantine fault tolerance (PBFT) consensus algorithm by optimizing the PBFT consensus process and using a score grouping mechanism to achieve a higher consensus efficiency. The experimental results show that the method can greatly improve the consistency efficiency and effectively prevent single-node attacks. Specifically, when the number of consensus nodes reaches 1000, the consensus time of our algorithm is only about 27% of what is required for the state-of-the-art PBFT consensus algorithm. Our proposed SG-PBFT algorithm is versatile and can be used in other application scenarios which require high consensus efficiency. [ABSTRACT FROM AUTHOR]

The median of a set of vertices P of a graph G is the set of all vertices x of G minimizing the sum of distances from x to all vertices of P. In this paper, we present a linear time algorithm to compute medians in median graphs. We also present a linear time algorithm to compute medians in the associated ℓ 1 -cube complexes. Our algorithm is based on the majority rule characterization of medians in median graphs and on a fast computation of parallelism classes of edges (Θ-classes) via Lexicographic Breadth First Search (LexBFS). We show that any LexBFS ordering of the vertices of a median graph satisfies the following fellow traveler property : the parents of any two adjacent vertices are also adjacent. Using the fast computation of the Θ-classes, we also compute the Wiener index (total distance) in linear time and the distance matrix in optimal quadratic time. [ABSTRACT FROM AUTHOR]

Sparse polynomial interpolation, sparse linear system solving or modular rational reconstruction are fundamental problems in Computer Algebra. They come down to computing linear recurrence relations of a sequence with the Berlekamp–Massey algorithm. Likewise, sparse multivariate polynomial interpolation and multidimensional cyclic code decoding require guessing linear recurrence relations of a multivariate sequence. Several algorithms solve this problem. The so-called Berlekamp–Massey–Sakata algorithm (1988) uses polynomial additions and shifts by a monomial. The Scalar-FGLM algorithm (2015) relies on linear algebra operations on a multi-Hankel matrix, a multivariate generalization of a Hankel matrix. The Artinian Gorenstein border basis algorithm (2017) uses a Gram-Schmidt process. We propose a new algorithm for computing the Gröbner basis of the ideal of relations of a sequence based solely on multivariate polynomial arithmetic. This algorithm allows us to both revisit the Berlekamp–Massey–Sakata algorithm through the use of polynomial divisions and to completely revise the Scalar-FGLM algorithm without linear algebra operations. A key observation in the design of this algorithm is to work on the mirror of the truncated generating series allowing us to use polynomial arithmetic modulo a monomial ideal. It appears to have some similarities with Padé approximants of this mirror polynomial. As an addition from the paper published at the ISSAC conference, we give an adaptive variant of this algorithm taking into account the shape of the final Gröbner basis gradually as it is discovered. The main advantage of this algorithm is that its complexity in terms of operations and sequence queries only depends on the output Gröbner basis. All these algorithms have been implemented in Maple and we report on our comparisons. [ABSTRACT FROM AUTHOR]

In algebraic geometry, the Frobenius map (or called Frobenius action , or Frobenius operator) F ⁎ on cohomology groups plays an important role in the classification of algebraic varieties over a field of positive characteristic. In particular, representation matrices for F ⁎ give rise to many important invariants such as p -rank and a -number. Several methods for computing representation matrices for F ⁎ have been proposed for specific curves. In this paper, we present an algorithm to compute representation matrices for F ⁎ of general projective schemes over a perfect field of positive characteristic. We also propose an efficient algorithm specific to complete intersections; it requires to compute only certain coefficients in a power of a multivariate polynomial. Our algorithms shall derive fruitful applications such as computing Hasse-Witt matrices, and enumerating superspecial curves. In particular, the second algorithm for complete intersections provides a useful tool to judge the superspeciality of an algebraic curve, which is a key ingredient to prove main results in Kudo and Harashita (2017a,b, 2020) on the enumeration of superspecial genus-4 curves. [ABSTRACT FROM AUTHOR]

Consider an action of a connected solvable group G on an affine variety X. This paper presents an algorithm that constructs a semi-invariant f ∈ K [ X ] = : R and computes the invariant ring (R f) G together with a presentation. The morphism X f → Spec ((R f) G) obtained from the algorithm is a universal geometric quotient. In fact, it is even better than that: a so-called excellent quotient. If R is a polynomial ring, the algorithm requires no Gröbner basis computations. If R is a complete intersection, then so is (R f) G. [ABSTRACT FROM AUTHOR]

Read-only memory (ROM) model is a classical model of computation to study time-space tradeoffs of algorithms. More recently, several graph algorithms have been studied under ROM model. In this paper, we study graph algorithms under two different relaxations of ROM model, referred to as the implicit and rotate models, and show that these simple relaxations allow us to implement fundamental graph search methods like BFS and DFS more space efficiently than in ROM model. All our algorithms are simple but quite subtle, and we believe that these models are practical enough to spur interest for other graph problems in these models. [ABSTRACT FROM AUTHOR]

Satisfiability of word equations problem is: Given two sequences consisting of letters and variables decide whether there is a substitution for the variables that turns this equation into true equality. The exact computational complexity of this problem remains unknown, with the best lower and upper bounds being, respectively, NP and PSPACE. Recently, the novel technique of recompression was applied to this problem, simplifying the known proofs and lowering the space complexity to (non-deterministic) O (n log ⁡ n). In this paper we show that satisfiability of word equations is in non-deterministic linear space, thus the language of satisfiable word equations is context-sensitive. We use the known recompression-based algorithm and additionally employ Huffman coding for letters. The proof, however, uses analysis of how the fragments of the equation depend on each other as well as a new strategy for non-deterministic choices of the algorithm. [ABSTRACT FROM AUTHOR]

It has been shown that any nonblocking algorithm for work-stealing in the standard asynchronous shared memory model of computation must use expensive Read-After-Write synchronization patterns or atomic Read-Modify-Write instructions. Algorithms for relaxations of work-stealing have been proposed, which only partially avoid this impossibility result. In restricted models of computation, work-stealing algorithms have been designed that avoid Read-After-Write patterns and atomic Read-Modify-Write instructions. This paper considers work-stealing with multiplicity , a relaxation in which every task is taken by at least one process, and any process can take any task at most once. We study two variants of the relaxation, for each variant designing a Read / Write wait-free algorithm in the standard asynchronous shared memory model. The two algorithms are devoid of Read-After-Write synchronization patterns in all their operations, and additionally, the algorithm for the second variant has constant step complexity and is fence-free. Namely, no specific ordering among the algorithm's instructions is required beyond what is implied by data dependence. To our knowledge, these are the first algorithms for relaxations of work-stealing possessing all these properties. The algorithms are also solutions to relaxed versions of single-enqueuer multi-dequeuer queues. The theoretical results are complemented with an experimental evaluation showing that the benefits of relaxed work-stealing vary depending on the application, concretely on the complexity of the work associated with each task. • We present two asynchronous work-stealing algorithms with relaxation, work-stealing with multiplicity and weak-multiplicity. • In the first one, tasks are taken by at least one operation and if taken by several operations, they must be pairwise concurrent. • In the second one, Take/Steal operations extracting the same task may not be concurrent, however, each process extracts tasks at most once. • The algorithms are wait-free, read/write, and devoid of read-after-write synchronization patterns. • The proposed algorithms outperform standard work-stealing algorithms and exhibit similar or better performance than known relaxed algorithms in some practical settings. [ABSTRACT FROM AUTHOR]

We develop the first algorithm for computing rational solutions of scalar integro-differential equations with polynomial coefficients. It starts by finding the possible poles of a rational solution. Then, bounding the order of each pole and solving an algebraic linear system, we compute the singular part of rational solutions at each possible pole. Finally, using partial fraction decomposition, the polynomial part of rational solutions is obtained by computing polynomial solutions of a non-homogeneous scalar integro-differential equation with a polynomial right-hand side. The paper is illustrated by examples where the computations are done with our Maple implementation. [ABSTRACT FROM AUTHOR]

Mixed trigonometric-polynomials (MTPs) are functions of the form f (x , sin ⁡ x , cos ⁡ x) where f is a trivariate polynomial with rational coefficients, and the argument x ranges over the reals. In this paper, an algorithm "isolating" all the real roots of an MTP is provided and implemented. It automatically divides the real roots into two parts: one consists of finitely many roots in an interval [ μ − , μ + ] while the other consists of countably many roots in R ﹨ [ μ − , μ + ]. For the roots in [ μ − , μ + ] , the algorithm returns isolating intervals and corresponding multiplicities while for those greater than μ + , it returns finitely many mutually disjoint small intervals I i ⊂ [ − π , π ] , integers c i > 0 and multisets of root multiplicity { m j , i } j = 1 c i such that any root > μ + is in the set (∪ i ∪ k ∈ N (I i + 2 k π)) and any interval I i + 2 k π ⊂ (μ + , ∞) contains exactly c i distinct roots with multiplicities m 1 , i ,... , m c i , i , respectively. The efficiency of the algorithm is shown by experiments. The method used to isolate the roots in [ μ − , μ + ] is applicable to any other bounded interval as well. The algorithm takes advantages of the weak Fourier sequence technique and deals with the intervals period-by-period without scaling the coordinate so to keep the length of the sequence short. The new approaches can easily be modified to decide whether there is any root, or whether there are infinitely many roots in unbounded intervals of the form (− ∞ , a) or (a , ∞) with a ∈ Q. [ABSTRACT FROM AUTHOR]

Atomic Broadcast is an essential broadcast primitive as it ensures the consistency of distributed replicas. However, it is notoriously non-scalable. In this work, we introduce the Leaderless Hierarchical Atomic Broadcast (LHABcast) algorithm, which has two properties to improve scalability. First, it is a fully decentralized algorithm that does not rely on a sequencer/leader, which is often a significant bottleneck. Processes running LHABcast send messages with local sequence numbers and order messages received from other processes using timestamps inspired on Lamport's logical clocks. A process that receives the required set of timestamps can make a decision about the overall sequence of message delivery. Second, the algorithm is hierarchical: processes are organized on a vCube logical overlay network, which has several logarithmic properties and allows the construction of autonomous spanning trees. vCube also works as a failure detector, assuming crash faults and an asynchronous system model. In this paper, LHABcast is described, specified, and proven to be correct. Both simulation and experimental results are presented. A comparison with an all-to-all strategy shows that the number of messages sent by LHABcast is significantly lower in both fault-free and faulty scenarios. An implementation of LHABcast in Akka.io achieved up to 3.9 times higher throughput in fault-free scenarios than an implementation of the Raft-based Apache Ratis. • LHABcast is a fully decentralized leaderless algorithm broadcast algorithm. • LHABcast organizes processes on a vCube, which has several logarithmic properties. • LHABcast uses autonomic spanning trees rooted at the sender for message dissemination. • LHABcast is described with examples, and multiple properties are proved. • LHABcast was evaluated both with a Neko simulation and using the Java Akka framework. [ABSTRACT FROM AUTHOR]

Let G be a finite solvable group, given through a refined consistent polycyclic presentation, and α an automorphism of G , given through its images of the generators of G. In this paper, we discuss algorithms for computing the order of α as well as the cycle length of a given element of G under α. We give correctness proofs and discuss the theoretical complexity of these algorithms. Along the way, we carry out detailed complexity analyses of several classical algorithms on finite polycyclic groups. [ABSTRACT FROM AUTHOR]

Synchronous SGD with data parallelism, the most popular parallelization strategy for CNN training, suffers from the expensive communication cost of averaging gradients among all workers. The iterative parameter updates of SGD cause frequent communications and it becomes the performance bottleneck. In this paper, we propose a lazy parameter update algorithm that adaptively adjusts the parameter update frequency to address the expensive communication cost issue. Our algorithm accumulates the gradients if the difference of the accumulated gradients and the latest gradients is sufficiently small. The less frequent parameter updates reduce the per-iteration communication cost while maintaining the model accuracy. Our experimental results demonstrate that the lazy update method remarkably improves the scalability while maintaining the model accuracy. For ResNet50 training on ImageNet, the proposed algorithm achieves a significantly higher speedup (739.6 on 2048 Cori KNL nodes) as compared to the vanilla synchronous SGD (276.6) while the model accuracy is almost not affected (<0.2% difference). • Adaptive parameter update frequency control for scalable parallel deep learning. • Allowing gradient accumulation considering the direction of the gradients. • Reducing per-iteration communication cost at the input side model layers. • Overlapping gradient communications with backpropagation computations. [ABSTRACT FROM AUTHOR]

• Limited power of randomization in dealing with adaptive adversaries. • Derandomizing algorithms via simulation. • Simulating a dynamic network on top of another dynamic network. This paper investigates the power of randomization in general distributed algorithms in dynamic networks where the network's topology may evolve over time, as determined by some adaptive adversary. In such a context, randomization may help algorithms to better deal with i) "bad" inputs to the algorithm, and ii) evolving topologies generated by "bad" adaptive adversaries. We prove that randomness offers limited power to better deal with "bad" adaptive adversary. We define a simple notion of prophetic adversary for determining the evolving topologies. Such an adversary accurately predicts all randomness in the algorithm beforehand, and hence the randomness will be useless against "bad" prophetic adversaries. Given a randomized algorithm P whose time complexity satisfies some mild conditions, we prove that P can always be converted to a new algorithm Q with comparable time complexity, even when Q runs against prophetic adversaries. This implies that the benefit of P using randomness for dealing with the adaptive adversaries is limited. [ABSTRACT FROM AUTHOR]

• Improved distributed approximation for Steiner tree. • Approximation algorithms for Steiner tree in the CONGEST model of distributed computing. • Steiner tree problem in network optimization. In this paper we present two deterministic distributed algorithms for the Steiner tree (ST) problem in the CONGEST model. The first algorithm computes a 2 (1 − 1 / ℓ) -approximate ST using O (S + n log ⁎ ⁡ n) rounds and O (m S + n 3 / 2) messages for a graph of n nodes and m edges, where S is the shortest path diameter of the graph and ℓ is the number of leaf nodes in the optimal ST. It improves the round complexity of the best distributed ST algorithm known so far, which is O ˜ (S + min { S t , n }) [34] , where t is the number of terminal nodes. The second algorithm improves the message complexity of the first one by dropping the additive term of O (n 3 / 2) at the expense of a logarithmic multiplicative factor in the round complexity. We also show that for graphs with S = O (log ⁡ n) , a 2 (1 − 1 / ℓ) -approximate ST can be deterministically computed using O ˜ (n) rounds and O ˜ (m) messages and these complexities almost coincide with the results of some of the singularly-optimal minimum spanning tree (MST) algorithms proposed in [15,22,37]. [ABSTRACT FROM AUTHOR]

• Propose the aligned storage formats ACSR and AELL. • Put forward a parallel SpMV algorithm based on ACSR and AELL formats. • Theoretically analyze the performance of SpMV on ARM processors. • Evaluate the performance of our optimization on Kunpeng 920 processors. Sparse matrix-vector multiplication (SpMV) has always been a hot topic of research for scientific computing and big data processing, but the sparsity and discontinuity of the nonzero elements in a sparse matrix lead to the memory bottleneck of SpMV. In this paper, we propose aligned CSR (ACSR) and aligned ELL (AELL) formats and a parallel SpMV algorithm to utilize NEON SIMD registers on ARM processors. We analyze the impact of SIMD instruction latency, cache access, and cache misses on SpMV with different formats. In the experiments, our SpMV algorithm based on ACSR achieves 1.18x and 1.56x speedup over SpMV based on CSR and SpMV in PETSc, respectively, and AELL achieves 1.21x speedup over ELL. The deviations between the theoretical results and experimental results in the instruction latency and cache access are 10.26% and 10.51% in ACSR and 5.68% and 2.91% in AELL, respectively. [ABSTRACT FROM AUTHOR]

Failure detectors (FD)s are celebrated for their modularity in solving distributed problems. Algorithms are constructed using FD building blocks. Synchrony assumptions to implement FDs are studied separately and are typically expressed as eventual guarantees that need to hold, after some point in time, forever and deterministically. But in practice, they may hold only probabilistically and temporarily. This paper studies FDs in a realistic system N , where asynchrony is inflicted by probabilistic synchronous communication. We first address a problem with ⋄ S , the weakest FD to solve consensus: an implementation of "consensus with probability 1" is possible in N without randomness in the algorithm, while an implementation of " ⋄ S with probability 1" is impossible in N. We introduce ⋄ S ⁎ , a new FD with probabilistic and temporal accuracy. We prove that ⋄ S ⁎ (i) is implementable in N and (ii) can replace ⋄ S , in several existing deterministic consensus algorithms that use ⋄ S , to yield an algorithm that solves "consensus with probability 1". We extend our results to other FD classes, e.g., ⋄ P , and to a larger set of problems (beyond consensus), which we call decisive problems. • We propose a way to preserve the usefulness of failure detectors (FD)s as software building blocks in probabilistically synchronous systems as (N). • We define <>S*, a probabilistic FD with accuracy ensured for arbitrarily long finite periods and that can be implemented in systems as N. • We present an optimal <>S* algorithm, which achieves in the best case the lowest communication overhead (C-1) compared to all known <>S algorithms. • We extend our FD definitions for other FD classes and other distributed computing problems besides consensus, which we call decisive problems. • We encapsulate the randomization of probabilistic links in the very abstraction of FD, without affecting deterministic algorithms built on top. [ABSTRACT FROM AUTHOR]

In this paper, we prove a supercongruence via the Wilf–Zeilberger method and symbolic summation algorithms in the setting of difference rings. That is, for any prime p > 3 , ∑ n = 0 (p − 1) / 2 3 n + 1 (− 8) n ( 2 n n ) 3 ≡ p (− 1 p) + p 3 4 (2 p) E p − 3 (1 4) (mod p 4) , where (⋅ p) stands for the Legendre symbol, and E n (x) are the Euler polynomials. This confirms a special case of a recent conjecture of Z.-W. Sun (Sun, 2019 , (2.18)). [ABSTRACT FROM AUTHOR]

We show how the classical notions of cohomology with local coefficients, CW-complex, covering space, homeomorphism equivalence, simple homotopy equivalence, tubular neighbourhood, and spinning can be encoded on a computer and used to calculate ambient isotopy invariants of continuous embeddings N ↪ M of one topological manifold into another. More specifically, we describe an algorithm for computing the homology H n (X , A) and cohomology H n (X , A) of a finite connected CW-complex X with local coefficients in a Z π 1 X -module A when A is finitely generated over Z. It can be used, in particular, to compute the integral cohomology H n ( X ˜ H , Z) and induced homomorphism H n (X , Z) → H n ( X ˜ H , Z) for the covering map p : X ˜ H → X associated to a finite index subgroup H < π 1 X , as well as the corresponding homology homomorphism. We illustrate an open-source implementation of the algorithm by using it to show that: (i) the degree 2 homology group H 2 ( X ˜ H , Z) distinguishes between the homotopy types of the complements X ⊂ R 4 of the spun Hopf link and Satoh's tube map of the welded Hopf link (these two complements having isomorphic fundamental groups and integral homology); (ii) the degree 1 homology homomorphism H 1 (p − 1 (B) , Z) → H 1 ( X ˜ H , Z) distinguishes between the homeomorphism types of the complements X ⊂ R 3 of the granny knot and the reef knot, where B ⊂ X is the knot boundary (these two complements again having isomorphic fundamental groups and integral homology). Our open source implementation allows the user to experiment with further examples of knots, knotted surfaces, and other embeddings of spaces. We conclude the paper with an explanation of how the cohomology algorithm also provides an approach to computing the set [ W , X ] ϕ of based homotopy classes of maps f : W → X of finite CW-complexes over a fixed group homomorphism π 1 f = ϕ in the case where dim ⁡ W = n , π 1 X is finite and π i X = 0 for 2 ≤ i ≤ n − 1. [ABSTRACT FROM AUTHOR]

The sparse difference resultant introduced in Li et al. (2015b) is a basic concept in difference elimination theory. In this paper, we show that the sparse difference resultant of a generic Laurent transformally essential system can be computed via the sparse resultant of a simple algebraic system arising from the difference system. Moreover, new order bounds of sparse difference resultant are found. Then we propose an efficient algorithm to compute sparse difference resultant which is the quotient of two determinants whose elements are the coefficients of the polynomials in the algebraic system. The complexity of the algorithm is analyzed and experimental results show the efficiency of the algorithm. [ABSTRACT FROM AUTHOR]