2008 Complexity Year in Review

Paper of the year goes to Optimal algorithms and inapproximability results for every CSP? by U. Washington grad student Prasad Raghavendra. The paper gives a semidefinite program approximating any constraint satisfaction problem, always the best possible approximation if the unique games conjecture holds.

Some other notables: Aaronson-Wigderson's Algebrization, Raz's counterexample to the strong parallel repetition theorem and many others. Another good year for Complexity.

Despite the dozens of "proofs" that have come my way, the P vs. NP problem remains open. Maybe next year.

NSF funding for theoretical computer science are at the highest levels since I started this blog. Princeton hosts a new NSF sponsored Center for Computational Intractability and Microsoft opened a new research lab in Cambridge, Mass. The theoretical computer science landscape looks quite strong.

However the current economic crisis will pose great challenges to computer science and all of academics as university budgets tighten. Great research can happen in awful economies—computability theory got its start during the great depression for example. But we all suffer if we lose a generation of theorists to this economy.

We remember David Gale, Nick Reingold, Ingo Wegener and others who inspired our lives, George Carlin, Arthur C. Clarke, Michael Crichton, Bobby Fischer and Randy Pausch.

We thank guest posters Richard Beigel, Manuel Bodirsky, Rance Cleavland, Iftah Gamzu, Evan Golub, Nicole Immorlica, Kamal Jain, Joe Kruskal, James Lee, Richard Matthew McCutchen, Amir Michail, Ketan Mulmuley, Vahan Mkrtchyan, Kirk Pruhs, Ken Regan, Rahul Santhanam, Uzi Vishkin, Philipp Woelfel and Jens Zumbraegel for their contributions to our blog this year.

A personal thanks to Bill Gasarch, not only for allowing me to come back to the blog and staying on as co-blogger, but also for organizing a great Computational Complexity Conference at Maryland.

I will always have many great memories for 2008. I started a new job at Northwestern in January and it was a great first year. My eldest daughter became a teenager and had her Bat Mitzvah in May. And after an entertaining election season, our junior senator is just weeks away from becoming the first African-American president of these United States of America. An exciting year indeed.

The Rooster

My daughters came up with the following joke.

Two roosters sat on on a barn. The first rooster asked the second what time he was supposed to crow. The second rooster replied "in the morning".

At 12:01 AM, the first rooster screamed "Cockle-Doodle-Do" waking up the farmer and his family. The second rooster said "Why are you doing that now?"

The first rooster said, "I looked up 'morning' in Wikipedia and it said morning starts at midnight."

The moral of the story: Don't trust Wikipedia.

After coming up with the joke, my daughters wanted to change the Wikipedia entry for morning to make the joke funnier but I talked them out of it. I always have a hard time convincing them that Wikipedia is usually quite trustworthy when their teachers at school keep pounding on how unreliable Wikipedia can be.

Enjoy the holidays. We'll be back next week with the Complexity Year in Review.

Springer Open Choice

First some administrative stuff. Posting will be light until the New Years. The comments feed is not working properly—Blogger is working on it. I deleted a spam comment from my spam post before I realized the comment was a joke. Sorry.

We just finished up an article for the Springer journal Theory of Computing Systems. If you go to the article's web page you'll see the paper is open access, you can download it from anywhere. How did that happen?

In the final stages of production, Springer offered us the opportunity to have our paper in their new Open Choice plan. For a fee we could have our paper downloadable with a license similar to that used by Creative Commons for non-commercial use.

That fee would be $3000, far too much than I'm willing to pay to let you download the paper from Springer when you can download a version from my home page for free.

But Springer has deals with some institutions, mostly Dutch, to offer Open Choice for all their papers. And one of my co-authors is Dutch. So enjoy!

No Good Deed Goes Unpunished

From the Ethicist in yesterday's New York Times Magazine.

Another college professor and I wanted a student to work on a project of ours, but she is a Mac user and the project required a program written for the PC. My colleague's husband, a Ph.D. in computer science, suggested an alternative program the student could download. She did; her computer froze and would not restart. The husband refused to assist her further. As the spouse of a colleague and the person whose advice caused the problem, isn't he obligated to help?

