Wednesday, September 30, 2009

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.)

Tuesday, September 29, 2009

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.

Monday, September 28, 2009

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.
  6. 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?

Friday, September 25, 2009

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.

Thursday, September 24, 2009

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.

Wednesday, September 23, 2009

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:

  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.

Tuesday, September 22, 2009

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.

Monday, September 21, 2009

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 and not the fake

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.


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.

Friday, September 18, 2009

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.

Thursday, September 17, 2009

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...

Wednesday, September 16, 2009

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. ~ ~

Tuesday, September 15, 2009

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.

Monday, September 14, 2009


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...

Friday, September 11, 2009

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.

Thursday, September 10, 2009

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.

Wednesday, September 09, 2009

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.

Tuesday, September 08, 2009

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. ~ ~ ~

Friday, September 04, 2009

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. 

Thursday, September 03, 2009

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 Ti such that there exists a set of i serious CS theorists, each one of them believing that P vs NP is ind of Ti?
  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.

Wednesday, September 02, 2009

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.

Tuesday, September 01, 2009

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 NC1 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, p1 and p2, such that no monotone circuit of size less than nk/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 nk/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).