Computational Complexity

Friday, September 05, 2008

 
Tracking Trends in Computer Science

Posted by GASARCH

What are the trends in computer science? This is a hard question to quantify; however, Brighten Godfrey has given it a shot on his blog here: trends. He counts how often certain words appear. What other ways could one measure this? ~

10:51 AM #

Thursday, September 04, 2008

 
Announcements

Posted by Lance

The FOCS conference is coming up October 25-28 in Philly. Early conference and hotel registration by October 3.

The STACS conference submission deadline is September 15.

Some Theory Funding News from the Committee for the Advancement of Theoretical Computer Science. Take advantage of the current theory-friendly environment at the NSF while it lasts. If you were putting together a letter of intent for CDI, stop and read this.

Luca reports on the untimely passing of probabilist Oded Schramm.

I'm traveling the next two weeks to two of my favorite European haunts, CWI in Amsterdam and Dagstuhl. I'll keep blogging from the other side of the pond.

10:41 AM #

Wednesday, September 03, 2008

 
I would bet on INTRADE that INTRADE will do badly picking VP Nominations

Posted by GASARCH

(Lance and I independently made a post on VP selection. This post is not related to his, nor is his related to mine. Dave Barrington helped me with some of the history in this post, as did some folks in their 80's who assure me that Nixon was a surprise VP pick.)

The day before McCain picked Palin a pundit said the following: I don't know who it will be but INTRADE has had a big spike for Romney. INTRADE is always right, hence I predict that some insiders know that its Romney and that is who it will be

Well, INTRADE is not always right, even before the Palin Pick. And would an insider be guilty of insider trading? I predict that in the future VP will be one of those things INTRADE does badly on. Why? Because it is idiosyncratic. Picking the Prez Nominees is like picking the Oscar: small number of possibilities, and one has a sense of things. Picking the VP is like picking what movie Lance Fortnow favorite movie of 2008: too many possibilities, too ill defined (what if he saw a movie made in 1998 in the years 2008, does that count?) and too dependent on his mood.

In the past there was no INTRADE, but there was a short list of VPs. Below is a list of VP candidates (not including incumbents VPs) and whether I think they would have done well on INTRADE. My speculation is based mostly on if they would have been on the short list. I also include the Prez Candidate, the party, and WON/LOST. BADLY means would do badly on INTRADE. GOODLY means would do goodly on INTRADE. OKAY is inbetween.

1. 2008: McCain picks Palin. Rep. BADLY.
2. 2008: Obama picks Biden. Dem. GOODLY.
3. 2004: Kerry picks Edwards. Dem. GOODLY. LOST
4. 2000: Gore picks Lieberman. Dem. OKAY. LOST
5. 2000: Bush picks Cheney. Rep. BADLY. (Cheney was head of VP selection committee, so really Cheney picked Cheney.) WON.
6. 1996: Dole picks Kemp. Rep. BADLY. LOST
7. 1992: Clinton picks Gore. Dem. OKAY. WON
8. 1988: Bush picks Quayle. Rep. BADLY. WON
9. 1988: Dukakis picks Bentson. Dem. OKAY. LOST
10. 1984: Mondale picks Ferraro. Dem. BADLY. LOST
11. 1980: Regean picks Bush. Rep. GOODLY. WON
12. 1976: Ford picks Dole. Rep. OKAY. LOST
13. 1976: Carter picks Mondale. Dem. OKAY. WON
14. 1972: McGovern picks Eagleton/Shriver. Dem. BADLY. LOST
15. 1968: Nixon picks Agnew. Rep. BADLY. WON
16. 1968: Humphrey picks Muskie. Dem. GOODLY. LOST
17. 1964: Goldwater picks Miller. Rep. BADLY. (Miller was in House not senate, so a surprise.) LOST
18. 1960: Kennedy picks Johnson. Dem. GOODLY. WON
19. 1956: Stevnson picks Kefauver. Dem. GOODLY. LOST. (Was serious contender for nomination.)
20. 1952: Stevenson picks Sparkman. Dem. BADLY. Speculation- (Was not a contender for nomination.) LOST
21. 1952: Eisenhower picks Nixon. BADLY. He was a 39 years old unknown at the time and a surprise. WON

1. 10 BADLY, 8 GOODLY, 5 OKAY. INTRADE usually does much better than this.
2. Dems: 6 GOODLY, 3 OKAY, 3 BADLY.
3. Reps: 1 GOODLY, 1 OKAY, 6 BADLY.
4. WINNERS: 2 GOODLY, 2 OKAY, 4 BADLY.
5. LOSERS: 3 GOODLY, 3 OKAY, 5 BADLY.

The winners/losers things may be unfair since these were all non-incumbents; however, some of the incumbents lost (Bush-Quayle and Carter-Mondale) so I leave it be. The stat I find most interesting is that INTRADE doesn't do that well here. Or wouldn't have. I may return to this study 10 years from now when I have real INTRADE data.

10:26 AM #

Tuesday, September 02, 2008

 
The Big Aggregators

Posted by Lance

Friday morning I wanted to know where the rumors were pointing to for McCain's running mate selection. I could have searched various political blogs, but instead I went to Intrade and checked out the current prices on VP candidates. Since Intrade has constant trading, these prices do aggregate the various rumors and their veracity. Sarah Palin was running at about 60%. Apparantly I was not the only one with this idea has Intrade had major performance problems on Friday.

After seeing the price for Palin, I had a question many other Americans were asking: Who is Sarah Palin? So I went to that other great aggregator Wikipedia and read up on her. The scariest part: For the first time, someone on a major party ticket is younger than me.

The wisdom of crowds boiled down to a number on a trading site and a constantly updated page with much more than I need to know. The rest of the Internet is just commentary.

Some graphs of Intrade's market on the Palin market lifetime and in the last day.

Two things to note: The markets didn't predict Palin until close to the end. Also big volatility in the closing hours. Market aggregate public information—they don't predict what isn't out there. In the last hours, even little rumors, accurate or inaccurate, can drive prices as some people try to make a fast buck.

Chris Maase's blog as always has much more Palin and all other things about prediction markets. Also check out the new Intrade.net which now has do it yourself prediction markets.

I created a simple widget for our Electoral Markets Map. You can see in on the left sidebar until the election and always have the most up to date account of who's ahead state by state.

10:32 AM #

Friday, August 29, 2008

 
The Ultimate Wallet

Posted by Lance

Once in a while a new product comes along, so well-designed, so cool, that I just have to get one. When I visited Yahoo earlier this month, two separate researchers had independently bought one and I instantly fell in love. I dropped some not so subtle hints to my family who got me one for my birthday and I am now a happy man. I'm talking of the All-Ett, a wallet replacement designed to remain thin even holding my many cards. My back pocket has never been more excited.

The All-Ett solves a problem I shouldn't have. I count 16 plastic cards currently in my wallet and that's only because I make a strong effort to keep the number down. We have the technology for me to hold a single card that can be loaded with the information of all of the other cards. Many universities, including Chicago and Northwestern, now have a single card that serve as ID, libary card, food service and other purposes. But there we have a centralized authority. It would drive the privacy advocates mad, but I'd love a national ID with both a smart chip and RFID and a mechanism that would let any other organization embed needed data on the card.

Why stop there? I shouldn't need a wallet at all. Every piece of plastic or paper in my wallet, including business cards, pictures of my kids and cash, could be handled by my all-purpose cell phone. It wouldn't be difficult to even have it open doors and allow me to start my car so I wouldn't need to carry keys either.

But, alas, those days are far away and I'll need to live with my many cards for a while. At least I have a decent place to store them now.

7:18 AM #

Thursday, August 28, 2008

 
If a Hobby relates to your work, is it a Hobby?

Posted by GASARCH

In yesterdays blog Lance mentions that he didn't see other math people or trade problems when he was on vacation, and that it wouldn't have been a vacation if he had.

This raises a question: Can you ever use a hobby in your work. I give a few examples below.

1. Steve Skiena wrote a book Calculated Bets about mathematical modelling and betting in sports. This combined Steve's lifelong hobby of watching and betting on Jai-Alai with serious math and computer science of interest.
2. Ken Regan's hobby is chess and he has some research there, as seen here.
3. My hobby is collecting novelty songs and I've gotten some blogs out of that. (Is blogging part of my job?) Other bloggers also use their hobbies on their blogs-- Luca and photography comes to mind.
4. Steve Rudich's hobby is magic, and I've seen him entertain at conferences. Some of the magic is based on math.
5. Lance has commented on the show NUMB3RS in the blog, and I wrote a reviewed Season 1 my SIGACT NEWS column. (If I buy the DVD and review it again, is that tax deducbible?)

If your hobby is some game then there may be some math of interest surrounding the game that you could get involved with research on. If your hobby is collecting paintings then you may have a harder time connecting it up with your work. (Maybe Game Theory of Auctions.) Do you even want to connect up your hobby with your work? Hobby is almost defined as not work.

Since most of us (I assume) like math, the line between hobby and work may be hard to see. If I work on Math problems in my leisure time, is that a hobby or work? If one of them inspires a paper then does it cease being a hobby? How does Sudoko fit into this? If I actually use the ZK Sudoko protocol to convince someone that I solved it, is that work or play?

9:40 AM #

Wednesday, August 27, 2008

 
While I Was Gone

Posted by Lance

Just got back from vacation. Unlike Bill, I didn't see other math people and trade problems with them. Then again it wouldn't have been a vacation if I did.

As reported on a few other theory blogs, computational complexity hit a home run in NSF's new Expeditions Program. A dozen researchers in the New Jersey/New York area won an award for Understanding, Coping with and Benefiting from Intractability. In fact all four of the Expeditions grants has at least some theory connections. I'm not a fan of these big NSF programs but it's good to see the money going to our community.

The September issue of Scientific American focuses on privacy and Anna Lysyanskaya wrote an article on theory-based cryptography. Further Reading points to an old post Zero-Knowledge Sudoku. Thanks for the plug.

Finally Peter Lee writes about the growing theory group at CMU.

9:44 AM #

Tuesday, August 26, 2008

 
What to teach in grad course in Comm Comp- some non-theorists in it

Posted by GASARCH

The topic What should a basic graduate complexity course, whose audience is mostly nontheorists (say 15 non-theorists, 20 theorists) have in it has been the subject of a a prior blog. This question is relevant to many people since such courses are common.

Today I ask a question that may be of less relevance. Univ of MD's requirements are such that I will be teaching a course on Communication Complexity that non-theorists will be taking. The Complexity Theory course is not a prereq. I will be using the book Communication Complexity by Kushilevits and Nisan which will add 10 to their book sales this year (maybe less-depends on the used book marked). What should be in such a course? Here is what I am planning, though I am flexible and your answers may influence me.

1. Overall themes: (1) Given a problem, what is its Comm. Comp.? (2) Applications to other models of computation.
2. 2-party Comm Comp
   1. Deterministic: Rectangles, foolings sets. SAMPLE : EQ requires n+1 bits. Not hard to prove, but interesting that, unlike complexity theory, we can actually get real results here. Will look at other functions as well like IP (Inner Product), Not sure if I will do Rank lower bound. Powerful, but somewhat mysterious.
   2. Nondeterministic: covers, relation to deterministic. SAMPLE: NE in N(log n), so in this setting P\ne NP. Also, in this setting NP\cap coNP = P. (P is polylog bits)
   3. Randomized: private coin and public coin. SAMPLE: Randomized provably more powerful than deterministic, as EQ shows.
   4. Relation to Circuits: Lower bounds on monotone circuits for MATCHING and other problems.
   5. Upper and lower bounds on streaming algorithms
   6. Upper and lower bounds on the Cell Probe Model
3. Multiparty Comp Complexity
   1. Multiparty Comp Complexity and Branching Programs and Ramsey Theory Go over Chandra-Furst-Lipton paper on this topic, but fill in all details and background (I'll have my own notes on this.) This is alot of material: Multiparty stuff, Ramsey Theory, Branching Programs. Will also do lower bounds on BP's that use 2-party (these results may imply the results with multiparty, but need to look at it more carefully). Will also do some other material on Branching Programs (might do Dave Barringtons result that NC^1 is in BP_5, but that may take us too far afield).
   2. Other applications of Multiparty comp. Complexity

1:03 PM #

Archives