Choosing an Undergrad School

It is the time of year in the US that high school students have found out what schools have accepted them and now have to decide where to spend the next four years. Maybe because I am of that age, but I find myself talking more to students and parents about what school they should choose.

So let's assume you are a high school student who knows they will eventually want to get a Ph.D. in computational complexity or perhaps some other math-related topic. Where to go to school? Depends much on your personality and your choices.

The Elites (examples: Princeton, Harvard, Stanford, Yale): Many rich kids who feel entitled so you can get good grades without working hard. But you can also take advantage of great professors and some challenging courses and research opportunities if you are up to the challenge.

Intense Schools (MIT, Caltech, U. Chicago): Here you have to work hard for your grades against other very strong students in challenging courses. You won't have a better math/science education anywhere else but these schools won't give you as broad a social experience.

Broad Private Schools (Cornell, Northwestern): Here I have biases having gone to Cornell undergrad and now teach at Northwestern. Fine math and science programs not quite as strong as the above but more than made up by experiencing an undergraduate life with smart students across a wide spectrum of disciplines. Many a theorist got their start as a Cornell undergrad.


Liberal Arts Schools (Williams, Wesleyan, Harvey Mudd): You don't get the large research programs but instead have very good profs who focus on undergrad teaching. This is the easiest way to get involved in research as an undergrad.


Big State Schools (Illinois, U. California, Michigan, Wisconsin): You get a real mix of students from athletes to partiers to really smart kids looking to save a few dollars. You can certainly get a great math and science education. But you'll have to work hard when many of your fellow students may not be.

General advice: Doesn't really matter that much where you go, as long as you work hard you will succeed. Above all enjoy your undergrad days for they will be the best times of your life.

Going off topic in class: I think it worked--- this time

Recently I went off topic in a class. I think it was okay but I want YOUR thoughts.

1. On Monday I
   1. defined Primitive Recursive functions
   2. showed them that addition, mult, exp are all primitive recursive,
   3. talked a little bit about TOWER and WOWER, both primitive recursive,
   4. constructed by diag a computable function that was not prim rec,
   5. noted that this function is not natural
   6. noted that there are natural computable functions that are not prime rec (NOTE that I noted this),
   7. made the point that I can do the same diag argument for ANY reasonable system of (total) computable functions.
2. On Wednesday I was all set to start Turing Machines when a student named Amber said You promised to show us a natural example of a computable function that is not primitive recursive! I didn't recall exactly promising that but I very well might have and if a student cares about these things you want to nurture that curiosity.
3. I told the class that I would toss out today's lesson plan and talk about this, but I would be informal and some of what I said might not be quite right, but would get the idea across.
4. I asked one of the students who had his laptop up to stop surfing porn and look up Ackermann's function for me, so I could get the definition right.
5. I talked about the Union-Find Data Structure that has amortized O(n INVERSE-ACK(n)) running time for n operations. I noted that this would not be an impressive use of the Ackermann's function if Amber could find an O(n) structure. I had the class vote on if Amber could do that. This was about fifty-fifty. I then told them that Amber could not, not because she is not a fine programmer, but because there is a lower bound proof that nobody can do better. That is, the lower bounds has been proven.
6. I then talked about Goodstein Sequences which lead to computable functions that are not primitive recursive.

I went off topic. I am one lecture behind. Was it worth it?

1. This class is not a prereq to anything else so I do not HAVE TO COVER everything.
2. If I don't cover the topics on the syllabus then the guy who made up the syllabus, Gasarch, might get mad at me. This does not worry me.
3. I doubt I will end up cutting anything important. I usually spend the last few lectures on misc topics (e.g., sparse sets cannot be NPC unless P=NP) which I can skip.
4. They were interested in this. Not just Amber, but the whole class. That makes it worthwhile.

Misc:

1. I told the linguistics major in the class that Ackermann's function has applications in linguistics. He believed me until I told him YOU"VE BEEN PUNK'D!!
2. Ackerman's function gets 2,870,000 hits on Google. Ackermann's function gets 6,740,000 hits on Google. Does that make Ackermann correct? What if the wrong spelling got more hits?

