Stoc seeking papers that...

STOC deadline is coming up and the organizers have asked me to publicize a particular aspect of it. Note that in the call for papers it says: Papers that broaden the reach of theory, or raise important problems that can benefit from theoretical investigation and analysis, are encouraged

Since I was explicitly asked to publicize this, I assume they really mean it.

Submision Deadline: 7:59PM, EST, Nov 19.

THANKS to Nicole's FOCS blogs and her positive outlook

I want to extend a warm thanks to Nicole Immorlica for Guest blogging from FOCS. So I will:

THANK YOU NICOLE!

(Would have done this yesterday but if I had delayed getting the WOLFRAM PRIZE information out there I would have gotten at least 10 more emails telling me to post it.)

The one thing that struck me the most about Nicoles FOCS blogs is the positive outlook usually missing from discussions about theory. If you look at this blog, other blogs, or just talk to people in theory, you usually read or hear negative comments like these:

1. FOCS is biased
2. STOC is too expensive
3. Theory is underfunded
4. Australian actresses are plagiarizing my quantum mechanics lectures to sell printers.
5. Back in the good old days people worked on important problems. Now they just get incremental results.
6. Bring back Lance!

Some of these complaints are certainly valid. But hearing or reading such negativism can be monotonous, and blind us to some positive developments. Hence I appreciate Nicole's positive outlook on FOCS and Theory in general. I hope it lasts her entire career.

Wolfram Prize won!- There IS a (2,3)-UTM

Recall that the Wolfram Prize which I blogged about here, was given to anyone who can determine if a certain Turing Machine was universal. It is now known that YES that machine IS universal.

Congrads to Stuart Kurtz, Lance Fortnow, and Kathryn Cramer, Jon Katz, and Katrina LaCurts- NOT for winning the prize but for being the first ones to tell me who won the prize so I could post it. For that they win... a mention in this blog.

Here are some websites about it, most of them emailed to me by Kathryn Cramer.

1. write up in nature
2. Stephen Wolfram's blog!
3. Smith's 44 page proof!
4. New Scientist Story
5. Alex Smith's Photo!
6. Geomblog scooped me here
7. Live Journal

BACK TO BILL:

How important is the result? Alex Smith got $25,000 for it. The market has spoken, the result is important.

FOCS VIII

Nicole's final FOCS post.

And it's over! The 48th FOCS ended at 6.10pm with a talk on "The Computational Hardness of Estimating Edit Distance". About 50 brave souls lasted the whole three days.

Overall it was a really great FOCS. The results were good. The company was good. I have to admit, even the food was generally pretty good!

See you all next spring at STOC in Victoria.

FOCS VII : Funding? NSF? whats it all about?

(Another Guest post from Nicole!) More from the Business Meeting

Funding status report: I'm not really the right person to blog about funding since I have never yet applied for a grant. From the business meeting, it seems like a lot of people are doing a lot of hard work to funnel more of the NSF budget into our hands. They seem to have had some success. There are two new initiatives -- CDI, Expeditions -- and several old ones which now have more money than before -- ToC, SING. Funding rates seem to be around 25% (33% for CAREER). (An aside, maybe we should also try in an organized way to funnel more of the federal budget into the NSF by, e.g., writing our representatives in congress -- you don't have to be a citizen to do this -- or through PR campaigns.)

But you can find all this info on the NSF website. What you can't find on the NSF website is how it affects us young academics. I am about to start my first faculty job, and funding has suddenly become a very real issue for me. I see these numbers, I hear about these politics, and I am totally in the dark. I have never written a proposal, never even read a proposal. I don't know how to play the game. I know my senior colleagues will help me through this process, but that does not reduce the anxiety. I suppose every career path has rites of passage like these. The thing is some rites of passage are fun. I could be wrong, but I'm not looking forward to this one. ~

FOCS VI- Local Arrangements AND the future of FOCS!

(Another Guest post from Nicole!)

The business meeting was fun thanks to Mihai!

