Skip to main content
24 votes

When have we found better bounds for known algorithms?

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,...
Peter Shor 's user avatar
13 votes

When have we found better bounds for known algorithms?

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^...
Jan Johannsen's user avatar
8 votes

When have we found better bounds for known algorithms?

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 ...
Mark Schultz-Wu's user avatar
7 votes

When have we found better bounds for known algorithms?

Recent work of Anupam Gupta, Euiwoong Lee, and Jason Li [1] shows that the Karger-Stein algorithm for the minimum $k$-cut problem has, in fact, asymptotic time complexity $O(n^{k+o(1)})$, improving ...
Clement C.'s user avatar
  • 4,471
6 votes
Accepted

What is the relevance of Real Analysis in TCS?

[This is only partly an answer but way too long for a comment] Real analysis is definitely relevant for computer science! It gets used all over the place in scientific computing. Take a look at any ...
Joshua Grochow's user avatar
6 votes
Accepted

Most efficient inplace merge algorithms (stable and unstable)

TLDR The latest stable one with linear moves is from 2008 and with detailed description can be found here. According to their benchmarks, it is less than two times slower than standard merge that ...
Guest's user avatar
  • 76
6 votes

When have we found better bounds for known algorithms?

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 ...
Chandra Chekuri's user avatar
4 votes

When have we found better bounds for known algorithms?

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 ...
JimN's user avatar
  • 1,318
3 votes

Random walk and mean hitting time in a simple undirected graph

In a recent paper, we found an mn upper bound (no big O) on the expected number of "cycles popped" by Wilson's algorithm and it is tight up to constants. It doesn't directly answer the question of ...
Heng Guo's user avatar
  • 375
2 votes

How is additive error handled in this simple algorithm? 'Product of all elements'

Use Taylor series expansion for the function $\prod_{i=1}^{n} (u_i + y)$ around $y=0$ to obtain the error as $\epsilon (\prod_{j=1}^{n} u_j) \sum_{i=1}^{n} u_i^{-1} + O(\epsilon^2)$. Note that Taylor ...
Soumya Basu's user avatar
2 votes

What are the worst-case and average-case time complexities of the greedy algorithm for the weighted set cover problem?

Let $n$ be the total number of elements in all sets in $F$, basically your input size. Maintain a priority queue of the remaining sets, prioritized by cost / number of uncovered elements. Every time ...
David Eppstein's user avatar
2 votes
Accepted

Proof techniques for string algorithms?

There is some work on developing an algebraic or grammar-based view of string algorithms, for example Robert Giegerich, Carsten Meyer, Peter Steffen: A discipline of dynamic programming over sequence ...
Christian Komusiewicz's user avatar
1 vote

What is the relevance of Real Analysis in TCS?

Real Analysis is very important to certain branches of computer science. I am assuming you know the epsilon-delta definition of the limit of a function, but I would argue that the heart of limits and ...
NaturalLogZ's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible