Computational Complexity

Wednesday, July 23, 2008

 
A Nonconstructive argument about the election

Posted by GASARCH

I have heard several times in the media the following nonconstructive proof that Obama will win the election. They, of course, do not call it a nonconstructive proof. Since politics is far less predictable and rigorous than math I do not really buy the argument, but its of some interest to me that there is a nonconstructive argument in politics. Here is how we might phrase it. There are two cases.

1. The Iraq war goes well. Then the Iraq war is off of the front pages. In this case, McCain's advantage, that he is seen (rightly or wrongly) as being better to have as prez when we are at war, is nullified. Hence Obama, which is seen (righly or wrongly) as being better on domestic issues will win.
2. The Iraq war goes badly. Then Obama can say (or he might not even need to say so explicitly) that he was right about the war being a mistake in the first place.

What is wrong with this argument?

1. The election may hinge on so many other things: a scandal, a mistatement, obvious things I am not mentioning, nonobvious things that have not come to light yet.
2. The Iraq war might go (or be portrayed as going) some intermediary thing which is neither well or badly. In fact, the very terms well and badl are not well defined.
3. More generally, its very hard to apply simple logic to an election. Or complex logic.

11:26 AM #

Tuesday, July 22, 2008

 
Open Math Problems easy to state to layperson

Posted by GASARCH

What open math problem is the easiest to explain to the layperson? Fermat's Last Theorem and the 4-color problem used to be the gold standard. How about now? Here are some candidates:

1. Goldbach's Conjecture Is every even number (except 2) the sum of two primes? PRO: If the layperson knows what primes are then this is easy to explain. PRO: Give examples easily: 4=2+2, 6=3+3, 8=3+5. The layperson can even generate these! CON: Can't really say why its important. THOUGHT: You can say that primes are important for crypto.
2. Twin Primes Conjecture. Are there are an infinite number of p such that both p and p+2 is also prime?. PRO: If the layperson knows what primes are then this is easy to explain. PRO: Give examples easily: (3,5), (11,13), (17,19), (21,23). CON: Can't really say why its important. THOUGHT: You can say that primes are important for crypto.
3. Chromatic Number of the Plane How many colors do you need to color the plane so that there are never two points an inch apart that are the same color? PROS: The layperson can probably show that 2 colors is not enough, and perhaps 3. PROS: Can easily show the layperson that 7 colors suffices. CON: Can't really say why its relevant. CON: The notion of a coloring of the plane (or even a piece of paper which is what I would use) is somewhat abstract.
4. n²+1 prime problem Are there an infinite number of primes of the form x²+1. PRO: If the layperson knows what primes are then this is easy to explain. PRO: Give examples easily: 5=4+1, 17=16+1. CON: Can't really say why its important. CON: Not as well known as the others on this list (I could not find it on wikipedia since I didn't have a good keyword. It may be there someplace.) THOUGHT: You can say that primes are important for crypto.
5. 3x+1 problem. Also see this website. Consider the following process. Take any number. If its even half it. If its odd then add 1 and divide by 3. Repeat with your result. Keep on going. Will you will eventually get to 1? PRO: They can do some computations. CON: Can't really say why its relevant.
6. P vs NP. If I phrase it as can you solve the TSP problem without going through all of those possibilities then the laypeople might understands it. I might add that there are many problems with the same flavor. I avoid SAT and I avoid NP. PRO: Practical problems! Relevant! CON: Just the notion of what a problem is might be hard. To most people a problem is easy to solve if there computer can solve it in less than a second.
7. Can we factor quickly?. Similar to P vs NP for the layperson, You can say that factoring is important for crypto.

10:55 AM #

Monday, July 21, 2008

 
The One Who Walked Away

Posted by Lance

I caught a rare sighting of Noam Nisan at the GAMES congress. Many of you young complexity theorists may not have ever met Noam or even cite many of his papers anymore. But his research lies at the heart of most of today's complexity research.

Using hard functions for psuedorandom generators started with Nisan who also had breakthroughs in space-bounded generators. Using Forier transforations in complexity got its start with Linial-Mansour-Nisan. Nisan did fundamental work on Communication Complexity and co-wrote the Book on the topic. Nisan may never had directly worked on quantum computing but the polynomial method for proving quantum lower bounds basically follows from Nisan-Szegedy. Not to mention Nisan was the first to show the surprising power of PCPs that led directly to IP = PSPACE and the PCP/Approximation lower bound revolution.

But around 1998 Noam walked away from computational complexity. Just ten years after Ph.D., he felt he had reached his limits in complexity and could no longer produce strong results (despite the fact that he continued to produce papers others could only dream about). Noam shifted gears focusing on economics. Sure he has had his successes there mostly in auction theory. Still what a loss to complexity to lose him over the past decade. If you ever want to return to your roots Noam, we'd be more than happy to have you back.

7:01 AM #

Friday, July 18, 2008

 
GAMES and Computer Science

Posted by Lance

About 30 computer scientists attended the recent GAMES (Game Theory Congress), a tiny fraction of the participants but a noticeable force including several theory heavyweights from a variety of backgrounds: Joe Halpern (Logic), Silvio Micali (Cryptography), Noam Nisan (Complexity) and Éva Tardos (Algorithms). There we also a few AI researchers shuttling between GAMES and AAAI.

The game theory community has made some efforts to welcome the computer scientists. There is now a Game Theory and Computer Science Prize given to The Complexity of Computing a Nash Equilibrium with a lecture given by Constantinos Daskalakis and co-authored by Paul Goldberg and Christos Papadimitriou (noticeably missing from GAMES). Goldberg also has several posts on his blog about the award and the conference.