Workshop/Award/Conference/Who wants to review books?

1. The Center for intractability at Princeton is having a Workshop on Approximation Algorithms. Here is the schedule of talks.
2. Vijay Vazirani, one of the organizers of the workshop, has won a Guggenheim CONGRATS!
3. There will be a conference on Theory of Computation as a Lens on the Sciences. Is Theory of Computation a Lens on the Sciences? What does that even mean? Goto the conference and find out! Who is the person under the Lens in the picture at the left side of this link?. A Clue- The answer is RELATIVEly easy.
4. Here are a list of books I need reviewed for my SIGACT NEWS column: HERE. To review a particular book email me at gasarch@cs.umd.edu. Before volunteering you should read my advice for reviewers. Also download a template for reviews either here as LaTeX or here as plaintext. I would like emails before April 25 which is when I put next column in final form. This way that columns list of books I want reviewed will be more accurate.
5. When does complexityblog make announcements? It is sporadic and somewhat random (Kolmogorov random?). Hence you are encouraged to look at this link for announcements of most theory events.

Do You Know the Way to San Jose?

Lots of CS Goodness going on at FCRC June 4-11.

• New for 2011 the STOC Poster Session: Share your exciting research on theory's greatest stage! Submission deadline May 2. Come and enjoy the posters and some refreshments Monday night. 
• Les Valiant gives his Turing award lecture Sunday evening followed by the STOC reception.
• Other great plenary speakers including Watson's David Ferrucci, reCAPTCHA's Luis von Ahn and theory's own Ravi Kannan. 
• The ever fun STOC Business Meeting on Tuesday (hosted by yours truly) including the presentations of this year's Gödel and Knuth prizes.
• There's also some conferences: STOC (Mon-Wed), Complexity (Wed-Fri), EC (Tutorials/Workshops Sun-Mon, Conference Tue-Thu), PODC (Mon-Wed), SPAA (Sat-Mon) and many more.
• Act now if you need a visa or STOC student travel support.

Register today (or by May 16 to avoid late fees) and I'll see you all in San Jose!

The Mathematics of Huging my great Niece Jordan

I have already blogged about (trying to) teach me Nephew Jason math here and my Great Nephew Justin math here. Now its my Great Niece Jordan's turn.

I was at a dinner with relatives including my 12 year old great niece Jordan. There were 10 people at the dinner.

BILL: Jordan, if everyone at this table hugged everyone else, how many hugs would there be?

JORDAN: If I get it right will you give me a hug?

BILL: I'll give you a hug in any case.

JORDAN: Okay. 10 times 10... so 100.

BILL: Can you hug yourself.

JORDAN: Sure (she then hugs herself).

BILL: For this problem lets assume you cannot hug yourself. Then how many.

JORDAN: Oh, that changes things. Its 10 times 9... so 90.

BILL: If I hug you and then you hug me, does that count as one hug or two?

JORDAN: Oh, that changes things. How do you do it?

BILL: Your answer of 90 counted BILL-HUGS-JORDAN and also JORDAN-HUGS-BILL. The same is true for every pair. So every pair was counted twice.

JORDAN: So... is the answer (9 times 10)/2 ... 45 ?

BILL: YES! Great. (They hug.)

JORDAN: You're not just a great uncle, you're an AWESOME Uncle!

BILL: And you're an AWESOME Niece!

Kanellakis and Grace Murray Hopper Prizes

The ACM announced several award winners today. Two of particular interest to the theory community.

Craig Gentry, recipient of the Grace Murray Hopper Award for his breakthrough construction of a fully homomorphic encryption scheme, which enables computations to be performed on encrypted data without unscrambling it.  This long-unsolved mathematical puzzle requires immense computational effort, but Gentry’s innovative approach broke the theoretical barrier to this puzzle by double encrypting the data in such a way that unavoidable errors could be removed without detection.  This insight has the potential to result in adaptable cryptography methods that can prevent security breaches and protect sensitive personal data.  Gentry is a researcher at IBM.  In 2009, he won the ACM Doctoral Dissertation Award.  The Hopper Award recognizes the outstanding young computer professional of the year. 


