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,...
- 24.3k
22
votes
Problems that started out with hopelessly intractable algorithms that have since been made extremely efficient
Computing a generating set of invariants (sometimes called the computational problem of "Noether's Normalization Lemma") for the action of $SL_3$ on an $n$-dimensional vector space $V$. (You ...
- 36.9k
17
votes
Problems that started out with hopelessly intractable algorithms that have since been made extremely efficient
The task of unification went from an exponential solution to linear time in the timespan of about a decade. The original exponential algorithm was a corner-stone for symbolic AI approaches and enabled ...
- 271
17
votes
Accepted
Entscheidungsproblem vs. Unvollständigkeitssatz (soft question)
The two words do not refer to the same thing. Hilbert's Entscheidungsproblem was the question whether there is an algorithm that decides the universal truth of first-order logical sentences, which was ...
- 4,631
14
votes
Accepted
Rabin's "degree of difficulty of computing a function, and a partial ordering of recursive sets"
There are two loanable copies at The National Library of Israel.
Here is a scanned copy.
- 14.3k
14
votes
Accepted
Are Turing machines still useful as model of computation?
I think the issue is that, you're misunderstanding the purpose of the Turing Machine model.
Turing Machines are not meant to be programmed in. If you're writing code, you absolutely should not be ...
- 2,830
14
votes
Accepted
When was co-NP introduced for the first time?
Albert R. Meyer and Larry J. Stockmeyer introduced the polynomial hierarchy in 1972 with their paper "the equivalence problem for regular expressions with squaring requires exponential space"...
- 5,840
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^...
- 4,631
12
votes
Problems that started out with hopelessly intractable algorithms that have since been made extremely efficient
I can think of two additional examples to the ones mentioned above, although I'm not sure that they were ever considered intractable.
Lovász Local Lemma - The Lovász local lemma (LLL) is a powerful ...
10
votes
Problems that started out with hopelessly intractable algorithms that have since been made extremely efficient
Interior point algorithms for LP. Although they came after Ellipsoid they are a different class of provably polynomial-time algorithms. And despite initial skepticism about their ability to outperform ...
- 6,979
10
votes
Problems that started out with hopelessly intractable algorithms that have since been made extremely efficient
Until Francis's QR algorithm was discovered, computing the eigenvalues was often done by first computing the characteristic polynomial, which was often an expensive and inaccurate endeavor, as has ...
- 101
10
votes
Accepted
Are there two definitions of Cobham's thesis?
Cobham's thesis is essentially the Extended Church-Turing thesis. Historians of computer science have gone back and figured out who first proposed it, and attached his name to it.
What Cobham was ...
- 24.3k
9
votes
Accepted
System F and System T names
I posted this to TYPES, but its probably worth copying here as well:
In "The system F of variable types, fifteen years later", Girard
remarks that there was no particular reason for the name F:
...
- 32.4k
9
votes
Accepted
Was counting complexity first introduced by Valiant in 1979?
Yes, the complexity class $\mathsf{\#P}$ is first introduced in Valiant's seminal paper "The complexity of computing the permanent." TCS, (1979). This is very clear. As for the terminology, strictly ...
- 184
8
votes
Accepted
Does Rabin/Yao exist (at least in a form that can be cited)?
After more than two years, I have to assume the answer is "no". (Posting this stub answer so the question can be marked as answered.)
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 ...
- 918
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 ...
- 4,451
7
votes
Are there any intersections between Theory A and Theory B?
One cool example of work that straddles things that are typically considered theory A and things typically considered theory B are the lower bounds on the running time of the simplex algorithm with ...
- 18.1k
6
votes
Are there any intersections between Theory A and Theory B?
One example (from my research field) is analysis of dynamical systems: in a (linear) dynamical system, you are given a matrix $A\in {\mathbb Q}^{d\times d}$ and you reason about various properties of $...
- 5,531
6
votes
Problems that started out with hopelessly intractable algorithms that have since been made extremely efficient
I wanted to say Linear Programming, but although theoretical algorithm that are as fast as matrix multiplication have now been found, in practice people are still mostly using the exponential Simplex ...
- 958
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 ...
- 6,979
6
votes
Problems that started out with hopelessly intractable algorithms that have since been made extremely efficient
Algorithms that computed the position of planets when they thought the earth was the center of the universe versus when they realized the sun was the center of the solar system. :-)
While that's not ...
5
votes
Problems that started out with hopelessly intractable algorithms that have since been made extremely efficient
Perhaps a good example is Graph Isomorphism testing, also discussed here:
Fastest known deterministic algorithm for the undirected Graph Isomorphism problem
and here:
https://people.cs.uchicago.edu/~...
- 1,596
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 ...
- 1,276
4
votes
Problems complete for non-deterministic PSPACE
A class that was more familiar at the time than NPSPACE was the class of context-sensitive languages.
Let CSL denote the set of context-sensitive languages. By Kuroda's theorem (1960), this set is ...
- 5,840
4
votes
Problems that started out with hopelessly intractable algorithms that have since been made extremely efficient
The ideal membership problem: if $f_1, \ldots, f_s$ are polynomials of degree at most $d$ with variables in $x_1, \ldots, x_n$, then are there $g_1, \ldots, g_n$ such that $f_1g_1 + \cdots + f_ng_n = ...
4
votes
Accepted
Is Barbara Liskov's claim that CLU was the first implemented language to provide linguistic support for data abstraction accurate?
Development of ML began circa 1973, but I can't find a published description of it earlier than POPL'78. As far as I can tell, it didn't have modules at that time. It did have ...
- 186
3
votes
History of recursion
From Recursive Functions article on SEP:
The use of recursion goes back to the 19th century. Dedekind [1888] used the notion to obtain functions needed in his formal analysis of the concept of ...
- 21.5k
3
votes
History of recursion
Maybe slightly tangential to the original question, but the blog entry "How recursion got into programming: a comedy of errors" describes an interesting part of early computing history.
- 11.4k
2
votes
Problems that started out with hopelessly intractable algorithms that have since been made extremely efficient
Travelling salesman may not theoretically be solvable in polynomial time, but given that there are probabilistic approximations, TSP is now realtime and polynomial. In the 80s a German problem ...
- 121
Only top scored, non community-wiki answers of a minimum length are eligible