Computational Complexity

Thursday, February 04, 2010

 
The more things change the more things change

Posted by GASARCH

There have been some articles on how much things have changed because of technology. One from the Washington Post Magazine, titled Going, Going, ..., Gone lists out items that are fading out of our lives Here are a few:

1. Cash: When is the last time you used cash in a transaction that was over 20 dollars? Over 10?
2. Slide rules: I thought they were already gone gone gone. You can buy them off the web here. The site does not seem to think of them as antiques.
3. Truly blind dates: In my day we couldn't Google our dates ahead of time.
4. FAX machines: Not sure they are really going going gone. If they had come out earlier they would be far more popular. If they had come out later they would have been far less popular. Are they here to stay?
5. Secretaries: I can't imagine having someone type my papers for me or book a trip for me.
6. Tonsillectomies: I actually got one when I was 8. I hope that wasn't a mistake.

However, nothing demonstrates how things have changed better than this unaired Pilot of the TV show 24 from 1994 here. ~

9:00 AM # 13 comments

Wednesday, February 03, 2010

 
Time Space Tradeoffs for SAT- good resuls but...

Posted by GASARCH

This is a real conversation between BILL and STUDENT (a Software Engineering Masters Student who knows some theory). As such there are likely BETTER arguments BILL or STUDENT could give for there point of view. I invite you to post such as comments. (ADDED LATER: Some of the comments below DO give VERY GOOD arguments for why the results are interesting. I URGE anyone reading this now to read the comments. They are an integral part of this post, more than usual.)

BILL: In 2007 the best student paper award at COMPLEXITY went to Ryan Williams for proving that SAT cannot be done in time O(n^1.801...) and O(n^o(1)) space!! The constant 1.801 is actually 2cos(π/7). (The paper is Time Space Tradeoffs for Counting SAT mod P. Note that the space is n to the little-o(1) which would include log space.)

STUDENT: Doesn't everyone think SAT is not in P?

BILL: YES.

STUDENT: So what's the big deal in proving that SAT is not in time O(n^1.801...) and not much space?

BILL: Its a stepping stone towards better lower bounds!

STUDENT: Are better lower bounds using these techniques likely?

BILL: Well, it is thought that these techniques cannot possibly get beyond SAT not in O(n²).

STUDENT: So... why is it such a good result?

BILL: Actually he proved more than that. He proved that, for all but one prime p, finding the number of satisfying assignments mod p requires O(n^1.801) time if you insist on O(n^o(1)) space.

STUDENT: Is the number of satisfying assignments mod p problem a problem people care about?

BILL: Complexity Theorists care about it!

STUDENT: I meant real people!

BILL: Um, ur...

STUDENT: Are there any interesting upper bounds on the number of satisfying assignments mod p problem so that the lower bounds are a counterpoint to them?

BILL: YES! There are some poly upper bounds are known for planar read-twice monotone formulas mod 7.! (see this paper by Valiant.)

STUDENT: Do people care about the number of solutions of planar read-twice monotone formulas mod 7?

BILL: Complexity Theorists care about it!

STUDENT: I mean real people! Oh. Are we entering an infinite loop?

BILL: The planar read-twice-monotone-formulas-mod-7 result is an example of a very powerful framework for algorithms.

STUDENT: So that paper may be important, but why is the SAT time-space tradeoff paper important?

I like these results, but STUDENT raises a good question: Are Time Space Tradeoffs for SAT important? IS SAT mod p important? I would argue YES since they are absolute lower bounds and there techniques combined with something else may yield more interesting results. However, if you have better arguments please leave comments.

Should Time Space Tradeoffs for SAT be taught in a grad theory course? There is one in Arora-Barak that is not hard. Hence it likely will be taught. If you teach it I hope you have students challenge you as STUDENT challenged me. It will mean they are awake and care. However, be prepared to answer them.

When this was taught in seminar recently the question arose: In the paper Time space Lower bounds for Satisfiability by Fortnow, Lipton, van Melkebeek, Viglas showed the following: For all c < φ (the golden ratio) there exists d such that SAT cannot be solved in time O(n^c) and space O(n^d). The techniques are such that it could have been proven in the 1970's. So why wasn't it? The seminar speculates that back then people were not so pessimistic about lower bounds to consider this a problem worth looking at. Now people do.

