# Beautiful results in TCS

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.

-
Near-duplicate of this question (but only near, because algorithms is a proper subset of TCS) – Jeffε Feb 26 '12 at 15:40
I am not if this is a good question in its current form, please see Good Subjective, Bad Subjective. – Kaveh Feb 26 '12 at 19:28
At the very least, this needs to be CW. – Suresh Venkat Feb 27 '12 at 3:41
Maybe we could modify the question to focus on non-algorithmic results -- seeing as the other thread is about algorithms. – Vijay D Feb 27 '12 at 19:57
In his blog, Lance Fortnow has lists of "favorite theorems" of each decade. There are quite a bit of beautiful results in those lists. – MCH Feb 28 '12 at 16:46

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.

-

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"?

-
Personnaly, I consider the Curry-Howard correspondance as the canonical example of duplicated theories due to different contexts whereas they have the same mathematical denotation. It should be rather considered as as shame of humans who aren't able to recognize existing structures and reinvent the wheel. – Ludovic Patey Feb 26 '12 at 19:11
I completely disagree. If Curry-Howard is about puny humans duplicating work, so is much of modern mathematics, particularly results relating structures in combinatorics, algebra and topology. – Vijay D Feb 27 '12 at 10:00
You are right in the sense that mathematics consists mainly of finding correlations between structures, and a correlation is by definition a non-independence, revealing some duplications in at least some parts of the theories. In order to be consistent, I must conclude that mathematics are a shame in its essence because if we were able to see duplications, theorems would be obvious and mathematics useless. ^^ – Ludovic Patey Feb 28 '12 at 18:46
Turingoid: I agree. I have come to similar conclusions (about reinventing the wheel) when working with symmetry concept. It is really a shame, that we are unable to work at level of primary symmetry/asymmetry relations. IMO there will be a collapse of some of actual sciences into wider ones when we finally break through. – Boordet Mar 2 '12 at 1:05
If only there were some way to automate the process. – Jeffε Mar 3 '12 at 3:59

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.

-

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)

-

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 - Actually, NDTM's already appear in Turing's 1936 paper as "choice machines"; see Wikipedia. – Jeffε Feb 28 '12 at 19:17 oops, ok. thx for correction. anyway the cook paper is maybe 1st to show the NDTM is much different than a DTM in a complexity theory sense. – vzn Feb 29 '12 at 15:39 Oops! Was just about to post this. I was also surprised it wasn't posted immediately. – Andrew D. King Feb 29 '12 at 19:26 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, .... - 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. - The probabilistic method is not really a result. It's just an immediate feature of the definition of probability. For similar reasons it's hard to argue it is special to TCS (despite there being a book with the same name). – Lembik May 19 '14 at 16:19 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. - 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. - Also note that Shannon almost invented information theory in its seminal paper. – Alejandro Piad Jun 20 '13 at 20:05 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. - Even more amazing since 7/8 of the clauses can be satisfied quite trivially (by a random assignment or a greedy algorithm.) – Jan Johannsen Feb 28 '12 at 8:17 This result isn't exactly the PCP theorem. It builds on the PCP theorem but needs much more work than that. – MCH Feb 28 '12 at 15:42 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. - note that factoring being NP-complete would be a big shock, as it would imply coNP = NP – Sasho Nikolov Feb 28 '12 at 16:32 I would put Simon's algorithm together with Shor's. – Juan Bermejo Vega Feb 29 '12 at 13:29 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, ... - 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. - 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 - This is definitely an important result, but beautiful? Really? – Jeffε Feb 28 '12 at 19:14 I agree with the above comment by JeffE. The result is vastly significant and thats what has been pointed out in the answer, rather than how (or what idea(s) used in) AKS primality testing is/are beautiful. – Nikhil Feb 29 '12 at 6:20 to me a "vastly significant" result is beautiful. "your mileage may vary". – vzn Feb 29 '12 at 15:36 Miller-Rabin is quite beautiful, on the other hand – Sasho Nikolov Feb 29 '12 at 21:08 dont know why people would consider the probabilistic algorithm superior in beauty to the exact algorithm. yes, AKS is largely based on Miller-Rabin but is major advance removing the randomization that was missed (or maybe not seen as possible) for decades & finally found. to me thats beautiful. moreover number theory is just a beautiful area of mathematics/algorithmics [with the theory of primes starring in number theory], this perspective can be seen in eg the famous book Mathematicians Apology by GH Hardy. – vzn Mar 7 '12 at 19:32 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. - I would have expected you to mention Yao's minmax principle for finding lower bounds on the expected running times of Las Vegas algorithms. It connects ideas of game theory with probability and algorithms. – karthik Feb 28 '12 at 17:43 Sure. But I'm spamming this question with enough answers already. Please add your favourite result as an answer. – Vijay D Feb 28 '12 at 18:36 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.

-

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...

-

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.

-

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).

-