Skip to main content
Share Your Experience: Take the 2024 Developer Survey
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
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 ...
Joshua Grochow's user avatar
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 ...
Jan Johannsen's user avatar
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 ...
liori's user avatar
  • 271
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"...
Hermann Gruber's user avatar
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.
Yuval Filmus's user avatar
  • 14.5k
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 ...
Joey Eremondi'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
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 ...
user3209423940248's user avatar
12 votes

What are pertinent references to cite on Scott domains?

I asked Dana Scott who kindly responded. I am relaying his answer: I think the paper “A type-theoretical alternative to ISWIM, CUCH, OWHY” answers the questions and gives the context of the discovery....
Andrej Bauer's user avatar
  • 29.2k
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 ...
Chandra Chekuri's user avatar
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 ...
Joe Boy's user avatar
  • 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 ...
Peter Shor 's user avatar
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 ...
Heyheyhey's user avatar
  • 184
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: ...
Neel Krishnaswami's user avatar
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 ...
Mark Schultz-Wu's user avatar
8 votes

What are pertinent references to cite on Scott domains?

First papers Scott (1993), A type-theoretical alternative to ISWIM, CUCH, OWHY. This 1969 manuscript was later published in TCS. The title is a bit odd but it seems to hide the very first written ...
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
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 ...
Sasho Nikolov's user avatar
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 $...
Shaull's user avatar
  • 5,646
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 ...
Neil Robertson's user avatar
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
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 ...
Thomas Ahle's user avatar
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/~...
Avi Tal's user avatar
  • 1,606
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 ...
Hermann Gruber'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
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 = ...
Jordan Barrett's user avatar
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 ...
benrg's user avatar
  • 186
3 votes

What are some "who ordered that?" moments in theoretical computer science?

Taking a liberal view of TCS, I can think of the following, all of which have profound influence on theoretical and practical computing. The Spectre vulnerability (which undermines speculation, a (...

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