Beautiful results in TCS

Question

Recently, a friend of mine (working in TCS) mentioned in a conversation that "he wanted to see/know all (or as much as possible) of the beautiful results in TCS in his lifetime". This kind of made me wonder about the beautiful results in this area and hence the motivation for the following question:

Which results (or ideas), in your opinion, are beautiful in theoretical computer science? It would be great if you mentioned the reason as well. [Would also be fine even if the ideas originate in mathematics, but have aroused interest and found uses in TCS]

I would start with an answer as Cantor's diagonal argument because it's simple, elegant and yet a powerful result.

Answer 1

The undecidability of the halting problem.

Beautiful for many reasons. It is an impossibility result. The proof uses diagonalisation. The statement applies to a broad range of models of computation. It can be formulated in a variety of ways, particularly, using standard programming languages. It was a watershed result in the history of computing. Extending this statement leads to Rice's Theorem, Turing degrees and many other cool results. Etc. Etc. Etc.

Answer 2

The possibility of public-key cryptography, for example, Diffie-Hellman key exchange scheme.

It breaks the very strong preconception that people have to meet before exchanging secrets on an insecure channel.

Answer 3

In my opinion, the Curry-Howard correspondence is one of the most beautiful theoretical results, and the one that drove me to do research.

The idea that two systems, programs on the one hand, and proofs on the other hand, have exactly the same structure, is almost of philosophical nature: are there some general "reasoning patterns"?

Answer 4

I was and still am surprised by Euclid's algorithm. To me, it is a testament to power of human thinking - that people could conceive of such an algorithm so early (around 300 BC if I trust my memory).

Fast forwarding, there is mind numbing literature on the subject. I think Scott Aaronson's list should be helpful in this regard - though, as Aaronson himself says its not complete (and not entirely theoretical)

Answer 5

surprisingly one of the most obvious answers not added yet. sometimes one works too much with something to see it impartially. the theory of NP completeness launched by Cook/Levin and immediately amplified by Karp who gave an early indication of its ubiquitousness, even more prescient in retrospect. in many ways this is the birth of modern TCS & complexity theory, and its core/key/notorious question P=?NP is still open after four decades of intense study/attack. P=?NP has a $1M Claymath award for its solution.

the Cook proof introduced the NDTM which is apparently not at all a mere theoretical curiosity but an almost extremely fundamental part of TCS. launched a thousand ships, so to speak. moreover, it continually resists/defies efforts via one of the other key/powerful TCS techniques mentioned in this list, diagonalization, seen in eg the BGS-75 Oracle/Relativization results-- suggesting that there must be something exotic and different about any possible solution, also further suggested/expanded by the Razborov-Rudich Natural Proofs paper (2007 Godel prize).

there are many, many refs on the subj but one more recent with some 1sthand account of the history can be found in The P=?NP Question and Godel's Lost Letter by RJ Lipton

Answer 6

Yao's technique to use von Neumann's Minmax Theorem to prove lower bounds for Randomized Algorithms. I find it as something out of this world.

Probabilistic method to prove the existence of objects that we find it difficult to construct including the Lovasz Local Lemma. These techniques are so simple, yet so powerful.

Madhu Sudan's coding theory constructions using polynomials.

Expanders (this started off as Ramanujan graphs) and Extractors and their applications in Pseudorandomness.

Cooley and Tukey's Fast Fourier Transform algorithm to find DFT. (Though, as assumed by Tukey, this was a rediscovery of a well known technique, at least known to Gauss!)

Barrington's Theorem, (a very surprising result in its time)

Parallel Repetition Theorem (though the result is nice, the proof is not easy)

Lovasz Theta function to estimate the shannon capacity of a graph.

Ellipsoid algorithm that showed that LP is in P, surprising many at a time when many still suspected it could be NP-Complete.

Answer 7

Kolmogorov Complexity and the incompressibility method.

The incompressibility method - based on Kolmogorov complexity - provided a new and intuitive way of formulating proofs. In a typical proof using incompressibility method, one first chooses an incompressible object from the class under discussion. The argument invariably says that if a desired property does not hold, then, in contrast with the assumption, the object can be compressed and this yelds the required contradiction.

See for example the proof that there is an infinite number of primes, the alternative proof of the Godel's incompleteness theorem, or the connections between Kolmogorov Complexity and Computational Complexity, ....

Answer 8

A beautiful result which builds on the PCP theorem states that it is computationally hard (NP-hard) to satisfy more than 7/8 of the clauses of 3SAT formula even for satisfiable ones.

Answer 9

I was (and still am) astonished by Kleene's Second Recursion Theorem. On the surface, it seems simple and not very useful but I later found out it's deep both mathematically and philosophically.

When I also read about the variant proven on Turing Machines (very very informally stating that machines can obtain their own descriptions or equivalently that there are machines that output their own description, like a program that prints itself..), I felt my brain twist so hard, yet intrigued like never before. Then, you see how the theorem is used to give one line proofs for undecidability of halting problem and unrecognizability of minimal machines..etc.

