FOCS Day 0

Alas, I'm not in Atlanta but in New York City for another meeting. Something different this time--FOCS through the eyes of two Northwestern students, Michele Budinich and Michael Lucas, both attending their first major theory conference.

The organization on day 0 was fantastic. Fox had even reserved a parking lot for us!!

Wait a second.

Are we sure this is where we're supposed to be?

Luckily enough we met more conscious computer scientists who pointed us in the right direction: the FOCS conference! What a novice mistake.

We finally made it to Georgia Tech's LeCraw Auditorium for Day 0 of the FOCS conference. Also called Theory Day, it was a dual celebration marking the 50th anniversary of FOCS and the 20th anniversary of Georgia Techs' ACO program.

Theory Day started off in the most appropriate way with a talk by Richard Karp who shared his favorite algorithms, pointing out the many different qualities that can make an algorithm "great."

After that two slightly more technical talks by Mihalis Yannakakis and Noga Alon, speaking about computational complexity of equilibria and path disjointness in graphs.

As very fitting conclusion for a 50th year anniversary the last talk gave some fascinating views and possible directions for computer science: Manuel Blum talked about getting to grips with consciousness, with some new neuroscience models that could shed some light (in a very literal sense) on how computers could eventually prove their own theorems.

Day 0 ended with the first official FOCS 2009 event: reception, where much food and camaraderie could be found.  Afterwards, the attendees of FOCS '09 returned to their hotel rooms to dream of algorithms and optimization.

Notes on Dagstuhl

A few notes on Dagshul which Lance and I were at last week.

