New answers tagged ho.history-overview
2
The work function algorithm for $k$-server was shown to be $(2k-1)$-competitive by Koutsipias and Papadimitrou - the algorithm was known previously and analyzed only in special cases. It is conjectured to be $k$-competitive.
8
The algorithm of Paturi, Pudlák, Saks and Zane (PPSZ) for $k\text{-} \mathrm{SAT}$ had been known to have a running time of $O(1.364^n)$ for $3\text{-}\mathrm{SAT}$, with a better bound of $O(1.308^n)$ for formulas guaranteed to have a unique satisfying assignment.
Later Hertli gave an improved analysis showing that this improved run-time bound also holds ...
3
The $3$-Hitting Set problem had a few iterations of "better analysis" (see Fernau's papers [1] [2])
The algorithm before these paper had some arbitrary choices (like 'choose an edge'...), but when the choices are specifically-chosen in a certain way, it allows for a more refined analysis, that is where the improvement comes in. And I think his Appendices in ...
5
The Logjam Attack mentions that analysis of the general number field sieve (as applied to computing discrete logarithms over $\mathbb{F}_p$) descent step was tightend, see top left of the 3rd page. As this is the only step that can't be pre-computed (if $\mathbb{F}_p$ is fixed), its efficiency was instrumental to their attack.
The initial analysis appears ...
17
The Union-Find algorithm, which Tarjan1 showed had complexity $n \alpha(n)$, where $\alpha(n)$ is the inverse Ackermann function, had been analyzed previously by several people. According to Wikipedia, it was invented by Galler and Fisher2, but this seems to be incorrect, as they did not have all the components of the algorithm needed to make it run that ...
Top 50 recent answers are included
