Last call to make your voice heard! Our 2022 Developer Survey closes in less than a week. Take survey.
104 votes
Accepted

What is the contribution of lambda calculus to the field of theory of computation?

$\lambda$-calculus has two key roles. It is a simple mathematical foundation of sequential, functional, higher-order computational behaviour. It is a representation of proofs in constructive logic. ...
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
44 votes

Real computers have only a finite number of states, so what is the relevance of Turing machines to real computers?

To complete the other answers: I think that Turing Machine are a better abstraction of what computers do than finite automata. Indeed, the main difference between the two models is that with finite ...
user avatar
  • 7,643
33 votes

The unreasonable power of non-uniformity

A flip answer is that this isn't the first thing about complexity theory that I'd try to explain to a layperson! To even appreciate the idea of nonuniformity, and how it differs from nondeterminism, ...
user avatar
32 votes
Accepted

Real computers have only a finite number of states, so what is the relevance of Turing machines to real computers?

There are two approaches when considering this question: historical that pertains to how concepts were discovered and technical which explains why certain concepts were adopted and others abandoned or ...
user avatar
  • 3,741
30 votes

Evidence that matrix multiplication is not in $O(n^2\log^kn)$ time

There's an algorithm for multiplying an $N \times N^{0.172}$ matrix with an $N^{0.172} \times N$ matrix in $N^2 \operatorname{polylog}\left(N\right)$ arithmetic operations. The main identity used for ...
user avatar
29 votes

What is the contribution of lambda calculus to the field of theory of computation?

I think $\lambda$-calculus has contributed in many ways to this field, and still contributes to it. Three examples follow, and this is not exhaustive. Since I am not a specialist in $\lambda$-calculus,...
user avatar
  • 4,400
28 votes

The unreasonable power of non-uniformity

Here is a "smoothness" argument that I heard recently in defense of the claim that non-uniform models of computation should be more powerful than we suspect. On one hand, we know from the time ...
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
27 votes

Theoretical explanations for practical success of SAT solvers?

I am assuming that you are referring to CDCL SAT solvers on benchmark data sets like those used in the SAT Competition. These programs are based on many heuristics and lots of optimization. There were ...
user avatar
  • 21.3k
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
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
22 votes

What is the contribution of lambda calculus to the field of theory of computation?

Apart from the foundational role of the $\lambda$-calculus, which was mentioned in all other answers, I would like to add something on What exactly did the lambda calculus do to advance the theory ...
user avatar
22 votes

Theoretical explanations for practical success of SAT solvers?

I am typing this quite quickly due to severe time constraints (and didn't even get to responding earlier for the same reason), but I thought I would try to at least chip in with my two cents. I ...
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
18 votes

Theoretical explanations for practical success of SAT solvers?

I'm not an expert in this area, but I think the random SAT / phase transition stuff is more or less completely unrelated to the industrial/practical applications stuff. E.g., the very good solvers ...
user avatar
18 votes

Theoretical explanations for practical success of SAT solvers?

Let me add my two cents of understanding to this, even though I've never actually worked in the area. You're asking one of two questions, "what are all the known approaches to proving theoretical ...
user avatar
17 votes

Why study type theory?

Type theories in which every type is inhabited are far from being useless. True enough, through the eyes of logic they are inconsistent, but there are other things in life apart from logic. A general ...
user avatar
  • 26.4k
17 votes

Status quo of category theory and monads in theoretical computer science research?

There have been a number of developments with regards to the use of monads in the theory of computation since Eugenio Moggi's work. I am not able to give a comprehensive account, but here are some ...
user avatar
  • 26.4k
17 votes

Theoretical explanations for practical success of SAT solvers?

There is a paper "Relating Proof Complexity Measures and Practical Hardness of SAT" by Matti Järvisalo, Arie Matsliah, Jakob Nordström, and Stanislav Živný in CP '12 that attempts to link the hardness ...
user avatar
17 votes

Possible to do Complexity theory with only counting and Pigeonhole

If you are looking for non-pigeon-hole type arguments, then there is good news: they exist! The pigeon-hole principle is a certain template for proof by contradiction. There are concepts in TCS which ...
user avatar
16 votes

Should reductions make us more or less optimistic for the tractability of a problem?

What is missing from the analogy is some notion of the relative distances involved. Let's replace Alaska in our analogy with the moon: You're an explorer, searching for a bridge between the North ...
user avatar
16 votes
Accepted

What CS theories are absolutely paramount for someone new to TCS to understand?

(Disclaimer: this answer has a focus on programming languages theory, which is only one of the many disciplines under the TCS umbrella. Apologies for the length.) A small digression You are asking ...
user avatar
  • 668
16 votes

What is the "question" that programming language theory is trying to answer?

The overall purpose of PLT is to make industrial software engineering (in a general sense) cheaper (also in a general sense), through optimising the most important tool (programming languages) and ...
user avatar
15 votes
Accepted

Analogies between VNP and NP

The basic idea is that summing over all Boolean strings (VNP) is like counting the solutions to an NP problem. Even from this perspective, one sees that VNP is more like #P than NP. This is also true ...
user avatar
14 votes
Accepted

Should reductions make us more or less optimistic for the tractability of a problem?

I think this is a very good question. To answer it we need to realise that: not all reductions are alike, to feel optimistic, we need to learn something genuinely helpful. Typically, whenever we ...
user avatar
13 votes

What is the contribution of lambda calculus to the field of theory of computation?

Your questions can be approached from many sides. I'd like to leave the historical and philosophical aspects on the side and address your main question, which I take to be this: What's the point of ...
user avatar
13 votes

Sensitivity-Block sensitivity conjecture - Implications

Here is what Scott Aaronson has to say on the subject: What makes this interesting is that block-sensitivity is known to be polynomially related to a huge number of other interesting complexity ...
user avatar
  • 14.1k
13 votes

Evidence that matrix multiplication is not in $O(n^2\log^kn)$ time

Well, one thing is I think that all the constructions we know of - and even the families of potential constructions that people have proposed (e.g., Cohn-Umans approaches, generalizations of ...
user avatar
12 votes

What is the contribution of lambda calculus to the field of theory of computation?

Turing argued that Mathematics can be reduced to a combination of reading/writing symbols, chosen from a finite set, and switching between a finite number of mental 'states'. He reified this in his ...
user avatar
  • 221

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