Local arrangements: First, let me say how wonderful the local arrangements were this year, a sentiment I've heard from many others here. Thanks so much for making this FOCS happen.

Claire gave a very detailed account of the local arrangements. The general message seemed to be that things are expensive. Expenditures this year reached $100K. The usual culprits were at fault -- food ($265 per person, total of $66,000), paper proceedings ($32 per person, total of $11,700), PC meeting/registration fees ($12,000), room/equipment rental ($4,200). Everything sunk in when it was announced that we're looking at a $525 registration fee for STOC 2008 in Victoria, admittedly thanks in part to the falling dollar.

The usual debates ensued -- paper vs CD vs online proceedings, catered lunch vs on-your-own, alternate conference venues. Let me capitalize on my journalistic duties to further my personal opinion on these matters: online proceedings (and ideally someday online PC meetings) are much more environmentally friendly. For me, this is enough. But, besides environmental and monetary costs, online proceedings are also easier to access after the meeting and can include media beyond print, e.g. slide presentations, videos of talks, etc. (see, for example, the excellent wiki of FOCS 06 built by Amin Saberi). People who really want paper proceedings can go to Kinko's with a printout of all the papers and pay $50 to bind them.

But honestly, I'm getting tired of this annual debate. Let's just do it my way. ;)

FOCS V- Report from Prog Comm.

Another great guest post from Nicole Nicole Immorlica, from FOCS

(Note from Bill G: This is one of several posts Nicole will be making from the Business meeting.)

Program committee report: Another congrats is in order. No matter what you think about the distribution of topics (see below), you can't deny that the PC did a great job this year. I was especially impressed by the extensive feedback, both internal and external, on submissions; the comments were thorough and explicitly stated the PCs reasons for their decision. Now for the statistics, well, here's the list that was presented at the business meeting: The number of submissions: 302. The number of accepts: 66. Below is a topic that there were papers submitted on, followed by how many submitted,and how many accepted.

1. Algebraic/Numerical Computation (14, 1)
2. Algorithmic Game Theory (27, 5)
3. Algorithms 85
   1. Approximation (35, 9)
   2. Geometric (8, 2)
   3. Graph (17, 1)
   4. Randomized (14, 4)
   5. Streaming (6, 2)
   6. Misc. (15, 0)
4. Combinatorics (2, 0)
5. Computational Biology (2, 0)
6. Computational Complexity (30, 14)
7. Cryptography (20, 7)
8. Data Structures (6, 2)
9. Geometry (13, 3)
10. Learning (7, 0)
11. Logic/Proof Complexity (11, 2)
12. Parallel/Distributed Computation (15, 1)
13. Property Testing (10, 5)
14. Quantum Computing/Crypto (25, 6)
15. Random Structures (7, 2)
16. Misc. (11, 0)
17. Out of Scope (6, 0)
18. P = NP (1, 0)

I think I'll leave it up to the commentators to interpret this.

FOCS IV

(Even More from Nicole Immorlica, guest-posting from FOCS. This post is from Oct 22, 7:00PM)

I remember taking writing classes in high school. We had a series of assignments emphasizing different writing techniques and topics. But each assignment started with the same question, the question which set the tone for the entire piece of work. Who is your audience? The importance of this question was the most valuable lesson I learned in those classes.

I've now attended about a quarter of the FOCS talks -- all the ones close to my area and a smattering of those completely outside my area -- and it seems to me that there are two types of audiences in every talk. There are the locals, those that are intimately familiar with the research area of the talk; and there are the tourists, those that want to explore something new.

How do you speak to such an audience? Most speakers seem to split the talk into two parts: accessible introduction/overview/problem statement and area-specific implications/proof techniques. And then they have to pack it all into 20 minutes. The result? Minds wander. What can be done about this? Longer talks to allow for a smoother ramp-up to the technical details (and hence fewer papers overall)? Parallel sessions (something FOCS has toyed with in the past)? Or maybe nothing? As my grandmother used to say, "you can please all of the people some of the time and some of the people all of the time but never all of the people all of the time."

