Qui n’a pas reçu un mail du genre : allez voir ce que dit Google lorsque vous tapez « miserable failure » ?

Cette recherche vous conduira droit sur la page du président des Etats-Unis : G.W. Bush.
Des explications sont données sur le blog de Google et même sur Wikipedia. Et Bush n’est pas la seule cible de ces « bombardement Google » comme l’indique encore un article de Wikipedia.
L’algorithme de Google a donc des défauts. La question que je me pose naturellement est de savoir si les autres algorithmes de ranking ont ces mêmes défauts, en particulier les algorithmes  dont j’ai déjà parlé ici. Pour le moment, c’est une question ouverte. Si quelqu’un a la réponse…

Un livre en ligne sur la théorie de la complexité :

Complexity Theory: A Modern Approach / Sanjeev Arora and Boaz Barak

avec un chapitre sur le calcul quantique.
Voici la table des matières :

Part I: Basic Complexity Classes

1. The computational model – and why it doesn’t matter. Definition of Turing machine, efficient universal TM, the class P.
2. NP and NP completeness. NP, Cook-Levin Theorem, NP-completeness, search vs. decision.
3. Space Complexity PSPACE, L, NL. TQBF is PSPACE complete, Savitch’s Theorem, Path is NL-complete, NL=coNL.
4. Diagonalization Time, Non-deterministic time, and space hierarchy theorems, Ladner’s theorem, oracle machines and proof that relativized methods can’t resolve P vs. NP.
5. The polynomial hierarchy and alternations. Definitions of PH via alternating quantifiers and alternating machines, conjecture it doesn’t collapse, time-space tradeoffs for SAT.
6. Circuits. Boolean circuits and the class Ppoly. Definition using advice. Karp-Lipton theorem. Non-uniform hierarchy theorem. circuit-satisfiability and alternative proof for Cook-Levin theorem.
7. Randomized Computation BPP, RP, coRP, ZPP. Examples of probabilistic algorithms. Error reduction via repetition. BPP in P/poly and PH. Randomized reductions, randomized logspace algorithms.
8. Complexity of Counting #P. #P-completeness and Valiant’s theorem. Toda’s theorem.
9. Interactive Proofs IP, AM. Graph non-isormorphism in AM. IP=PSPACE.
10. Cryptography One-way functions, pseudorandom generators: prediction vs. distinguishing. Goldreich-Levin theorem. Zero knowledge and ZK proof for graph isomorphism. Overview of advanced topics in cryptography.

Part II: Lower bounds for concrete computational models

11. Decision Trees certificate complexity, randomized complexity, sorting lowerbounds
12. Communication Complexity Lowerbound methods (fooling set, rank, tiling, discrepancy), multiparty communication complexity
13. Circuit lowerbounds. Hastad switching lemma, lowerbounds for monotone circuits, frontier of circuit lowerbounds, approaches using communication complexity.
14. Algebraic complexity Algebraic trees and circuits, Blum-Shub-Smale model.

Part III: Advanced Topics

15. Average Case Complexity: Levin’s Theory DistNP and its complete problems.
16. Random and pseudorandom walks on graphs second eigenvalue and analysis of random walks, expander graphs, zig-zag construction of expanders, reingold’s deterministic logspace algorithm for undirected connectivity.
17. Derandomization and Extractors Pseudorandom generators from average-case hardness – the NW generators. Extractors from hash functions. Trevisan’s extractor from NW.
18. Hardness amplification and error correcting codes Worst-case to average case reduction. Error correcting codes. Pseudoarndom generators from worst-case assumptions. List decoding and its use for hardness amplification.
19. PCP and hardness of approximation. NP in PCP(poly,1). The PCP theorem (Dinur’s proof). Independent set is hard to approximate within a polynomial factor.
20. More PCP Theorems and the Fourier Transform Technique Fourier transforms over GF(2)^n. Analysis of linearity testing. Hastad’s 3-query PCP, 3SAT is hard to 7/8+epsilon approximate. Learning fourier coefficients (Goldreich-Levin / Kushilevits-Mansour)
21. Quantum Computation Quantum computation and the class QBP. Shor’s factoring algorithm.
22. Logic in complexity theory Proof complexity.
23. Why are circuit lower bounds so difficult? Natural proofs.