1. I could tell you about the talks, but the website does a better job: here
2. I value going to talks more than Lance does, which is odd since he probably gets more out of them. Nevertheless, they serve two functions:
   1. Lets me know of new results or even areas I should look into (E.g. Chattopadhyay's talk on Linear Systems over Composite Moduli was news to me and is stuff I want to learn about.)
   2. Makes me feel guilty for not having already looked into an areas (E.g., Anna Gal's talk on Locally Decodable Codes reminded me that I really should learn or relearn some of that stuff and update my PIR website, Swastik's talk on parity quantifiers and graphs reminds me that I should read a book I've had on my shelf for about 10 years: The strange logic of Random Graphs by Joel Spencer.)
3. I thought that I was the only person going to both Dagstuhl and Ramsey Theory in Logic and ... so that I could give the same talk in both places. But Eli Ben-Sasson will be at both. But he missed my talk at Dagstuhl. He'll see a better version in Italy since I have made some corrections.
4. At Dagstuhl there is a book that people hand write their abstracts in. In this digital hardwired age do we need this? In case a Nuclear Bomb goes off and all information stored electronically are erased, we can rebuilt civilization based on those handwritten notebooks. The first thing people will want to know after they crawl out of their bomb shelters will be: is there an oracle separating BQP from PH. And Scott Aaronson's Handwritten abstract will tell them. (I hope his handwriting is legible.)
5. Peter Bro Miltersen gave an excellent talk. His open problems were very odd. He did NOT say I want to solve problem such-and-such. He instead said I want to find a barrier result to show that problem such-and-such is hard. It seems to me that one should really try hard to solve a problem before proving its hard. Then again, by trying to prove its hard he may solve it. I hope that if he solves it he won't be disappointed. Maybe his paper will be titled A proof that showing that problem such-and-such is hard is itself hard.
6. One odd benefit of being in Dagstuhl: I spend some time in the library reading articles that I really could have read at home, but somehow don't have time to. Here is one result I read about that I will blog about later: Let d be a distance. If you have n points in a circle of diameter 1 how many pairs of points are you guaranteed have distance \le d apart?
7. Next week I'll be in Italy and not posting, so you get Lance Fortnow all five days! Lets hope they are not all on P vs NP.

Need a Roomate for a conference?

(Guest Post by Dave Doty pointing to a blog by ***SORELLE*** which points to a roomate finding service for conferences.)

Sorelle has announced a new roommate finding forum for conferences: http://conferences.proboards.com. I think this forum a great way to help graduate students and other cash-strapped conference attendees to save money, and I encourage future conference organizers to link to it. ~

The Humbling Power of P v NP

[Note from Bill: He now has an on-line list of papers who still need reviewers]

Noam Nisan, back in grad school in the 80's made the following suggestion:

Everyone theorist should try to prove P = NP and P ≠ NP early in their career to understand why the problem is so difficult to solve.

So go ahead and find a polynomial-time algorithm to 3-color graphs. Show that clique can't be solved by small circuits. Not because you will succeed but because you will fail. No matter what teeth you sink into P vs NP, the problem will bite back. Think you solved it. Even better. Not because you did but because when you truly understand why your proof has failed you will have achieved enlightenment.

You will understand that computation is a nasty beast. Very hard to tame, to see what it can't do. Nearly as hard to control, to use it to solve those hard search problems.

Watch Tim Gower's multiple personalities try to tackle even simpler lower bounds. The P v NP monster humbles the best of us. And that's what makes the P v NP problem exciting and us just human.

An unintentional Sociology of Blogs experiment

Yesterday I posted a list of books that I want reviews of as SIGACT NEWS Book Review Column Editor. This resulted in an unintentional study of Sociology and Blogs which would make an awful paper but a reasonable posting. Some comments below, plus response to comments, and some pointers.

1. So far 12 books have been claimed. More than 12 people made requests but some of the books were already claimed. Of the 12 only 1 has reviewed for me before. The typical column generates 3 or 4 requests, and even those are usually from people who have reviewed before. Why is the blog so much more effective than my column for finding people to write book reviews for me?
2. The most popular book by far was not Knuth Vol 4 Fascicle 0, nor any of the other algorithms book, or crypto books (usually a popular topic) but was instead the book Concentration of Measure for the Analysis of Randomized Algorithms. Why that one? The catchy title? The hotness of the topic? Perhaps several of the other books on my list people already have from the publishers as they are potential textbooks, but this one is not in that category.
3. One of the commenters wanted to know if you need to be an expert to read a book. NO. But you have to be interested and actually read it and have the background to read it.
4. One of the commenters wanted to know what level the books were at. Alas. In the far future there may be a way to, given a book title, type it into what might be some kind of Engine of Search and find out more about it. Next time I do this I will supply more information about the book, unless by some miracle some sort of Search Technology has evolved to make such unneeded.
5. Below I have the revised list with the books that are already claimed removed.
6. Deadline for reviews is Jan 14, 2010, though the intention is to finish them before your next semester starts. If you need more time then tell me. LaTeX template is at here. Plaintext is also fine if the review does not have too much math in it.

Books on Algorithms and Data Structures

1. Algorithmic Adventures: From Knowledge to Magic by Juraj Hromkovic.
2. Algorithms and Data Structures: The Basic Toolbox by Mehlhorn and Sanders.
3. The Algorithms Design Manual by Skiena.
4. Combinatorial Geometry and its Algorithmic Applications: The Alcala Lectures by Pach and Sharir.
5. Algorithms for Statistical Signal Processing by Proakis, Rader, Ling, Nikias, Moonen, Proudler.
6. Nonlinear Integer Programming by Li and Sun.
7. Binary Quadratic Forms: An Algorithmic Approach by Buchmann and Vollmer.
8. Parallel Algorithms by Casanova, Legrand, and Robert.
9. Mathematics for the Analysis of Algorithms by Greene and Knuth.
10. Concentration of Measure for the Analysis of Randomized Algorithms by Dubhashi and Panconesi.
11. Vehicular Networks: From Theory to Practice Edited by Olariu and Weigle.

Books on Cryptography

1. Introduction to Modern Cryptography by Katz and Lindell.
2. Concurrent Zero-Knowledge by Alon Rosen.
3. Elliptic Curves: Number Theory and Cryptography by Washington.
4. Secure Key Establishment by Choo.
5. Algebraic Cryptanalysis by Bard
6. A Course in Number Theory and Cryptography by Koblitz.
7. Cryptanalytic Attacks on RSA by Yan.

Books on Coding Theory

1. Algebraic Function Fields and Codes by Stichtenoth.
2. Applied Algebra: Codes, Ciphers, and Discrete Algorithms by Hardy, Richman, and Walker.

Books on Theory of Computation

1. The Calculus of Computation: Decision Procedures with Applications to Verification by Bradley and Manna.
2. Models of Computation: An introduction to Computability Theory by Fernandez.

Combinatorics

1. Applied Combinatorics by Roberts and Tesman.
2. A Course in Enumeration by Aigner.
3. Chromatic Graph Theory by Chatrang and Zhang.
4. Design Theory by Lindner and Rodger.
5. Combinatorial Methods with computer applications by Gross
6. A combinatorial approach to matrix theory and its application by Brualdi and Cvetkovic.

Misc Books

1. Quantum Computer Science: An Introduction by Mermin.
2. Complex Social Networks by Vega-Redondo
3. Branching Programs and Binary Decision Diagrams by Wegener.
4. When Least is Best: How Mathematicians Discovered many clever ways to make things as small (or as large) as possible by Nahin.
5. Stories about Maxima and Minima by Tikhomirov.
6. Decision and Elections: Explaining the Unexpected by Saari.
7. Creative Mathematics by Wall
8. Is Mathematics Inevitable? A Miscellany Edited by Underwood Dudley.
9. Comprehensive Mathematics for Computer Scientists 1: Sets and numbers, graphs and algebra, logic and machines, linear geometry by Mazzola, Milmeister, and Weissmann.
10. Difference Equations: From Rabbits to Chaos by Cull, Flahive, and Robson.
11. A Concise introduction to Data Compression by Salomon.
12. Practical Text Mining with Perl by Roger Biliosly.

List of books I want reviewed

I have been the SIGACT NEWS Book Review Column Editor for a while now. Every issue I have a list of books that I WANT reviewed. This works pretty well, but I recently thought if only I had a way to let LOTS of people know the list of books I want reviewed. That might work better. Until I do, here is the current list of books I want reviewed. If you want to review one of them then email me by Thursday Oct 22 (I will be sending in the column, including a hopefully shortened version of this list, on Oct 23.) You email should include your postal address so I'll know where to send the book. If you are in America I will postal mail you the book, if you are in a different country I will try to get the publisher to send you the book (this works most of the time). For ADVICE on reviewing books see here

Books on Algorithms and Data Structures

1. The Art of Computer Prgramming Vol 4, Fascicle 0: An introduction to Combinatorial Algorihtms and Boolean Functions by Donald Knuth
2. Algorithmic Adventures: From Knowledge to Magic by Juraj Hromkovic.
3. Matching Theory by Lovasz and Plummer.
4. Algorithms and Data Structures: The Basic Toolbox by Mehlhorn and Sanders.
5. The Algorithms Design Manual by Skiena.
6. Algorithms on Strings by Crochemore, Hancart, and Lecroq.
7. Combinatorial Geometry and its Algorithmic Applications: The Alcala Lectures by Pach and Sharir.
8. Algorithms for Statistical Signal Processing by Proakis, Rader, Ling, Nikias, Moonen, Proudler.
9. Nonlinear Integer Programming by Li and Sun.
10. Binary Quadratic Forms: An Algorithmic Approach by Buchmann and Vollmer.
11. Time Dependent Scheduling by Gawiejnowicz.
12. The Burrows-Wheeler Transform: Data Compression, Suffix Arrays, and Pattern Matching by Adjeroh, Bell, Mukherjee.
13. Parallel Algorithms by Casanova, Legrand, and Robert.
14. Mathematics for the Analysis of Algorithms by Greene and Knuth.
15. Concentration of Measure for the Analysis of Randomized Algorithms by Dubhashi and Panconesi.
16. Handbook of Large Scale Random Networks Edited by Bollobas, Kozma, and Miklos.
17. Vehicular Networks: From Theory to Practice Edited by Olariu and Weigle.

Books on Cryptography

1. Introduction to Modern Cryptography by Katz and Lindell.
2. Concurrent Zero-Knowledge by Alon Rosen.
3. Introduction to cryptography: Principles and Applications by Delfs and Knebl.
4. Elliptic Curves: Number Theory and Cryptography by Washington.
5. Secure Key Establishment by Choo.
6. Algebraic Crypanlysis by Bard
7. An introduction to Mathematical Crytography by Hoffstein, Pipher, Silverman.
8. A Course in Number Theory and Cryptography by Koblitz.
9. Cryptanalytic Attacks on RSA by Yan.

Books on Coding Theory

1. Algebraic Function Fields and Codes by Stichtenoth.
2. Coding for Data and Computer Communications by David Salomon.
3. Applied Algebra: Codes, Ciphers, and Discrete Algorithms by Hardy, Richman, and Walker.

Books on Theory of Computation

1. The Calculus of Computation: Decision Procedures with Applications to Verification by Bradley and Manna.
2. Computability of the Julia Sets by Braverman and Yampolsky.
3. Models of Computation: An introduction to Computability Theory by Fernandez.

Combinatorics

1. Applied Combinatorics by Roberts and Tesman.
2. Combinatorics the Rota Way by Kung, Rota, and Yan.
3. A Course in Enumeration by Aigner.
4. Chromatic Graph Theory by Chatrang and Zhang.
5. Design Theory by Lindner and Rodger.
6. Combinatorial Methods with computer applications by Gross
7. A combinatorial approach to matrix theory and its application by Brualdi and Cvetkovic.

Misc Books

1. Quantum Computer Science: An Introduction by Mermin.
2. Complex Social Networks by Vega-Redondo
3. Branching Programs and Binary Decision Diagrams by Wegener.
4. When Least is Best: How Mathematicians Discovered many clever ways to make things as small (or as large) as possible by Nahin.
5. Stories about Maxima and Minima by Tikhomirov.
6. Decision and Elections: Explaining the Unexpected by Saari.
7. Creative Mathematics by Wall
8. Is Mathematics Inevitable? A Miscellany Edited by Underwodd Dudley.
9. Comprehensive Mathematics for Computer Scientists 1: Sets and numbers, graphs and algebra, logic and machines, linear geometry by Mazzola, Milmeister, and Weissmann.
10. Difference Equations: From Rabbits to Chaos by Cull, Flahive, and Robson.
11. Mathematical Tools for Data Mining by Simovici and Djeraba.
12. A Concise introduction to Data Compression by Salomon.
13. Practical Text Mining with Perl by Roger Biliosly.

Typecasting Again

Lance: Welcome to our second typecast on the last full day of Dagstuhl. I may not see Bill for a while so we'd thought we'd get in one more chat before we go our separate ways.

Bill: Let's wave to the audience. 

Lance: So Bill have you been enjoying the workshop?

Bill: I enjoyed the hike while you stayed here working on a BOGUS theorem.

Lance: I never do the hike. I enjoy the quietness of a nearly-empty Dagstuhl. Saw the castle, did some shopping.

Bill: We're miles from civilization, or kilometers I suppose in Germany.

Lance: A short drive to beautiful downtown Wadern.

Bill: I thought Wadern was too small to have a downtown.

Lance: Well its no Chicago but does have a central shopping area. I got some cool German pencils for the kids and chocolate for the rest.

Bill: Are you enjoying the talks you don't sleep through?

Lance: Don't talk so loud, you are waking me up. Yes the talks have (mostly) been quite good. And luckily not too many of them.

Bill: If I can understand the problem being worked on then I'm happy because I can always claim I read the paper later.

Lance: Then why do you stay awake for the last 30 minutes of each talk? 

Bill: There is photographic evidence that I don't. By the way, do you realize we invented a new word yesterday, "TYPECAST".

Lance: I hate to break it to you but the word is already in the dictionary, first meaning "to cast (type)" which is exactly what we are doing.

Bill: Has the word typecast been used in this way as a contrast to podcast and vidcast?

Lance: Next topic. Let's leave the new words to the Optimizer.

Bill: Do you mean Scott Aaronson's new word "fourellated"?

Lance: Let's not forget his "algebrization". By the way people in this room are now arguing over the spelling of "fourellate". Let's move on please.

Bill: Let's get back to Dagstuhl. Name three talks that you like and one thing that you learned.

Lance: And have someone be angry I left them out? I learned not to rank talks.

Bill: I have no such fears, everyone is already angry at me :-) I like the Swastik Kopparty talk on 0-1 laws for Random Graphs with First-order Plus Parity, Anna Gal's talk on lower bounds on 3-query linear locally-decodable codes, and Arkadev Chattopadhyay's Linear Systems over Composite Moduli. These talks all had real result unlike yours.

Lance: Since when does it make sense to judge a paper by its theorems?

Bill: Since the DAWN OF TIME. Also I learned I can that I can beat Razborov in ping pong, at least with John Rogers help. 

Lance: Let's wrap it up. You know we could typecast again using IM or Google Wave. 

Bill: Once I join the modern age.

Lance: So until next June at Complexity, remember, in a complex world best to keep it simple.

Thanks for the Fuzzy Memories

In the 1990's Manindra Agrawal and V. Arvind published a paper claiming that if SAT is reducible to a (non-uniform) weighted threshold function then P = NP. Their proof relied on the following splitting lemma:

For all n, and q_ij∈{0,1}ⁿ, 1 ≤ i ≤ j ≤ n+2, there don't exist d_k∈{0,1}ⁿ, 1 ≤ k ≤ n+2 such that for all i,j, and k, d_k⋅q_ij > 0 if k=i or k=j and d_k⋅q_ij < 0 otherwise.

Manindra Agrawal and Thomas Thierauf used the splitting lemma to give a polynomial-time algorithm for factoring. They got quite excited and couldn't find a bug in their proof. Apparently I suggested to Thomas at the time that he patent the algorithm before they publish. But later Klaus Wagner showed the splitting lemma actually implied P=NP and Agrawal went back and found that the proof of the splitting lemma wasn't correct and Jochen Messner found a counterexample.

Manindra wrote a retraction for Theoretical Computer Science but for some reason it wasn't published.

I've seen this before. If a technical lemma doesn't imply anything particularly surprising, it might not get checked very carefully. But only later when researchers start using it to get amazing results do people go back and realize there was a problem with the lemma after all.

Flash forward more than a decade later to this week at Dagstuhl. Harry Buhrman, John Hitchcock and Harry's student Bruno Loff came to Dagstuhl all excited. They proved that SAT disjunctively-tt reducible to a sparse set implies SAT is reducible to a weighted threshold and by Agrawal-Arvind thus implies P = NP, answering a long-standing open question. We tried to understand the Agrawal-Arvind paper and Thomas Thierauf "vaguely remembered" there might have been a bug in the splitting lemma.

Arvind who is here at Dagstuhl didn't remember the paper well. Manindra, one of the organizers of this week's workshop, is not here at all but had to attend an IIT event in of all places Chicago. Eventually Harry called Manindra who acknowledged the bug.

Once revealed Jacobo Torán, Messner's advisor, told me the whole sordid story above and Nikolai Vereshchagin showed the splitting lemma true for n ≤ 4 and found counterexamples for n ≥ 5. After talking about the conjecture at the open problem session last night, at breakfast Amir Shpilka showed me an easy proof that the splitting lemma fails even if you allow an infinite number of points for n = 5.

Don't worry, Manindra's proof with Kayal and Saxena that Primes are in P is still safe.

Bill and Lance's Excellent German Adventure

Lance: Because we don't have a good microphone, Bill and I decided to have our first typecast. Hi Bill.

Bill: Hi Lance. We'll be typecast SUPERSTARS.

L: What's today's topic Bill?

B: DAGSTUHL!!! First question of the day, they seat us at lunch and dinner randomly but I've had lunch and dinner with Valentine Kabenets four times. What's with that?

L: No need to yell Bill, it's a typecast. Isn't Valentine an expert in pseudorandomness? You should ask him.

B: If I have one more meal with him, I will.

L: So what is your favorite talk so far?

B: Mine of course. But after mine, yours of course.

L: I agree. I like mine the best too :)

