J'ai trouvé le livre Pairwise Independence and Derandomization sur le sujet, mais il est plus axé sur la recherche que sur le tutoriel. Je suis nouveau sur le sujet de la "dérandomisation", et en tant que tel, je voulais savoir de quelle référence commencer? Je préfère celui qui traite de la...
Pour autant que je sache, la plupart des implémentations de la génération de nombres pseudo-aléatoires utilisent des méthodes telles que les registres de rétroaction à décalage linéaire (LSFR), ou ces algorithmes "Mersenne Twister". Bien qu'ils passent de nombreux tests statistiques (heuristiques),...
Étant donné deux arbres AVL T1T1T_1 et T2T2T_2 et une valeur trtrt_r telle que ∀x∈T1,∀y∈T2,x<tr<y∀x∈T1,∀y∈T2,x<tr<y\forall x \in T_1, \forall y \in T_2, x < t_r < y , il est facile de construire un nouvel arbre AVL contenant trtrt_r et les valeurs en T1T1T_1 et T2T2T_2 dans le temps...
Quels sont quelques exemples majeurs de dérandomisation réussie ou du moins de progrès dans la démonstration de preuves concrètes vers l' objectif (pas la connexion de dureté aléatoire)?P= BPPP=BPPP=BPP Le seul exemple qui me vient à l'esprit est le test de primalité polynomiale déterministe AKS...
Supposons qu'un algorithme randomisé utilise rrr bits aléatoires. La plus faible probabilité d'erreur à laquelle on puisse s'attendre (en deçà d'un algorithme déterministe avec 0 erreur) est de 2−Ω(r)2-Ω(r)2^{-\Omega(r)} . Quels algorithmes randomisés atteignent une telle probabilité d'erreur...
Il existe de nombreuses situations où une "preuve" randomisée est beaucoup plus facile qu'une preuve déterministe, l'exemple canonique étant le test d'identité polynomiale. Question : Existe-t-il des "théorèmes" mathématiques naturels où une preuve randomisée est connue mais pas une preuve...
Dans l'article Randomized Primal-Dual analysis of RANKING for Online Bipartite Matching , tout en prouvant que l'algorithme RANKING est -concurrentiel, les auteurs montrent que le dual est réalisable en attente (voir Lemme 3 page 5). Ma question est:( 1 - 1e)(1-1e)\left(1 - \frac{1}{e}\right)...
Dans les tables de hachage qui résolvent les collisions par sondage linéaire, afin d'assurer les performances attendues de , il est à la fois nécessaire et suffisant que la fonction de hachage provienne d'une famille à 5 indépendants. (Suffisance: "Sondage linéaire avec indépendance constante",...
Je révise un modèle cryptographique. Pour montrer son insuffisance, j'ai conçu un protocole artificiel basé sur l'isomorphisme des graphes. Il est "banal" (et pourtant controversé!) De supposer l'existence d'algorithmes BPP capables de générer "des instances dures du problème d'isomorphisme des...
Adleman a montré en 1978 que BPP⊆P/polyBPP⊆P/poly\mathrm{BPP}\subseteq \mathrm{P/poly} : si une fonction booléenne fff de nnn variables peut être calculée par un circuit booléen probabiliste de taille MMM , alors fff peut également être calculé par un circuit booléen déterministe de taille polynôme...
Je me demande ce qui se passerait si, dans la définition de (Hiérarchie polynomiale, voir, par exemple ici ), le rôle de N P serait remplacé par R P ?PHPHPHNPNPNPR PRPRP Il semble que nous pourrions encore construire une hiérarchie, de la même manière que est construit, juste en utilisant R P...
Les progrès de l'informatique quantique ont conduit au développement de nouveaux algorithmes classiques. Des exemples récents notables sont des algorithmes d'inspiration quantique pour l'algèbre linéaire: Un algorithme classique d'inspiration quantique pour les systèmes de recommandation...
Je voudrais savoir (en relation avec cette autre question ) si des limites inférieures étaient connues pour le problème de test suivant: on a accès à une requête à une séquence de nombres non négatifs et , avec la promesse que ou . ε ∈ ( 0 , 1 ) ∑ n k = 1 a k = 1 ∑ n k = 1 a k ≤ 1 - εunen≥ ⋯ ≥...
J'essaie de trouver une distribution sur vecteurs aléatoires, disons , sur la sphère de l'unité dimensionnelle (où ) qui minimise soumis à la contrainte \ mathbb {E} [x_i ^ Tx_j] = 0 .nnnx1,…,xnx1,…,xnx_1,\ldots, x_nkkkn>kn>kn > kmaxi≠jVar(xTixj)maxi≠jVar(xiTxj)\max_{i\neq j}...
L'inégalité de Fano peut être exprimée sous de nombreuses formes, et une particulièrement utile est due (avec une modification mineure) à Oded Regev : Soit une variable aléatoire, et soit où est un processus aléatoire. Supposons l'existence d'une procédure qui, avec puisse reconstruire avec une...
Les algorithmes distribués qui résistent aux défaillances peuvent être déterministes ou probabilistes. Prenons par exemple le problème du consensus. Paxos est déterministe dans le sens où, étant donné l'hypothèse qu'il fait, il fonctionne toujours . En revanche, le consensus randomisé fonctionne...
Ce blog parle de générer des "petits labyrinthes sinueux" à l'aide d'un ordinateur et de les énumérer. L'énumération peut être effectuée en utilisant l'algorithme de Wilson pour obtenir l' UST , mais je ne me souviens pas de la formule du nombre.
B P PBPP\mathsf{BPP} etZPPZPP\mathsf{ZPP} sont deux des classes de complexité probabiliste de base. BPPBPP\mathsf{BPP} est la classe de langages décidée par les algorithmes de Turing à temps polynomial probabiliste où la probabilité que l'algorithme renvoie une réponse incorrecte est limitée,...
J'ai 400 balles, dont 100 rouges, 40 jaunes, 50 vertes, 60 bleues, 70 violettes, 80 noires. (les boules de la même couleur sont identiques) j'ai besoin d'un algorithme de brassage efficace, de sorte qu'après le brassage, les balles soient dans une liste, et Les 3 balles consécutives ne sont pas de...
Dans l'étude sur deux problèmes de théorie de l'information , Erdõs et Rényi donnent des limites inférieures sur le nombre minimum de pesées à faire pour déterminer le nombre de fausses pièces dans un ensemble de pièces.nnn Plus formellement: Les fausses pièces ont un poids plus petit que les...