Answer 10

shors algorithm for factoring in BQP. in my opinion/memory, quantum computation was more just a theoretical curiosity until this result in 1994, at which point it seems the literature and research interest into QM computing exploded. its still arguably one of the most important QM algorithms known. awarded the 1999 Gödel prize. it also reveals that factoring in QM computation is actually in a sense somewhat better understood than in classical computing where eg the question of whether Factoring is NP complete is still open.

Answer 11

Shannon's source and channel coding theorems.

A mathematical definition that distinguished between the transmitted, receiver and medium and which ignored the semantics of the message was a big step. Entropy, in the context of data is a fantastically useful notion. And because information theory should be better known.

Answer 12

I think graph minor theorem by Robertson and Seymour was most wonderful theories I ever seen (and partially read it). First of all it's quiet complicated, but base conjectures are not hard and may be everyone working in TCS can guess them. Their extreme effort to prove them was wonderful. In fact after I read some of the papers in that series I understand power of human mind.

Also graph minor theorem has a great impact on different fields of TCS. Like graph theory, approximation algorithm, parametrized algorithms, logic, ...

Answer 13

seems to me the AKS P-time primality test is quite beautiful in various senses. a breakthrough at the time, one of the great but rather rare breakthroughs seen in complexity theory in our lifetimes. it solves a problem dating back to greek antiquity & relates to some of the earliest algorithms invented (sieve of eratosthenes), ie identifying primes efficiently. its a constructive proof that primality detection is in P as opposed to many great proofs that are unfortunately nonconstructive.

its interconnected to the RSA cryptography algorithm mentioned in another answer because that algorithm needs to find large primes quickly, prior to the AKS algorithm this was only probabilistically possible. its fundamentally connected to number theory & other deep problems eg the Riemann conjecture which in many ways is the original realm of algorithmics.

awarded the 2006 Gödel Prize and the 2006 Fulkerson Prize

Answer 14

One of my favourite family of results is that various problems of a seemingly infinite nature are decidable.

1. The first order theory of real closed fields is decidable (by Tarski). Euclidean geometry is also a model of the axioms of real-closed fields, hence, by Tarski, first order statements in this model are decidable.
2. Presburger arithmetic is decidable.
3. First order theory of algebraically closed fields (this includes complex numbers) is decidable.
4. Monadic second order logic over infinite (and finite) words is decidable. The proof is elegant and can be taught to undergrads.

Answer 15

There are lots of lovely results about probabilistic algorithms, which are deceptively simple and a great step forward in the way we think about computation.

von Neumann's trick for implementing a fair coin with a biased one. We are so used to probabilistic algorithms now, but from an outside perspective, this is unbelieveably cool. Both the algorithm and proof are accessible to anyone who knows high-school probability.

Answer 16

The result by Tim Griffin that control operators such as call/cc are related to classical logic, extending the Curry-Howard correspondence.

Basically, the typing of call/cc is such that if $E$ has type $\neg\neg \tau$, then $\mathtt{call/cc}{(E)}$ has type $\tau$. This works out when interpreting the type $\neg\tau$ as $\tau\rightarrow\bot$, as is standard in logic, and corresponds to the type of a function that takes a $\tau$ and never returns. That's exactly what a continuation does, making the correspondence work.

His paper, "A Formulae-as-types notion of control", appears in POPL 1990.

Answer 17

My favorite is Rabin's linear time algorithm for computing the closest pair of points in the plane (or more precisely its simplification). It get across the importance of the computation model, the power of randomized algorithms, and some elegant way to think about randomized algorithms.

This said, CS is still far from achieving the level of elegance one encounters in mathematics (well, they had 5000 years head start), from basic definitions/results in calculus, topology (fixed point theorems), combinatorics, geometry (Pythagorean theorem http://en.wikipedia.org/wiki/File:Pythag_anim.gif), etc.

If you look for beauty, look for it everywhere...

Answer 18

This result is probably a bit recent to qualify as fundamental, but I believe that the types-as-homotopy-types interpretation qualifies. This view allows interpreting types from constructive type theory as sets with certain geometric properties, in this case homotopy.

I find this point of view to be particularly beautiful as it makes certain previously complex observations about type theory simple, for instance the fact that"axiom K" is not derivable.

An overview of this budding field by Steve Awodey can be found here.

Answer 19

Zero-knowledge proof is a very interesting concept. It allows for an entity, the prover, to prove (with high probability) to another entity, the verifier, that it knows "a secret" (a solution to some NP-problem, a modular square-root of some number, a discrete log of some number etc …) without giving any information at all about the secret (which is difficult at first glance, since the first idea for proving that you know a secret is to actually tell the secret, and that any communication that could result in the verifier believing that you know the secret can a priori only increase the knowledge of the verifier about the secret).