FOCS III

More from Nicole Immorlica from FOCS.

The first day of FOCS is over. The highlight of the afternoon was the talk by Nancy Lynch, winner of the Knuth Prize. She began with, as one attendee put it, a nostalgic synopsis of FOCS/STOC from her first Denver 1972 conference in a cheap hotel across from a dirty movie theater on through the splintering of theory and distributed computing in the 80s. She then launched into a very accessible description of her famous paper on the impossibility of distributed consensus. The talk ended with an overview of current and future work in the field.

I think everyone in the audience was pretty satisfied with her outlined research agenda involving models of distributed computing on mobile networks until the air traffic controller example. She primed us by suggesting that her research could replace traffic lights with virtual traffic lights, which made me tense up slightly. Then she suggested we could even replace human air traffic controllers with virtual ones. While we all understand the benefits (e.g., you can have controllers over the ocean, machines don't get tired, etc.), I think we all had a sort of collective gasp. I guess at the end of the day, I just want to know there's a human behind it all, attentive and directly in charge.

One more thing I think is worth mentioning – this is the first Knuth prize (out of 8) awarded to a woman. This same year was the first year (out of 41) that a woman, Fran Allen, won the Turing award. This trend is both alarming (it took 41 years?) and encouraging (ample research and personal experience demonstrates the significance of female role models for professional women). Congratulations and my sincere gratitude to you both for paving the way.

FOCS II

Nicole Immorlica continues to blog from FOCS.

Just finished the morning sessions of day one. I guess it's time for the standard disclaimer – the talks I blog about are those I happened to attend and should not be interpreted as the "best" or even my personal "favorite" results, etc. etc. etc.

So about the sessions. Session one started at 8.30 AM and I'm embarrassed to admit that despite being the "guest blogger" of FOCS I missed the first talk. Somehow research before 9.00 AM is akin to hard liquor before breakfast for me. I just can't stomach it. I caught the end of the talk though, and was shocked that the room was packed! I took a picture, try and see who isn't there. :)

The second session was much closer to my research area – algorithmic game theory – and hence I got much more from those talks. One particular nice result was that from the paper Mechanism Design via Differential Privacy. The authors introduce a new solution concept for mechanism design which resolves many of our frustrations with dominant strategy mechanism design, and they do so through a creative connection to a seemingly unrelated field – privacy.

FOCS I

Nicole Immorlica guest posts from FOCS.

I wake up bleary-eyed and jet-lagged at 6 AM begging of myself WHY? Why do I subject my body to such torturous trans-atlantic flight for three days of, of what? Of talks of which I will attend at most a quarter? Of hotel banquet food? Of aching back muscles from lugging around massive proceedings and laptops bundled together in free canvas tote bags that I don't really want anyway?

For me, the answer is the people, my friends, my colleagues, their quirky interests and insightful comments. It's the research in the corridors, the animated technical arguments over the lunch tables, the great stories that get told by a diverse set of people from a diverse set of backgrounds.

Basically, it's like a big family reunion. But families you are born into. How do you get born into the FOCS family? I remember my first FOCS – Las Vegas 2001 – feeling alone, isolated, shy. Now I feel a part of the family, accepted into this community due in part to my papers, yes, but also labels that were really a matter of luck. What becomes of all those people that didn't have my luck?

Why do I find this result interesting- MOD 17 SAT

I find the following result to be really interesting but can't quite say why: (For this exposition ≤_m means poly-m-reduction)

Let SAT₁₇ be the set of formulas such that the number of satisfying assignments is a multiple of 17.

If SAT₁₇ ≤_m S, S sparse, then SAT₁₇ ∈ P.

This is one of those results where the proof in the literature is hard because they prove something far more powerful (btt reductions- and more). Hence I have my own exposition that I made for my class here.

I presented it in class recently and the students questioned why it was interesting. I can usually answer questions like this (even about such things as the Polynomial VDW theorem) but this one is harder to say. I DO find it interesting (not just the proof, but the result) but can't quite say why.

SO, here is my challenge: either tell me a reason the result is interesting OR tell me a result that YOU find interesting but can't quite say why.

A more intelligent SPAM discussion

I wish to start a more intelligent discussion of spam then my last post lead to (my fault). And YES, the story I pointed to was a hoax.

Is Spam a big problem? I contend that it is and that it is going to get worse. Some random thoughts, some of which are what to do about it.

1. Make it illegal or make the penalties tougher. I don't know what the current legal status is, but even with tough laws this is hard to enforce because (1) What is spam? and (2) it would require international cooperation.
2. We could try just making spam that is trying to rip you off illegal. I'm sure it is. But sometimes its hard to tell what is a rip off and what is not. The ``Nigerian Billionaire'' scam is clearly a ripoff (does anyone still fall for that?) but the ``you can get viagra at a cheap price'' might not be. The ``we can get you out of debt'' is much harder to judge since (from what I understand) they pay your debts, charge you an enormous interest, but let you pay it off over a much longer period of time. It may well be legal but unethical. It may even be legal and ethical.
3. Keep designing better software to block spam. This is the current solution, and it works pretty well, but its getting harder, and too much real email is being blocked. Also, this is more of why I think its a big problem- we (as a society) spend an awful lot of time and effort on this.
4. As more people know that these are scams and less people fall for them, will the scam-spams stop? Can we educate people so they know better?
5. Fighting back- there was an article in the Atlantic Monthly about people who scam the scammers- with success. But there are not enough of them, and they are not that effective, to be a real deterrent.

So there are essentially legal, technical, and educational solutions. Are there others? (NOT including assasination.) Can they work? Who is winning this war? How can we tell?

Spam Assassin

In Russia a notorious spammer was assassinated

Is this a crime? Should it be? Consider the contrast:

1. Killing one person. How many people suffer and how much? The victim of course. Maybe his family and friends. But not that many people. So this is High Impact on a Few People.
2. Spamming 100,000,000 people. How many people suffer and how much? Far more than 100,000,000 suffer. Why so many? The following suffer:
   1. Software is more expensive because you need to put in spamassassin's.
   2. People who send legit email that is blocked. This has caused confusion not worthy of a bad sitcom.
   3. The people who fall for these spam-scams.
   4. The Nigerian billionaires who really do want to give me $5,800,000 dollars. Its hard to tell the real ones from the fake ones.

So, how to measure the cost-benefit of killing this spammer?

{ s₁, s₂, ..., s_n } is the people that suffer by the spammers death. Person s_i suffers a_i.

{ t₁, t₂, ..., t_N } is the people that suffer by the spammers action. Person t_i suffers b_i.

Its safe to assume that n is MUCH LESS THAN N and that b_i is MUCH LESS THAN a_i. If

a₁ + a₂ + a₃ + ... + a_n < b₁ + b₂ + b₃ + ... + b_N

then the spam assassin should not be charged with a crime.

The more serious question here is how to deal with spammers who transcend boundaries and seem outside of the law. The Russians may be onto a solution...

Is Computer Science a Science?

Is Mathematics a Science? Is Computer Science a Science (hmmm- it has to be, its in the name :-) )? Is Richard Stallman a computer scientist? How about Bill Gates? How about my wife who has a job programming? For a serious discussion of some of these issues see an blog of Lance's For a less serious discussion, I offer the following thoughts.

