13 papers · ranked by Valyu relevance
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…
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 |…
Aydın Buluç, Tamara G. Kolda, Stefan M. Wild, Mihai Anitescu + 15 more
'Anthony M. DeGennaro' 'John Jakeman' 'Chandrika Kamath' 'Ramakrishnan Kannan' 'Miles E. Lopes' 'Per‐Gunnar Martinsson' 'Kary Myers' 'Jelani Nelson' 'Juan M. Restrepo' 'C. Seshadhri' 'Draguna Vrabie' 'Brendt Wohlberg' 'Stephen J. Wright' 'Chao Yang' 'Peter H. Zwart'] ARCS ARSC SCAR CRSA CSAR SACR CRAS ASRC RCAS ASRC…
Antoine Lhomme, Nicolas Catusse, Nadia Brauner
A frequently studied performance measure in online optimization is competitive analysis. It corresponds to the worst-case ratio, over all possible inputs of an algorithm, between the performance of the algorithm and the optimal offline performance. However, this analysis may be too pessimistic to give valuable insight…
Emin Karayel
Derandomization techniques are often used within advanced randomized algorithms. In particular, pseudorandom objects, such as hash families and expander graphs, are key components of such algorithms, but their verification presents a challenge. This work shows how such algorithms can be expressed and verified in…
William M. Hoza
Suppose a language L can be decided by a bounded-error randomized algorithm that runs in space S and time n · poly(S). We give a randomized algorithm for L that still runs in space O(S) and time n · poly(S) that uses only O(S) random bits; our algorithm has a low failure probability on all but a negligible fraction of…
Axel Bacher, Olivier Bodini, Alexandros Hollender, Jérémie Lumbroso
This article introduces an algorithm, MERGESHUFFLE, which is an extremely efficient algorithm to generate random permutations (or to randomly permute an existing array). It is easy to implement, runs in nlog2n + O(1) time, is in-place, uses nlog2n + Θ(n) random bits, and can be parallelized accross any number of…
Allan Borodin, Christodoulos Karavasilis, David Zhang
Interest in the random order model (ROM) leads us to initiate a study of utilizing random-order arrivals to extract random bits with the goal of de-randomizing algorithms. Besides producing simple algorithms, simulating random bits through random arrivals enhances our understanding of the comparative strength of…
Daniel Lemire
In simulations, probabilistic algorithms and statistical tests, we often generate random integers in an interval (e.g., [0,s)). For example, random integers in an interval are essential to the Fisher-Yates random shuffle. Consequently, popular languages like Java, Python, C++, Swift and Go include ranged random integer…
Nevin Brackett‐Rozinsky, Daniel Lemire
Pseudorandom values are often generated as 64-bit binary words. These random words need to be converted into ranged values without statistical bias. We present an efficient algorithm to generate multiple independent uniformlyrandom bounded integers from a single uniformly-random binary word, without any bias. In the…
Manuel Penschuck
Shuffling is the process of rearranging a sequence of elements into a random order such that any permutation occurs with equal probability. It is an important building block in a plethora of techniques used in virtually all scientific areas. Consequently considerable work has been devoted to the design and…
Yongxin Li
This work starts from definition of randomness, the results of algorithmic randomness are analyzed from the perspective of application. Then, the source and nature of randomness is explored, and the relationship between infinity and randomness is found. The properties of randomness are summarized from the perspective…
Frederick W. James, L. Moneta
This is a review of pseudorandom number generators (RNG's) of the highest quality, suitable for use in the most demanding Monte Carlo calculations. All the RNG's we recommend here are based on the Kolmogorov-Anosov theory of mixing in classical mechanical systems, which guarantees under certain conditions and in…