10:13 AM # 18 comments

Tuesday, February 02, 2010

 
Naming and Ranking

Posted by GASARCH

Martin Kruskal invented Soliton Waves which were a very important concept in Physics. (NOTE- one of the comments clarifies this statement.)

Rebecca Kruskal (Martin's Granddaughter): Daddy, how come they are not called Kruskal Waves?

Clyde Kruskal (Martin's Son, Rebecca's Father): You can't name things after yourself.

Rebecca Kruskal: Why not?

Rebecca raises a good question. In academia the etiquette has evolved that you simply do not name things after yourself. Why is this? Is it a good thing? How did this tradition get started? Have people tried to name things after themselves? What happens in other endeavors?

On a related topic: if you are asked to give a list of the top items in your field then is it okay to list some of your own?

In THE NEW BOOK OF LISTS by Wallechinsky (spell check wanted me to change the name to Lewinsky) and Wallace they have several lists where an expert in X lists his favorite things in X. Some include their own work:

1. Johnny Cash's 10 Favorite Country Songs of all Time includes his own I Walk the Line (at number 1) and Folsom Prison Blues (at number 4). To be fair, they are awesome songs!
2. Oliver Stone's 12 Best Political Films of all Time actually lists 10 movies (films?) but then says Stone Notes: And two more with apologies: 11-12. JFK and Salvador. Because I never thought either could be made, much less be appreciated by a large audience. This strikes me as a good way of doing it- since 10 is the usual number on a list make it 12 and include two of your own and apologize for it. However, the movie JFK was way too long. The point of the movie was made more concisely here
3. Federico Fellini's 10 All Time Favorite Films include his own 8 1/2 as number 10.
4. Lucille Ball's 10 Favorite TV Series has as item 10 and of course I Love Lucy.
5. Charles M. Schultz's 10 Greatest Cartoon Characters includes, at number 1, Charlies Brown and Snoopy.

If I was asked for my favorite theorems and I had one that I thought was reasonable I wouldn't put it on the list. But I would add at the end something like With apologies I include ..... I think it is unfair to compare your own work with others.

9:10 AM # 14 comments

Monday, February 01, 2010

 
Travel Support for Grad Students who GOTO STOC 2010

Posted by GASARCH

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

What is the best way to get this information out? What is the best wayy to get any kind of information out?

1. Websites. For STOC there is an obvious website, and indeed it is there under Travel Support. This works for conferences. It does not work if the info is hidden deep in a non-obvious place OR if its not there and should be. This happens more than it should. Big Plus: Posting on a website is NOT intrusive like email.
2. Blogs: There are so many blogs and its not clear who reads which ones. Also, some do not do annoucements like this. However, blogs are not intrusive and some people who did not know the info now do.
3. Email: We all get too much and ignore lots of it. Not reliable. See this blog entry for more on that.
4. Twitter: There are still people who don't get tweets. I am one of them. Though I do read Lance's Tweets on the Complexity Home Page---to see how he tweets my posts.
5. Facebook: There are still people who don't do facebook. I am one of them. I may have to at some point. See here.

10:33 AM # 1 comments

Thursday, January 28, 2010

 
Referees'''' reports

Posted by GASARCH

A commenter a LOOOOONG time ago left the following:

Tell me, Gasarch, how in the world do you get your papers published when you consistently skip the apostrophe in it's and that's? Do referees notice these things anymore, or are you simply careless in blogs.

This commenter unintentionally raised some good questions:

1. Do referees notice these things anymore... This indicates that there was a time when referees were real referees, and men were real men, and women were real women, and little blue fuzzballs from alpha-8 were real little blue fuzzballs from alpha-8. Was there such a time? Or is this is really case of nostalgia for a time that never was? If anything I think referees are more demanding of changes then in a past time since they know that with word processors such changes are easy to make.
2. What should referees look for? Ian Parberry has a good paper on this that is linked to from our website. Informally, here is what I think the order should be (1) Are the results true/important/interesting?` (2) Are they well presented? See next item for expansion on (2).
3. Being well presented also has a priority ordering: (1) Are the results well motivated? (2) Are the proofs presented in a way that the reader can see the intuition? (3) Grammar. (4) Spelling. (5) Apostrophes.
4. A referee's job is not just to accept or reject a paper. Its also to offer advice on a paper to make it better

Are referees now more demanding than they used to be? less? This splits into many questions: concern with truth, importance, interest, motivation, intuition, grammar, spelling, apostrophes. I do not claim to know the answers.

9:09 AM # 14 comments

Wednesday, January 27, 2010

 
Guest post on ICS 2010 (x of y for some x and y)

Posted by GASARCH

(Another Guest post about ICS 2010. From Aaron Sterling. Is he on his way to break the MOST GUEST POSTS IN A YEAR record? I doubt it- I think I hold it from before I became a co-blogger, and I think its at least 10.)

Bill asked me if I thought the ICS conference truly was innovative, and in particular how I thought the content compared to that of STOC or FOCS. I've never been to either STOC or FOCS (though I've read some papers and seen some videotaped presentations from those conferences), so I don't consider myself qualified to answer that question directly. However, something related has been on my mind, and I think it's important enough to share with the larger community.

I do believe it is innovative and politically significant that ICS literally represents another country heard from -- and that the derivatives paper appeared there, not in either STOC or FOCS. Compare the derivatives paper to Gentry's homomorphic encryption paper. Gentry's result is of course a stunning breakthrough in an area that had remained wide-open for many years; and, to my (brief) reading, it contains more profound mathematics than the derivatives paper. However, it's quite possible that the derivatives paper will spark changes in the regulation of the multi-trillion-dollar financial product industry. If that happens, it would be reasonable to argue that the derivatives paper would be one of the most influential TCS papers ever.

That comparison, to me, captures the value new concepts can add to the field. US consumers would only have to save $10 million on financial services for Uncle Sam to be 100% repaid for his investment in an Intractability Center. I don't it's a coincidence that that Center's director is a co-author of the derivatives paper, and also a co-author of this CACM position paper on how computer scientists should represent their field to better raise money.



I've had the last two paragraphs of that paper on my office door for a few months now, because I got sick of people complaining to me that there was nothing to be done about financial woes. I'll reproduce those paragraphs here.

One wonders if the failure of computer scientists to articulate the intellectual excitement of their field is not one of the causes of their current funding crisis in the U.S. Too often, policymakers, and hence funding agencies, treat computer science as a provider of services and infrastructure rather than as an exciting discipline worth studying on its own. Promises of future innovation and related scientific advances will be more credible to them if they actually understand that past and current breakthroughs arose from an underlying science rather than from a one-time investment in 'infrastructure.

It is high time the computer science community began to reveal to the public its best kept secret: its work is exciting science -- and indispensable to society.

I also believe it is no coincidence that both co-authors of that paper are on the Steering Committee of ICS. There's nothing like a conference that encourages innovation to demonstrate "promises of future innovation and scientific advances."

A generation or two ago, aerospace contractors used the Space Race as a fundraising tactic. I got the impression from some comments on my first ICS blog post that people were threatened by the idea that China might be a major TCS player, and would prefer if I hadn't even mentioned the possibility. I think that attitude is foolish, and, rather, China's presence on the world TCS stage should be embraced, and used as a reason it is that much more important for the US to invest in theory. After all, if Washington allows things to continue as they are, in ten years, it could be facing a Square Root of Log N Gap!

Okay, that last phrase made me laugh when it popped into my head, so I figured I'd share it. My point, however, is a serious one. A handful of Ph.D's will get postdocs this year at IAS or through the Simons Fellowship. Most people won't, even if they're good. If the CI Fellows program isn't renewed, that means pretty much everyone else is going abroad. In fact, when I was at ICS, a senior researcher told me that he was advising students and recent grads to go abroad, not just for postdocs but also for assistant professorships, and only to return to the US for tenure. That is not a recipe for maintaining scientific prominence in a field, especially if one's "major competitor" is investing heavily in recruitment of theorists.

I will end with a question to consider, if I may. How can we better communicate that computer science, and, in particular, theoretical computer science, is indispensable to society? The government of China doesn't seem to have any trouble understanding this. What about the government of the United States?

10:30 AM # 42 comments

Tuesday, January 26, 2010

 
The First pseudorandom generator- probably

Posted by GASARCH

(The following was told to be by Ilan Newman at Dagstuhl 2009. His source was the book The Broken Dice and other mathematical tales of chance.)

What was the first pseudorandom number generator? Who did it? While these type of questions are hard to really answer, the book The Broken Dice by Ivar Ekeland gives a very good candidate.

Brother Edvin (a monk), sometime between 1240 and 1250 AD, was preparing a case for the sainthood of King Olaf Haraldsson, who had been the King of Norway. There was a well documented story (that could still be false) that King Olaf and the King of Sweden needed to determine which country owned the Island the Hising. They agreed to determine this by chance. They were using normal 6-sided dice. The King of Sweden rolled two dice and got a 12. Then King Olaf rolled and got a 12 AND one of the dice broke (hence the name of the book) and he got an additional 1 for a 13. Some attributed this event to divine intervention, which strengthened his case for sainthood.

Brother Edvin got interested in the general question of how you can generate a random number so that nobody could manipulate it. He may have phrased it as a way to know what was divine intervention as opposed to human intervention.

1. There are two players and they want to pick a random number between 0 and 5. They want the process to be such that neither player can bias the outcome. Each picks a natural number in secret. They are revealed, added, and then the remainder upon division by 6 is taken. Brother Edvin noted that the players really only need pick numbers between 0 and 5; however, he thought it best not to tell the players this since they will think they have more choice then they do.
2. What if its only one person. It is too easy to bias things. But Brother Edwin proposed the following in modern notation.
   1. Pick a 4-digit number x.
   2. Compute y₁=x²,
   3. y₁ will be 7 or 8 digits. Remove the two leftmost digits and one or two rightmost digits to obtain a 4-digit number z₁.
   4. Repeat this process four times to obtain z=z₄.
   5. Divide z by 6 and take the remainder.

The hope is that it is very hard for a human to bias the results by picking a particular original 4-digit number. Brother Edvin did note that some choices for x make the final choice choice obvious and hence not random (e.g., 1001). Brother Edvin proposed some solution: make sure the initial x has no 0's and no repeated digits. He also suggesting taking more initial digits or more times that you iterate the process. But he does realize that this might not work.

The method was rediscovered by von Neumann in a different context. He wanted to generate long random-looking sequences of numbers. His idea was to take a 4-digit number x₁, square it, and take the middle 4 digits, repeat some number of times (say 4) to obtain x₂ then repeat to get more and more numbers. It was abandoned since the periods weren't that large. People used linear congruential generators instead. (Are they still used?)

However, Brother Edvin does deserve LOTS OF credit. Given the math known in his day it is impressive that he asked these questions and got some reasonable answers.

10:33 AM # 7 comments

Monday, January 25, 2010

 
When is a theorem really proven?

Posted by GASARCH

One of the comments on this blog pointed out correctly that for a theorem to be accepted by the community is not a Eureka Moment. It is a social process. The author of the comment was probably alluding to an excellent article by DeMillo and Lipton that I blogged about here. I highly recommend reading the article that blog points to.

We often say or write things like

1. In 1978 Yao proved that if you store n elements of U in a table of size n then (for large U) membership requires log n probes (Ref FOCS 78).
2. In 1981 Yao proved that if you store n elements of U in a table of size n then (for large U) membership requires log n probes (Ref JACM 81).

Personally I try to include both the conference and the journal version in a citation. That solves the citation problem. However, what does prove mean? It could be that Yao proved this in 1977. The exact time/day/year when something is proved is not that well defined. The original post was about the Fund Lemma where the paper was written in 2004 and accepted in 2009. What was its status in 2006? Proven or unproven? Is there a better way to say these things?

1. In his FOCS 1978 paper (see also Journal version in JACM 1981) Yao proved the following:
2. In his JACM 1981 paper (original in conference version in FOCS 1978) Yao proved the following:

These both sound awkward. I am willing to live with using proved even though its not quite right. Does someone have an alternative?

Was Time Magazine right to say that the Fund Lemma was one of the big Science Stories of 2009 even though the paper was written in 2004? I think so- acceptance in a journal seems like a good time to declare YES THIS IS TRUE. And I do not know an alternative.

9:04 AM # 20 comments

Archives