Kurt Mehlhorn, recipient of the Paris Kanellakis Theory and Practice Award for contributions to algorithm engineering that led to creation of the Library of Efficient Data Types and Algorithms (LEDA).  This software collection of data structures and algorithms, which Mehlhorn developed with Stefan Näher, provides practical solutions for problems that had previously impeded progress in computer graphics, computer-aided geometric design, scientific computation, and computational biology.  LEDA’s software has been incorporated in the applied research programs of thousands of companies worldwide in telecommunications, bioinformatics, Computer-Aided Design (CAD) and Geographic Information System (GIS), banking, optical products, and transportation.  Since 2001, LEDA has been developed and distributed by Algorithmic Solutions Software GmbH, founded by Mehlhorn with Näher and Christian Uhrig, who introduced a novel distribution model that is free to researchers and licensed to companies.  Mehlhorn is the founding director of the Max Planck Institute for Informatics and a professor at Saarland University in Saarbrucken, Germany.  A Fellow of ACM, he received the Gottfried Wilhelm Leibniz Prize in 1986, and the European Association for Theoretical Computer Science (EATCS) Award in 2010. The Kanellakis Award honors specific theoretical accomplishments that significantly affect the practice of computing.

A New Proof of the Nondeterministic Time Hierarchy

A nondeterministic time hierarchy was first proved by Cook and in the strongest form by Seiferas, Fischer and Meyer.  Zàk gave a simple proof that we sketched in this post. Here is another.

Theorem: If t₁ and t₂ are time-constructible functions and t₁(n+1)=o(t₂(n)) then NTIME(t₁(n)) is strictly contained in NTIME(t₂(n)).

Proof: 

Let M₁,… be an enumeration of nondeterministic Turing machines. We define a nondeterministic machine M that acts as follows on input w=1ⁱ01^m0y

• If |y|<t₁(i+m+2) then accept if M_i accepts both inputs 1ⁱ01^m0y0 and 1ⁱ01^m0y1 in t₂(|w|) steps.
• If |y|=t₁(i+m+2) then accept if M_i rejects input 1ⁱ01^m0 on the computation path described by y.

This machine uses time O(t₂(n)). If NTIME(t₁(n))=NTIME(t₂(n)) then there is an equivalent machine M_i using time O(t₁(n)).

Since t₁(n+1)=o(t₂(n)) we have for sufficiently large m,

1ⁱ01^m0 in L(M) ⇔ 1ⁱ01^m0y in L(M) for |y|=1⇔ … ⇔ 1ⁱ01^m01y in L(M) for |y|=t₁(i+m+2)⇔ M(1ⁱ01^m0) rejects on all computation paths ya contradiction. QED

The advantage over Zàk is that you only need t₁ steps instead of exponential in t₁. On the other hand Zàk can give you a unary language and can be generalized to a broader set of complexity measures.

Rahul Santhanam and I needed and discovered this proof for our recent paper. The proof came out of a failed attempt at an oracle to show that no such relativized proof would be possible.

The Complexity of the Soul

A CS vision professor once told me "Of course we know there is an efficient algorithm for that humans can do it." Are we just nothing more than Turing machines running simple algorithms using machine learning techniques that have been hard wired into our brains through evolution. How sad.

But it's not true. I think therefore I am. I have self-awareness. A Turing machine can't be self-aware. There are people who try to formalize self-awareness and then show those formulations can be realized on Turing machines. But these don't match my intuitive notion of self-awareness so self-awareness cannot be formalized. There is something beyond computation that allows me to be self-aware, something called the soul.

I suspect you readers all have souls too but I can't prove it.

Does the soul violate the Church-Turing thesis? Does it allow us to compute things beyond that of a Turing machine? Does it allow us to compute problems much faster than a soulless computer could every do?

I think not. The soul is just another input to the Turing machine we call our brain. How the information gets from the soul to the brain is a process we may never fully understanding because reasoning about the soul requires the very soul we are trying to reason about.

