150 votes
Accepted

Was the reduction in Shor's algorithm originally discovered by Shor?

I have to admit (surprising as it sounds) that I don't know really the answer. I either discovered or rediscovered this reduction myself. I discovered the discrete log algorithm first, and the ...
user avatar
65 votes
Accepted

The origin of the notion of treewidth

If you really want to know what led Neil Robertson and me to tree-width, it wasn't algorithms at all. We were trying to solve Wagner's conjecture that in any infinite set of graphs, one of them is a ...
user avatar
54 votes

Was the reduction in Shor's algorithm originally discovered by Shor?

The random reduction from factorization to order-finding (mod N) was very well known to people working in number theory algorithms in the late 1970's and early 1980's. Indeed, it appears in a paper ...
user avatar
31 votes
Accepted

Who introduced nondeterministic computation?

I have always seen the notion of nondeterminism in computation attributed to Michael Rabin and Dana Scott. They defined nondeterministic finite automata in their famous paper Finite Automata and Their ...
user avatar
28 votes
Accepted

Impact of Grothendieck's program on TCS

Grothendieck's inequality, from his days in functional analysis, was initially proved to relate fundamental norms on tensor product spaces. Grothendieck called the inequality "the fundamental theorem ...
user avatar
26 votes
Accepted

What was the original intent for the creation of Lambda calculus?

He wanted to create a formal system for the foundations of logic and mathematics that was simpler than Russell's type theory and Zermelo's set theory. The basic idea was to add a constant $\Xi$ to ...
user avatar
25 votes
Accepted

Rabin–Karp vs Karp–Rabin

I've asked Dick personally out of curiosity a few years back. He said that as far as he knows Rabin-Karp was a random switch many years after the paper was first published. He also indicated that it ...
user avatar
24 votes
Accepted

Why was there a need for Martin-Löf to create intuitionistic type theory?

Very briefly: the simply-typed $\lambda$-calculus does not have dependent types. Dependent types were proposed by de Bruijn and Howard who wanted to extend the Curry-Howard correspondence from ...
user avatar
23 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,...
user avatar
22 votes

Arguments for/against Kolmogorov's conjecture about the circuit complexity of P

The footnote of my paper that you cite refers to a heuristic "argument" as well, at least, what we think was Kolmogorov's intuition -- the positive resolution of Hilbert's thirteenth problem. http://...
user avatar
22 votes
Accepted

How exactly does lambda calculus capture the intuitive notion of computability?

You're in good company. Kurt Gödel criticized $\lambda$-calculus (as well as his own theory of general recursive functions) as not being a satisfactory notion of computability on the grounds that it ...
user avatar
  • 26.6k
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 ...
user avatar
19 votes

Impact of Grothendieck's program on TCS

Grothendieck's impact can be felt in type theory and logic. For instance, Bart Jacobs' 700+ page volume Categorical Logic and Type Theory gives a uniform treatment of various type theories ($X$-type ...
user avatar
  • 16.6k
17 votes
Accepted

Did Stephen Cook see the significance of showing that SAT is NP-Hard before actually proving it?

First of all, Cook actually showed that the problem of whether a logical expression is a tautology is $\mathbb{NP}$-complete under Cook reductions. The proof however works by replacing them with Karp ...
user avatar
  • 3,741
17 votes
Accepted

Why was Schönfinkel's work on eliminating "bound variables" in logic so crucial?

TL;DR. The metamathematics of binding are subtle: they seem trivial but aren't — whether you deal with (higher-order) logics or 𝜆-calculus. They're so subtle that binding representations form an open ...
user avatar
  • 1,999
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 ...
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 ...
user avatar
  • 271
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.
user avatar
  • 14.1k
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 ...
user avatar
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"...
user avatar
12 votes

Impact of Grothendieck's program on TCS

Any applications of $p$-adic cohomology, etale cohomology in point counting formulas for algebraic varieties has roots in his work. I am guessing Mulmuley's vision of generalization of Riemann ...
user avatar
  • 12.5k
12 votes

Applications of topology to computer science

Nobody has yet mentioned directed algebraic topology, which was in fact developed to provide a suitable algebraic topological toolbox for the study of concurrency. There are also several low ...
user avatar
12 votes

Arguments for/against Kolmogorov's conjecture about the circuit complexity of P

The answer of Stasys on the previous question provides some intuition potentially in favor: https://cstheory.stackexchange.com/a/22048/8243 . I'll try to restate here as I understand it. The key ...
user avatar
  • 7,052
12 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^...
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 ...
user avatar
11 votes

Who introduced nondeterministic computation?

Here is what Odifreddi says on the issue: "Our model of a Turing machine is deterministic, in the sense that the instructions are required to be consistent (at most one of them is applicable ...
user avatar
  • 21.3k
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 ...
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 ...
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 ...
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 ...
user avatar
  • 184

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