386 results
Search Results
2. Simplified Algorithm for the Worldvolume HMC and the Generalized Thimble HMC.
- Author
-
Fukuma, Masafumi
- Subjects
MONTE Carlo method ,JACOBIAN matrices ,NEWTON-Raphson method ,ORTHOGONAL decompositions ,ORTHOGONAL functions ,ALGORITHMS - Abstract
The Worldvolume Hybrid Monte Carlo method (WV-HMC method) is a reliable and versatile algorithm towards solving the sign problem. Like the tempered Lefschetz thimble method, this method removes the ergodicity problem inherent in algorithms based on Lefschetz thimbles. In addition to this advantage, the WV-HMC method significantly reduces the computational cost because one need not compute the Jacobian of deformation in generating configurations. A crucial step in this method is the RATTLE algorithm, where the Newton method is used at each molecular dynamics step to project a transported configuration onto a submanifold (worldvolume) in the complex space. In this paper, we simplify the RATTLE algorithm by employing a simplified Newton method (the fixed-point method) along with iterative solvers for orthogonal decompositions of vectors, and show that this algorithm further reduces the computational cost. We also apply this algorithm to the HMC algorithm for the generalized thimble method (GT-HMC method). We perform a numerical test for the convergence of the simplified RATTLE algorithm, and show that the convergence depends on the system size only weakly. The application of this simplified algorithm to various models will be reported in subsequent papers. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
3. A novel memetic algorithm for solving the generalized traveling salesman problem.
- Author
-
Cosma, Ovidiu, Pop, Petrică C, and Cosma, Laura
- Subjects
TRAVELING salesman problem ,ALGORITHMS ,HUMAN chromosomes - Abstract
This paper investigates the Generalized Traveling Salesman Problem (GTSP), which is an extension of the well-known Traveling Salesman Problem (TSP), and it searches for an optimal tour in a clustered graph, such that every cluster is visited exactly once. In this paper, we describe a novel Memetic Algorithm (MA) for solving efficiently the GTSP. Our proposed MA has at its core a genetic algorithm (GA), completed by a Chromosome Enhancement Procedure (CEP), which is based on a TSP solver and the Shortest Path (SP) algorithm and for improving the convergence characteristics of the GA, a Local Search (LS) operation is applied for the best chromosomes in each generation. We tested our algorithm on a set of well-known instances from the literature and the achieved results prove that our novel memetic algorithm is highly competitive against the existing solution approaches from the specialized literature. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
4. InstaPrism: an R package for fast implementation of BayesPrism.
- Author
-
Hu, Mengying and Chikina, Maria
- Subjects
SOURCE code ,GENE expression ,HETEROGENEITY ,ALGORITHMS ,SPEED ,GIBBS sampling ,DECONVOLUTION (Mathematics) - Abstract
Summary Computational cell-type deconvolution is an important analytic technique for modeling the compositional heterogeneity of bulk gene expression data. A conceptually new Bayesian approach to this problem, BayesPrism, has recently been proposed and has subsequently been shown to be superior in accuracy and robustness against model misspecifications by independent studies; however, given that BayesPrism relies on Gibbs sampling, it is orders of magnitude more computationally expensive than standard approaches. Here, we introduce the InstaPrism package which re-implements BayesPrism in a derandomized framework by replacing the time-consuming Gibbs sampling step with a fixed-point algorithm. We demonstrate that the new algorithm is effectively equivalent to BayesPrism while providing a considerable speed and memory advantage. Furthermore, the InstaPrism package is equipped with a precompiled, curated set of references tailored for a variety of cancer types, streamlining the deconvolution process. Availability and implementation The package InstaPrism is freely available at: https://github.com/humengying0907/InstaPrism. The source code and evaluation pipeline used in this paper can be found at: https://github.com/humengying0907/InstaPrismSourceCode. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
5. A novel fully distributed discrete-time min–max consensus seeking algorithm with high convergence speed.
- Author
-
Rezaei, Vahid and Khanmirza, Esmaeel
- Subjects
- *
ALGORITHMS , *SPEED , *DATA transmission systems , *TECHNOLOGY convergence - Abstract
In this paper, we propose a novel discrete-time consensus algorithm based on the new min–max criterion for the discrete-time second-order linear agents. To boost the convergence speed, the proposed algorithm allocates three different operating modes to the network agents. Unlike most of the existing consensus algorithms in which the links of the communication graph have specific weights and these weights are required to have positive lower bounds to achieve asymptotic convergence, the communication graph in this paper has unspecific link weights. Accordingly, because of data transmission errors and faults, the weights of the communication links can even go from a positive to a negative value. Thus, the proposed algorithm can bring the agents to consensus under more general conditions. To demonstrate the efficacy of the proposed algorithm, numerical simulations are performed, and their results are compared with those of the minimum consensus algorithm, which shows a significantly faster convergence speed. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
6. real-time lucky imaging algorithm based on Fourier transform and its implementation techniques.
- Author
-
Huang, Xueming, Li, Binhua, Wang, Jinliang, and Li, Junwu
- Subjects
FIELD programmable gate arrays ,ATMOSPHERIC turbulence ,IMAGE reconstruction ,ALGORITHMS - Abstract
Lucky imaging is a high-angular-resolution astronomical image reconstruction technique which can effectively reduce or remove the effects of atmospheric turbulence. There have been successful real-time lucky imaging algorithms and corresponding implementations in the spatial domain. Although the results of lucky imaging algorithms in the frequency domain are better than in the spatial domain, until now there has been no corresponding real-time algorithm and implementation due to its complexity. This paper proposes a real-time lucky imaging algorithm based on Fourier transform that features real-time processing and dynamic updating and display. The algorithm is implemented on a small- or medium-scale field programmable gate array (FPGA) development board. In this system, a two-dimensional fast Fourier transform of the image is carried out by means of dimension reduction. In order to achieve real-time lucky imaging in the frequency domain, the sum of the squares of the real and imaginary parts are used to replace the amplitude for data selection, and the method of image grouping is used to speed up the data selection. Compared with other real-time lucky imaging algorithms in the spatial domain, this algorithm shows great advantages in image quality. Moreover, the system can carry out real-time lucky imaging processing in the frequency domain for more than 10000 frames of an original image of 512 × 512 pixels continuously, and dynamic display with an image of 128 × 128 pixels. The experimental results illustrate the validity of the proposed algorithm and the feasibility of the proposed implementation techniques for the FPGA-based algorithm. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
7. Reply to comment on Geophysical inversion and Optimal Transport, 231, 172–198, by Okazaki & Ueda.
- Author
-
Sambridge, Malcolm, Jackson, Andrew, and Valentine, Andrew P
- Subjects
WAVE analysis ,GROUND penetrating radar ,ELECTRON tube grids ,ALGORITHMS - Abstract
Concerns raised by Okazaki & Ueda (2022) on the paper by Sambridge et al. (2022) are addressed. Two issues are discussed and some new numerical results presented. The first concerns whether the properties of the Wasserstein time-series misfit introduced in our earlier paper will translate to model space non-uniqueness in a seismic waveform inversion setting. It is argued that this is unlikely, given the special conditions, which must exist between all observed/predicted seismic waveform pairs for non-uniqueness to result. The second issue discussed is the efficacy of using the Sliced Wasserstein algorithm of Bonneel et al. (2015) as an alternate to the marginal Wasserstein algorithm, as proposed by Okazaki & Ueda (2022). It is argued that for optimization-based waveform fitting, the Sliced Wasserstein algorithm is a viable alternate provided care is taken to ensure that conditions arise which do invalidate analytical derivative expressions of the resulting Wasserstein misfit. In practice, this would likely mean recasting the 2D Optimal Transport problem posed in our earlier paper onto unstructured grids. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
8. Efficient Parameter Server Placement for Distributed Deep Learning in Edge Computing.
- Author
-
Wu, Yalan, Yan, Jiaquan, Chen, Long, Wu, Jigang, and Li, Yidong
- Subjects
APPROXIMATION algorithms ,DEEP learning ,EDGE computing ,NP-hard problems ,PROBLEM solving ,ALGORITHMS - Abstract
Parameter servers (PSs) placement is one of the most important factors for global model training on distributed deep learning. This paper formulates a novel problem for placement strategy of PSs in the dynamic available storage capacity, with the objective of minimizing the training time of the distributed deep learning under the constraints of storage capacity and the number of local PSs. Then, we provide the proof for the NP-hardness of the proposed problem. The whole training epochs are divided into two parts, i.e. the first epoch and the other epochs. For the first epoch, an approximation algorithm and a rounding algorithm are proposed in this paper, to solve the proposed problem. For the other epochs, an adjustment algorithm is proposed, by continuously adjusting the decisions for placement strategy of PSs to decrease the training time of the global model. Simulation results show that the proposed approximation algorithm and rounding algorithm perform better than existing works for all cases, in terms of the training time of global model. Meanwhile, the training time of global model for the proposed approximation algorithm is very close to that for optimal solution generated by the brute-force approach for all cases. Besides, the integrated algorithm outperforms the existing works when the available storage capacity varies during the training. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
9. Probabilistic Proofs, Lottery Propositions, and Mathematical Knowledge.
- Author
-
Hamami, Yacin
- Subjects
PROPOSITION (Logic) ,PROBABILITY theory ,FUNDAMENTAL theorem of calculus ,ALGORITHMS ,MATHEMATICIANS - Abstract
In mathematics, any form of probabilistic proof obtained through the application of a probabilistic method is not considered as a legitimate way of gaining mathematical knowledge. In a series of papers, Don Fallis has defended the thesis that there are no epistemic reasons justifying mathematicians' rejection of probabilistic proofs. This paper identifies such an epistemic reason. More specifically, it is argued here that if one adopts a conception of mathematical knowledge in which an epistemic subject can know a mathematical proposition based solely on a probabilistic proof, one is then forced to admit that such an epistemic subject can know several lottery propositions based solely on probabilistic evidence. Insofar as knowledge of lottery propositions on the basis of probabilistic evidence alone is denied by the vast majority of epistemologists, it is concluded that this constitutes an epistemic reason for rejecting probabilistic proofs as a means of acquiring mathematical knowledge. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
10. A simple weighting method for inverting earthquake source parameters using geodetic multisource data under Bayesian algorithm.
- Author
-
Xi, Can, Wang, Leyang, Zhao, Xiong, Sun, Zhanglin, Zhao, Weifeng, Pang, Ming, and Wu, Fei
- Subjects
- *
EARTHQUAKES , *STANDARD deviations , *CONSTRAINT algorithms , *GEODESICS , *SEARCH algorithms , *ANGLES , *ALGORITHMS - Abstract
More accurate inversion of source fault geometry and slip parameters under the constraint of the Bayesian algorithm has become a research hotspot in the field of geodetic inversion in recent years. In nonlinear inversion, the determination of the weight ratio of the joint inversion of multisource data is more complicated. In this context, this paper proposes a simple and easily generalized weighting method for inversion of source fault parameters by joint geodetic multisource data under the Bayesian framework. This method determines the relative weight ratio of multisource data by root mean square error (RMSE) value and can be extended to other nonlinear search algorithms. To verify the validity of the method in this paper, this paper first sets up four sets of simulated seismic experiment schemes. The inversion results show that the joint inversion weighting method proposed in this paper has a significant decrease in the large residual value compared with the equal weight joint inversion and the single data source joint inversion method. The east–west deformation RMSE is 0.1458 mm, the north–south deformation RMSE is 0.2119 mm and the vertical deformation RMSE is 0.2756 mm. The RMSEs of the three directions are lower than those of other schemes, indicating that the proposed method is suitable for the joint inversion of source parameters under Bayesian algorithm. To further verify the applicability of the proposed method in complex earthquakes, the source parameters of the Maduo earthquake were inverted using the method of this paper. The focal depth of the inversion results in this paper is closer to the focal depth released by the GCMT agency. In terms of strike angle and dip angle, the joint inversion in this paper is also more inclined to the GCMT results. The joint inversion results generally conform to the characteristics of left-lateral strike-slip, which shows the adaptability of this method in complex earthquakes. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
11. Committee-Based Blockchains as Games between Opportunistic Players and Adversaries.
- Author
-
Amoussou-Guenou, Yackolley, Biais, Bruno, Potop-Butucaru, Maria, and Tucci-Piergiovanni, Sara
- Subjects
BLOCKCHAINS ,COMMITTEES ,GAMES ,COMPUTER network protocols ,ALGORITHMS - Abstract
We study consensus in a protocol capturing in a simplified manner the major features of the majority of Proof of Stake blockchains. A committee is formed; one member proposes a block; and the others can check its validity and vote for it. Blocks with a majority of votes are produced. When an invalid block is produced, the stakes of the members who voted for it are "slashed." Profit-maximizing members interact with adversaries seeking to disrupt consensus. When slashing is limited, free-riding and moral-hazard lead to invalid blocks in equilibrium. We propose a protocol modification producing only valid blocks in equilibrium. Authors have furnished an Internet Appendix , which is available on the Oxford University Press Web site next to the link to the final published paper online. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
12. A Self-Stabilizing Distributed Algorithm for the Generalized Dominating Set Problem With Safe Convergence.
- Author
-
Kobayashi, Hisaki, Sudo, Yuichi, Kakugawa, Hirotsugu, and Masuzawa, Toshimitsu
- Subjects
DOMINATING set ,DISTRIBUTED algorithms ,ALGORITHMS - Abstract
A self-stabilizing distributed algorithm is guaranteed eventually to reach and stay at a legitimate configuration regardless of the initial configuration of a distributed system. In this paper, we propose the generalized dominating set problem, which is a generalization of the dominating set and |$k$| -redundant dominating set problems. In the generalized dominating set we propose in this paper, each node |$P_{i}$| is given its set of domination wish sets, and a generalized dominating set is a set of nodes such that each node is contained in the set or has a wish set in which all its members are in the set. We propose a self-stabilizing distributed algorithm for finding a minimal generalized dominating set in an arbitrary network under the unfair distributed daemon. The proposed algorithm converges in |$O(n^{3}m)$| steps and |$O(n)$| rounds, where |$n$| (resp. |$m$|) is the number of nodes (resp. edges). Furthermore, it has the safe convergence property with safe convergence time in |$O(1)$| rounds. The space complexity of the proposed algorithm is |$O(\Delta \log n)$| bits per node, where |$\Delta $| is the maximum degree of nodes. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
13. Efficient Algorithms For Storage Load Balancing Of Outsourced Data In Blockchain Network.
- Author
-
Liu, Tonglai, Wu, Jigang, Li, Jiaxing, Li, Jingyi, and Zhang, Zikai
- Subjects
BLOCKCHAINS ,TABU search algorithm ,CRYPTOCURRENCIES ,HEURISTIC algorithms ,ALGORITHMS ,GENETIC algorithms ,STORAGE - Abstract
Decentralized storage of data is one of the typical applications in the blockchain network. However, most of the existing works neglected the storage balancing problem in the blockchain network, which has an immediate impact on the availability and stability of the network. Therefore, this paper proposes a storage balancing problem for non-local data storage in the blockchain network and proves that the problem is non-deterministic polynomial (NP)-hard. The criterion of the storage balance is established by a balanced coefficient in the proposed scheme. A heuristic matching algorithm (HMA), a genetic algorithm (GA) and a tabu search algorithm (TSA) are customized to solve the problem of imbalanced storage formalized in this paper. Compared with our previous algorithm fast matching algorithm (FMA), experimental results demonstrate that HMA achieves better performance in terms of accuracy, computation overhead and storage overhead. Specifically, the computation overhead of HMA is lower than that of FMA by 84.45% on average, whereas the storage overhead of HMA is lower than that of FMA by 32.26% on average. By using the initial solution of HMA, TSA achieves the highest accuracy among GA, TSA and moth-flame optimization (MFO). Meanwhile, by using the initial solution of FMA, TSA achieves the highest accuracy among GA, TSA and MFO. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
14. Read-once refutations in Horn constraint systems: an algorithmic approach.
- Author
-
Subramani, K, Wojciechowski, Piotr, and Sheng, Ying
- Subjects
NUMBER systems ,LINEAR systems ,ALGORITHMS ,TIME management ,APPROXIMATION algorithms - Abstract
In this paper, we discuss exact and parameterized algorithms for the problem of finding a read-once refutation (ROR) in an unsatisfiable Horn constraint system (HCS). Recall that a linear constraint system |$\mathbf {A \cdot x \ge b}$| is said to be an HCS if each entry in |$\textbf {A}$| belongs to the set |$\{0,1,-1\}$| and at most one entry in each row of |$\textbf {A}$| is positive. In this paper, we examine the importance of constraints in which more variables have negative coefficients than positive coefficients. In particular, we study the impact of the proportion of these 'net-negative' constraints has on the difficulty of finding RORs. There exist several algorithms for checking whether an HCS is feasible. To the best of our knowledge, these algorithms are not certifying, i.e. they do not provide a certificate of infeasibility. Our work is concerned with providing a specialized class of certificates called 'read-once refutations'. In an ROR, each constraint defining the HCS may be used at most once in the derivation of a refutation. The problem of checking if an HCS has an ROR has been shown to be NP-hard. We analyse the HCS ROR problem from three different algorithmic perspectives, viz. parameterized algorithms, exact exponential algorithms and approximation algorithms. In particular, we show that the HCS ROR problem is fixed-parameter tractable (FPT) with respect to the number of constraints in the system that have more variables with negative coefficient than variables with positive coefficient. Additionally, we show that the HCS ROR problem becomes easy when this parameter is both small and large. We also derive an algorithm that runs in time |$O(1.66^{m})$| , where |$m$| is the number of constraints in the HCS. On the lower-bound side, we derive a lower bound on the algorithmic resources needed for this problem using the Exponential Time Hypothesis. We also establish that the HCS ROR problem does not have a polynomial kernel when the number of constraints with three or more variables in a refutation is used as a parameter. Finally, we show that the problem of approximating the length of the shortest ROR in an HCS is NPO PB-complete
1 . [ABSTRACT FROM AUTHOR]- Published
- 2022
- Full Text
- View/download PDF
15. A Principle-based Account of Self-attacking Arguments in Gradual Semantics.
- Author
-
Beuselinck, Vivien, Delobelle, Jérôme, and Vesic, Srdjan
- Subjects
SEMANTICS ,ARGUMENT ,GENERAL semantics ,SCHOLARS ,ALGORITHMS - Abstract
The issue of how a semantics should deal with self-attacking arguments was always a subject of debate among argumentation scholars. A consensus exists for extension-based semantics because those arguments are always rejected (as soon as the semantics in question respects conflict-freeness). In case of gradual semantics, the question is more complex, since other criteria are taken into account. In this paper, we check the impact of those arguments by using a principle-based approach. Principles like self-contradiction and strong self-contradiction prescribe how to deal with self-attacking arguments. We show that they are incompatible with the well-known equivalence principle (which is satisfied by almost all the existing gradual semantics), as well as with some other principles (e.g. counting). This incompatibility was not studied until now and the class of semantics satisfying self-contradiction is under-explored. In the present paper, we explore that class of semantics. We show links and incompatibilities between several principles. We define a new general oriented argumentation semantics that satisfies (strong) self-contradiction and a maximal number of compatible principles. We introduce an iterative algorithm to calculate our semantics and prove that it always converges. We also provide a characterization of our semantics. Finally, we experimentally show that our semantics is computationally efficient. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
16. Lifting propositional proof compression algorithms to first-order logic.
- Author
-
Gorzny, Jan, Postan, Ezequiel, and Paleo, Bruno Woltzenlogel
- Subjects
FIRST-order logic ,PROPOSITION (Logic) ,ALGORITHMS - Abstract
Proofs are a key feature of modern propositional and first-order theorem provers. Proofs generated by such tools serve as explanations for unsatisfiability of statements. However, these explanations are complicated by proofs which are not necessarily as concise as possible. There are a wide variety of compression techniques for propositional resolution proofs but fewer compression techniques for first-order resolution proofs generated by automated theorem provers. This paper describes an approach to compressing first-order logic proofs based on lifting proof compression ideas used in propositional logic to first-order logic. The first approach lifted from propositional logic delays resolution with unit clauses , which are clauses that have a single literal. The second approach is partial regularization , which removes an inference |$\eta $| when it is redundant in the sense that its pivot literal already occurs as the pivot of another inference in every path from |$\eta $| to the root of the proof. This paper describes the generalization of the algorithms LowerUnits and RecyclePivotsWithIntersection (Fontaine et al.. Compression of propositional resolution proofs via partial regularization. In Automated Deduction—CADE-23—23rd International Conference on Automated Deduction, Wroclaw, Poland, July 31–August 5, 2011 , p. 237--251. Springer, 2011) from propositional logic to first-order logic. The generalized algorithms compresses resolution proofs containing resolution and factoring inferences with unification. An empirical evaluation of these approaches is included. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
17. Smart Multimedia Compressor—Intelligent Algorithms for Text and Image Compression.
- Author
-
Oswald, C and Sivaselvan, B
- Subjects
IMAGE compression ,DATA compression ,ALGORITHMS ,DATA mining ,GRAPHICAL user interfaces ,COMPRESSORS - Abstract
A number of text compression algorithms have been proposed in the past decades, which have been very effective and usually operate on conventional character/word-based approaches. A novel data compression perspective of data mining is explored in this research and the paper focuses on novel frequent sequence/pattern mining approach to text compression. This work attempts to make use of longer-range correlations between words in languages for achieving better text compression. We propose a novel and efficient method by making the compression of any word-level text in a universal manner for corpora across domains referred as Universal Huffman Tree-based encoding. The major contribution of this work is in terms of avoidance of code table communication to the decoder. Simulation results over benchmark datasets indicate that Universal Huffman encoding employing frequent sequence mining (achieves [20%, 89%] improvement in compression in reduced time. The paper also contributes a usable interface for Data compression that employs the proposed frequent sequent mining-based data compression algorithm. The interface supports features such as feedback, consistency, usability, navigation, visual appeal, performance and accessibility on par with existing compression softwares. The work results in an intelligent data compression software employing knowledge engineering perspective. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
18. Algorithm to Construct Completely Independent Spanning Trees in Line Graphs.
- Author
-
Wang, Yifeng, Cheng, Baolei, Fan, Jianxi, Qian, Yu, and Jiang, Ruofan
- Subjects
SPANNING trees ,TREE graphs ,TIMBERLINE ,HYPERCUBES ,MOLECULAR connectivity index ,ALGORITHMS - Abstract
In the past few years, much importance and attention have been attached to completely independent spanning trees (CISTs). Many results, such as edge-disjoint Hamilton cycles, traceability, number of spanning trees, structural properties, topological indices, etc. have been obtained on line graphs, and researchers have applied the line graphs of some interconnection networks such as generalized hypercubes, augmented cubes, crossed cubes, etc. into data center networks, such as SWCube, AQLCube, BCDC, etc. At the meanwhile, few results of CISTs are reported on the line graphs. In this paper, we establish the relation of edge-disjoint spanning trees in an interconnection network |$G$| ' with its line graph |$G$| by proposing a general algorithm for the first time. By this method, more CISTs can be obtained comparing with results in the literature. Then, the decrease of diameter is discussed and simulation experiments are shown on the line graphs of hypercubes. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
19. Hyperbolic Jigsaws and Families of Pseudomodular Groups II.
- Author
-
Lou, Beicheng, Tan, Ser Peow, and Vo, Anh Duc
- Subjects
CENTROIDAL Voronoi tessellations ,ALGORITHMS - Abstract
In our previous paper [ 5 ], we introduced a hyperbolic jigsaw construction and constructed infinitely many noncommensurable, nonuniform, non-arithmetic lattices of |$\textrm{PSL}(2,{\mathbb R})$| with cusp set |$\mathbb{Q} \cup \{\infty \}$| (called pseudomodular groups by Long and Reid [ 4 ]), thus answering a question posed by Long and Reid. In this paper, we continue with our study of these jigsaw groups exploring questions of arithmeticity, pseudomodularity, and also related pseudo-Euclidean and continued fraction algorithms arising from these groups. We also answer another question of Long and Reid [ 4 ] by demonstrating a recursive formula for the tessellation of the hyperbolic plane arising from Weierstrass groups, which generalizes the well-known "Farey addition" used to generate the Farey tessellation. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
20. The changing face of anti-trust in the world of Big Tech: Collusion versus Monopolisation.
- Author
-
Armoogum, Prishnee, Davies, Stephen, and Mariuzzo, Franco
- Abstract
This paper presents new evidence on two key developments in worldwide anti-trust in the last decade: (i) a downturn in the number of cartels detected by competition authorities and (ii) exponential growth in cases of monopolisation/abuse of dominance. Big Tech firms have been, undoubtedly, the main focus of the latter but almost totally absent in the former. These two developments offer perspectives on the description of Monopoly Capitalism as set out by Keith Cowling 40 years ago. Superficially at least, this seems to deny the prediction of ever-widening collusion, but, on the other hand, it resonates with the prediction of increasingly unassailable dominant firms. We suggest that the two trends can best be understood by the emergence of the Big Tech giants who have established dominance by exceeding tipping points in many markets. In turn, this leads to an alternative form of collusion— ‘mutual forbearance’ in which firms back away from aggressive competition in the other giants’ areas of strength. Given this dominance, they do not need collusion— put simply, no sizeable rivals are remaining with whom they need to collude. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
21. Improved Collision Detection Of MD5 Using Sufficient Condition Combination.
- Author
-
Shen, Yanzhao, Wu, Ting, Wang, Gaoli, Dong, Xinfeng, and Qian, Haifeng
- Subjects
ALGORITHMS - Abstract
Counter-cryptanalysis uses cryptanalytic techniques to detect cryptanalytic attacks. It was introduced by Stevens with a collision detection algorithm that detects whether a message is one of a colliding message pair constructed using a collision attack. Later, Stevens and Shumow improved the collision detection against SHA-1 by using unavoidable conditions. However, there are no results improving collision detection against MD5 due to its weak diffusion properties. In this paper, an improved collision detection algorithm against MD5 is proposed by using the 14-bit sufficient condition combinations. This leads to the dividing the 223 classes into four sets. Each element, belonging to the first two sets, holds the same sufficient condition combination. Our new algorithm can classify 126 classes efficiently. The runtime is 28.6% of the previous collision detection method. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
22. Transcribing in the digital age: qualitative research practice utilizing intelligent speech recognition technology.
- Author
-
Eftekhari, Helen
- Subjects
- *
AUTOMATIC speech recognition , *DIGITAL technology , *DOCUMENTATION , *COST control , *DATA security , *COMPARATIVE grammar , *TRANSLATIONS , *INTERVIEWING , *ALGORITHMS , *TIME ,RESEARCH evaluation - Abstract
The digital revolution provides many opportunities for researchers to develop and evolve data collection methods. A key process in qualitative research data collection is the transcription of interviews, focus groups or fieldwork notes. Transcription is the process of converting audio, video or notes into accessible written format for qualitative data analysis. Transcribing can be time intensive, costly and laborious with decisions and methods of transcribing requiring transparency. The development of intelligent speech recognition technology can change how qualitative data is transcribed. This methods paper describes audio data transcribing, current challenges, opportunities and implications in using intelligent speech recognition technology for transcribing. An application of this methodology is presented. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
23. A posteriori error estimates for fully coupled McKean–Vlasov forward-backward SDEs.
- Author
-
Reisinger, Christoph, Stockinger, Wolfgang, and Zhang, Yufei
- Subjects
- *
APPROXIMATION error , *ALGORITHMS - Abstract
Fully coupled McKean–Vlasov forward-backward stochastic differential equations (MV-FBSDEs) arise naturally from large population optimization problems. Judging the quality of given numerical solutions for MV-FBSDEs, which usually require Picard iterations and approximations of nested conditional expectations, is typically difficult. This paper proposes an a posteriori error estimator to quantify the |$L^2$| -approximation error of an arbitrarily generated approximation on a time grid. We establish that the error estimator is equivalent to the global approximation error between the given numerical solution and the solution of a forward Euler discretized MV-FBSDE. A crucial and challenging step in the analysis is the proof of stability of this Euler approximation to the MV-FBSDE, which is of independent interest. We further demonstrate that, for sufficiently fine time grids, the accuracy of numerical solutions for solving the continuous MV-FBSDE can also be measured by the error estimator. The error estimates justify the use of residual-based algorithms for solving MV-FBSDEs. Numerical experiments for MV-FBSDEs arising from mean field control and games confirm the effectiveness and practical applicability of the error estimator. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
24. An Improved Density Peaks Clustering Algorithm Based On Density Ratio.
- Author
-
Zou, Yujuan, Wang, Zhijian, Xu, Pengfei, and Lv, Taizhi
- Subjects
- *
ALGORITHMS , *K-nearest neighbor classification , *CLUSTERING of particles , *COLLOIDAL stability , *DECISION trees - Abstract
Density peaks clustering (DPC) is a relatively new density clustering algorithm. It is based on the idea that cluster centers always have relatively high local densities and are relatively far from the points with higher densities. With the aforementioned idea, a decision graph can be drawn, and cluster centers will be chosen easily with the aid of the decision graph. However, the algorithm has its own weaknesses. Because the algorithm calculates local density and allocates points based on the distances between certain points, the algorithm has difficulty in classifying points into proper groups with varying densities or nested structures. This paper proposes an improved density peaks clustering algorithm called Dratio-DPC to overcome this weakness. First, Dratio-DPC adjusts the original local density with a coefficient calculated with the density ratio. Second, Dratio-DPC takes density similarity into consideration to calculate the distances between one point and other points with higher local densities. We design and perform experiments on different benchmark datasets and compare the clustering results of Dratio-DPC, traditional clustering algorithms and three improved DPC algorithms. Comparison results show that Dratio-DPC is effective and applicable to a wider range of scenarios. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
25. Service Function Placement Optimization For Cloud Service With End-to-End Delay Constraints.
- Author
-
Yan, Guofeng, Su, Zhengwen, Tan, Hengliang, and Du, Jiao
- Subjects
- *
CLOUD computing , *MARKOV processes , *STOCHASTIC analysis , *ALGORITHMS , *LOAD balancing (Computer networks) - Abstract
Network function virtualization (NFV) has been proposed to enable flexible management and deployment of the network service in cloud. In NFV architecture, a network service needs to invoke several service functions (SFs) in a particular order following the service chain function. The placement of SFs has significant impact on the performance of network services. However, stochastic nature of the network service arrivals and departures as well as meeting the end-to-end Quality of Service(QoS) makes the SFs placement problem even more challenging. In this paper, we firstly provide a system architecture for the SFs placement of cloud service with end-to-end QoS deadline. We then formulate the end-to-end service placement as a Markov decision process (MDP) which aims to minimize the placement cost and the end-to-end delay. In our MDP, the end-to-end delay of active services in the network is considered to be the state of the system, and the placement (nonplacement or placement) of SF is considered as the action. Also, we discuss the rationality of our analytical model by analyzing the Markov stochastic property of the end-to-end service placement. To obtain the optimal placement policy, we then propose an algorithm (Algorithm 1) for dynamic SFs placement based on our model and use successive approximations, i.e. |$\epsilon $| -iteration algorithm (Algorithm 2) to obtain action distribution. Finally, we evaluate the proposed MDP by comparing our optimal method with DDQP, DRL-QOR, MinPath and MinDelay for QoS optimization, including acceptance probability, average delay, resource utilization, load-balancing and reliability. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
26. MBSO Algorithm For Handling Energy-Throughput Trade-Off In Cognitive Radio Networks.
- Author
-
Ramchandran, M and Ganesh, E N
- Subjects
COGNITIVE radio ,RADIO networks ,ALGORITHMS ,ERROR rates ,BRAINSTORMING ,EVOLUTIONARY algorithms - Abstract
Cognitive Radio network (CRN) depends on opportunistic spectrum access and spectrum sensing for improving the wireless networks' spectrum efficiency. Since throughput maximization can result in high-energy consumption, the spectrum sensing technique should address the energy-throughput trade-off. The spectrum sensing time has to be determined by the considering the residual battery energies of each secondary user (SU). The primary user (PU) interference degrades the throughput of the entire network. Hence, the transmit power level should be determined by considering the PU interference and SU battery energy. This paper proposes the multi-objective brain storm optimization (MBSO) algorithm for handling energy-throughput trade-off in CRN. In this work, the sensing time is adaptively determined based on the residual battery energy of SUs, and the transmit power is determined based on the energy level of the PU signal and the residual battery energy of the SUs. A multi-objective optimization problem is formulated in order to maximize the throughput and minimize the packet error rate (PER) and is solved by applying the MBSO algorithm. Experimental results show that MBSO attains improved throughput, higher residual energy with lesser PER. The spectrum sensing performance is enhanced with higher probability of detection. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
27. Using Numerical Methods to Design Simulations: Revisiting the Balancing Intercept.
- Author
-
Robertson, Sarah E, Steingrimsson, Jon A, and Dahabreh, Issa J
- Subjects
COMPUTER simulation ,EXPERIMENTAL design ,STATISTICS ,STATISTICAL models ,LOGISTIC regression analysis ,STATISTICAL correlation ,DATA analysis ,EPIDEMIOLOGICAL research ,ALGORITHMS - Abstract
In this paper, we consider methods for generating draws of a binary random variable whose expectation conditional on covariates follows a logistic regression model with known covariate coefficients. We examine approximations for finding a "balancing intercept," that is, a value for the intercept of the logistic model that leads to a desired marginal expectation for the binary random variable. We show that a recently proposed analytical approximation can produce inaccurate results, especially when targeting more extreme marginal expectations or when the linear predictor of the regression model has high variance. We then formulate the balancing intercept as a solution to an integral equation, implement a numerical approximation for solving the equation based on Monte Carlo methods, and show that the approximation works well in practice. Our approach to the basic problem of the balancing intercept provides an example of a broadly applicable strategy for formulating and solving problems that arise in the design of simulation studies used to evaluate or teach epidemiologic methods. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
28. Differential evolution algorithm with improved crossover operation for combined heat and power economic dynamic dispatch problem with wind power.
- Author
-
Mengdi Li, Dexuan Zou, and Haibin Ouyang
- Subjects
WIND power ,DIFFERENTIAL evolution ,ADAPTIVE control systems ,ALGORITHMS ,GLOBAL optimization - Abstract
This paper proposes a differential evolution algorithm with improved crossover operation (ICRDE) to deal with combined heat and power dynamic economic dispatch (CHPDED) problems with wind power. First, the improved crossover operation is used to maintain the population diversity by using original individuals, first mutated individuals, and second mutated individuals. Second, the scaling factor and weighted factor are incorporated into the mutation operation to improve the convergence efficiency of the algorithm. Third, adaptive control parameters are introduced to balance local exploitation and global exploration. Moreover, after being updated by the mutation and crossover operation of ICRDE at each generation, the solutions of ICRDE will be further amended using a constraint handling method, which improves the chance of acquiring feasible solutions. Experimental results demonstrate that ICRDE has strong global optimization ability and surpasses the compared algorithms for the CEC2017 benchmark functions, the combined heat and power economic dispatch problems, and the CHPDED problem with and without wind power. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
29. Sine cosine algorithm with communication and quality enhancement: Performance design for engineering problems.
- Author
-
Helong Yu, Zisong Zhao, Jing Zhou, Heidari, Ali Asghar, and Huiling Chen
- Subjects
ENGINEERING design ,SWARM intelligence ,ALGORITHMS ,SEARCH engines ,GLOBAL optimization ,COMMUNICATION strategies - Abstract
In recent years, the sine cosine algorithm (SCA) has become one of the popular swarm intelligence algorithms due to its simple and convenient structure. However,the standard SCA tends to fall into the local optimum when solving complex multimodal tasks, leading to unsatisfactory results. Therefore, this study presents the SCA with communication and quality enhancement, called CCEQSCA. The proposed algorithm includes two enhancement strategies: the communication and collaboration strategy (CC) and the quality enhancement strategy (EQ). In the proposed algorithm, CC strengthens the connection of SCA populations by guiding the search agents closer to the range of optimal solutions. EQ improves the quality of candidate solutions to enhance the exploitation of the algorithm. Furthermore, EQ can explore potential candidate solutions in other scopes, thus strengthening the ability of the algorithm to prevent trapping in the local optimum. To verify the capability of CCEQSCA, 30 functions from the IEEE CEC2017 are analyzed. The proposed algorithm is compared with 5 advanced original algorithms and 10 advanced variants. The outcomes indicate that it is dominant over other comparison algorithms in global optimization tasks. The work in this paper is also utilized to tackle three typical engineering design problems with excellent optimization capabilities. It has been experimentally demonstrated that CCEQSCA works as an effective tool to tackle real issues with constraints and complex search space. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
30. Fast splitting algorithms for sparsity-constrained and noisy group testing.
- Author
-
Price, Eric, Scarlett, Jonathan, and Tan, Nelvin
- Subjects
DECODING algorithms ,ALGORITHMS ,ERROR probability ,DNA sequencing - Abstract
In group testing, the goal is to identify a subset of defective items within a larger set of items based on tests whose outcomes indicate whether at least one defective item is present. This problem is relevant in areas such as medical testing, DNA sequencing, communication protocols and many more. In this paper, we study (i) a sparsity-constrained version of the problem, in which the testing procedure is subjected to one of the following two constraints: items are finitely divisible and thus may participate in at most |$\gamma $| tests; or tests are size-constrained to pool no more than |$\rho $| items per test; and (ii) a noisy version of the problem, where each test outcome is independently flipped with some constant probability. Under each of these settings, considering the for-each recovery guarantee with asymptotically vanishing error probability, we introduce a fast splitting algorithm and establish its near-optimality not only in terms of the number of tests, but also in terms of the decoding time. While the most basic formulations of our algorithms require |$\varOmega (n)$| storage for each algorithm, we also provide low-storage variants based on hashing, with similar recovery guarantees. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
31. Novel phase-locked loop-based resonant frequency tracking control for linear reciprocating compressor.
- Author
-
Wang, Liqiang, Yu, Xiaofan, Lei, Meizhen, and Yin, Xiuxing
- Subjects
COMPRESSORS ,PHASE-locked loops ,POWER resources ,ALGORITHMS ,MODE-locked lasers - Abstract
The paper presents a novel phase-locked loop (PLL)-based resonant frequency tracking method for linear compressors with oscillatory motions. The proposed method achieves the phase-locked control between two signals by using PLL, which includes a multiplier, and a low-pass filter to obtain the phase signal difference. Consequently, based on the phase signal difference, the electrical frequency of the power supply can be adjusted through a PI (proportional-derivative) regulator such that the phase signal difference converges to 90° and the linear compressor works under the resonant frequency conditions. The analytical expression of the resonant frequency condition is proposed for the linear compressor. Then, the detailed design and procedure of the proposed method are presented. The designed method and the resonant frequency characteristics are verified by using the simulation experiment. The simulated results demonstrate that the proposed algorithm has faster response speed and higher convergence accuracy to step load change in comparison with the other commonly used algorithms. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
32. First-break prediction in 3-D land seismic data using the dynamic time warping algorithm.
- Author
-
Souza, W E, Cerqueira, A G, and Porsani, M J
- Subjects
- *
TIME management , *SEDIMENTARY basins , *ALGORITHMS , *GEOPHYSICISTS , *SEISMOGRAMS - Abstract
This paper presents a new methodology to assist geophysicists in determining the first-break event in a 3-D seismic data set using the well-known technique called dynamic time warping algorithm (DTW), which is usually used to find the optimal alignment between two time-series. We used the optimal path from the cost matrix to identify the first break in the seismogram using a few picks (seeds) made by an interpreter as a reference to perform this task. Furthermore, the data were pre-conditioned by the topographic and linear moveout to improve the method's accuracy. To demonstrate the technique's robustness, first, we applied the methodology in a synthetic seismic data. After demonstrating the efficiency of the algorithm, we applied the aforementioned methodology in the Polo-Miranga 3-D seismic cube located in the Recôncavo sedimentary basin, Bahia-Brazil, and in the seismic data acquired from the Blackfoot field in Alberta, Canada. The high-quality results showed consistency in determining the first break in all ranges of offsets, demonstrating an alternative way to accelerate this seismic processing step. Furthermore, we compared the results obtained by the proposed methodology with an algorithm based on comparing the short-time averages with long-time averages. Finally, we performed the static correction calculation to ensure that the time distortion resulting from the terrain and the low-velocity layer was mitigated in shoot gathers and in the stacked section. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
33. A new inversion-free iterative algorithm for the discrete algebraic Riccati equation.
- Author
-
Wang, Li and Zhu, Yuli
- Subjects
- *
ALGEBRAIC equations , *ALGORITHMS - Abstract
In this paper, by the transformation form of the discrete algebraic Riccati equation (DARE), we propose a new inverse-free iterative algorithm to obtain the positive definite solution of the DARE. Furthermore, the monotone convergence is proved and convergence rate analysis is presented for the derived algorithm. Compared with some existing algorithms, numerical examples demonstrate the feasibility and effectiveness of our algorithm. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
34. On geometric convergence for the Metropolis-adjusted Langevin algorithm under simple conditions.
- Author
-
Oliviero-Durmus, Alain and Moulines, Éric
- Subjects
- *
ALGORITHMS - Abstract
While the Metropolis-adjusted Langevin algorithm is a popular and widely used Markov chain Monte Carlo method, very few papers derive conditions that ensure its convergence. In particular, to the authors' knowledge, assumptions that are both easy to verify and guarantee geometric convergence, are still missing. In this work, we establish V -uniformly geometric convergence for the Metropolis-adjusted Langevin algorithm under mild assumptions about the target distribution. Unlike previous work, we only consider tail and smoothness conditions for the potential associated with the target distribution. These conditions are quite common in the Markov chain Monte Carlo literature. Finally, we pay special attention to the dependence of the bounds we derive on the step size of the Euler–Maruyama discretization, which corresponds to the proposed Markov kernel of the Metropolis-adjusted Langevin algorithm. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
35. Benchmarking multi-omics integration algorithms across single-cell RNA and ATAC data.
- Author
-
Xiao, Chuxi, Chen, Yixin, Meng, Qiuchen, Wei, Lei, and Zhang, Xuegong
- Subjects
- *
MULTIOMICS , *RNA , *DATA integration , *ALGORITHMS , *DATA visualization - Abstract
Recent advancements in single-cell sequencing technologies have generated extensive omics data in various modalities and revolutionized cell research, especially in the single-cell RNA and ATAC data. The joint analysis across scRNA-seq data and scATAC-seq data has paved the way to comprehending the cellular heterogeneity and complex cellular regulatory networks. Multi-omics integration is gaining attention as an important step in joint analysis, and the number of computational tools in this field is growing rapidly. In this paper, we benchmarked 12 multi-omics integration methods on three integration tasks via qualitative visualization and quantitative metrics, considering six main aspects that matter in multi-omics data analysis. Overall, we found that different methods have their own advantages on different aspects, while some methods outperformed other methods in most aspects. We therefore provided guidelines for selecting appropriate methods for specific scenarios and tasks to help obtain meaningful insights from multi-omics data integration. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
36. Development of the lyrics-based deep learning algorithm for identifying alcohol-related words (LYDIA).
- Author
-
Bonela, Abraham Albert, He, Zhen, Luxford, Dan-Anderson, Riordan, Benjamin, and Kuntsche, Emmanuel
- Subjects
- *
MUSIC , *LANGUAGE & languages , *TASK performance , *PHONOLOGICAL awareness , *DESCRIPTIVE statistics , *DEEP learning , *STATISTICS , *ALCOHOL drinking , *SPEECH perception , *SINGING , *ALGORITHMS , *INTER-observer reliability - Abstract
Background Music is an integral part of our lives and is often played in public places like restaurants. People exposed to music that contained alcohol-related lyrics in a bar scenario consumed significantly more alcohol than those exposed to music with less alcohol-related lyrics. Existing methods to quantify alcohol exposure in song lyrics have used manual annotation that is burdensome and time intensive. In this paper, we aim to build a deep learning algorithm (LYDIA) that can automatically detect and identify alcohol exposure and its context in song lyrics. Methods We identified 673 potentially alcohol-related words including brand names, urban slang, and beverage names. We collected all the lyrics from the Billboard's top-100 songs from 1959 to 2020 (N = 6110). We developed an annotation tool to annotate both the alcohol-relation of the word (alcohol, non-alcohol, or unsure) and the context (positive, negative, or neutral) of the word in the song lyrics. Results LYDIA achieved an accuracy of 86.6% in identifying the alcohol-relation of the word, and 72.9% in identifying its context. LYDIA can distinguish with an accuracy of 97.24% between the words that have positive and negative relation to alcohol; and with an accuracy of 98.37% between the positive and negative context. Conclusion LYDIA can automatically identify alcohol exposure and its context in song lyrics, which will allow for the swift analysis of future lyrics and can be used to help raise awareness about the amount of alcohol in music. Highlights Developed a deep learning algorithm (LYDIA) to identify alcohol words in songs. LYDIA achieved an accuracy of 86.6% in identifying alcohol-relation of the words. LYDIA's accuracy in identifying positive, negative, or neutral context was 72.9%. LYDIA can automatically provide evidence of alcohol in millions of songs. This can raise awareness of harms of listening to songs with alcohol words. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
37. Quantum Attacks on 1K-AES and PRINCE.
- Author
-
Cai, Bin-Bin, Wu, Yusen, Dong, Jing, Qin, Su-Juan, Gao, Fei, and Wen, Qiao-Yan
- Subjects
PRINCES ,CIPHERS ,ALGORITHMS ,PROBABILITY theory ,MEMORY - Abstract
By introducing the BHT algorithm into the slide attack on 1K-AES and the related-key attack on PRINCE, we present the corresponding quantum attacks in this paper. In the proposed quantum attacks, we generalize the BHT algorithm to the situation where the number of marked items is unknown ahead of time. Moreover, we give an implementation scheme of classifier oracle based on Quantum Phase Estimation algorithm in presented quantum attacks. The complexity analysis shows that the query complexity, time complexity and memory complexity of the presented quantum attacks are all |$\mathcal{O}(2^{n/3})$| when the success probability is about |$63\%$| , where |$n$| is the block size. Compared with the corresponding classical attacks, the proposed quantum attacks can achieve subquadratic speed-up under the same success probability no matter on query complexity, time complexity or memory complexity. Furthermore, the query complexity of the proposed quantum slide attack on 1K-AES is less than Grover search on 1K-AES by a factor of |$2^{n/6}.$| When compared with the Grover search on PRINCE, the query complexity of the presented quantum attack on PRINCE is reduced from |$\mathcal{O}(2^{n})$| to |$\mathcal{O}(2^{n/2}).$| When compared with the combination of Grover and Simon's algorithms on PRINCE, the query complexity of our quantum attack on PRINCE is reduced from |$\mathcal{O}(n\cdot 2^{n/2})$| to |$\mathcal{O}(2^{n/2}).$| Besides, the proposed quantum slide attack on 1K-AES indicates that the quantum slide attack could also be applied on Substitution-Permutation Network construction, apart from the iterated Even-Mansour cipher and Feistel constructions. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
38. Approximation of fractional harmonic maps.
- Author
-
Antil, Harbir, Bartels, Sören, and Schikorra, Armin
- Subjects
VECTOR fields ,PARTIAL differential equations ,FRACTIONAL differential equations ,POINT defects ,HARMONIC maps - Abstract
This paper addresses the approximation of fractional harmonic maps. Besides a unit-length constraint, one has to tackle the difficulty of nonlocality. We establish weak compactness results for critical points of the fractional Dirichlet energy on unit-length vector fields. We devise and analyze numerical methods for the approximation of various partial differential equations related to fractional harmonic maps. The compactness results imply the convergence of numerical approximations. Numerical examples on spin chain dynamics and point defects are presented to demonstrate the effectiveness of the proposed methods. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
39. Artificial Intelligence in Breast Imaging: Challenges of Integration Into Clinical Practice.
- Author
-
Ozcan, B. Bersu, Patel, Bhavika K., Banerjee, Imon, and Dogan, Basak E.
- Subjects
BREAST disease diagnosis ,PROFESSIONAL practice ,PRIVACY ,EVALUATION of human services programs ,ARTIFICIAL intelligence ,RULES ,MACHINE learning ,DIAGNOSTIC imaging ,HUMAN services programs ,WORKFLOW ,DATA security ,MEDICAL ethics ,ALGORITHMS ,WOMEN'S health - Abstract
Artificial intelligence (AI) in breast imaging is a rapidly developing field with promising results. Despite the large number of recent publications in this field, unanswered questions have led to limited implementation of AI into daily clinical practice for breast radiologists. This paper provides an overview of the key limitations of AI in breast imaging including, but not limited to, limited numbers of FDA-approved algorithms and annotated data sets with histologic ground truth; concerns surrounding data privacy, security, algorithm transparency, and bias; and ethical issues. Ultimately, the successful implementation of AI into clinical care will require thoughtful action to address these challenges, transparency, and sharing of AI implementation workflows, limitations, and performance metrics within the breast imaging community and other end-users. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
40. sasa: a SimulAtor of Self-stabilizing Algorithms.
- Author
-
Altisen, Karine, Devismes, Stéphane, and Jahier, Erwan
- Subjects
ALGORITHMS ,STOCHASTIC models - Abstract
In this paper, we present sasa , an open-source SimulAtor of Self-stabilizing Algorithms. Self-stabilization defines the ability of a distributed algorithm to recover after transient failures. sasa is implemented as a faithful representation of the atomic-state model (also called the locally shared memory model with composite atomicity). This model is the most commonly used one in the self-stabilizing area to prove both the correct operation of self-stabilizing algorithms and complexity bounds on them. sasa encompasses all features necessary to debug, test and analyze self-stabilizing algorithms. All these facilities are programmable to enable users to accommodate to their particular needs. For example, asynchrony is modeled by programmable stochastic daemons playing the role of input sequence generators. Properties of algorithms can be checked using formal test oracles. The sasa distribution also provides several facilities to easily achieve (batch-mode) simulation campaigns. We show that the lightweight design of sasa allows to efficiently perform huge such campaigns. Following a modular approach, we have aimed at relying as much as possible the design of sasa on existing tools, including ocaml , dot and several tools developed in the Synchrone Group of the VERIMAG laboratory. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
41. Comparing the Accuracy of Diagnostic Tests When Disease Is Characterized by an Ordinal Scale.
- Author
-
Obuchowski, Nancy A
- Subjects
CORONARY artery stenosis ,ARTIFICIAL intelligence ,SEVERITY of illness index ,COMPARATIVE studies ,CORONARY angiography ,COMPUTER-aided diagnosis ,SENSITIVITY & specificity (Statistics) ,DIAGNOSTIC errors ,CARDIOVASCULAR disease diagnosis ,ALGORITHMS ,PROBABILITY theory ,EVALUATION - Abstract
In diagnostic medicine, the true disease status of a patient is often represented on an ordinal scale—for example, cancer stage (0, I, II, III, or IV) or coronary artery disease severity measured using the Coronary Artery Disease Reporting and Data System (CAD-RADS) scale (none, minimal, mild, moderate, severe, or occluded). With advances in quantitation of diagnostic images and in artificial intelligence (AI), both supervised and unsupervised algorithms are being developed to help physicians correctly grade disease. Most of the diagnostic accuracy literature deals with binary disease status (disease present or absent); however, tests diagnosing ordinal-scaled diseases should not be reduced to a binary status just to simplify diagnostic accuracy testing. In this paper, we propose different characterizations of ordinal-scale accuracy for different clinical use scenarios, along with methods for comparing tests. In the simplest scenario, just the proportion of correct grades is considered; other scenarios address the magnitude and direction of misgrading; and at the other extreme, a weighted accuracy measure with weights based on the relative costs of different types of misgrading is presented. The various scenarios are illustrated using a coronary artery disease example where the accuracy of AI algorithms in providing patients with the correct CAD-RADS grade is assessed. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
42. Cauchy mutation boosted Harris hawk algorithm: optimal performance design and engineering applications.
- Author
-
Weifeng Shan, Xinxin He, Haijun Liu, Heidari, Ali Asghar, Maofa Wang, Zhennao Cai, and Huiling Chen
- Subjects
OPTIMIZATION algorithms ,ENGINEERING design ,ALGORITHMS ,BOOSTING algorithms ,MACHINE learning - Abstract
Harris hawks optimization (HHO) has been accepted as one of the well-established swarm-based methods in the community of optimization and machine learning that primarily works based on multiple dynamic features and various exploratory and exploitative traits. Compared with other optimization algorithms, it has been observed that HHO can obtain high-quality solutions for continuous and constrained complex and real-world problems. While there is a wide variety of strategies in the HHO for dealing with diverse situations, there are chances for sluggish performance, where the convergence rate can gradually slow with time, and the HHO may stay stuck in the current relatively better place and may be unable to explore other better areas. To mitigate this concern, this paper combines the Cauchy mutation mechanism into the HHO algorithm named CMHHO. This idea can boost performance and provide a promising optimizer for solving complex optimization problems. The Cauchy mutation mechanism can speed up the convergence of the solution and help HHO explore more promising regions compared to its basic release. On 30 IEEE CEC2017 benchmark functions, the study compared the proposed CMHHO with various conventional and advanced metaheuristics to validate its performance and quality of solutions. It has been found through experiments that the overall optimization performance of CMHHO is far superior to all competitors. The CMHHO method is applied to four engineering challenges to investigate the capabilities of the proposed algorithm in solving real-world problems, and experimental results show that the suggested algorithm is more successful than existing algorithms. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
43. A Hybrid Strategy Improved Whale Optimization Algorithm for Web Service Composition.
- Author
-
Ju, Chuanxiang, Ding, Hangqi, and Hu, Benjia
- Subjects
WEB services ,MATHEMATICAL optimization ,QUALITY of service ,DIFFERENTIAL evolution ,PROBLEM solving ,METAHEURISTIC algorithms ,ALGORITHMS - Abstract
With the rapid growth of the number of web services on the Internet, various service providers provide many similar services with the same function but different quality of service (QoS) attributes. It is a key problem to be solved urgently to select the service composition quickly, meeting the users' QoS requirements from many candidate services. Optimization of web service composition is an NP-hard issue and intelligent optimization algorithms have become the mainstream method to solve this complex problem. This paper proposed a hybrid strategy improved whale optimization algorithm, which is based on the concepts of chaos initialization, nonlinear convergence factor and mutation. By maintaining a balance between exploration and exploitation, the problem of slow or early convergence is overcome to a certain extent. To evaluate its performance more accurately, the proposed algorithm was first tested on a set of standard benchmarks. After, simulations were performed using the real quality of web service dataset. Experimental results show that the proposed algorithm is better than the original version and other meta-heuristic algorithms on average, as well as verifies the feasibility and stability of web service composition optimization. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
44. A New Approach for Resource Recommendation in the Fog-Based IoT Using a Hybrid Algorithm.
- Author
-
Xu, Zhiwang, Qin, Huibin, Yang, Shengying, and Arefzadeh, Seyedeh Maryam
- Subjects
SERVICE-oriented architecture (Computer science) ,INTERNET of things ,ALGORITHMS ,RECOMMENDER systems ,BEES algorithm ,FOG ,PARTICLE swarm optimization - Abstract
Internet of things (IoT) is an architecture of connected physical objects; these objects can communicate with each other and transmit and receive data. Also, fog-based IoT is a distributed platform that provides reliable access to virtualized resources based on various technologies such as high-performance computing and service-oriented design. A fog recommender system is an intelligent engine that suggests suitable services for fog users with less answer time and more accuracy. With the rapid growth of files and information sharing, fog recommender systems' importance is also increased. Besides, the resource management problem appears challenging in fog-based IoT because of the fog's unpredictable and highly variable environment. However, many current methods suffer from the low accuracy of fog recommendations. Due to this problem's Non-deterministic Polynomial-time (NP)-hard nature, a new approach is presented for resource recommendation in the fog-based IoT using a hybrid optimization algorithm. To simulate the suggested method, the CloudSim simulation environment is used. The experimental results show that the accuracy is optimized by about 1–8% compared with the Cooperative Filtering method utilizing Smoothing and Fusing and Artificial Bee Colony algorithm. The outcomes of the present paper are notable for scholars, and they supply insights into subsequent study domains in this field. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
45. Compressive independent component analysis: theory and algorithms.
- Author
-
Sheehan, Michael P and Davies, Mike E
- Subjects
INDEPENDENT component analysis ,RESTRICTED isometry property ,ALGORITHMS ,COMPRESSED sensing ,STATISTICAL learning ,IMAGE compression ,COMPUTATIONAL complexity - Abstract
Compressive learning forms the exciting intersection between compressed sensing and statistical learning where one exploits sparsity of the learning model to reduce the memory and/or computational complexity of the algorithms used to solve the learning task. In this paper, we look at the independent component analysis (ICA) model through the compressive learning lens. In particular, we show that solutions to the cumulant-based ICA model have a particular structure that induces a low-dimensional model set that resides in the cumulant tensor space. By showing that a restricted isometry property holds for random cumulants e.g. Gaussian ensembles, we prove the existence of a compressive ICA scheme. Thereafter, we propose two algorithms of the form of an iterative projection gradient and an alternating steepest descent algorithm for compressive ICA, where the order of compression asserted from the restricted isometry property is realized through empirical results. We provide analysis of the CICA algorithms including the effects of finite samples. The effects of compression are characterized by a trade-off between the sketch size and the statistical efficiency of the ICA estimates. By considering synthetic and real datasets, we show the substantial memory gains achieved over well-known ICA algorithms by using one of the proposed CICA algorithms. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
46. Extension-based semantics for incomplete argumentation frameworks: properties, complexity and algorithms.
- Author
-
Mailly, Jean-Guy
- Subjects
SEMANTICS ,SEMANTICS (Philosophy) ,MANURES ,ALGORITHMS - Abstract
Incomplete Argumentation Frameworks (IAFs) have been defined to incorporate some qualitative uncertainty in abstract argumentation: information such as 'I am not sure whether this argument exists' or 'I am not sure whether this argument attacks that one' can be expressed. Reasoning with IAFs is classically based on a set of completions, i.e. standard argumentation frameworks (AFs) that represent the possible worlds encoded in the IAF. The number of these completions may be exponential with respect to the number of arguments in the IAF. This leads, in some cases, to an increase of the complexity of reasoning, compared to the complexity of standard AFs. In this paper, we follow an approach that was initiated for Partial Argumentation Frameworks (PAFs) (a subclass of IAFs), which consists in defining new forms of conflict-freeness and defense, the properties that underly the definition of Dung's semantics for AFs. We generalize these semantics from PAFs to IAFs. We show that, among three possible types of admissibility, only two of them satisfy some desirable properties. We use them to define two new families of extension-based semantics. We study the properties of these semantics, and in particular, we show that their complexity remains the same as in the case of Dung's AFs. Finally, we propose a logical encoding of these semantics, and we show experimentally that this encoding can be used efficiently to reason with IAFs, thanks to the power of modern SAT solvers. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
47. Target unbiased meta-learning for graph classification.
- Author
-
Ming Li, Shuo Zhu, Chunxu Li, and Wencang Zhao
- Subjects
DEEP learning ,GRAPHIC methods ,CLASSIFICATION ,ARTIFICIAL neural networks ,STATISTICAL bias ,ALGORITHMS - Abstract
Even though numerous works focus on the few-shot learning issue by combining meta-learning, there are still limits to traditional graph classification problems. The antecedent algorithms directly extract features from the samples, and do not take into account the preference of the trained model to the previously "seen" targets. In order to overcome the aforementioned issues, an effective strategy with training an unbiased meta-learning algorithm was developed in this paper, which sorted out problems of target preference and few-shot under the meta-learning paradigm. First, the interactive attention extraction module as a supplement to feature extraction was employed, which improved the separability of feature vectors, reduced the preference of the model for a certain target, and remarkably improved the generalization ability of the model on the new task. Second, the graph neural network was used to fully mine the relationship between samples to constitute graph structures and complete image classification tasks at a node level, which greatly enhanced the accuracy of classification. A series of experimental studies were conducted to validate the proposed methodology, where the few-shot and semisupervised learning problem has been effectively solved. It also proved that our model has better accuracy than traditional classification methods on real-world datasets. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
48. State-of-charge estimation for second-life lithium-ion batteries based on cell difference model and adaptive fading unscented Kalman filter algorithm.
- Author
-
Du, Banghua, Yu, Zhang, Yi, Shuhao, He, Yanlin, and Luo, Yulin
- Subjects
KALMAN filtering ,ALGORITHMS ,PROBLEM solving ,LITHIUM-ion batteries - Abstract
Lithium-ion batteries retired from electric vehicles can provide considerable economic benefits when they are retired for secondary use. However, retired batteries after screening and restructuring still face the problem of inaccurate battery pack state-of-charge (SOC) estimation due to the existence of extreme inconsistency. To solve this problem, an adaptive fading unscented Kalman filtering (AFUKF) algorithm based on the cell difference model (CDM) is proposed in this paper for improving the accuracy of SOC estimation of retired lithium-ion battery packs. Firstly, an improved CDM based on a hypothetical Rint model is developed based on a second-order resistor/capacitor equivalent circuit model. Secondly, an AFUKF algorithm is developed to improve the adaptability and robustness of local state estimation against process modelling errors. Finally, characteristic data are obtained by conducting discharge tests on the screened retired lithium-ion batteries under specific operating conditions. The proposed method can improve the accuracy of SOC estimation of retired lithium-ion battery packs and provide a new idea for SOC estimation of retired lithium-ion battery packs, as shown by the simulated real experimental data. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
49. Application of learning to rank in bioinformatics tasks.
- Author
-
Ru, Xiaoqing, Ye, Xiucai, Sakurai, Tetsuya, and Zou, Quan
- Subjects
BIOINFORMATICS ,TASKS ,ALGORITHMS - Abstract
Over the past decades, learning to rank (LTR) algorithms have been gradually applied to bioinformatics. Such methods have shown significant advantages in multiple research tasks in this field. Therefore, it is necessary to summarize and discuss the application of these algorithms so that these algorithms are convenient and contribute to bioinformatics. In this paper, the characteristics of LTR algorithms and their strengths over other types of algorithms are analyzed based on the application of multiple perspectives in bioinformatics. Finally, the paper further discusses the shortcomings of the LTR algorithms, the methods and means to better use the algorithms and some open problems that currently exist. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
50. Two-locus identity coefficients in pedigrees.
- Author
-
Vigeland, Magnus Dehli
- Subjects
- *
GENEALOGY , *KINSHIP , *GENETICS , *ALGORITHMS - Abstract
This paper proposes a solution to a long-standing problem concerning the joint distribution of allelic identity by descent between two individuals at two linked loci. Such distributions have important applications across various fields of genetics, and detailed formulas for selected relationships appear scattered throughout the literature. However, these results were obtained essentially by brute force, with no efficient method available for general pedigrees. The recursive algorithm described in this paper, and its implementation in R, allow efficient calculation of two-locus identity coefficients in any pedigree. As a result, many existing procedures and techniques may, for the first time, be applied to complex and inbred relationships. Two such applications are discussed, concerning the expected likelihood ratio in forensic kinship testing, and variances in realized relatedness. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.