Randy Cohen, the Ethicist, gave a wishy-washy response that the husband doesn't have to help but he should.

Ignoring the whole Mac/PC issues, why is "a Ph.D. in computer science" relevant to the story? We don't get the fields of the questioner or the colleague.

I certainly would stop giving advice if every time I recommended a program there was an implicit promise of additional support. Though my Ph.D. is in Applied Math so the situation above doesn't apply to me.

Reminds me of some good advice I got as an undergrad when I was working as a programmer for Cornell computer services. Some person called me by mistake asking for some technical support and I helped him out. But then this person kept calling. My officemate suggested I give him some wrong but harmless advice. The caller thought I was an idiot and never called again. Problem solved.

Predicability in Movies: was there ever a case where...

This post was inspired by HALF of the movie FLIGHTPLAN.

I have watched HALF of the movie FLIGHTPLAN. In the movie Kyle Pratt (played by Jodie Foster- I didn't know that know that Kyle could be a girls name) takes her 6 years old kid on an airplane, the kid disapears, and the Flight Manifest said she was never there. So the captain and others think that Kyle is nuts.

Having not seen the rest of the movie yet I wonder which is true: (1) Kyle Foster IS nuts, or (2) there is some weird conspiracy going on. Gee, I wonder which one it will be!

In the real world I would of course assume (1). But since its a movie I absolutely know that (2) will be the case. The only point of suspense for me is will the final explanation make sense?.

SO, here is my question: Do you recall ever seeing a movie or TV show where it is clear that EITHER (1) the main character is nuts, or (2) there is a massive conspiracy. and it ends up being (1)? (I don't count if it ends up being a dream.)

YES, I know that if the main character was just nuts the story might not be as interesting. However, they should have the main character be nuts once in a while so that its not so predicable. That way when watching these things we would have a genuine question and genuine suspense. As for making it interesting- thats their job!

Have We Solved Spam?

The amount of spam in my spam folder has dropped below fifty per day down from several hundred a few months ago. The amount of spam that gets through Gmail's filters to my inbox is well under one a day. I'm not sure why. Better spam filters, better enforcement, less economic incentives for spam, maybe even the bad economy is playing a role. While not completely solved, email spam is no longer a significant problem for me.

This has happened without you having to pay me, solve a CAPTCHA or have your computer solve some hard problem to send me email. I have a mailto link on my home page (albeit generated by javascript code) and my various email addresses show up in plaintext on hundreds of pages scattered over the Internet.

For those of you who insist on making it painful to send you email (anything beyond a simple click or cut-and-paste without further editing), time to change your ways and not make your fear of spam make extra work for those of us who simply want to say hello, and maybe ask you to review a paper.

TEACH EVERYONE PROGRAMMING! (Guest Post)

(Guest Post by Amir Michail)

The case for teaching everyone programming

If everyone could program, then anyone could more easily and cheaply scale his/her world view to reach millions in one-on-one conversations to, for example, have greater impact on the results of an election.

If everyone could program, then anyone can more cheaply achieve immortality by encoding what they would like others to remember about them into a simulation of themselves.

Is it ethical to deny people such capabilities? Moreover, is it ethical to deny people the chance to dream up and create entirely new sorts of programs to enhance their lives?

But I hear you say that programming is a difficult skill that only a few could learn. Not really. Learning programming is easier than learning reading and writing, basic arithmetic, or playing a musical instrument. Programming at a professional level is hard, but so is writing a novel, proving theorems, or playing in an orchestra.

Nonetheless, we need to start thinking about ways to make programming more accessible to the vast majority of the population. This might mean taking the math out of programming and using languages that are not Turing-complete. Chatbot programming is one such example.

Prediction Markets Review

Yesterday the Electoral College delegates voted, 365 for Barack Obama and 173 for John McCain. How did the markets do?

To compare, here is my map the night before the election and the final results. The leaning category had Obama at 364. The markets leaned the wrong way for Missouri and Indiana, their 11 electoral votes canceling each other out. The extra vote for Obama came from a quirk in Nebraska that the Intrade markets didn't cover: Nebraska splits their votes based on congressional delegations, one of which went to Obama.

Indiana and Missouri were the most likely Republican and Democratic states to switch sides according to the markets, which mean the markets did very well this year again. Had every state leaned the right way (again), one would wonder if the probabilities in each state had any meaning beyond being above or below 50%.

Many argue the markets just followed the predictions based on polls like Nate Silver's fivethirtyeight.com. True to a point, Silver did amazingly well and the markets smartly trusted him. But the markets also did very well in 2004 without Silver. One can aggregate polls and other information using hours upon hours of analysis or one can just trust the markets to get essentially equally good results with little effort.

In some other prediction market news: A couple of years ago, Tradesports spun off their non-sports markets into a new site Intrade. Last month Tradesports shut down. Intrade still lives and hopefully it will continue to provide an exciting collection of political and other prediction markets.

Cantor Fitzgerald, owners of the Hollywood Stock Exchange, have filed with the CFTC to create real money markets based on box office receipts. Each share will pay off one-millionth of the first four weeks of the film's gross. They don't call it a prediction market since it doesn't have a binary outcome but I do because it is based on a specific time-limited event and the price should accurate reflect the expected gross of the movie.

Not market related but the big news in Illinois is of course the embarrassment of our governor right after the Obama high we've been on. At least Blagojevich will, hopefully, fade from view soon while Obama should leave a strong legacy as president that we in Illinois will remember for a long time.

A NIM-game and some possibly open problems

I made up the following problem which was on the Univ of MD Math Competition for HS Students Part II. (It was question 3 of 5, indicating intermediary difficulty.) It leads to other questions that may be open and/or interested. I state it differently then it appeared so I can more easily state the other questions.

Let A&sube N - {0}. Let n&isin N. NIM(A,n) is the following game: There are initially n stones on the table. Players I and II alternate removing stones from the table. They can remove x stones iff x &isin A. The first player who can't move loses. Let SQ be the set of squares. Show that there exists an infinite number of n such that Player II wins NIM(SQ,n).

1. Most people who read this blog should be able to do this problem. The solution is at the link above.
2. Let p &isin Z[x]. Let A_p = { p(x) : x &isin Z, p(x)>0 } It is easy to show that there are an infinite number of n such that player II wins NIM(A_p,n).
3. Let POW2 be the set of powers of 2. Let A=N-POW2. It is easy to show that there are only a finite number of n such that player II wins NIM(A,n).
4. OPEN: classify exactly which A are such that there are an infinite number of n such that Player II wins NIM(A,n). (Note- it may not have a nice classification.)

Request for Grant Reviewers from NSF

(Guest post from Richard Beigel, NSF Program Director for Algorithmic Foundations)

In order that proposals from CDI PIs (See below for what the CDI grants are) get a fair and knowledgeable review it is important that we have experts available for all areas covered by CISE to serve on these panels. To make this happen it is important to have the CISE community volunteer in large numbers to serve as reviewers for CDI. There is a webform available at here for anyone who wants to volunteer to review CDI proposals.

Cyber-Enabled Discovery and Innovation (CDI) is NSF's bold five-year initiative to create revolutionary science and engineering research outcomes made possible by innovations and advances in computational thinking. Computational thinking is defined comprehensively to encompass computational concepts, methods, models, algorithms, and tools. Applied in challenging science and engineering research and education contexts, computational thinking promises a profound impact on the Nation's ability to generate and apply new knowledge. Collectively, CDI research outcomes are expected to produce paradigm shifts in our understanding of a wide range of science and engineering phenomena and socio-technical innovations that create new wealth and enhance the national quality of life.

The Job Market

Bill's post Monday of a Michigan post-doc position garnished quite a few comments, generated by legitimate worries about the academic job market.

1992 was the single worst year so far in the CS faculty job market. Many of our students applied to 100-200 schools. Very few got good jobs and several others either left academics or took jobs at departments at levels well below their capabilities.

That bad job market discouraged many from getting Ph.D.s in computer science. But those who did graduated in the middle of the dot-com boom when CS jobs were relatively plentiful. The moral: Don't let today's job market determine whether you consider graduate school. By the time you finish your Ph.D. and a postdoc position, the recession should be well over and the first wave of theoretical computer scientists will start retiring.

That's little comfort for those searching for a faculty job this year. I expect this year's academic job market to be much worse than 1992, not just in theoretical computer science but in all academic disciplines. At Northwestern "hiring into new positions will be deferred as much as possible, while hiring into vacated positions will be carefully scrutinized to ensure that the prospective candidates present significant opportunities that might not be available in the future" and we are one of the healthiest financially. Harvard is freezing both hiring and faculty salaries. I'm hearing of many schools that plan to cut salaries.

Best suggestion is to ride it out. Take another postdoc or other temporary position. Consider jobs outside of North America. The disappearing slots will have to be filled once the economy rebounds and no one will hold it against you that you were unable to secure a US faculty job in 2009.

How was New York Theory Day?

REPORT AND REFLECT ON IBM/NYU/Columbia THEORY DAY

Most years in the FALL there is a THEORY DAY at NYU and in the SPRING there is a THEORY DAY at Columbia. They now call this IBM/NYU/Columbia Theory Day. The website did not say which numbered theory day, but the 2004 webpage for Theory day said it was the 25th one. If they have had these every semester since then... well, you can do the math.

1. I was GOING TO post about content of the talks. But the abstracts of the talks do a better job, so I refer you to those. Should I have stayed home and just read the abstracts? NO. Seeing someone give a talk on something does provide extra insight.
2. What does one get out of such things? It is good to know what is going on in theory, especially in parts of theory that you are NOT working on.
3. Why is it good? I could say you might switch areas OR you might spot a connection to your area and make a contribution OR you might get a paper out of it. While all of these are true, just KNOWING stuff is important. One tangible aspect of that is, if you are on a Program Committee you will have a better idea of the papers not in your area. Also, it helps you follow talks at the next theory day, or some other venue where their are talks not in your area.
4. I don't expect to follow that much of the talk. But I do expect (and this happened) to get introduced to an area and get some references that I may read later.
5. Talks are an hour long. If it's a relatively new field (e.g., on-line Ad slot scheduleing) this is good. If it's a survey talk (Joe Mitchell's talk was) this is good. If it's on a classical field that you are not familiar with and they are proving the very latest results, then a full hour is a bit much. But this is just from my viewpoint of wanting to be introduced to a field. wanting to be introduced to a field.
6. Most interesting thing I learned: Joe Mitchell, Comp Geom from SUNY Stonybrook, has had some of his work actually used by real people in the real world. (That may be a post later.) Since I am often skeptical of the practicality of theory, I was happy to hear this.
7. Oddest thing I learned: NYU and Brooklyn Poly-Tech are merging in some fashion. Nobody quite knows the details or what this means yet. I'm hoping it means that theory day will one day be at Brooklyn Poly-Tech which will make my train ride to theory day 15 minutes shorter.
8. New York Theory Day is usually announced about a month before it happens. This is not really enough time to plan. In fact, I have missed Columbia Theory day in the past because I had other plans by the time it was announced.

Ingo Wegener (1950-2008)

Philipp Woelfel remembers his advisor.

"Doktorvater" (doctor father) is the unofficial German term for PhD adviser – from my perspective, I can't think of a better word to describe my PhD adviser, Ingo Wegener, who passed away on November 26, 2008, after a long battle with cancer.

Probably many readers of this blog know about Ingo's work in complexity theory. Exemplary for his research are the topics of two of his monographs: The Complexity of Boolean Functions, 1987 (known to most of us simply as the Blue Book), and Branching Programs and Binary Decision Diagrams – Theory and Applications, 2000. Probably less known in this community is that about 10 years ago, Ingo began to investigate and analyze randomized search heuristics (evolutionary algorithms). Ingo and his research group strongly influenced the theory of this area; previously research was primarily experimental.

Ingo has been recognized as an outstanding scientist. He was a member of the "Wissenschaftsrat" (the most important scientific advisory committee of the German government), a member of the German Academy of Sciences Leopoldina, and the Academy of Sciences of Nordrhein-Westfalen. In 2006 he was awarded the Konrad-Zuse-Medal, the most prestigious German computer science award.

Here are some things I remember about Ingo (hopefully, some readers can add their recollections to the comments).

• Ingo always wrote his scientific texts by hand. And Ingo was an incredibly efficient writer: when he was writing his recent textbook Complexity Theory: Exploring the Limits of Efficient Algorithms, the students who were LaTeXing the manuscript, as well as those who were proof-reading it, used to complain that Ingo was preparing the manuscripts too fast for them to keep up. (Ingo was on Sabbatical, though.)
• Ingo was a gifted teacher. The students of the University Dortmund had an evaluation system, where each term they would elect the worst teacher, who would then be called "Lehrer Lempel" (sorry, probably only Germans understand the term). Ingo's lectures were known to be most difficult. Despite this, he usually came out "last" in the contest without any chance of ever winning the infamous "Lehrer Lempel" cup. In fact (according to Wikipedia) Ingo won the (real) teaching award of the University Dortmund twice.
• One of my favorite quotes is this. Asked about the difficulty of exams, he replied by asking whether anyone, who couldn't distinguish a kidney from a liver should be allowed to graduate from medical school...
• Ingo was one of the best organized people I have ever met. When I handed in my PhD thesis, Ingo said he'd be going to a workshop the next day, but he would write the report after returning. Sure enough, he came back from the workshop 5 days later, with the report on my thesis in his bag (and he wasn't a co-author of any of its papers).

We have lost an outstanding researcher, teacher, adviser, and friend, who for me was a true "Doktorvater".

A job posting for THEORY-Univ of Michigan

(Guest Post from Anna Gilbert from Univ of Michigan. Its actually a pointer to a job posting in theory!)

We have an opening for a postdoctoral fellow in Theoretical Computer Science at the University of Michigan. This is a joint position between the Department of Mathematics and the Department of Computer Science Engineering. Please apply by January 1, 2009 when we start reviewing applications.

Here is the URL for a more complete description. here

Science of Victory!

The Army has a new video The Science of Victory (via the CRA Blog).

An impressive argument for basic research though a bit heavy on the scare tactics.

Proofs Still Not Dead

Helger Lipmaa points to Justin Beldin's essay on the epistemology of Interactive/Zero-Knowledge proofs and asks my opinion on the general topic.

Reminds me of the 1993 Scientific American article "The Death of Proof" by John Horgan. Horgan talked about experimental proofs and computer-assisted proofs as well as interactive proofs. Most notably there was a sidebar story titled "A Splendid Anachronism?" on Wiles' then recent proof of Fermat's last theorem. It's nice to report that fifteen years later the traditional mathematical proof is not dead yet.

Back to Helger's question. I have no problems with the probabilistic aspect of interactive proofs. With a proper source of randomness, one can make the error so small it gets washed out by other cosmic effects. I have no problems with the interaction in an interactive proof either. I learn all proofs interacting, either with a person or a paper.

But a proof is something to be savored and shared and interactive proofs prevent both. One can understand a traditional mathematical proof at many levels of details, the same way one can read Shakespeare either as a quick read or looking at it in depth to find new meanings. Interactive proofs require proofs are the purely logical level, sort of like explaining the Mona Lisa by giving a bit map of the image. And in the end the verifier only gets to learn that there is a Mona Lisa, possibly without any idea what it looks like.

Moreover when you hear a great proof you want to tell the world, much the way you want to share a good joke, something I've occasionally done on this blog (proofs and a bad joke now and then). But an interactive proof of tautology or a zero-knowledge proof of satisfiability one cannot share. You believe but you cannot convince others.

Nothing against the theory of interactive proofs and zero-knowledge. What we can do with them is quite surprising, the applications, particularly to approximation algorithms and cryptography, are quite amazing and I'm lucky to have played a role in their development. But the proofs that interactive proofs do what they do will always excite me much more than the proofs they generate.

Quantum Leap/Quantum of Solace/What does Quantum mean anyway?

When the term quantum is used in English it often means large as in the TV show Quantum Leap. The recent James Bond Movie Quantum of Solace seems to use the word quantum to mean small (also the name of a bad guy organization). What should it mean to better reflect what it is in Physics?

1. Large: Quantum is discrete and hence moving in jumps is large compared to continuos things that move in very very small units (if units at all).
2. Small: The jumps are really small!
3. Neither: The point of Quantum is that things are discrete. This is neither large or small.

Some other random thoughts on this:

1. Was the term quantum originally a word in English that is now used for science, or was it originally a word in science that is now used in English?
2. The word random in English often means something slightly different- arbitrary.
3. The word continuos as it is used in math bothers me. There are some functions that look non-continuos but by the formal definition they are. The term uniformily continuos takes care of this, but they should just rename things so math-continuos matches common-sense-continuos.
4. Valiant defined a parsimonious reduction to be a reduction where the number of solutions is preserved (e.g., if SAT \le 3-COL via such a reduction f then if \phi has X sat assignments, then f(\phi) has X 3-colorings). I had never heard of the term parsimonious before I saw those reductions. It means thrifty but with a positive angle (as opposed to cheap). I don't quite see why thats really what you want to call these reductions.

How Many Sides to Your Error?

I often get asked various questions about complexity but I now had the same question asked twenty years apart.

Are there natural problems in BPP not known to be in RP∪co-RP?

Informally the class of BPP are the problems efficiently computable on a probabilistic computer with a very small chance of error. For RP if the program says "Yes" it is always right. For co-RP, if the program says "No" it is always right. The questions asks if there are any natural problems that have probabilistic algorithms that seem to require error on both the Yes and No answers.

In the late 80's, David Johnson asked me (and several others) the question when he was putting together his Catalog of Complexity Classes for the Handbook. I didn't have any examples and his catalog ended up citing the 1984 work of Bach, Miller and Shallit offering up Perfect Numbers (and some variants) an an answer to the question. But Bach et. al made their argument based on the fact that the current primality tests put Primes in co-RP but not in RP. In 1987, Adleman and Huang (building on Goldwasser and Kilian) put Primes in RP too. This puts Perfect Numbers in RP killing that example a few years before the Handbook appeared.

Since Primes were put in P in 2002, we have so few problems even known to be in BPP but not in P with the best remaining example the co-RP problem of determining whether two algebraic circuits are identical. So we still don't have any good answers to the above question except for some contrived problems like given three algebraic circuits, are exactly two of them identical. Most complexity theorists believe we have strong enough pseudorandom generators to avoid the randomness in probabilistic algorithms altogether. So in the end the question is likely irrelevant. Still we complexity theorists also like to know what we can prove beyond what we just believe.

All this doesn't mean BPP is not the right class to capture probabilistic algorithms when you can trust your randomness and don't mind a negligible error on either side. Complexity classes are defined to capture the properties we want them to have, not to mold to our limited knowledge of current problems.

Cellprobe complexity- Yao model still relevant?

Some sad news, complexity theorist Ingo Wegener passed away last Wednesday at the age of 57. We will have a proper obituary soon.

My last post LINK asked a question about Yao's paper. MIP said (essentially) that since there are more realisitic models of data structures for membership, and very good (better than binary search) algorithms, by now, there is nothing interesting in Yao's paper for computer science, just for people passionate about Ramsey Theory.

That raises a few questions: When is a problem no longer interesting?

1. When it stops having practical applications. If we take this answer then large parts of math and even TCS have stopped being interesting. (Maybe this is true.)
2. When it stops being relevant to the problem it was intended to solve. This fit Yao's paper. But other branches of math are far removed from the problem they were first deveoloped to solve. For one example, computability theory seems far removed from questions in the foundations of math. But is it still interesting?
3. However, I still want to know the answer to my question. Its mostly been answered, but not completely. (The paper IMPLICITY O(1) PROBE SERACH by Fiat and Naor, SICOMP Vol 22, 1993 has better bounds for some cases, but not quite for the one I had in mind.)
4. So, only of interest to people passionate about Ramsey Theory. Actually, I doubt Ronald Graham cares about the problem. Might be more correct to say people passionate about applications of Ramsey Theory. Are there such people? Are there people who have websites dedicated to applications of Ramsey Theory? Are there papers on Ramsey Theory Applications? Perhaps there are, and to the authors the question may still be of interest.