14 papers · ranked by Valyu relevance
Krasimir Yordzhev
The paper considers implementations of some randomized algorithms in connection with obtaining a random n 2 × n 2 Sudoku matrix with programming language C++. For this purpose we describes 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.…
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…
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…
Vincent Cicirello
Evolutionary algorithms rely very heavily on randomized behavior. Execution speed, therefore, depends strongly on how we implement randomness, such as our choice of pseudorandom number generator, or the algorithms used to map pseudorandom values to specific intervals or distributions. In this paper, we observe that the…
M. E. Huber, Danny Vargas
In 1976, Knuth and Yao presented an algorithm for sampling from a finite distribution using flips of a fair coin that on average used the optimal number of flips. Here we show how to easily run their algorithm for the special case of rolling a fair die that uses memory linear in the input. Analysis of this algorithm…
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…
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…
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…
Thomas L. Draper, Feras A. Saad
"Randomness recycling" is a powerful algorithmic technique for reusing a fraction of the random information consumed by a randomized algorithm to reduce its entropy requirements. This article presents a family of efficient randomness recycling algorithms for sampling a sequence X1, X2, X3, . . . of discrete random…
Vincent Cicirello
This report presents algorithms for generating small random samples without replacement. It considers two cases. It presents an algorithm for sampling a pair of distinct integers, and an algorithm for sampling a triple of distinct integers. The worstcase runtime of both algorithms is constant, while the worstcase…
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…
Stefan Kutschera, Wilhelm Zugaj, Wolfgang Slany
—We aim to access entropy sources available within smartphones in order to construct and evaluate a random number generator which is competitive in comparison with existing and proven random number generators. A prototype utilizing the herein proposed algorithm shall generate data that can be tested against the…
Jiefeng Zhou, Zhen Li, Yong Deng
Random walk is an explainable approach for modeling natural processes at the molecular level. The Random Permutation Set Theory (RPST) serves as a framework for uncertainty reasoning, extending the applicability of Dempster-Shafer Theory. Recent explorations indicate a promising link between RPST and random walk. In…