Computational Complexity

Thursday, July 24, 2008

 
Vinyl Record Bowls

Posted by Lance

Walking through an small art fair recently we came across a booth selling vinyl records deformed into bowls. They proudly kept a long list of classic rock albums they had desecrated to create those bowls. What kind of world do we live in where one takes great music and turns it into a vessel to hold dog food?

I reacquired a phonograph player a couple of years ago but I admit I rarely use it. The problem is technical: You can only get at best 23 minutes of continuous play from a record, as opposed to 75 minutes from a CD or days from my iPod. Somehow I survived childhood changing the record every 20 minutes or so but I'm not sure how.

When my children first saw a vinyl record they just called it a large CD and they didn't know who I would fit it in a player. Their children will likely never know physical media for music at all. Let's see them make a bowl out of an MP3.

6:57 AM #

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 #

Friday, July 11, 2008

 
Some NSF notes of interest

Posted by GASARCH

Notes from NSF.

1. The core theory soliciation for fiscal 2009 is online.
2. A grant annoucment that may be of interest here.
   
   Deadline: October, November, or December 2008 depending on the size of the project
   
   Estimated number of awards: 36 to 50. (WOW!)
   
   Synopsis: The program will support projects that strengthen the scientific foundations of trustworthiness, in order to inform the creation of new trustworthy technologies. We especially seek new models, logics, algorithms*, and *theories *for analyzing and reasoning about all aspects of trustworthiness-- reliability, security, privacy, and usability about all components and their composition. Building on its predecessor program Cyber Trust, the Trustworthy Computing program will also continue to support projects that explore the fundamentals of cryptography, that examine and strengthen security weaknesses in current algorithms or protocols, and that explore new computing models that promise to improve trustworthiness or our reasoning about it.
3. As Richard Beigel (NSF Theory Director) mentioned at the Complexity Conference, interdisciplinary programs have been noticeably theory-friendly of late. AND Note to PIs: Your proposal title should could enough information so we can figure out which panel your program belongs in.

2:59 PM #

Thursday, July 10, 2008

 
Electoral Markets Map

Posted by Lance

Two years ago we created maps to show state-by-state how the 2006 US Senate and Gubernatorial races were shaping up, based on security prices at Tradesports. These markets did very well in predicting the outcomes of those races.

Now in a presidential election year, we have recreated a map, this time for the electoral college and gave it its own URL electoralmarkets.com. This map takes its prices from Intrade, Tradesports current site for their non-sports securities. Once again darker blue indicates a more likely vote for the Democratic candidate (Obama) and darker red more likely for the Republican McCain. Roll over a state for more information or click on that state to go to the Intrade site for that security with historical information.

We created these maps to promote prediction markets as a useful tool for information aggregation. The Third Workshop on Prediction Markets was held at EC yesterday.

As the summer goes on we plan to add several new features so keep checking back and watch the election play out in probabilities in real time.

8:50 AM #

Wednesday, July 09, 2008

 
Attendence at CCC: We have no edge people

Posted by GASARCH

This summer the Computational Geometry Conference (SoCG) and the Conference on Computational Complexity (CCC) were both held in College Park Maryland. Hence a direct comparison is possible. Here are some numbers:

1. SoCG drew 140 people. Recent America SoCG confs that were not to FCRC or co-located with anything: 2006-AZ: 125 people, 2004-NY: 180 people.
2. CCC drew 80 people. Recent America CCC confs that were not FCRC or co-located with anything: 2005-San Jose: 67 people, 2004-Amherst: 82 people, 2001-Chicago: 96 people. For more complete data see this post

Some thoughts on these numbers:

1. SoCG has more people then CCC. Why? (1) more people are working in it, and (2) more people on the edge--- people in graphics or vision or Comp Biology or algorithms who, IF SoCG is local then these edge-people might go. CCC doesn't really have this.
2. We do not have edge people. Who should our edge people be? Crypto? Algorithms? Combintorists? Quantum People? Philosophers/Historians/Sociologists of Science? For Crypto and Algorithms there have been some results (though not alot) of interest to them. For Quantum People they should care about Quantum Computing , but do they? Phil/Hist/Soc of science might be interested in seeing a young field where they can still interview some of the founders, but that is not the same as going to the conference. Besides, they probably don't have grant money.
3. I can count about 5 people who often go to CCC who missed CCC08 and 10 more who I think should go (who am I to say they should go?) who didn't. Some of those who missed it had pretty lame reasons (e.g., a daughters wedding). Before trying to outreach to Crypto, Algorithms, Combinatorists, Quantum Physicists, P/H/S of science to go, we should get our own people to go.
4. Are there othere potential edge-people I have overlooked?

8:31 AM #

Tuesday, July 08, 2008

 
Busy Conference Week

Posted by Lance

I don't travel far for my next conference, the ACM Electronic Commerce conference being held in downtown Chicago. Tutorial and workshop sessions start today.

The conference is not about using credit cards on the internet, but rather a slew of topics connecting computer science and economics, lots of auctions and networks for instance. I am general chair this year, a bit more challenging than the six years I spent in the same position at the Complexity conference because of having to integrate the different cultures of CS theory, AI and economics.

But EC is not the only game going on right now. ICALP, the major European theory conference is happening as we speak in Iceland while in Finland we have COLT, the learning theory coference starting Thursday. The sun won't set on ICALP or COLT this year.

Let's not also forget the IEEE International Symposium on Information Theory in Toronto so nicely described by Mitzenmacher.

Unfortunately conflicts like these require difficult choices. I (and many others) have attended and had papers in ICALP, COLT and EC in the past. Why do we have these conflicts? These conferences need to be planned out years in advance with a number of various date constraints making coordination very difficult and early to mid July makes for good conference dates as a post-classes, pre-vacation time in many countries. As CS expands and adds more conferences to cover the increasing number of papers we produce, this problem will only get worse in the future.

