This work is licensed under a
Creative Commons License.

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, semidefinite programs and unique games.
 Great advances in coding theory in particular listdecoding 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 Email 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. Multicore computers with millions of cores. Probably. Largescale 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 ResearchNYUColumbia 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 20032007 or be updated.
bill gasarch
P.S. The talks look AWESOME!
The IBM ResearchNYUColumbia 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 SubConstant 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 Kindlelike 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 exponentialsized 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 PSPACEhard 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
Xmen 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. 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.

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.

But, the audience knows he can do this.

The more precise his statements are
(e.g., I sense that Bill cowrites a Blog with someone named Lance)
the more obvious it is that he used GOOGLE and hence the
less impressed I would be.

Lets look at this another way: How could a real mindreader convince
us that he wasn't using Google? Or some other hightech device?

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.

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.

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