The Shapley lecture, given each congress by a researcher under 40, was given this year by computer scientist Tim Roughgarden. Afterwords there was a CS-Game Theory lovefest between Tim and Ehud Kalai, one of the leaders of the game theory community. It doesn't hurt that Ehud's son, Adam, is one of our own.

On Monday the conference had a panel by recent Nobel prize winning game theorists Eric Maskin, Robert Aumann and Roger Myerson on the recent history and future of the field. Mostly the expected preaching to the choir but at the end Aumann did talk about the importance of computer science in games in the areas of crypto, games played on computers, auctions and real-time algorithms. He followed up with a memorable take on the future by singing the chorus of Que Sera Sera.

Sergiu Hart, new president of the Game Theory Society, gave an invited talk on his paper with Yishay Mansour showing exponential lower bounds for convergence to a Nash equilibrium in certain models. A nice result but he unfortunately picked up the CS habit of using "natural" as shorthand for "the set of assumptions needed to prove the main theorem."

Computer science showed up in several other presentations. For example, Iter Sher uses max-flow to analyze persuasion. Nearly every topic in game theory hits on CS issues and many (though not all) game theorists seem welcome to have computer scientists work on their problems. There are still many language, technical and cultural issues to overcome to have true collaborations but I foresee a bright future between our fields. So go talk to a game theorist. They don't bite.

Not CS related by on Wednesday we had lunch-time entertainment presentation by Yoram Bauman, self-proclaimed stand-up economist. He opened the talk with his translation of the 10 Principles of Economics which you can watch yourself in this video.

6:36 AM #

Thursday, July 17, 2008

 
Topics for theory grad course for non theorists?

Posted by GASARCH

(Guest Post by Kirk Pruhs.)

I am taking over teaching our graduate CS theory course. I will be teaching to PhD students who will not become theoreticians. I want to emphasize concepts and broad knowledge, not formal proofs or training students to do formal proofs. The plan for most classes is to get the students to understand the statement of one theorem, and the significance of that theorem, with the remaining time devoted to some intuitive explanation of why the theorem is true. I want the the course to be at least a little bit broader than a standard complexity class. For example, possible topics that are not standard complexity topics:

1. Impossibility of distributed consensus with faults
2. von Neumann minimax theorem
3. no minimum energy for computation

I would like to solicit suggestions as to what theorems and topics one should teach to CS PhD students who will not become theoreticians. I probably will have time to 25 to 30 topics.

8:43 AM #

Wednesday, July 16, 2008

 
An Interesting Summation- NOT new but raises some questions

Posted by GASARCH

In my last post I asked for information about the summation &sum_i (-1)ⁱ (k choose i)(a+i)^k (Where the sum goes from i=0 to i=k.)

I knew it was (-1)^kk! but wondered if this was already known and if there was a combinatorial proof. The comments said YES to both questions. (Side Note: THANK YOU READERS. The comments were INTELLIGENT and HELPFUL!.) This raises some questions.

1. The book A=B gives a way to determine for a large class of sums if they are expressible in closed form, and if so what that form is. My sum did not fall into there category since mine has that pesky a in it.
2. Since my summation is solvable with calculus of finite differences is there an algorithm, perhaps an extension of A=B, that will also deal with summations like this. Might be hard to define like this.
3. One of the commenters gave a combinatorial proof but then said that it was better understood using calculus of differences. Doren Zeilberger might agree. In this interesting essay he seems to be saying that once you have a mechanical proof of something (e.g., like those in A=B) then having combinatorial proofs of them that are over a page then such proofs are not that interesting. The combinatorial proof was under a page, but I think Zeilberger was really referring to how complicated things are rather than actual page length. Might be a close call.
4. Dear Anonymous 6 on my last post: When I write a paper that uses this sum I will include your combinatorial proof. I will of course credit you. What name should I use? Anonymous 6 (and point to the website) of course.

9:21 AM #

Tuesday, July 15, 2008

 
An interesting summation- new?

Posted by GASARCH

I recently came across the following sum in my research:

&sum_i (-1)ⁱ (k choose i)(a+i)^k (Where the sum goes from i=0 to i=k.)

I had reason to believe that this summed to (-1)^kk! (which is independent of a). A mathmatician from Univ of MD, Brian Hunt, proved it for me and I wrote it up here.

1. Is this result already known? I suspect yes but was unable to find it.
2. I was unable to find a table of known sums on the web. Does anyone know of one?
3. The techniques of the book A=B do not seem to apply. Does some modification of them suffice?
4. Is there a combinatorial proof where you show that both sides solve the same problem? Is there a more elegant proof?

10:06 AM #

Monday, July 14, 2008

 
GAMES

Posted by Lance

Now I am attending GAMES 2008, the third World Congress of the Game Theory Society being held at Northwestern. A real shame that GAMES will prevent me from visiting AAAI also in Chicago.

GAMES has about 800 participants much larger than any theoretical computer science conference I've ever attended (which was STOC 1987 in New York at about 500). Are there that many more game theorists than CS theorists? No, just that GAMES is held only every four years and has massively (up to 14) parallel sessions where most everyone who wants to talk can talk. This gets the whole community together, much like how Mitzenmacher describes ISIT, an information theory conference. The invited plenary and "semi-plenary" (5 parallel sessions) talks at GAMES are reasonably strong invited talks, though the regular sessions are more mixed.

So should we have a TCS Congress held every n years with theory broadly defined and massively parallel sessions to encourage participation to bring our community together at least once in a while? (And no, FCRC doesn't count.) Unless we have a corresponding reduction in emphasis of the other conferences, having one more conference to attend will not likely have the desired effect.

5:58 AM #

Archives