1. Calling something science, engineering, art, or business is not an insult or a compliment.
2. A topic is a science if it has a lab where there is the potential for danger. Physics has radiation, Chemistry has explotions, Biology has germs. So they are sciences. Neither Math nor Computer Science has those.
3. Hence, asking if Richard Stallman is a computer scientist is not really a question. So perhaps we need a different term. `Computer Programmer' is a fine term and we know what it means. How about if we call ourselves `Computer non-programmers'? Depends if you consider LaTeX a programming language (it is Turing-Complete).

The Free Software Foundation and Richard Stallman

Richard Stallman gave a talk at University of Maryland at College Park. He is the head of the free software foundation. The terminology `free software' does not mean that software should be given out for free. It means that once you buy software you should have the right to use, study, copy, modify, and redistribute it as much as you like. EMACS, which he wrote, has this kind of license. So does GNU which is an FSF project. The talk was pretty good. He made some valid points about the evils of the current system. I think he has some good points to make.

1. He talked for 1 hour 45 minutes. This is probably 45 minutes too long.
2. When I say he talked for 1 hour 45 minutes I am being literal- no slides, no blackboard presentation, just talking. This may be because to use technology he would have had to use Software from a company that he does not approve of.
3. He speaks of free software as a human right. He speaks of it as the worst evil in the world. There are worse evils in the world; however, all good causes need true believers, and he is one.

I've heard all this before and further ago than most people. In 1982 he was my housemate in Graduate School. He had some of these ideas then, but they are better develped now. I sortof wish I had gotten involved with Free-Software early on since its a good cause and it would be nice to be able to contribute to society in this way.

P.S. Richard Stallman is not the most famous computer scientist who knows me. Serge Brin, co-founder of Google, had two courses from me as an Undergraduate. I definitly wish I had gotten involved with Google early early on since its a good product and it would be nice to be able to contribute to my bank account in this way.

If pigs could fly then bacon would be cheaper

Pretend you didn't know the Karp-Lipton theorem. Consider the following two statements

SAT has poly size circuits.

The Poly Hierarchy collapses.

You probably think both are false. Which statements truth would surprise you more? Personally I think SAT has poly size circuits would surprise me more.

Karp-Lipton Theorem:

If SAT has poly size circuits then Poly Hierarchy Collapses.

Does this really make your belief that SAT does not have poly sized circuits stronger? You already believed that. I know of one theorists who tells me that she believes SAT does not have poly sized circuits MUCH MORE than she believes that PH does not collapse. Hence this theorem does not tell her anything.

If you have

(unbelievable statement A) --> (unbelievable statement B)

what do we then know that we didn't know before? We know that A is MORE unbelievable than B, I suppose. We seem to have taken

BLAH --> P=NP

as the gold standard in showing that we believe BLAH is false and

BLAH --> PH=\Sigma_2^p

BLAH --> PH=\Sigma_2^p

etc. as forming a hierarchy of non-belief.

This is a nice picture, but it may be that BLAH is just not that believable in its own right and does not need to imply something like $\PH = \Sigma_3^p$ to give NOT(BLAH) street cred.

Deal-No Deal: MORE $ = LESS Interesting

I caught an episode of DEAL-NO DEAL recently (see this for a description). The math behind this game has been described in blog postings of Lance (see this as well as the above link)

The episode I saw showed something wrong (at least in my opinion) with the way they are promoting the show during premiere week. They have upped the amount of money to be a max of $4,000,000 (instead of $1,000,000). I saw the following (this might not be quite accurate but makes the point) There were 6 numbers left:

1. $5,000
2. $10,000
3. $20,000
4. $100,000
5. $1,000,000
6. $4,000,000

and the bankers offer was $700,000. $700,000 is so large and so life changing that the decision to take it (which she did) is rather obvious. Even the audience WAS NOT yelling `NO DEAL! NO DEAL!' like they usually do. To exaggerate this, imagine if the top amount was $40,000,000 and your dilemma was whether to take $7,000,000 or risk it to maybe do alot better but maybe do alot worse. YOU WOULD TAKE THE $7,000,000. (or at least I would).

A question like `would you take $70,000 or take the chance that you get $400,000' is mildly interesting. But the $700,000 is to large to not take. Hence the game gets less interesting mathemtatically.

Given a persons utility function (or something like it) what would be the optimal max amount (and optimal set of amounts) to maximize the games INTEREST? This question might be interesting.