Erratum: Fusible HSTs and the randomized k-server conjecture

There is a non-trivial gap in Section 5.3.2 of the paper posted to the arxiv and the version appearing on my web page. There is a proposed fix for the gap, but the integration of that fix with the rest of the argument is not complete, and if/when the writeup is finished, it will need to be carefully checked. This may take considerable time, as a major goal is to restructure the analysis so that it is more easily verified for correctness.

Given this situation, I currently make no claims about the status of the randomized completitive ratio for $k$-server in general metric spaces. The previously claimed result should not be taken or cited as a mathematical truth. And if another person or persons were to claim the result in the meantime, the credit would be fully theirs.

Indeed, I am leaving the current version online (with an appropriate warning inserted into the PDF), and I encourage interested parties to use the outline and methods as a basis for their own solution if they so wish. (In fact, this is the ideal situation scientifically, as a straightforward revision of the present argument involves additional technical complications that further obscure the main ideas.) I am happy to answer questions about the draft by email (jrl at cs).