B: You've seemed to have resolved the prisoner's dilemma dilemma. For that you deserve the Nobel prize in Economics. It won't be the only premature Nobel prize given this year.

L:  Too late. Actually you already know my favorite talks from yesterday.

B: Wow, we can do links in a typecast, but not in a vidcast. This is AWESOME!!

L: Quiet down Bill there are people on the other side of this table trying to prove theorems and not wasting time typing to each other. But actually you can put links in Youtube if I knew how. Or so I believe.

B: A real question now. We saw a talk, a really good talk, that proved planar graph isomorphism is in a log space. It was a great talk because it gave an outline of where he (Fabian Wagner) was going so even when I got lost later I got something out of it. Why is it a complexity talk (CCC '09) and not a SODA talk?

L: Hard to say but it felt like a complexity talk. He certainly had complexity co-authors like Thomas Thierauf.

B: Co-authors do not a field make.

L: A field is defined by its people.

B: If you, Lance Fortnow, start doing algorithmic game theory would that start becoming part of complexity.

Rahul Santhanam: Yes, because the premise won't happen.

Chris Umans: What are you doing?

B: It's a typecast, like a vidcast only we type.

C: Really, are you serious? 

B: If you walk in you are fair game. 

C: How can this be a typecast if you can edit it?

L: Like we don't edit the video? We got a bit off track. What I do is complexity because I write the blog.

B: By that theory Ramsey theory is now complexity because I write the blog too.

L: You don't count.

B: I count MOD P!

L: So Vinod gave a neat talk yesterday showing the equivalence between Kolmogorov extractors and randomness extractors which I conjectured here first.

Meena: So why wasn't my talk Monday mentioned on the blog?

L: Time constraints.

R: No, space constraints.

B: Let's wrap up soon. So are you enjoying Dagstuhl?

L: Any time I get to spend with you and Rahul is a pleasure.

B: Same here.

L: But you get to be with yourself all the time.

B: And don't think I don't appreciate it! 

L: And so until next time, when in a complex world best to keep it simple.

Dagstuhl Day One

The talks Monday were after my own heart. The day started with relativization: The always entertaining Scott Aaronson talked on his approach to get an oracle where BQP is not in the polynomial-time hierarchy. He gets some partial progress and a new conjectured language for separation, something he called Fourier checking.

Valentine Kabanets followed up talking about his work with Impagliazzo and Kolokolova giving a new axiomatic characterization of relativization. In my (seemingly minority) opinion, the number of tools we have that don't relativize are pretty slim and and traditional oracle models tell us plenty about what we can't do.

Fabian Wagner described his log-space algorithm for checking whether two planar graphs are isomorphic. Rahul Santhanam talked about our work (with Harry Buhrman) on the lower bounds we proved at last year's Dagstuhl. I talked about applications of computational complexity to economics and why everyone should walk from the Complexity Conference across the street to Electronic Commerce next summer and see for themselves.

But the best part of Dagstuhl are the open time where we meet and socialize over coffee, or wine and beer and discuss problems, struggle over old questions and try to prove new ones. That's the magic of Dagstuhl.

The Molly Solution

This week Bill and I are both at the Dagstuhl Workshop on Algebraic Methods in Computation Complexity. I'll try to cover some of the talks and discussions on the blog and on Twitter.

Called home last night and had the following conversation with my 11-year old daughter.

Molly: I was thinking about this P/NP problem. What do P and N stand for?

Lance: You probably won't understand but P stands for "Polynomial-Time" and N stands for "Nondeterministic"

Molly: Well, if P and N were random variables then P=NP if N equals one.

An old joke, but my daughter had figured it out all on her own. So I answered her with the only response I could give.

Lance: Or if P equals zero.

Complexity Vidcast 2

Bill and I battle it out over what should be taught in a complexity course in our new vidcast.

Publicity for P versus NP

On the New York Times website, John Markoff writes an article Prizes Aside, the P-NP Puzzler has Consequences motivated by my CACM article on The Status of the P Versus NP Problem. Not a bad job describing the basic problem, at least for the layman.

The issues center around a group of classic computer science problems, like the traveling salesman problem — how to figure out the most efficient route through a number of cities given certain constraints. Factoring a large number is also a good example of what is referred to as an NP problem. At present, there is no understood method for doing it in polynomial time, but given an answer it is easy to check to see if it is correct…Checking to see if any particular solution is correct is simple, but finding the best solution in the case of very large problems is infinitely difficult.

Good to see some press for this great problem and theoretical computer science in general. And getting a mention in the Times impresses my mom more than any JACM article ever could.

One of the sentences is tricky to parse.

An esoteric branch of mathematics known as algebraic geometry may offer an avenue to prove or disprove the problem, which was first outlined by Stephen A. Cook, a University of Toronto computer scientist, in 1971.

As you readers should know, while Cook (and independently Leonid Levin in Russia) first outlined the P vs. NP problem, the much more recent algebraic geometry approach is primarily due to my former U. Chicago colleague Ketan Mulmuley.

The last Universal Mathematician was ???

The book Prime Obsessions has the following on Page 159:

You will see it written that Hadamard was the last of the universal mathematicians--- the last, that is, to encompass the whole of the subject, before it became so large that this was impossible. However, you will also see this said of Hilbert, Poincare, Klein, and perhaps of one or two other mathematicians of the period. I don't know to whom the title most properly belongs, though I suspect the answer is actually Gauss.

1. I have never heard Hadamard or Klein mentioned as such, though this does not mean it has not been said.
2. I would add Kolmogorov to the list of candidates.
3. My wife would add Aristotle and Archimedes to the list.
4. Gauss seems like a good choice to me.
5. Do any current mathematicians qualify? One stumbling block--- I do not know of anyone lately who has made serious contributions to logic and some non-logic branch of mathematics.
6. It is, of course, an ill defined question. Is there a way to better define it and answer it?

~

You are coordially invited... Why?

When you get an invitation via email should you accept? How well targeted is it? Some real examples that I got.

EXAMPLE ONE: I would like to invite you to participate at the workshop Ramsey Theory in Logic, Combinatorics and Complexity which will take place in Bertinoro international Center for informatics click here Italy, October 25-30, 2009. The organizers: Pavel Pudlak, Lorenzo Carlucci, Nicola Galesi and Andreas Weiermann Note that this is well targeted (I do Ramsey Theory AND I do Logic!) and the organizerers are people I've heard of (positively!). I have the time to go. This is a clear ACCEPT. (Sorry Lance and Vijay- I'll be missing FOCS.)

