Parallel probabilistic searching and sorting algorithms
Ivan Kramosil (1990)
Kybernetika
Similarity:
Displaying similar documents to “The PCP theorem”
Parallel probabilistic searching and sorting algorithms
Shao's theorem on the maximum of standardized random walk increments for multidimensional arrays
Zakhar Kabluchko, Axel Munk (2009)
ESAIM: Probability and Statistics
Similarity:
We generalize a theorem of Shao [ (1995) 575–582] on the almost-sure limiting behavior of the maximum of standardized random walk increments to multidimensional arrays of i.i.d. random variables. The main difficulty is the absence of an appropriate strong approximation result in the multidimensional setting. The multiscale statistic under consideration was used recently for the selection of the regularization parameter in a number of statistical algorithms as well...
Random walks on finite groups with few random generators.
Pak, Igor (1999)
Electronic Journal of Probability [electronic only]
Similarity:
Strong result for real zeros of random algebraic polynomials.
Uno, T. (2001)
Journal of Applied Mathematics and Stochastic Analysis
Similarity:
A selection-based formal description of an environment
Ivan Kramosil (1976)
Kybernetika
Similarity:
Computing a glimpse of randomness.
Calude, Cristian S., Dinneen, Michael J., Shu, Chi-Kou (2002)
Experimental Mathematics
Similarity:
Random generation for finitely ambiguous context-free languages
Alberto Bertoni, Massimiliano Goldwurm, Massimo Santini (2001)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
We prove that a word of length from a finitely ambiguous context-free language can be generated at random under uniform distribution in time by a probabilistic random access machine assuming a logarithmic cost criterion. We also show that the same problem can be solved in polynomial time for every language accepted by a polynomial time -NAuxPDA with polynomially bounded ambiguity.