Phillipe Flajolet passed away

Today I read on Lipton's Blog that Phillipe Flajolet passed away (1948-2011). Flajolet worked in Analytic Combinatorics. His book with Sedgewick on the field (see this review) practically defined the term Analytic Combinatorics.

Most of the math we use in Theoretical computer science is discrete math. However, analytical mathematics is also useful and I wonder if its potential has been fully tapped yet. Here) is an example: a paper by Flajolet that uses Complex Analysis to show that certain context free languages are inherently ambiguous.

I am teaching 30 students a course on Formal Language theory now and I suspect that less than 3 know any complex analysis. I suspect that in earlier times more would have. I do not miss those times; however, it means that results like the one cited above cannot be taught.

An unusual Voting Scheme

(I want to thank Bobby Kleinberg for bringing this to my attention.)

Consider the following voting scheme

1. Choose a random person A₁.
2. A₁ chooses a set at random of 30 people. Call the set A₂.
3. Choose a random set of 9 from the 30 in A₂. Call this set A₃.
4. The members of A₃ pick a set of 40 people. This is NOT random. In fact, every person they choose must be approved by at least 7 of the 9. Call this set of 40 A₄.
5. Choose a random set of 12 from the 40 in A₄. Call this set A₅.
6. The members of A₅ pick a set of 25 people. This is NOT random. In fact, every person chosen must be approved by at least 9 of the 12.
7. Choose a random set of 9 from the 25 people in A₅. Call this set A₆.
8. The members of A₆ pick a set of 45 people. This is NOT random. In fact, every person chosen must be approved by at least 7 of the 9.
9. Choose a random set off 11 from the 45 people.
10. These 11 chose a final set of 41. They do this by every member choosing a candidate which they may examine in person. The candidates with the most approvals are picked.
11. THESE 41 chose the WINNER - but the winner had to get at least 25. (It is not clear if any of them could be the winner.)

Which of the following is true?

1. This is a real scheme that was really used.
2. This scheme was part of a BREAKTHROUGH!!!! result.
3. This scheme is a counterexample to a conjecture about voting schemes.
4. This scheme (with parameters) is an example of a voting scheme that is NP-hard to manipulate.

I would have guessed that it is a contrived scheme to serve as a counterexample, but NO- this scheme was really used to pick the new doges of Venice from 1268 until roughly 1768. Why so complex? To avoid anyone rigging the election. You can read more about it here. I suspect it would be hard to manipulate, though I don't think it is known to be NPC to manipulate.

Why did this come up? Bobby Kleinberg gave a talk at UMCP where he brought it up to show that his results (about how randomness can help make mechanisms hard to manipulate) had a real world counterpart. See here for his paper, which has co-authors Jason Hartline and Azarakhsh Malekian.

How I'm Spending my Spring Break

This week I returned to Dagstuhl for the workshop on Computational Complexity of Discrete Problems. I come here so often that when I tweeted that I was om way Dagstuhl tweeted back that they want another typecast. But no Bill here so no typecast.

This has been a theory-friendly month for Dagstuhl. Last week the Geometers and two weeks before that Algorithms. One of the algorithms attendees thought he saw me at the Frankfurt airport on his way home but didn't think I would have any reason to be in Germany. But it was me returning from Porto.

Dagstuhl really gives me a chance to find out the latest and greatest of what's going on in complexity. No major breakthroughs but lots going on down in the low complexity range (low-depth circuits). Keep watching my Twitter for Dagstuhl updates.

There's a conflicting complexity seminar in Paris that's splitting our crowd. If you happen to be in Paris tomorrow, Avi Wigderson is giving a popular talk on P v NP.

Dagstuhl is expanding to have either larger or more seminars. There is also a new Dagstuhl-like seminar in Japan and the Banff center has new housing. Seems to be the model we are in: Big conferences to publish your papers, small workshops to mingle and collaborate. I love these small workshops but I do worry they silo us theorists even more.

Travel Support for Students going to STOC 2011

If you are a grad student and want to goto STOC 2011 there is travel support money that you can apply for. See here for details.