EXAMPLE TWO:

It is my pleasure to invite you to publish at the Journal of Emerging Technologies in Web Intelligence (JETWI) (ISSN 1798-0461 ) published by the Academy Publisher in Finland. JETWI is a peer reviewed and indexed international journal and is teamwork of the distinguished editorial board along with the Academy Publisher to respond to the emerging research needs in the evolving area of Web Intelligence and related Technologies. The aim, scope and the targets of this journal are listed at the journal Web Site: click here

This is badly targeted. I am not in the area. So why did I get this email? There is no harm to the sender to send it to ALOT of people since it doesn't cost anything. I wish that, as a courtesy, they would do better targetting. For me a clear DECLINE. Should I email them and tell them to take me off of their list? I doubt it would work and might even be counterproductive. I hope they read this blog entry and take me off of the list. (I also hope to show P\ne NP.)

EXAMPLE THREE:

There is a book that won't be written for many years, yet its here today for you to review. Courtesy of Jahred Kammen, comes a short but salient retrospective on the life and impact of Ted Kennedy. The complete work is Available at _Freedompressintl@aol.com_ (mailto:Freedompressintl@aol.com). J. D. Russell, President Freedom Press International

Why did this get send to me? I get many such emails since I run a book review column for SIGACT NEWS and book publishers are not that good at targetting. While I am tempted to get free books that I have no intention of reviewing, I refrain. I wish they did better targeting, but I get to hear about books that are out there that I might not have heard about otherwise.

EXAMPLE FOUR: (I leave it for you to judge this one)

BECAUSE YOU DESERVE IT! Is your lack of a degree holding you back from career advancement? Are you having difficulty finding employment in your field of interest because you don't have the paper to back it up, even though you are qualified? If you are looking for a fast and effective solution, we can help! Call us right now for your customized diploma: Inside U.SA.: 1-718-989-5746 Outside U.S.A.: +1-718-989-5746. Just leave your NAME & TEL. PHONE # (with country-code) on the voicemail and one of our staff members will get back to you promptly!

Two Recent Complexity Books omit Mahaney's theorem- ovesight or wisdom?

In a prior post (a while back) I pondered if Mahaney's theorem (SAT \le_m S, S Spare, implies P=NP) should be taught in a basic grad course in complexity. I thought YES.

As a sequel to that I note the following: The theorem is not in EITHER Goldreich's Complexity book or Arora-Barak's Complexity book. One of the following is true:

1. Gasarch is right and Goldreich and Arora-Barak are wrong. It should have been in their books.
2. Gasarch is wrong and Goldreich and Arora-Barak are right. Its okay that its not in their books.
3. It is in the book but Gasarch couldn't find it.

Clearly option (2) is correct. These people have thought long and hard on what should be in such a course and are broader and deeper in the field then me. The question arises, why did I think this was important anyway? I could argue (as some of the commenters did) about the Berman-Hartmanis conjecture being important (all NPC sets are really THE SAME SET!) but the real reason is that I was impressed with it in my early years and it is hard to shake that off.

When I taught Graduate Algorithms (I really did!) I taught Yao's MST algorithm that ran in time O(|E|log log |V|). The students asked me WHY this was important (there were better algorithms available). Then I realized that I taught it only because Samir Khuller taught it when he taught the class, so I asked him why it was important. He said it very much impressed him when he was a graduate student.

The contents of the Goldreich book and Arora-Barak book are influenced by a deep understanding of the field, and not by things that impressed them in their youth.

Is Mahaney's theorem important? The real question might be compared to what?. As the number of things that you absolutely have to have in a course grows, at some point, something has to be tossed out.

On Being Narrow

In a tweet a few days ago, David Bacon

wonders why everyone always assumes all he can do is quantum computing? Oh, because that's all he's done. Time to do something new?

What David (aka the Quantum Pontiff) says can apply to any discipline. Are you a narrow researcher? Take my simple one question test.

Do all your co-authors know each other?

Being narrow has some advantages but mostly disadvantages.

• You can really know an area. Particularly in a field like quantum computing which has steep learning curve before you can become and remain an active researcher. 
• Your are part of a very tight community. These people know you well. You look forward to seeing them at workshops and conferences. They can write you wonderful recommendation letters (and vice versa).
• On the flip side, you don't know many outside your research area and they don't know you. 
• Narrow researchers often lose themselves in the minutiae of the field, looking at questions whose importance seems obvious from those inside the field but impossible to explain to outsiders.
• You tend to go to smaller and focused workshops and conferences because the majority of the broader meetings have little that interest you. This further isolates you from the larger community.
• As David laments, others view you as focused and unable to solve problems outside your field.
• As your field loses importance, so do you.
• There are fewer grant programs you can apply to, and you have co-authored with most of the people who could properly evaluate your research, making them ineligible to review your proposals.

It's fine for a graduate student to remain focused for their dissertation research. But even then best to take advantage of your university's offerings and take courses in a broad range of topics. As a post-doc or young assistant professor, you should talk to other professors and ask them about their problems. You'd be surprised how much the tools, models and techniques of one field can apply in another. But be careful, others get upset if you try and impose your field's beliefs on their fields. 

Many successful senior researchers will completely change fields a few times in their career, taking a year or more off, maybe during as Sabbatical, to learn the background and important problems of another area and then start tackling those questions.

The Journal Manifesto 2.0

Reminder: FOCS early registration deadline today. Go here

Below is a revised version of the Journal Manifesto. I restate the key sentence from my last post and then redo the manifesto in light of the (very enlightening!) comments that my last post got.

However, I have a Manifesto: a list of actions that we as individuals can do to make the academic world a better place.

Keep in mind: I am NOT talking to the NSF or to Journal publishes or to Conference organizers. I am NOT going to say what any of these people should do. I am talking to US, the authors of papers. If WE all follow this manifesto then the problems of high priced journals and limited access may partially go away on their own. To be briefer: To the extend that WE are the problem, WE can be the solution.

REQUEST: Leave as comments a simple YES if you agree with the manifesto and a NO and a reason if you do not. I may set this up as a formal online thing that people can sign off on if there is enough interest.

Preamble: We academics publish papers so they can be read. We want anyone in the world to be able to read our papers. We do not expect any money in exchange. Here is what we can all do to facilitate this, not just for our papers but for everyones papers.

1. Whenever you publish a paper in a conference or journal, post it on your website AND on some appropriate archive. Also post improvements if there are some (the version on your website may be better than the one in the journal!). You would think this is standard practice by now, but alas, it is not. In particular AS SOON AS YOU SUBMIT the final version to a conference it should go on your website. The fact that 12 papers from FOCS 2009 are still not online shows that there is plenty of improvement to be made on our end.
2. If you give a talk on a paper then post the slides and if possible a video of the talk, along with the paper, on your website. On the archives perhaps post a link to the slides and video.
3. If you have old papers that are not available on line (it is common go to a website and see only papers past, say, 1995, are online) then get them scanned in (some schools do this for you) and put them on your website. Do not be humble. That is, do not think Nobody cares about that old paper. Somebody might.
4. If you goto a website and it has a link to a paper, but the link does not work, then email the website owner. Do not be shy. I have done this with some of the best people in our field and they have been grateful.
5. When you write a paper make sure that all of the bibliography entries include all links where the paper is available: the journal website, the authors website, some archives. If people follow items 1,2,3,4 above then the issue of What if the journals is not online? will become irrelevant. There may still be a problem with older articles; however, this will also become irrelevant over time.
6. If you gather up papers in an area for your own use, then you may want to make a website out of them. I have done this with the Erdos Distance Problem, Private Information Retrieval, Constructive lower bounds on Ramsey Numbers, Applications of Ramsey Theory, and of course VDW Theorem stuff. There may be some legal issues here, and also some issues of what the publishers will enforce. I have no guidelines to offer, so I leave it to you. However, I will note that I've had my {\it applications of Ramsey Theory} site up for at least 5 years with no problem. Also, not that this point is optional. I suspect that, more than the other items, its one that people think other people should do. (I understand that it can be a pain in the neck to maintain such sites.) THIS ITEM IS OPTIONAL.
7. If you get a contract to write a book make sure they allow you to post it free online. Blown to Bits, by Abelson, Ledeen, and Lewis is available this way. So is A=B by Petkovsek, Wilf, and Zeilberger. (I understand that if you are writing an undergrad textbook and expect to make real money on it then you may not want to do this.)

