Comments on: Logicians on safari

By: aram

aram — Tue, 05 Dec 2006 12:41:15 +0000

My last post should have been qualified by assuming some sort of plausible conjecture, of course.

By: aram

aram — Tue, 05 Dec 2006 12:39:03 +0000

One interesting thing about the chess example is that it’s not sufficient merely to know a winning strategy for chess. So the aliens’ job would be much harder than merely playing optimally against any opponent.

By: Scott

Scott — Wed, 08 Nov 2006 08:42:00 +0000

Scott, what TCS results do you intend in example #1 with the chess strategy?

As I said before, the result in question is IP=PSPACE [Shamir, 1990].

By: Scott

Scott — Wed, 08 Nov 2006 08:38:00 +0000

Bram, funny you should mention that — while your friend’s file distribution software might not be theory, it is something that I downloaded just a week ago, and that I’ve been happily using ever since to watch South Park episodes. Tell your friend I said thanks — he’s enabled a whole new level of procrastination!

By: Bram Cohen

Bram Cohen — Wed, 08 Nov 2006 07:03:00 +0000

Scott, for some interesting work in distributed computing, a ‘friend’ of mine did some interesting work in robust file distribution techniques. You might find the actual theory behind it to be so straightforward as to be trivial, and I would generally be inclined to agree, but there’s this funny business of other smart people having attacked the same problem and come up with much more complicated, less serviceable solutions.

By: TCS ignoramus mathematician

TCS ignoramus mathematician — Tue, 07 Nov 2006 23:52:00 +0000

Scott, what TCS results do you intend in example
#1 with the chess strategy? It sounded like the god has a proof of a theorem describing the winning strategy and this is then encoded as probabilistically checkable proof. But maybe you mean something else.

By: chiz

chiz — Tue, 07 Nov 2006 05:44:00 +0000

I wasn’t flaming, just asking a sincere question. There is, however, an ambiguity - whether we’re asking for significant developments in TCS that would be worthy of writing up in a book, or Sean’s original question, significant developments, especially recent ones, that help us understand the universe.

The discovery of phrase-structured grammars, or that you can build set-theoretical models for the lambda calculus, or the discovery of lazy evaluation strategies for programming languages, or the discovery of the various linear logics are all important but they have limited relevance outside CS, excet sometimes to cognitive science. It’s difficult to think of anything outside complexity theory that applies more broadly.

By: Scott

Scott — Mon, 06 Nov 2006 10:47:00 +0000

Now, what about areas of TCS other than complexity theory?

A main reason I went into complexity theory is that I couldn’t find so many tender nuggets in the other parts of TCS. If any distributed computing or programming language people disagree with that assessment, don’t flame me — nugget me!

By: Scott

Scott — Mon, 06 Nov 2006 08:05:00 +0000

Scott, could you give me a good reference specifically on the Riemann Hypothesis angle?

What I said applies to formal proofs of any statement whatsoever. The Riemann Hypothesis was just an example.

By: Kea

Kea — Mon, 06 Nov 2006 07:43:00 +0000

Scott, could you give me a good reference specifically on the Riemann Hypothesis angle?