24 papers · ranked by Valyu relevance
Alan R. Rogers
The Legofit statistical package uses genetic data to estimate parameters describing population history. Previous versions used computer simulations to estimate probabilities, an approach that limited both speed and accuracy. This article describes a new deterministic algorithm, which makes Legofit much more accurate…
Gengsheng L. Zeng
A restricted Boltzmann machine is a fully connected shallow neural network. It can be used to solve many challenging optimization problems. The Boltzmann machines are usually considered probability models. Probability models normally use nondeterministic algorithms to solve their parameters. The Hopfield network which…
Artur Czumaj, Peter Davies-Peck, Merav Parter
In this paper, we study the power and limitations of component-stable algorithms in the low-space model of massively parallel computation (MPC). Recently Ghaffari, Kuhn and Uitto (FOCS 2019) introduced the class of component-stable low-space MPC algorithms, which are, informally, those algorithms for which the outputs…
Ruben Becker, Davide Cenzato, Sunghwan Kim, Bojana Kodric + 2 more
'Riccardo Maso' 'Nicola Prezza'] Wheeler automata were introduced in 2017 as a tool to generalize existing indexing and compression techniques based on the Burrows-Wheeler transform. Intuitively, an automaton is said to be Wheeler if there exists a total order on its states reflecting the natural co-lexicographic order…
Yuri Gurevich
The modern notion of algorithm was elucidated in the 1930s–1950s. It was axiomatized a quarter of a century ago as the notion of "sequential algorithm" or "classical algorithm"; we prefer to call it "basic algorithm" now. The axiomatization was used to show that for every basic algorithm there is a behaviorally…
Martin Šošić, Mile Šikić
We present Edlib, an open-source C/C++ library for exact pairwise sequence alignment using edit distance. We compare Edlib to other libraries and show that it is the fastest while not lacking in functionality, and can also easily handle very large sequences. Being easy to use, flexible, fast and low on memory usage, we…
Susanne Albers, Maximilian Janke
Makespan minimization on identical machines is a fundamental problem in online scheduling. The goal is to assign a sequence of jobs to m identical parallel machines so as to minimize the maximum completion time of any job. Already in the 1960s, Graham showed that Greedy is $2-1/m$-competitive. The best deterministic…
Leonid A. Levin
These are notes for the course CS-172 I first taught in the Fall 1986 at UC Berkeley and subsequently at Boston University. The goal was to introduce the undergraduates to basic concepts of Theory of Computation and to provoke their interest in further study. Model-dependent effects were systematically ignored.…
Wolfram Barfuss
A dynamical systems perspective on multi-agent learning, based on the link between evolutionary game theory and reinforcement learning, provides an improved, qualitative understanding of the emerging collective learning dynamics. However, confusion exists with respect to how this dynamical systems account of…
Hector Zenil, Narsis A. Kiani, Francesco Marabita, Yue Deng + 4 more
It remains fundamentally unclear how to reprogram complex evolving systems. Here, we introduce a conceptual framework and an interventional calculus to steer and manipulate systems based on their intrinsic algorithmic probability using the universal principles of the theory of computability and algorithmic information.…
Authors not listed
We present a vector-based method to balance chemical reactions. The algorithm builds candidates in a deterministic way, removes duplicates, and always prints coefficients in the lowest whole-number form. For redox cases, electrons and protons/hydroxide are treated explicitly, so both mass and charge are balanced. We…
Yann Garniron, Thomas Applencourt, Kevin Gasperich, Anouar Benali + 15 more
Quantum Package is an open-source programming environment for quantum chemistry specially designed for wave function methods. Its main goal is the development of determinant-driven selected configuration interaction (sCI) methods and multi-reference second-order perturbation theory (PT2). The determinant-driven…
Jesse Kreger, Natalia L. Komarova, Dominik Wodarz
Multiple infection (when a single cell can become super-infected with multiple copies of virus) can effect evolutionary processes in HIV infection, such as the generation and spread of different mutations. Synaptic transmission (where multiple copies of virus can be transferred during a single cell-to-cell interaction)…
Sander Borst, Daniel Dadush, Sophie Huiberts, Danish Kashaev
Explorable heap selection is the problem of selecting the nth smallest value in a binary heap. The key values can only be accessed by traversing through the underlying infinite binary tree, and the complexity of the algorithm is measured by the total distance traveled in the tree (each edge has unit cost). This problem…
Michał Ćwik, Jerzy Józefczyk
An uncertain version of the permutation flow-shop with unlimited buffers and the makespan as a criterion is considered. The investigated parametric uncertainty is represented by given interval-valued processing times. The maximum regret is used for the evaluation of uncertainty. Consequently, the minmax regret discrete…
Authors not listed
Strong coupling and environmental memory render many open quantum systems intractable to classical computation. To overcome this barrier, we present a variational quantum algorithm capable of solving generalized form time-local quantum master equations directly on Noisy Intermediate-Scale Quantum (NISQ) processors. Our…
James R. Riehl, Maxwell I. Zimmerman, Matthew F. Singh, Gregory R. Bowman + 1 more
Equilibria, or fixed points, play an important role in dynamical systems across various domains, yet finding them can be computationally challenging. Here, we show how to efficiently compute all equilibrium points of discrete-valued, discrete-time systems on sparse networks. Using graph partitioning, we recursively…
Yaqiao Li, Mahtab Masoori, Lata Narayanan, Denis Pankratov
We study the Renting Servers in the Cloud problem (RSiC) in multiple dimensions. In this problem, a sequence of multi-parameter jobs must be scheduled on servers that can be rented on-demand. Each job has an arrival time, a finishing time, and a multi-dimensional size vector that specifies its resource demands. Each…
James Aspnes
| | Table of contents | | | ii | | --- | --- | --- | --- | --- | | | List of figures | | | xiv | | | List of tables | | | xv | | | List of algorithms | | | xvi | | | Preface | | | xvii | | 1 | | Randomized algorithms | | 1 | | | 1.1 | A trivial example | | 2 | | | 1.2 | Verifying polynomial identities | | 3 | | | 1.3 |…
Krasimir Yordzhev
Some randomized algorithms, used to obtain a random n 2 × n 2 Sudoku matrix, where n is a natural number, is reviewed in this study. Below is described the set Πn of all (2n) × n matrices, consisting of elements of the set Zn = {1, 2, . . . , n}, such that every row is a permutation. It is proved that such matrices…
Peter L. Bartlett, Chris Junchi Li, Jingfeng Wu, Bin Yu
In the field of optimization, developing accelerated methods for solving minimax and fixed-point problems remains a fundamental challenge. This paper presents a novel family of dual accelerated algorithms that achieve optimal convergence rates for both minimax and fixed-point problems. By exploring new anchoring…
Authors not listed
Deriving versatile and robust mechanistic models from experimental data is a key challenge in engineering and natural sciences. This is especially true in chemical reaction engineering, where reactor manufacturers and operators increasingly pursue the development and maintenance of digital twins that rely on frequent…
Tobias Røikjer, Asger Hobolth, Kasper Munch
Phase-type distributions model the time until absorption in continuous or discrete-time Markov chains on a finite state space. The multivariate phase-type distributions have diverse and important applications by modeling rewards accumulated at visited states. However, even moderately-sized state spaces make the…
Lionel Zoubritzky, François-Xavier Coudert
We present here an open-source Julia library for the topological identification of crystalline materials, with algorithmic and computational improvements over the previously available software in the field, resulting in a speed increase of one order of magnitude. This new algorithm and implementation can therefore be…