The Journal Manifesto

Some people say that for-profit journals do not currently serve our community well. Some even think they cannot do so. Others think they are doing a fine job as is (I don't know any such people but surely they must exist). I am not going to weigh in on this issue for now. However, I have a Manifesto: a list of actions that we as individuals can do to make the academic world a better place. I truly believe that when people see this list they will agree that everyone else should follow it.

Preamble: We academics publish papers so they can be read. We want anyone in the world to be able to read our papers. We do not expect any money in exchange. Here is what we can all do to facilitate this, not just for our papers but for everyone's papers.

1. Whenever you publish a paper in a conference or journal, post it on your website AND on some appropriate archive. You would think this is standard practice by now, but alas, it is not.
2. If you give a talk on a paper then post the slides and if possible a video of the talk, along with the paper, on your website. On the archives perhaps post a link to the slides and video.
3. If you have old papers that are not available on line (it is common go to a website and see only papers past, say, 1995, are online) then get them scanned in (some schools do this for you) and put them on your website. Do not be humble. That is, do not think Nobody cares about that old paper. Somebody might.
4. If you goto a website and it has a link to a paper, but the link does not work, then email the website owner. Do not be shy. I have done this with some of the best people in our field and they have been grateful.
5. When you write a paper make sure that all of the bibliography entries include links to where you can get to the paper for free. If there is no such place, and you can access the paper yourself for free, then download it, put it in a file in your own directory, and have your bibliography point there.
6. If you gather up papers in an area for your own use, then you may want to make a website out of them. I have done this with the Erdos Distance Problem, Private Information Retrieval, Constructive lower bounds on Ramsey Numbers, Applications of Ramsey Theory, and of course VDW Theorem stuff. (I understand that it can be a pain in the neck to maintain such sites.)
7. If you get a contract to write a book make sure they allow you to post it free online. Blown to Bits, by Abelson, Ledeen, and Lewis is available this way. So is A=B by Petkovsek, Wilf, and Zeilberger. (I understand that if you are writing an undergrad textbook and expect to make real money on it then you may not want to do this.)

The IT Rules

My family has discovered a British Series, the IT Crowd, about two techies in a corporate IT department. An American version never got past the pilot phase. 

One of the running jokes are the immediate responses given to anyone who calls.

1. Have you tried turning it off and on?
2. Are you sure it's plugged in?

My kids often track me down when the computer, cell phone, Wii or some of our many other tech devices don't work. Almost invariably I solve the problem by turning the device off and on, and in one case my daughter's cell phone wasn't charging because the charger wasn't plugged into the outlet. So I just remind them of the IT rules and they laugh but they'll forget for the next time.

So just remember: When in doubt, reboot. Too bad this usually doesn't work for fixing proofs.

Debunking Proofs

One of the comments of the last post asked my (or someones) opinion on the proofs floating around that P=NP or P\ne NP.

1. As a grad student I used to read these until I found the mistake or until it was incomprehensible, which was the more common experience. Now I do not even bother going to the website that claims to have the proof.
2. I do not believe that someone whose knowledge of math is not very deep could possibly prove P\ne NP. Actually I do not believe anyone right now can prove P\ne NP. Any paper claiming such would have to begin with the answer to What are you using to get around the known barriers?
3. A proof that P=NP is more plausible now, except that I believe that P\ne NP.
4. Our time is limited. For most people in the field, debunking proofs is not worth our time. Once you've debunked a few and gotten into arguments with the authors you will agree.
5. My most recent debunking was actually okay. I got a paper that claimed that he MIGHT have a proof that P\ne NP (I like the humbleness) and it was reasonably well written. I told him that everything he wrote about Ham Cycle applies to Eulerian Cycle as well, and hence the proof cannot work. He accepted that but also said he may get me a better draft later. He has not.
7. I have found that debunking a proof that P\ne NP is usually easy: like the above, Eulerian Cycle may be a counterexample to the usual You have to go through all possibilities argument. Debunking a proof that P=NP may be harder since they can be just code. But I would like commentary on this--- what have you debunked and what to you find easy or hard to debunk?

Inspiring a Love of Math

A reader writes

I come to you by way of your computational complexity blog. I get that there is some really good stuff there, but frankly don’t understand about 99% of it. What I do understand is that math can be fascinating and that knowing how to ask the right questions can fill a lifetime with wonder. I am now homeschooling one of my children. He has a good grasp of basic math of the elementary and junior high level, but I just don’t have the experience to pose the questions that don’t have clear answers and that can keep a young mind engaged on a deeper level.

I am writing in the hope that you can share with me, or even poll your readers on, the questions that inspired you and them to further your own investigations and advancement in the worlds of math. Ideally, I would be interested in creating some structure that I could share with the homeschooling community so that an unsophisticated mathematical mind could enjoy this journey with its homeschooled child.

You might try some of the books I enjoyed as a child, Flatland, Gödel, Escher, Bach and the puzzles of Raymond Smullyan.

Everybody's story is different. While I did well in math growing up, I didn't really consider taking a career in a math-related field until college when I discovered my need to know why. But what did fascinate me as a child was process, for example what happens to my letter from when the mailman picked it up until it got delivered. Once I started having access to computers as a teen I started thinking about what they could and couldn't do. For example, I remember asking myself whether our school's computer with its fixed amount of memory could eventually print all the digits of π (no it can't). Not until late in my college career did I find out there was a whole field of study devoted to the mathematical understanding of the possibilities and limits of computation. And I was hooked.

My two cents on P vs NP

There have been several posts on blogs about P vs NP and two expository articles. Is there anything else to add. I'm not sure, but here are my 2 cents.

1. QUESTION: If it is shown that P &ne NP then how will this affect the real world? ANSWER: The solution will give great insight into computation and thus will ultimately help the real world of algorithms. QUESTION: How do you know this? ANSWER: Um...
2. QUESTION: If you were told that P vs NP was REALLY SOLVED yesterday and asked to bet which way it went, how would you bet? I would bet P=NP. I actually believe that P&ne NP; however, my believe in the paucity of current techniques for showing P &ne NP is greater than my believe that P&ne NP.

Another Reason to goto FOCS: Theory Day!

(Posted by request of Vijay V. Vazirani. Flame him for any spelling or grammar mistakes, or if you don't like the content.)

Another reason to goto FOCS: There will be a theory day on Saturday Oct 24:

Celebrating

1. 50th Anniversary of Foundations of Computer Science, and
2. 20th Anniversary of the ACO Program at Georgia Tech

This will be held in conjunction with FOCS 2009 on Saturday, October 24, 2009 in the LeCraw Auditorium on the Georgia Tech campus. The event will consist of one hour lectures by

1. Richard Karp, University of California, Berkeley
2. Mihalis Yannakakis, Columbia University
3. Noga Alon, Tel Aviv University
4. Manuel Blum, Carnegie Mellon University

To register and for more information please visit here

ACO is a multidisciplinary PhD Program in Algorithms, Combinatorics and Optimization at the Georgia Institute of Technology.

(Back to Bill. Flame him for any spelling or Grammar mistakes or if you don't like the content.) (1) Lance pointed out that you DO NOT need a paper to goto FOCS (or any other conference). This is even more true for Theory Day's where typically there are only 4 or 5 speakers. What if only those who were presenting went? What if they gave a theoryday and nobody came? (2) What do you think of having theory days or workshops or whatnot adjacent to a conference? I think its a great idea since it saves on travel time. Does it get more people to goto the conference? Does it get more people to goto the theory day or workshop? Is there any downside? For the user I suspect NO DOWNSIDE. For the organizers it may add some complications.

The Netflix Prize and the Sequel

Nearly three years ago I posted on the just announced Netflix prize. First to a 10% increase in the quality of the movie recommendations would receive a million dollars, coincidently the same amount one would get for settling P v. NP. Three years later in an exciting finish, Belkor's Pragmatic Chaos gives their best solution 20 minutes before an equally good solution from The Ensemble. Details from the New York Times and Netflix Blog.

Computer science got a nice boost of publicity when the contest started and a little bit less with the end, I think because of the big lag before the contest ended on July 26th and the final results announced yesterday. Still good to get some positive CS press after trading algorithms (and by consequence computer science) get some of the blame for the financial crisis.

Netflix got both publicity and nicer algorithms from the contest. So they will do it again this time with demographic and historical data. 

Meanwhile P v. NP remains open.

Why You Shouldn't Not Go to FOCS

You can now register on-line for FOCS which includes the 50th celebration. Early registration deadline is October 1. Hotel rate good until October 9th or while supplies last. Be sure to register at the correct FOCS site http://www.cc.gatech.edu/focs2009 and not the fake focs2009.org.

There are some understandable reasons why you might not go to FOCS. It costs money. It takes time. You have a conflict or other responsibilities. You are just not into theory.

But recently I've started to hear a new excuse.

I don't have a paper at FOCS.

I've heard students say they are embarrassed to go to FOCS without a paper. Some say they don't think they are supposed to go without a paper. Some say it's "tradition" not to go to a conference unless you have a paper to present.

Hogwash.

I and many others went to every STOC and FOCS (and Complexity) as a grad student usually without a paper to give. It's a chance to find out the latest results, to discover the faces and personalities behind the names that you know. A place to talk to the current and future leaders of the theory community and give them a chance to know you. A chance to feel part of a large and strong theoretical computer science world beyond your own institution.

You should go to FOCS because you are a theorist and not just go only when you have the chance to toot your own horn.

You Will All Work for Google

Google has acquired reCAPTCHA, Luis von Ahn's project to use humans to aid transcribing old documents. We consider Luis an honorary theorist and congrats for the successful commercialization of his research. 

CAPTCHA helps distinguish humans from automated web robots to prevent, for example, making unlimited free email accounts for spamming purposes. CAPTCHA typically presents a distorted word that the user needs to enter. I hate that we need CAPTCHA but I understand its need and reluctantly make all of you solve a CAPTCHA when you leave a comment on this blog that dramatically helped decrease the amount of comment spam.

reCAPTCHA gives two words for the user to type in, one to test the user and the other from some corpus to help determine a word from a scanned image. When I purchase from Ticketmaster I had to deal with reCAPTCHA which helped understand words from old New York Times articles. 

I'm less a fan of reCAPTCHA, forced to perform a task for someone else even if that task is admirable. Google will use reCAPTCHA to help in digitizing scanned images from their books project. Google makes revenue from this corpus and I don't see why I should be forced to perform tasks for them even if it takes only a little bit of my time.

I assume Google will replace all the CAPTCHAs on their properties with reCAPTCHA, including Blogger, the software that powers this weblog. So if you want to leave an anonymous comment on this blog without signing into Google, you will have to give Google some of your time.

Possibly Recruits for the Polymath Primes Project

In the book The Man who Mistook his Wife for a Hat and other Clinical Tales by Oliver Sacks there is a true story about two twin brothers (John and Michael), both autistic, who have the following properties (Sentences in italics are direct quotes from the books.)

1. They cannot do simple addition or subtraction with any accuracy, and cannot even comprehend what multiplication and division mean. (page 197)
2. John would say a number--- a six figure number. Michael would catch the number, nod, smile and savour it. (page 201). Oliver Sacks wrote down their numbers and, following a hunch, found out they were all primes.
3. Oliver Sacks joined them and spoke an 8-digit prime. There was a long pause--- it was the longest I had ever known them to make, it must have lasted half a minute or more---- and then suddenly, simultaneously, they both broke into smiles.... An hour later they were swapping 20 figure primes, at least I assume this was so as I had no way of checking. (Page 203. Note that this happened in 1966.)

This raises several questions.

1. How are they doing it? These brothers were unable to tell Oliver Sacks. However, in other essays in books when Oliver Sacks gets to talk to savants that are not autistic they also can't explain how they do it.
2. Since these twins do not know basic arithmetic they are not using the Sieve of Eratosthenes. Nor are they using the AKS Primality algorithm to test their primes. I speculate that they are using a different model of computation then we work with. One is tempted to say Neural Nets! or Analog Computers, but I suspect it is something completely unfamiliar to us.
3. If we could figure out what they are doing could it lead to a solution to the polymath problem on finding primes? Alas no, since I doubt what they are doing would fit into what we are doing.
4. Prediction:
   1. Someone will devise a model of Savant Computing. The Polymath problem referred to above will be in SAVANT-P, giving the field a push (not as big a push as FACTORING IN QP gave Quantum).
   2. People will come up with 1 or 2 more real problems in SAVANT-P, and dozens of complexity classes and theorems about SAVANT computing.
   3. There will be some results in lower bounds on classical models (which my then may include quantum) that are claimed to be easy to prove with SAVANT concepts but not otherwise. People will argue about is it really easier?.
   4. I will write a blog Is Savant the next Quantum?.
5. Could the twins get a job at the NSA? Today no, since they need primes far bigger than 20 digits. But back in 1966...

Announcing a New Blog: Silent Glen Speaks

There is another Theory Blogger: Silent Glen. How can a blogger by silent? Sounds like a contradiction in terms! Hope its not a contradiction since she is already on our blogroll.

I emailed her the offer to annouce her blog (already annouced by ***SORELLE*** and Jeff Erikson and Livejournal) and to email me a statement about why she blogs, that I would post. She ended up emailing me and then posting her WHY I BLOG note on her own blog. Rather than waste electrons reproducing what she said, just go HERE.

In her first blog she asked for advice on being the lone theorists at a University (she just started). I gave her some advice and so did others. It was all good advice, though some of it was contradictory. Rather than restate it, I'll just point you HERE.

This entry is mostly two pointers to other blogs. This raises a question in a different context: In this age of easy access is it worth reprinting something? I have sometimes in my SIGACT NEWS book review column had a review that was Reprinted with permission. If the source I am reprinting from is online, and if the reader is reading SIGACT NEWS online, I could just point to it. We are not quite there yet, but there will come a time when Reprinted with permission will be silly. ~ ~

Fashionable Research

A student asks "How do you survive in the academic world if what you want to do is not fashionable?"

You shouldn't necessarily focus your research on the currently hot topic. Many people will flock to this area so you'll have considerable competition. And while today maybe you'll see many papers in area X being accepted to the big conferences this year, topics can get cold quickly and so will you.

But what about the other extreme, where you do research in an area of very small interest because you have a strong passion for it. Unless you get very lucky and this area goes hot in the future, you'll be giving up any chance of larger fame or fortune. But if you do good work in this area, you can use your passion to sell this area in a job talk and get strong letters from those few senior researchers in the field happy to promote people in their field. So often you can get a job at a reasonable university and spend your life working on what you love. Is that so bad?

Research always comes to passion and ability and you have love what you do and be good at it, no matter the topic. If you don't enjoy your research, you can usually make much more money doing something else you don't enjoy.

Ambiguity

I recently heard or read the following phrases.

1. former cop killer
2. ideal compromiser
3. even prime numbers have their uses

In each case it was ambiguous. The first two intentionally and the last one by accident.

1. On the TV show MONK the main character, Adrian Monk, is a former cop. There was an episode where someone tried to shoot him. The shooter was called A former cop killer. The show played the ambiguity for laughs- did they mean someone who used to shoot cops or someone who shoots former cops? What would be the proper way to write that? former-cop killer would work, though I am not sure the English language allows hyphens.
2. On the TV show BETTER OFF TED a character was asked to compromise her ideals. Her friend Ted said (I may be paraphrasing) Don't make her into an ideal compromiser!. This was also played for laughs--- did he mean that she should not compromise her ideals, or did she mean she should not get really good at compromising? I do not know how to disambiguate that.
3. In the book PRIME OBSESSION (about the Riemann Hypothesis- both the math and the history) they make the point that pure math can have surprising applications. I was reading this book to my darling (I often read her math books to help her fall asleep) and I read Even prime numbers have their uses. She perked up and said Are they saying that 2 is useful? Well, I suppose it is since you can't get from 1 to 3 without it. I think she was sleep talking. The author should have just said Prime numbers have their uses, but is there some way to keep the phrase as he has it and disambiguate it? Perhaps Even the prime numbers have their uses; however, that still sounds odd since it sounds like you are saying of course the composites are useful but who would have thought the primes were! which is not what he is trying to convey. Better to just say Even Number Theory has its uses. Hmmm- that might be interpreted as the theory of even numbers...

The Mystique of the Open Problem

The story goes that Andrew Wiles dreamt of proving Fermat's last theorem when he was a kid. No surprise since all of us math-loving kids dreamed of solving this famous problem. We certainly talked about it much longer than the more important Fermat's Little Theorem which already had a proof. Now my kids have never heard of Fermat's last theorem. Why should they? Nothing there left to dream there.

It is the challenges that inspire. It was much more interesting to go to the moon in the 60's than it is today. Computational complexity is blessed with such a great challenge, one of extreme theoretical and practical importance, that brings needed attention to our small domain. 

My CACM article on P v. NP has proven very popular in great part because of the excitement of the unknown. In that article I wrote "Perhaps we will see a resolution of the P versus NP problem in the near future but I almost hope not." For much as I'd like to see a proof that P ≠ NP, I would also hate to lose that mystique. Who would read an article on the status of P v. NP if the status was "proven 15 years ago"?

Let me note one correction in the article pointed out by Andrew Appel: It was Armin Haken, and not his father Wolfgang, that showed that there are no short resolutions proofs for the pigeon hole principle.

Update: Eric Allender has his own A Status Report on the P versus NP Question appearing in the Advances in Computing series. We should have coordinated titles.

Models versus Proofs

The STOC Call for Papers (deadline November 5th) and FOCS Program including the 50th Celebration are now available (FOCS registration info coming soon). Also a reminder that the Beijing Innovations in Computer Science conference submission deadline is Tuesday. 

On a not entirely unrelated note, even if you have no interest in economics, be sure and read Noam Nisan's post on the differences in the theoretical CS and Econ communities.

Economists and game theorists take their models much more seriously and literally than computer scientists do. While an economists’ model should correspond to some real phenomena, a CS model should correspond to a host of unknown future situations. A CS reader is more willing to take the leap of imagination between the model as stated and various unknown future scenarios. In compensation, the CS reader expects a take-away that transcends the model, often found in the form of mathematical depth. An economics reader is much more skeptical of a model and demands specific justification, but on the other hand, mathematical depth is not seen as a feature but rather as a nuisance to be buried in the appendix.

I made a similar point in a question during the panel session at the Cornell Workshop last week, that proofs dominate most CS theory talks but Econ theory talks rarely mention them. The micro-economists quickly claimed they care just as much about proofs but Noam does capture a major difference of emphasis between our communities. But I disagree with Noam on the importance of the proof over the model.

Our focus on proofs is not inherent in theoretical computer science. CS theory grew initially out of the logic community and initially focused more on models and results than deeper mathematical proofs in the first couple of decades of the field. As the field started drawing more diverse mathematicians (particularly with the combinatorialists in the 80's) we slowly started to see a trend towards using proofs as a major yardstick in measuring the quality of a paper. Our conference systems exacerbates this process: With so many strong submissions to major conferences, it's easier to find faults in new models than in deep mathematical proofs.

We have more sophisticated mathematical techniques in TCS because we reward these techniques causing a feed-back loop. Doesn't make us any more forward looking just less relevant. 

My talk at the workshop described a new model for handling complexity in games, and described a theorem without giving a proof. The actual proof (with Rahul Santhanam, write-up in progress) is messy but not technically deep. Muthu called the presentation a "quintessential" theory talk, a code-word for "old-fashioned".  I'll take that as a compliment.

Panos Ipeirotis and Rakesh Vohra also have takes on the difference between econ and CS.

An apology for Turing may be in the works

Recall that Alan Turing

1. helped Britain win WW II with his breaking the enigma,
2. was a brilliant mathematician who was one of the founders of our field
3. was prosecuted for being a homosexual by the British Government,
4. was forced to take chemicals to cure him of it,
5. committed suicide (almost surely because of the drugs and prosecution),

There is now a movement in England to have posthumous apology to Alan Turing (see here) by the British Government. I suspect that most of the readers of this blog would agree with such. I do also. But see next paragraph.

Does one need to help the war effort and be a brilliant mathematician to get the apology? I think they should lower the standard to the following: you need to have either helped the war effort or be a brilliant mathematician to get the apology. Or how about anyone who was persecuted under those laws? Should Britain offer a blanket apology? Would that weaken the impact? I don't know? Perhaps the question is also- what are they trying to achieve?

Whatever apology they end up giving I would like to see it accompanied by legislation that Turing would have approved of (Marriage Equality? Anti-Discrimination? Hate crime legislation? More Grant money in Recursion Theory? AI?) Or maybe an award in his name.

Hiring at Univ of MD at College Park

As Jon Katz blogged about here and as Lance Fortnow Twittered about, yes indeed, Univ of Maryland at College Park is hiring. (I delayed posting on it until it was official, hence Jon Scooped me!) See here for details. One thing to note: the deadline for applications is October 15, which is rather early. So if you want to apply, get your resume updated, your letter writers writing letters, and your webpage in order. ~ ~ ~

Interface Between Computer Science and Economics

I'm at Cornell for the NSF-sponsored workshop on Research Issues at the Interface of Computer Science and Economics which has brought together a great collection of CS and Econ people interested in questions of common interest. Economist Larry Blume mentioned how CS helps understand the "inadequacies of the Bayesian paradigm" generally used by economist. Computer Scientist Jon Kleinberg talks how econ helps "broad the range of algorithms" and how computation can be both a resource and constraint in economic models.

NSF CCF director and CS theorist Sampath Kannan talked about similarities between CS and econ: Both deal with human-created artifacts and both talk about understanding the possible and the impossible. I would argue that while computers are a human-created artifact, computation itself is a natural process. I suppose an economists might make a similar argument.

Most importantly Sampath talked about the strong support of the NSF in both CS and Econ to focus more on these communities. The NSF Econ program office Nancy Lutz also promoted this view talking about the fondness of math in both fields.

Much of my research in the last couple of years has been looking at ways to apply tools of computational complexity to economic models which is what I'll be talking about later today. Can we harness the computational powers of "the market"? How does agents of limited computational ability change the outcomes of economic situations? Can we use computation to help explain economics phenomenon? Somehow I need to talk more complexity theorists to work on these problems. Why should algorithms people have all the fun?

On that note the accepted papers for SODA is out and Noam picks out the ones related to CS/Econ issues. 

Is P=?NP ind of ZFC a respectable viewpoint?

I recently got an email that told me there is a debate going on about whether the the position P=?NP is independent of an axiom system such as ZFC deserves its own section on the Wikipedia P=?NP page. This raises several questions:

1. Math Question: Is P=?NP ind of ZFC? I tend to think that P=?NP can be resolved in ZFC. My (possibly naive) reasoning is that P=?NP is a question about rather concrete objects, as opposed to CH which deals with the reals. This is not a strong believe on my part and I would like to see more serious arguments for and against.
2. Sociology Question: Are there any serious CS theorists who believe that P=?NP is ind of ZFC? Of course this question depends on your definition of serious, theorist, and believe. Also it might not be the right question since, if (say) Terry Tao or Saharon Shelah thought that P=?NP was ind of ZFC then that is to be taken seriously, even though they are not CS theorists.
3. An Infinite Number of Sociology Questions: For all i what is the strongest theory T_i such that there exists a set of i serious CS theorists, each one of them believing that P vs NP is ind of T_i?
4. Wikipedia Question: How does Wikipedia decide these things? I do not know. However, if there was a credible paper saying why it is plausible that P=?NP might be ind of set theory, then I think it should be included. I do not know of any.

The End of Summer Classes (Guest Post)

(Guest post by Sorelle Friedler. Companion post at her blog

This summer I taught the 400-level Algorithms class at the University of Maryland. Two summers ago I taught a 300-level programming languages class, and promised myself that I'd never teach another summer class. Apparently the lure of getting to teach Algorithms was just too much for me. I love teaching, and enjoyed teaching this summer, but summer classes are exhausting for students and teachers. I also believe that they're ill-advised for the students and think it's a problem that students are not warned against them. This, of course, is the true problem; I knew what I was getting into - they didn't.

While summer classes have the same amount of in-class time as regular semester classes, the out of class time is significantly less (the regular semester class takes 15 weeks, while the summer version takes 6). This satisfies the accountants, but doesn't give the students enough time to actually absorb the material. In addition, as Bill notes in the dual to this post, the students who take summer classes do not represent the standard distribution of ability. Specifically, there are more weak students - the students who could most use the extra time. In Computer Science, especially in programming classes, having enough time is critical.

And what about the strong students? They certainly still learned the material and did a great job on the homework. I decided to assign a somewhat open-ended programming project (a topic for a different post), and the strong students challenged themselves and did an amazing job. Yet with more time there would have been more opportunity for challenging problems and more advanced topics.

I admit, of course, that having summer classes makes logistical sense. It's a good chance for students to get ahead or just manage to graduate on time. Despite the problems, students learn something, pass, and get to move on. But if the goal is a deep understanding of the material or even an understanding equivalent to that achieved in a regular semester course, the summer just isn't good enough.

Musing from the Barriers Workshop

Rahul Santhanam guest posts with thoughts from last week's Barriers in Computational Complexity workshop in Princeton.

1. What's a complexity theorist's definition of an algorithm? A failed attempt to prove a lower bound. One of the more famous examples of this is Arora's approximation algorithm for Euclidean TSP. At the workshop, I heard about a couple more. Chris Umans mentioned that the new algorithms for matrix multiplication in his paper with Henry Cohn came about in part because of a failed attempt to prove their approach was unviable. While chatting with Dave Barrington about his counter-intuitive characterization of NC¹ by bounded-width branching programs, I learned that this too resulted from an "obstruction" to proving a lower bound (By the way, Dave's result was voted the most surprising result in complexity theory by an eminent panel on the first day). It struck me that this ability to toggle freely between "hard" (reductions from complete problems, oracle & black-box results) and "easy" (algorithms) viewpoints is a very productive component of our way of thinking. Of course this is formalized in results such as Razborov-Rudich and Kabanets-Impagliazzo, but it's also an indication that Nature is far from adversarial. It could have been that interesting problems are not just hard but also that we could say nothing interesting about their hardness... Instead, we have an extensive theory, a rich web of implications. Sure, lower bound proofs are difficult, but then there are the chance flowerings of failed attempts.

2. The highlight of the workshop for me was talking with Ketan Mulmuley about his approach to P vs NP using geometric invariant theory. Ketan has been working on this approach for more than a decade now. Given his seminal work on semantics of programming languages, parallel algorithms and computational geometry, and his reputation as a brilliant problem solver, he was always going to be taken seriously. But there was also an element of mystification - was all this high-powered mathematics really necessary to attack P vs NP? Why spend time learning about this approach when it might not pay any dividends for the next half a century? And how could Ketan claim that this was in a sense the only possible approach to P vs NP? The fact that Ketan wasn't comfortable evangelizing about his approach didn't help matters.

It seems to me that now there's a qualitative shift. There seem to be two factors in the shift - one is that Ketan is more confident in the viability of his program than he was in the formative stages, and the second is that he is more aware now of the importance of communicating both with mathematicians and with complexity theorists about his approach. Indeed, the scale of the project is so immense that collaborations across the board are necessary to its success.

To his credit, Ketan has realized this. Earlier, when the possibility was suggested to him that his approach might lead to weaker but still interesting lower bounds along the way, or to connections with other problems, he didn't seem very interested, possibly because he was focused on the ultimate goal of separating P and NP. Now, he is more actively encouraging of the search for such connections. Also, he doesn't claim that his approach is the only one for separating NP vs P - such a claim is hardly tenable. Instead, he makes a much more nuanced argument in terms of the barriers that other approaches run up against and which his own program avoids, as well as for the mathematical naturalness and aesthetic value of his approach. As for the time scale of the project, it's true that carrying it out in its present form would involve solving mathematical conjectures that algebraic geometers consider far beyond the reach of present techniques. But there is always the possibility of short cuts arising from unexpected connections and new ideas. For this reason, estimates of time scales are speculative, and perhaps not all that relevant.

The P vs NP question is the most important in our area, and as of now there seems to be exactly one program (in the mathematical sense) for solving it, and that's Ketan's program. Simply for that reason, it deserves serious study. At the very least, the decade of mathematical labour that has gone into developing the approach, together with the current efforts to explicate the approach and its relation to barriers complexity-theoretic and mathematical, have raised the standards for any future approach to be taken seriously.

The best sources for learning about the approach are his Complexity Theoretic Overview of GCT and Mathematical Overview of GCT.

3. A few people at the workshop questioned the focus on barriers. Ran Raz gave a great talk in which the "barrier" slide merely had a picture of the human brain (but then, isn't it even more unlikely that a computer could prove P != NP?). Why are we so obsessed with barriers? Perhaps it's because we are computer scientists rather than mathematicians. Mathematicians don't care about constructivity - they believe that proofs exist, however long it takes to find them. It was a question of when Fermat's last theorem would be proved, not whether. We, however are used to doing things efficiently (at least in theory). So if we fail to find a proof quickly, the fault surely "lies not in ourselves but in our stars". Walls tend to spring up around us just as we're on the verge of something extraordinary. Oracles give us gloomy portents. We're forced to be unnatural. ZFC shrugs and turns away from the question...

Yet there is something uncanny about the whole thing. Lower bound questions can be formulated (and have been formulated) in many different ways mathematically - there hasn't been any real progress with any of these formulations. Just as an algorithm for SAT would also solve every other NP-complete problem, a lower bound proof would say something about all these formulations at once, which seems odd since they pertain to apparently unrelated areas of mathematics.

Just another barrier with which to amuse ourselves.

4. The very last talk of the workshop was given by Luca Trevisan, on the advantages of being a polyglot. Historically, complexity theory is rooted in logic and combinatorics. As it matures as a discipline, theorists are able to ply their skills in other mathematical provinces. Pseudorandomness is an especially "extroverted" part of complexity theory. Theorists have made important contributions to problems such as explicit constructions of Ramsey graphs (Barak-Rao-Shaltiel-Wigderson) and the Kakeya conjecture (Dvir) using the language and techniques of pseudorandomness.

Luca's talk was about connections between pseudorandomness and additive number theory, with an emphasis on the result by Green and Tao that the primes contain arbitrarily long arithmetic progressions. He made the point that the techniques that go towards proving this result can be phrased in a couple of different languages, the language of functional analysis (functions, norms) and the language of pseudorandomness (distributions, distinguishability, statistical tests). It's useful to construct a "dictionary" between these two languages, since concepts that are transparent when phrased in one language become less so when translated into the other. For example, the functional analysis viewpoint implies that distributions and adversaries are the same kind of object, which seems strange from the other viewpoint. Not only is this dictionary useful in learning the new language, but also because it exposes new concepts that our native language is not well equipped to handle. Indeed, there have already been many fruitful applications of the Gowers uniformity concept to theoretical computer science, including the Samorodnitsky-Trevisan work on low-error PCPs, the work by Bogdanov, Viola and Lovett on PRGs for low-degree polynomials, and the recent beautiful work by Kolaitis and Kopparty on modular convergence laws for first-order logic with the Mod p operator. It seems likely that there are many fruitful connections still unexplored. Luca's survey in the SIGACT News complexity column (PDF) is well worth checking out.

5. There were also several cool talks at the workshop where I learned about new results. Ben Rossman talked about average-case monotone lower bounds for Clique under natural distributions - this is a problem that has been open for a while. He shows that there are two values of the edge probability for Erdos-Renyi graphs, p₁ and p₂, such that no monotone circuit of size less than n^k/4 can solve k-Clique well on average on both of the corresponding graph distributions. This result complements Ben's other recent result showing that k-Clique does not have constant-depth circuits of size less than n^k/4, and uses some of the same techniques, inspired by intuitions from finite model theory. Toni Pitassi spoke about work with Paul Beame and Trinh Huynh on "lifting" proof complexity lower bounds from rank lower bounds for Resolution to lower bounds for stronger systems such as Cutting Planes and Lovasz-Schrijver. This builds on the "pattern matrix" method of Sherstov, which Toni discovered was also implicit in the Raz-McKenzie separation of the monotone NC hierarchy from more than a decade back (see correction below). Of course it would be very interesting to "lift" circuit lower bounds in this fashion, but few results of that kind are known. Adam Kalai talked about work with Shang-Hua Teng on learning decision trees and DNFs under smoothed distributions - product distributions where every co-ordinate probability is chosen uniformly in random from some small range. These learning algorithms do not use membership queries - corresponding results for the uniform distribution would solve longstanding open problems. Adam made the point that his result can be thought of as modelling Nature in a way that is not fully adversarial. At least for "most" reasonable distributions, we can in fact learn efficiently in these cases.

6. The workshop was a great success, in part because it brought together more complexity theorists than any current conference does. It was also very smoothly organized. Thanks to Avi, Russell, the session organizers, the admin staff and the student volunteers for making it such a valuable experience.

Correction from Sherstov (10/5/09): What Toni meant is that the two works study related communication problems (just like there are many papers on the disjointness problem); the two differ fundamentally as to the techniques used and results achieved. This point is clarified in the revised version of Toni's paper on ECCC (page 3, line -15).