7:00 AM #

Monday, July 07, 2008

 
Attendence at CCC I: History

Posted by GASARCH

(This is the first of two postings about Attendencd at CCC. Todays is about history. Next time I post (probably Wedensday) I'll talk about College Park and modern times.) Here is attendence for all years of CCC.

Where	Year	Attendence	Comment
Berkeley	1986	110	co-locate with STOC
Cornell	1987	100	co-locate with LICS
Wash, DC	1988	89
Oregon	1989	63
Barcelona	1990	108	Europe
Chicago	1991	100
Boston	1992	100
San Diego	1993	123	FCRC
Amsterdam	1994	110	Europe
Minnesota	1995	80
Philadelphia	1996	90	FCRC
Ulm	1997	80	Europe
Buffalo	1998	84
Atlanta	1999	84	FCRC
Florence	2000	66	Europe
Chicago	2001	96
Montreal	2002	140	Co-located with STOC
Aarhus	2003	78	Europe
Amherst	2004	82
San Jose	2005	67
Prague	2006	75	Europe
San Diego	2007	85	FCRC
College Park	2008	81

1. As part of FCRC: 123, 90, 84, 85. So lately this has not been a real boon, but not a loss either.
2. Co-locate with STOC, non-FCRC: 110, 140.
3. Co-locate with LICS. 100.
4. Europe Attendence: 108, 110, 80, 66, 78, 75. I suspect that Florence drew so badly because there are no complexity theorists in Italy (at least not since Luca was in High School.)
5. American non-co-locate, non-FCRC: 89, 63, 100, 100, 80, 84, 96, 82, 67, 81. Note that the two in the 60's were on the West Coast. Chicago did very well: it was there twice and we got 96 and 100. Boston is the other 100. 100 is a suspiciouly round number- I suspect they only had 99.
6. Lessons Learned: Good to co-locate with stoc, and good to have it in a place that has a strong complextiy community. We might have very high attendence in Boston co-locating with STOC in 2010. Mitigating factor: the price of gas.

7:49 AM #

Thursday, July 03, 2008

 
The Great Procrastinators

Posted by Lance

A chemist earlier this week called computer scientists famous procrastinators with our uncanny ability to put off to tomorrow what we could have done today. I'd feel insulted except that he's absolutely right. For those who disagree, aren't you supposed to be working on your SODA papers now?

Why is procrastination seemingly part of our culture? Much has to come from our deadline-driven conference and grant system. If deadlines motivate us highly then not having a specific deadline for a task (say writing or refereeing a journal paper) tends to push that task down to later when we'd rather be doing something else like research.

Sometimes people take it to the extreme: One time someone decided to skip a workshop months in the future because a STOC deadline was at the end of the same week. I convinced that person to sign up for the workshop by tricking them into thinking the deadline was one week earlier. Maybe I lied but wasn't everyone better off for it?

And then, of course, as computer scientists we are always on a computer with access to the web, the great distractor. It's just too easy to catch some videos, catching the latest political news, reading and writing email and blogs…OK, back to work for me.

Enjoy the 4th everyone and we'll be back on Monday.

9:09 AM #

Wednesday, July 02, 2008

 
A NEW Blog in Town-kdphd

Posted by GASARCH

(***SORELLE*** requested and approved this message, though I wrote it.)

There is a new theory blogger on the scene and as you read that sentence you may be wondering `oh, who is he?' That would be the wrong question.

Check out kdphd.blogspot.com a new blog by a ***SORELLE*** a female theorist. Her first blog is a short intro to herself. The second one is about a women-in-computing workshop she went to.

What will ***SORELLE*** blog about in the future? She says it will be women's issues (a term she doesn't like- perhaps she'll blog about what to replace it with), computer science, grad school, politics, the politics of computer science grad school, and whatever else comes up. She is multi-dimensional and so I assume her blog will be too.

She is a Comp Geometry student from The University of Maryland. I am happy to say I have had no influence on her whatsoever. She is her own women.

Why is her name ***SORELLE*** ? Because I was once asking people what their stage names would be if they had one. Sorelle is one of those people like MADONNA and CHER and others celebs that have one word names. Hence she will always be ***SORELLE*** to me. Actually, I don't know her last name.

A pointer to her blog can now be found on our blog under `Sorelle'. (Lance is not big on asterisks and capital letters.)

8:21 AM #

Tuesday, July 01, 2008

 
NSF and CACM

Posted by Lance

I received two "Dear Colleague" letters over the weekend. Jennette Wing, current head of the Computer & Information Science & Engineering directorate at NSF, describes the restructuring of CISE including a new Algorithmic Foundations program, of interest to many readers of this blog. Many program solicitations have already been posted with deadlines much earlier than in previous years.

Moshe Vardi tells us that we all ought to join the ACM, partly to help support the main computer science society, but also because now you will receive the new redesigned Communications of the ACM under Vardi's editorialship.

ACM serves two very different communities, academic computer scientists and practicing computer professionals. The flagship magazine, CACM, has to cater to both groups to succeed. The old CACM mostly had articles around some common topic written by academics, aimed at practitioners and not fitting the needs of either group.

So how is the new CACM? The first redesigned issue (July) just came out and is available online. It hasn't reached the full vision but does give a taste with some opinionated pieces on topics from XML to quantum computing. It also has interviews with Donald Knuth and the Turing award winners.

Definitely an improvement but I didn't find any articles that truly excited me. If CACM hopes to become the "first magazine I want to read each month," it will have to take more risks, producing articles that give new perspectives to up and coming topics in computer science and lead the field instead of just reporting on it.

6:32 AM #

Archives