Computational Complexity

Friday, May 08, 2009

 
Doctor for Two Decades

Posted by Lance

I measure academic age by years since Ph.D. and by that measure I just turned twenty. I passed my Ph.D. defense on May 5, 1989 (though technically I didn't graduate until June).

20 years. Wow. 20 years before my Ph.D. we didn't have a P vs. NP problem. Does the PCP theorem seem as ancient to today's grad students as Cook's theorem was to me?

In those 20 years we had incredible advances in 

• Complexity of approximations which includes developments of interactive proofs, probabilistically checkable proofs, the parallel repetition theorem, semi-definite programs and unique games.
• Great advances in coding theory in particular list-decoding codes.
• Tight connections between circuit hardness and derandomization. And we don't need random coins anymore for primality. 
• Explicit constructions of extractors, expanders and various other combinatorial objects with SL=L coming out of this theory.
• Quantum computing.
• Proof Complexity.
• Cryptography. Almost anything you can imagine you can implement cryptographically, at least in theory.
• The applications of computation theory to economic theory and vice versa.
• Amazing connections between all of the above.

And I got to watch it all in real time.

I've seen the Internet go from E-mail to Twitter. I've seen fax machines and CDs go from amazing technologies to has beens. And computers got much faster and smaller. I no longer have time for a restroom break when I LaTeX a paper.

Technology that hasn't changed much: Transportation. I still get from point A to point B the same way I did twenty years ago though now without being fed. 

What will the next twenty years bring? Many great theorems. Definitely. Multi-core computers with millions of cores. Probably. Large-scale quantum computers. Doubtful. A proof that P≠NP. Don't count on it.

7:33 AM # 4 comments

Thursday, May 07, 2009

 
New York THEORY DAY 2009

Posted by GASARCH

Dear Organizers of IBM Research|NYU|Columbia Theory Day,

You emailed me the ad for Spring 2009 Theory Day. THANKS!
You did this about a week ago. Hence, as is often the
case this is too much short notice to go.
Please announce it earlier in the future.

Also, I could not find on your website a pointer to the
abstracts of this years talks (If I missed it then please
let me know.  Other readers, also let me know.)

And lastly, your page on Recent and Upcoming Theory Days
should be retitled
Theory Days from 2003-2007 or be updated.

                                        bill gasarch

P.S. The talks look AWESOME!


                 The IBM Research|NYU|Columbia Theory Day
                         Friday, May 22, 2009


The Theory Day will be held at the Davis auditorium,
412 Schapiro (CEPSR) building, Columbia University, New York.

                                  Program

9:30   - 10:00    Coffee and bagels

10:00  - 10:55    Dr. Dana Moshkovitz (IAS)
                  Two Query PCP with Sub-Constant Error

10:55  - 11:05    Short break

11:05  - 12:00    Dr. Craig Gentry (IBM Research)
                  Fully Homomorphic Encryption Using Ideal Lattices

12:00  -  2:00    Lunch break

 2:00  -  2:55    Dr. Mark Braverman (Microsoft Research)
                  Approximating bounded depth circuits with polynomials

 2:55  -  3:15    Coffee break

 3:15  -  4:10    Dr. Muthu Muthukrishnan 
                  (Google Labs and Rugers University)
                  3 Problems in Internet Ad Systems

For directions, please see DIRECTIONS

To subscribe to their mailing list, follow instructions at HERE

Organizers:
Yevgeniy Dodis   dodis@cs.nyu.edu
Rocco Servedio   rocco@cs.columbia.edu
Tal Rabin        talr@us.ibm.com
Baruch Schieber  sbar@us.ibm.com

11:03 AM # 5 comments

Wednesday, May 06, 2009

 
My Kindle

Posted by Lance

As an MIT alum I have an automatic subscription to Technology Review, a pretty nice perk. Wrapped around the current issue was a note that I could trade my printed issue for access to the digital issue, with more content and earlier availability. I'll keep the printed issue because I can't read documents on the screen for long periods of time. I get a complementary digital issue of Scientific American by being part of their blog network but end up just skimming it and printing out any articles I really want to read.

But I found I can read for long periods from the Kindle which I got when Amazon released their second edition a few months ago. I've fallen in love with the device. I cancelled my paper subscription to the New York Times and read it now on the Kindle and have downloaded and read several books on the device. Often I'll send text documents to the Kindle for reading. The Kindle has resparked my interest in reading and I love many of the features including automatic bookmarking and easy dictionary look up where before I rarely put in the effort.

I saw recently that the Kindle attracts a much higher age demographic than most new electronic devices. My guess is that us older people have never gotten used to reading off a computer screen and are willing to spend money on a device that just lets you read.

But the Kindle doesn't work for much of my reading—mathematical research papers. The Kindle doesn't do formatting well, just converting PDFs to text. 

Today Amazon will announce the new Kindle DX with a larger screen, true PDF formatter and supposedly textbook friendly and thus I assume math friendly. Imagine for example putting conference proceedings on a Kindle-like device instead of having a heavy book or proceedings one has to use a laptop to look at. Or putting all the papers you need to referee/review on such a device. Would that make it more or less likely you will get the reviews in on time?

But how do I justify getting a new Kindle when I already own one? Sometimes being slightly ahead of the technology curve works against you.

6:12 AM # 11 comments

Tuesday, May 05, 2009

 
My Publications

Posted by Lance

I spent some time this weekend updating my publications page. I did well in the summer conference season: An ICALP paper and two each in Complexity and TARK. Not to mention my first ever Algorithmica paper was just accepted for publication.

My proudest 2009 publication: The Complexity of Forecast Testing written with Rakesh Vohra that appeared in the January issue of Econometrica, generally considered the top journal in economic theory. Consider the problem of testing a forecaster (like a weatherperson) who give a probability each day of an even that happens the next day. Alvaro Sandroni proved a strong negative result: Suppose a tester T makes decisions in a finite number of steps and passes (with high probability) any forecaster that correctly predicts nature. Then there is a probabilistic forecaster that will, with high probability, pass test T without any knowledge of nature, even if nature is adversarial.

Sandroni's forecaster requires solving exponential-sized linear programs. Vohra and I showed that Sandroni's theorem doesn't hold if we limit both the tester and forecaster to be efficiently computable (under generally believed hardness assumptions). We created efficiently computable testers so that for some distributions for nature, a forecaster would have to factor numbers or solve PSPACE-hard problems to pass the test.

This paper represents a large part of my current research: Applying the ideas and tools of computational complexity to economic theory, in particular seeing what happens in a wide variety of economic models with when we require the agents to be computationally efficient. Given the success of this paper (and others), perhaps some economists are beginning to realize the importance of capturing computation costs in their models.

5:51 AM # 7 comments

Monday, May 04, 2009

 
A new way to educate the public

Posted by GASARCH

How well known is the concept of the Turing Test? Readers of this blog know what it is. On Google it gets 2,360,000 hits. It has a Wikipedia entry: here. None of these mean that the public knows what it is.

I didn't think it was well known. However, in Roger Ebert's review of the movie X-men Origins: Wolverine he titles the review

A monosyllabic superhero who wouldn't pass the Turing Test.

In the review he never mentions the Turing Test or what it means. Does he expect his readers to know? Do they? Does the general public know what the Turing Test is? Will readers of the Ebert's column go to Wikipedia to find out? Might this be a way to educate people?

CHALLENGE TO MY READERS: find a movie whose review could illustrate a computer science or math concept. Here is one: The Usual Suspects:

As complicated an enjoyable as the classical proof of van der Waerden's theorem.

11:03 AM # 6 comments

Friday, May 01, 2009

 
Foundations of Complexity

Posted by Lance

In the first year of this blog I wrote a series of "lessons" to give an informal introduction to computational complexity but I never wrote a single post that links to them all. 

1. What is a Computer?
2. Computable and Computably Enumerable Languages
3. Universal Turing Machines and Diagonalization
4. Noncomputable Computably Enumerable Languages
5. Reductions
6. The Halting Problem
7. The Recursion Theorem
8. Efficient Computation
9. Nondeterminism
10. The P versus NP Problem
11. NP-Completeness
12. Turing Machine Redux
13. Satisfiability
14. CNF-SAT is NP-complete
15. More NP-complete Problems
16. Ladner's Theorem 
17. Space Complexity
18. Savitch's Theorem
19. The Immerman-Szelepcsényi Theorem

I hope to add more lessons in the future.

7:40 AM # 3 comments

Thursday, April 30, 2009

 
Converse oF Clarke's famous quote

Posted by GASARCH

The following kind of act was popular (say) 40 years ago: Someone claims to be able to read minds. He says things like I sense there is someone here named Bill. Then someone named Bill says Yes, thats me! Then the mindreader talks to Bill and seems to know things about him. How did the mindreader do it? He studies styles of clothes (Mindreader thinks: The way Bill is dressed he must be a college professor.) He gets Bill to reveal stuff about himself and echoes it back. The mind reader may have people who mingle with the crowd ahead of time and try to overhear conversations. This took some real skill to pull off.

Fast forward to the year 2008.

1. The mindreader could get everyones name ahead of time since most paid by credit card, and google some of them to find out more about them.
2. But, the audience knows he can do this.
3. The more precise his statements are (e.g., I sense that Bill co-writes a Blog with someone named Lance) the more obvious it is that he used GOOGLE and hence the less impressed I would be.
4. Lets look at this another way: How could a real mindreader convince us that he wasn't using Google? Or some other high-tech device?
5. Recall Arthur Clark's famous quote

   Any sufficiently advanced technology is indistinguable from magic.

   What is happening here is the inverse or converse or something of that:

   In a sufficiently advanced technlogical society it will be hard for a magician to impress anyone.

10:48 AM # 3 comments

Wednesday, April 29, 2009

 
International Spy Museum

Posted by GASARCH

I went to the International Spy Museum recently. I recommend it. However, there were two things I spotted that I know were incorrect. This makes their credibility as a source of information suspect. This is too bad--- as we'll see later.

1. The museum has the story of Nathan Hale. He was a spy for the Americans during the Revolutionary War. He was hanged and his last words were I regret that I have but one life to give for my country. In reality his last words were probably AAAAAAAAAAAHHHHHHHHHH. Actually they were never recorded, though some serious historians think he was the kind of guy who would say I regret ... . Not the same as saying it.
2. The museums had an exhibit of the Enigma machine. They were trying to make the (true) point that the story of cracking the Enigma was a secret for many years, and hence Turing didn't get credit until later. They phrased this as

   If the story of cracking the Enigma was known earlier then Turing would have won a Nobel Prize.

   A Nobel Prize? In what? Chemistry? Physics? Literature? Medicine? Peace? Economics? Peace (maybe its shortened the war)? The statement is clearly false. What they should have said was

   If the story of cracking the Enigma was known earlier, and if the Turing Award had been established, then Turing would have likely won a Turing Award.

Having gotten these two items wrong I now turn to a question for which I do not know the truth.

Did the Nuclear Secrets that Julius Rosenberg gave to the USSR speed up the building of the USSR's nuclear bomb?

I have read YES and NO for this question. The NO that I have read says that the biggest nuclear secret that the USSR ever got was the fact that the bomb could be built. Hence the person who leaked our biggest nuclear secret was... President Harry Truman. The YES that the Spy museum said was that the USSR bomb design was very close to the American one. What is the truth? That's just it- I don't know! If the spy museum had not made those other mistakes I would believe them on this. (My believe may still have been wrong.)

Wikipedia says the secrets were not valuable. Are they more credible?

1:34 PM # 8 comments

Archives