We are particularly interested in getting people who normally ARE NOT able to get to STOC (or FOCS or...) to go to this. SO, if you know some grad students who would LIKE to go to STOC if they had travel money, but DO NOT have travel money, then urge them to apply.

Update on 17x17 problem

UPDATE: Problem HAS been solved. See Feb 8, 2012 post. There IS a 4-coloring of 17x17 and also of 18x18. Can also see my arXiv paper on grid coloring.


Long time readers may recall that 17x17 problem that I posted on Nov 30, 2009 here. I am sometimes asked if the problem is still open. Alas it is. Is the bounty on it still available. Alas it is. Some thoughts and experiences

1. See this for a different take on it.
2. When I wrote the post not that many people tried it seriously. Because of the post and because Brian Hayes picked up on it (see here) many people have worked on it seriously. This is good in that I now know that its hard, but bad in that its still unsolved.
3. A High School Student wanted a formal contract before showing me his alleged solution. I told him that if he posted a comment with the coloring ON MY BLOG I would have to pay up and would do so gladly. His solution didn't work anyway.
4. Do I still think that 17x17 is 4-colorable? The problem is that this is a finite problem. The fact that nobody has found a 4-coloring MIGHT mean there isn't one. But it might just mean there are very few of them.
5. As a pessimist I think that 17x17 IS 4-colorable. Why is that? The following three problems are open: is 17x17 4-colorable? is 17x18 4-colorable? is 18x18 4-colorable? If 17x17 was NOT 4-colorable then the rest would NOT be 4-colorable with no additional work. We will not be that lucky. By the same reasoning I think 18x18 is NOT 4-colorable. (There are a few other grids where we do not know if they are 4-colorable but not many.)
6. Will future faster computers help? Maybe, but there needs to be a math breakthrough, even a small one, as well.
7. Will future Quantum Computers help? I doubt anyone will go to the expense of building a quantum computer for the 17x17 grid problem. And I doubt there will be general-purpose quantum computers.
8. The following problem is inspired by my problem but has not gotten that much attention: How hard is the following: Given (n,m,c) and a partial rectangle-free c-coloring of nxm, can it be completed to a total rectangle-free c-coloring of nxm. Should be NP-complete but I have not been able to prove this I also haven't tried that hard- Maybe I'll get a bright High School Student to do it and get some free lunches out of it (see here).
9. JohnPaul Adamovsky claimed that they had a proof that 17x17 was NOT 4-colorable and had comments on it on my blog here. I could not make sense of his proof. I suspect he no longer believes this since recent email from him describes an approach to finding a 4-coloring. He also made an offer that if I bought him some type of computer (he says which type) he will solve the problem. I have declined it; however, I offered to do a post on updated status of the 17x17 problem so he could make a comment on it offering it to others (I am doing that NOW). Note that if he posted on my older posts very few people would see it. He did not respond kindly to my offer; however, we'll see if he comments.
10. I gave a talk on grid colorings at an Algorithms and Theory of Computation Day that Zachos invited me to in New York. A the end I had the following exchange with Lane Hemaspaandra who had also given a talk.
    
    LANE: What does this have to do with Algorithms or Theory of Computation?
    
    BILL: I could make something up but I respect you and the audience too much for that. The answer is NOTHING.
    
    LANE: Then why are you giving a talk on it at Algorithms and Theory of Computation day?
    
    BILL: Because Zachos invited me. You could ask why he invited me, but I think it is because he knows my parents live in the area so I would be a cheap date- no housing costs.
    
    OTHER AUDIENCE MEMBER: Actually this material does have applications. This is part of Ramsey Theory and there is an entire website of applications of Ramsey Theory to Computer Science.
    
    BILL (Thinking- there's ANOTHER one aside from mine? I should take a look at it) OH- that's good to know- what is the pointer to it?
    
    OTHER AUDIENCE MEMBER: Its http://www.cs.umd.edu/~gasarch/ramsey/ramsey.html. Oh- that's you! (READERS- see here.)
    
    BILL: YES, Ramsey Theory has had applications to computer science and that's great! However, I am not going to make the following incorrect claim: (1) Ramsey theory has had apps to CS, (2) The Grid problem was inspired by Ramsey Theory. Hence (3) The Gird problem has apps to CS. That would be bad logic.

TAMC conference accepts are out/What does a name tell you about a general theory conference?

The TAMC conference list-of-accepts is posted here. TAMC stands for Theory and Application of Models of Computation.

For general theory conferences does the name tell you anything? I will consider FOCS, STOC, ICALP, TAMS, COCOON. (I am sure there are more general-theory conferences-- I invite you to comment on them and on if their name tells you anything.)

1. FOCS- Foundations of Computer Science. Are there more papers on the Foundations of computer science here than at STOC or ICALP or TAMS or COCOON? Since people speak of STOC/FOCS papers the question is- are they different?
2. STOC- Symposium on Theory of Computation. What is Theory? There are large parts of theory that are left out such as Semantics.
3. ICALP- International Colloquium on Automata, Languages, and Programming. AH- its a Colloquim not a conference. ICALP does has a different flavor than FOCS and STOC; however, I don't think the name captures it. By the name it could be more of a PL conference, and its not. Also- I had thought they changed the A to mean Algorithms. Is that one of those items they debate in the business meeting? Should they change it to Algorithms?
4. COCOON-Computing and Combinatorics Conference. Does this have more Combinatorics then STOC, FOCS, ICALP? Is this intended to be a general theory conference?
5. TAMC Theory and Application of Models of Computation. I don't think the papers are more on models than the other conferences.

The best way to tell what a conference is about is to look at the Call for Papers list of topics. The name does not tell you much.

Computer Science Takes Over

We live in our own research areas. I focus on computational complexity and marvel at what our field has accomplished over my over 25 years in the field as well as the simple problems we have failed to solve. But every now and then we should pull ourselves our of our forests and take a look around. The whole of computer science has dramatically advanced and as the Internet have changed the way we do almost everything, be prepared for a whole new change.

My daughter is about to get her driver's license. Her children won't need one as their cars will drive themselves. One issue I have as SIGACT chair is gathering information together from various old proceedings and newsletters. In a few years computers will do this for me as quickly as I can ask for them. Right now we have great tools for finding information on the web. In the future our tools will make sense of that information.  In the near future there will be no such thing as unstructured data. Where will all this lead us? I wish I knew--I could be a wealthy man.

Machine Learning has become a very mathematical and statistical-based research area yet the theoretical computer science community hasn't played the role in this area that we could have.

The New York Times have been running a series of articles about AI and its implications to society. A recent article talked about how legal firms save considerable money by using computer software for document discovery. Less money means less white-collar employees needed to sift through documents, a point Krugman pointed out in his column. Krugman also says

Conversely, jobs that can’t be carried out by following explicit rules — a category that includes many kinds of manual labor, from truck drivers to janitors — will tend to grow even in the face of technological progress.

I don't expect truck drivers will exist in 10-20 years either. Technology has so far tended to create more jobs than it destroys but will there be any safe jobs in the future?

STOC 1989

A student at Northwestern gave a presentation about a STOC 1989 paper. I've been to well over a hundred conferences and the memories of many just merge into each other. But some conferences stand out in one's life and STOC 1989 was definitely one of those for me.

I was just finishing my Ph.D. at MIT and took my first trip to Seattle for this conference. The Boston Red Sox were staying at the conference hotel and we saw them lose to the Mariners in the Kingdome, a stadium I do not miss. I gave a talk on a paper that we later had to retract.

But above all I remember going to this mid-May conference with no job offers for the next year. I had planned to spend the reception asking people about job opportunities but my heart wasn't in it and I started drinking instead. Janos Simon came up to me and told me that Chicago would be making me an offer. It took all I had to give a coherent response and not toss my cookies on him.

The student was a baby at the time.

Les Valiant wins the Turing Award

In a definite case of when not if, Leslie Valiant will receive the 2010 ACM Turing Award, the highest honor in all of computer science. Valiant has done incredible work in learning theory (he invented PAC learning), parallel and distributed computing and more recently holographic algorithms. Valiant's brilliant work in counting complexity, including the #P-completeness of the Permanent and his work with Vijay Vazirani that shows that solving NP problems with a single solution is as hard as arbitrary NP problems, have played a critical role in much of my own research.

Valiant will give his Turing Award lecture at FCRC in San Jose on the evening of Sunday June 5th, which will be a special treat for those of us going to STOC or the other FCRC meetings.

Three Questions that I think Watson would have trouble with

Here are two questions that were on Jeopardy (the shows slogan: Watch "Jeopardy!", Alex Trebek's fun TV quiz game show!) that I do not think Watson would have gotten right. I have added a third that I also think Watson would not have gotten right. What do you think?

QUESTION ONE: The FINAL JEOPARDY category was Computer Science. Here is the question. I mean the answer.

John Tukey coined this compound word in 1959 saying it was as important as "Tubes, transistors, wires, tapes ..."

Person A wrote WHAT IS A MOTHERBOARD. Wrong. Person B wrote down WHAT IS. Wrong. (This might have worked if the question was in philosophy.) Peron C wrote down WHAT IS WI-FI. Wrong. I got it right from reasoning not memory. I do not have the quotes of John Tukey memorized. Does Watson? I doubt it. I think he would have gotten it wrong. (The answer can be found HERE.)

QUESTION TWO: The FINAL JEOPARDY category was 1930's Films. Here is the... answer

In this classic film, one of the characters tries to quote the Pythagorean theorem, but gets it wrong.

Two of the contestants wrote Gone with the Wind. The third one wrote the correct answer which I will not reveal here in case you want to try it. (The contestant who got it right won the game.) I doubt Watson would know it--- too much to correlate. (The answer can be found HERE.)

QUESTION THREE: This was not on Jeopardy. I am asking it in the form of a question: What is unusual about the Jeopardy Slogan? (The answer can be found HERE.)

Greetings from Porto

Today we just finished the thesis defense of Andre Souto at University of Porto. Good News: He passed the defense so now we call him Dr. Souto. Better news: By law he has to be paid more in his current teaching job. Not so good news: They will fire him before they pay him more. First time I put someone out of a job by passing them in a Ph.D. defense.

His thesis was in Kolmogorov complexity. One particularly neat trick from his thesis: A PRG that under reasonable assumptions maps strings of length O(log n) to strings of length 2^O(n), a double exponential jump done by combining two PRGs based on Nisan and Wigderson.

I love doing these defenses outside the US. We got to dress like monks when quizzing the defendant. After the defense we had a wonderful lunch with Port Wine from Porto of course.

Andre the Defender

The Jury: Harry Buhrman, Luis Antunes, me and Armando Matos

A good article on how science is publicized gets the science wrong

(Guest Post by John Rogers)

I have just been reading the recently published book "Seeing Further". Edited by Bill Bryson, it contains essays commissioned for the 350th anniversary of the Royal Society. Among the contributors are James Gleick, Neal Stephenson, and Richard Dawkins. The last essay is written by Martin Rees. A cosmologist and science writer, he was president of the Society from 2005 to 2010. On page 476 of the U.S. edition, he writes on how today scientific results are publicized in ways different than even in the recent past:

A few years ago, three young Indian mathematicians invented a faster scheme for factoring large numbers - something that would be crucial for code-breaking. They posted their results on the web. Such was the interest that within just a day, twenty thousand people had downloaded the work, which was the topic of hastily convened discussions in many centres of mathematical research around the world.

As readers of this blog know, the result he refers to is the 2002 paper PRIMES is in P by Agrawal, Kayal, and Saxena. Now the point of the paragraph is how the web is changing the way scientific results get promulgated. Still, I thought it odd that he would mis-state the result. He does mention that faster factoring would have cryptographic import so he (or an editor?) has some knowledge beyond what was in the headlines.

My question is: Is it indeed odd that a scientist would not realize that this is a result about decision and not about search, that if a "faster scheme" had been found to solve the search problem then even a very quick literature search would have turned about up quite a bit more about the code-breaking implications?