Computational Complexity: August 2006

Wednesday, August 30, 2006

Misha Alekhnovich Retrospective

Posted by Lance

Last night we had a session to remember Mikhail Alekhnovich who died earlier this month in a white-water kayaking accident in Russia. Eli Ben-Sasson and Sasha Razborov (the later through a letter) gave personal remembrances of Misha. Alexander Shen in Russia turned Misha to theoretical computer science, where he came to IAS to work with Razborov as a "visiting postdoc" before he actually did his doctorate at MIT followed by a real postdoc back at IAS before taking a faculty position at UCSD. He was very confident and aggressive in both his non-research and research lives, for example never being intimidated when working with Razborov.
Toni Pitassi and Russell Impagliazzo highlighted a small sample of Misha's great work in proof complexity. Toni focused on automizability, given a proof system like resolution or DPLL (backtracking), how hard is it to find a proof not much larger than the original proof. Misha and his co-authors showed you cannot find

Resolution proofs with a nearly linear factor larger than the smallest possible proof unless P=NP. (JSL 2001)
Resolution proofs within a polynomial of the smallest proof size unless W[p] is fixed-parameter tractable, which implies SAT can be solved in time 2^εn for some ε<1. (FOCS 2001)
These results also hold for DPLL and many other proof systems. Misha played a lead role in these papers, finding simple examples that cut to the heart of the problems.
Russell talked about the problem of showing lower bounds for DPLL algorithms. Alekhnovich, Hirsch and Itsykson showed that certain randomly generated satisfiable formulas cannot be solved by certain kinds of backtracking algorithms (ICALP 2004). The 2005 Complexity paper showed lower bounds even when allowing arbitrary pruning of the search tree. Work on strengthening this later paper was an ongoing project when Misha passed away.
When we lose our colleagues at or near the end of their careers we celebrate what they have given to our field. When we lose them early, like Alekhnovich at 28, we also regret what might have been. He would have continued his great research career as well as about to start a new phase in his personal life with a wedding in Russia planned for just next week. His loss still deeply affects many at this workshop.
7:48 AM #

Tuesday, August 29, 2006

Parallel Repetition Redux

Posted by Lance

This week I return to Banff for Recent Advances in Computational Complexity. The mountains help attract quite an impressive collection of fellow complexity theorists.
Last night Paul Beame presented a new paper by Thomas Holenstein that simplifies and improves part of Ran Raz's proof of the Parallel Repetition Theorem, one of the more complicated arguments in computational complexity. The new result replaces roughly Section 6 of Raz's paper with a new embedding argument (Holenstein's Lemma 8), a way for two players to usually agree on the outcome of a distribution where they both have approximations of the distribution, using only shared randomness and no other communication.
Paul did take nearly an hour sketching Raz's proof (with a little help from Ran who was in the audience) before he could even describe Holenstein's contribution so we don't yet have a simple version of the parallel repetition theorem, but it has become much simpler than before.
8:21 AM #

Monday, August 28, 2006

Analyzing the Zoo

Posted by Lance

Greg Kuperberg wrote software that runs transitive closure and other tricks on the Complexity Zoo to produce inclusion diagrams and a list of complexity class relations. Kuperberg's project has great value, the ability to tell immediately whether one class is contained in another can save us time rederiving these results and gives us a clearer picture of how complexity classes relate to each other.
Kuperberg's software also produces a large number of open questions, finding the most and least likely open relativizable containments.
Go through the list of open questions and you will find some problems that follow from known results. Let Greg know and he will update his program, which of course might list other known "open" questions, but this process must converge in a finite amount of time.
You can also find some interesting open questions you might not have thought about and you'll also find a number of long-standing open questions.
But mostly you will find problems that just don't look that interesting. Why? Kuperberg's software treats complexity classes as syntactic objects, all of equal importance. But every class has a story, invented for a reason such as to capture an interesting computation model, to understand the complexity of some real world problems, or just to help us understand the relationship of other classes. Many classes get less interesting over time because the reasons we invented them have changed. Comparing two classes developed in very different contexts, say quantum classes and crypto-based classes, doesn't give us much insight unless the classes are extremely common. Finally in most cases we expect a separation and usually one gets little credit for the effort to create an oracle to get a separation we already expected.
7:58 AM #

Thursday, August 24, 2006

Who Wants to Watch?

Posted by Lance

Is it me or does the Fields medal seem to be getting more attention this year than usual? Nothing like a famous theorem and a crazy mathematician to spice up the awards a bit.
You can watch the ICM invited and prize winning talks here, both live and archived. Speakers of note include Terence Tao, Avi Wigderson (the first two talks of the third session) and, of course, Jon Kleinberg (last talk of the fifth session). Avi has a paper to go with his talk.
On a lighter note watch Stephen Colbert's take on the Fields Medal by clicking here then here.
(Thanks to Lenore Blum and Bill Gasarch for the pointers above.)
In other science news, Pluto is no longer a planet. Everything I learned in grade school was a lie.
3:23 PM #

Wednesday, August 23, 2006

Conferences Best Practices

Posted by Lance

Four years ago today I had my first real post announcing, among other things, that Madhu Sudan had recently won the last Nevanlinna prize. Hard to believe I've found four years worth of stuff to write about.
From the latest CACM, a short article describing a wiki set up by the ACM Health of Conferences Committee to discuss best practices for running conferences. As I write this the wiki is empty, a victim of spam attacks.
The article mentions several selected ideas for computer science conferences in general with some of my TCS oriented viewpoints.

Accepting More Papers. What is the right acceptance rate for a conference? The article suggests 20-30%, about where we have it for many theory conferences. We don't focus so much on acceptance rates, it tends to happen automatically. If we add more talk slots, then more people tend to submit.
Visionary Venues. Showcasing papers that present more farsighted or creative ideas. Some theory conference have informal rump and open problem sessions. Should we do more?
Author Responses (Rebuttals). Allow the authors to provide the program committee responses to reviewers concerns. In my opinion this will add too much to the reviewing time and if the authors cannot properly express their ideas, they can update their paper for the next conference.
Competitions. For example the Electronic Commerce conference runs competitions on various automated trading strategies. Not particularly applicable to theory conferences.
Tracking Reviews. Passing reviews on a paper from one conference to another. Sounds too complicated for us since we have so many different overlapping conferences.
Two-Phase Reviewing. Some conferences have introduced a two-phase review process where papers with an obvious bug, obviously non-novel or out of scope are rejected with a less rigorous review than those that are competitive. This happens already in theory conferences as it is much easier for us to separate the wheat from the chaff.
Double-Blind Submissions. Keeping authors and/or reviewers anonymous.
Hierarchical Program Committee. Theory conferences still aren't large enough to warrant this structure.
Co-Located Workshops. Helps boost attendance with more focused programs. We should also have more joint conferences, even just two in the same location as well as the occasional monstrous FCRC.
Hopefully the ACM can get the wiki back up and running but until then we can have our discussion here.
3:37 PM #

Tuesday, August 22, 2006

Nevanlinna and Fields Medals

Posted by Lance

Jon Kleinberg wins the Nevanlinna Prize, announced today at the 2006 International Congress of Mathematicians. Congratulations to Jon!
From the press release:
Jon Kleinberg's work has brought theoretical insights to bear on important practical questions that have become central to understanding and managing our increasingly networked world. He has worked in a wide range of areas, from network analysis and routing, to data mining, to comparative genomics and protein structure analysis. In addition to making fundamental contributions to research, Kleinberg has thought deeply about the impact of technology, in social, economic, and political spheres.

The Fields Medals go to Andrei Okounkov, Grigori Perelman, Terence Tao and Wendelin Werner. Perelman as expected for his work on the Poincaré Conjecture. Terence Tao played a role in work on Gowers Uniformity as well as many other areas of mathematics.
Finally Kiyoshi Ito wins the first Gauss Prize for Applications of Mathematics.
Luca is in Madrid and has the on-site ICM perspective. According to Luca, Perelman has declined the Fields Medal.
Update: BBC Story
7:41 AM #

Monday, August 21, 2006

Elsevier Updates

Posted by Lance

The editorial board of the Elsevier journal Topology have followed the lead of the editors of the Journal of Algorithms and have resigned effective the end of the year.
The Editors have been concerned about the price of Topology since Elsevier gained control of the journal in 1994. We believe that the price, in combination with Elsevier's policies for pricing mathematics journals more generally, has had a significant and damaging effect on Topology's reputation in the mathematical research community, and that this is likely to become increasingly serious and difficult, indeed impossible, to reverse in the the future.
As you know, we have made efforts over the last five to ten years to negate this effect. When the alternative subscription option was introduced a few years ago (electronic access combined with annual print delivery for half the regular price), we were hopeful that it would help in this regard. However it made little impact, probably because most university libraries which subscribe to Topology do so through consortia deals.
No word yet if the editors have plans to set up a new journal elsewhere. More from Not Even Wrong. (Thanks to Dan Zaharopol for the pointer).
Also the year-long Information and Computation experiment opening up online access to issues since 1995 concluded last week. Current Elsevier theory journals editor Sweitze Roffel writes
A look at the preliminary results reveals the following:

We have seen an increase in article downloads for the journal, interestingly both from subscribed and non subscribed users.
Some of the increase appears to result from systematic downloads, potentially from automated crawlers or from a few locations downloading many articles.
There seems to be a relation between press coverage and usage.

To quantify and qualify these preliminary results, understand their implications, and develop recommendations, we need to perform detailed analyses. Over the next three months, I will oversee an analysis by Elsevier of the complex and diverse information generated by this experiment and will subsequently share the results and methodologies fully.
Further review of this experiment, which we hope to conduct in close collaboration with the Editorial Board, should then determine actual lessons learned and suggest future actions to be taken for Information and Computation and possibly other journals.
Elsevier is committed to such a collaborative, factual approach to testing, learning, and implementing publication methods and policies that serve the academic community, while remaining commercially sustainable. This approach has successfully led, for example, to our new and more liberal copyright policies, our responses to the concerns of funding agencies, and our sponsored articles initiative. Elsevier wants to deliver demonstrable, innovative, and sustainable benefits to the scientific and other communities it serves.
3:18 PM #

Sunday, August 20, 2006

Mikhail Alekhnovich (1978-2006)

Posted by Lance

Thanks to Claire for guest blogging during my vacation. I apologize for the various technical difficulties on the weblog last week and all should be better now.
Unfortunately I come back to news of a loss of a young member of the complexity community. Mikhail Alekhnovich died in a white-water rafting accident in Russia on August 5. Misha, who just finished his first year as an assistant professor at UCSD Math, had some very deep results in theory, most notably in propositional proof complexity.
Misha did his postdoctoral work at the Institute for Advanced Study and the IAS theory page has more on this tragedy.
7:12 AM #

Saturday, August 19, 2006

French Universities

Posted by Claire Kenyon

I was a professor at a French university from 1997 to 2002. In France, universities are legally bound to accept any student who has obtained the "baccalaureat" degree at the end of high school (that's 80% of the population). There is no control of either quantity of quality of entering undergraduate students. The best 10% of the student population usually prefer the parallel "grandes ecoles" system and are largely absent from the university student body. The enrollment numbers are only known a few days before the start of the academic year, which leads to last-minute scrambles to hire additional lecturers and open additional sections. Tuition fees are a few hundred dollars per year, and give the student health care benefits, possible access to subsidized student housing, subsidized student cafeterias, rebates on public transportation, on movie theater tickets, etc. Some small fraction of the students enroll solely for those benefits and never appear in class or at exams, so the official enrollment numbers are not quite accurate.
About 50% of the students fail and have to leave the university after two or three uears without a degree. The students' actual knowledge is pretty reasonable by US college standards (a testimony to the quality of French education up to the high school level), but what is striking is their inertia, lack of motivation, and inability to study by themselves outside class time. At the freshman level, there can be discipline problems: students reading newspapers in class, talking aloud, throwing paper airplanes, groups standing up and chatting at the back of the lecture hall, etc. Saddled with fear of future unemployment, even conscientious students exude a feeling of helplessness and morosity.
In terms of number of hours spent in instruction in front of the students, the teaching load is similar to a 2/2 semester load in the US, although efficient organization could in principle reduce it to 2/1. At my university, at least 75% of anyone's teaching had to be at the undergraduate level (at some universities, graduate courses do not even count in the teaching load). To deal with the shortage of instructors, faculty are encouraged to teach (for a little bit of extra money) more than their legal teaching load, and going over by 15% is quite common. Refusing to do so is possible but shunned as un-cooperative. Faculty teach lectures but also (along with graduate TAs) some recitation sections and some labs, and grading is evenly distributed among the instructors. The class size is 150 at the freshman and sophomore levels and 120 at the junior and senior levels, although non-mandatory courses may have much less. There is no required textbook since that would force the students to spend money on books and thus violate the principle of free education.
Incredibly, there is no university-wide calendar. At my former university, undergraduate courses follow the semester system, with recitation sections staggered one week after the lectures and labs further staggered two weeks after the lectures; graduate courses follow the quarter system; coop students follow the "3 weeks on, 3 weeks off" calendar; and the computer engineering school has its own calendar. After the final exam, instructors are allowed several weeks to grade, which further delays committees and jurys. Thus, overall the earliest "last day of class" is in early May and the latest jury is in the first half of July, with a gradually dwindling volume of teaching-related activities between those two dates. By law, students who fail must be given a second chance in the form of a makeup exam, and so a second round of exams, grading, and jurys, happens during the first half of september, just before the start of the new semester. Overall, the only period during which all the faculty are completely free goes from July 14 to August 31. Such a short summer is a serious hindrance to research. Sabbaticals are not a right but a privilege, like some kind of local grant for which the faculty compete with one another, and the number of available sabbaticals is budget-dependent.
Classes, often located half way accross the campus, start as early as 8am and some classes end as late as 6:30pm. Luckily, they have enough classrooms to not need to schedule any classes on Saturdays.
Although professors officially are supposed to spend 1/3 of their work time on each of teaching, research and administrative activities, in practice research is largely viewed as a luxury and must fit in the intervals between lectures and meetings, along with supervision of PhD students. Grants are needed for travel, for which the university has no money. There are many opportunities for grants, usually for minuscule amounts of money . Individual grants are non-existant. In my experience, the grant proposal success rate is high: get together with a few of your research buddies, concatenate your vitas, add the requisite number of pages of text, throw in the right buzzwords, and you're in. Once you have three or four grants, you and your students' travel needs are covered.
The salary is somewhat less than half of that for a comparable position in the US, but because of universal health coverage, retirement benefits, and free education, that difference is not as great as it might seem at first.
Overall, the system is incredibly wasteful and inefficient, and local efforts for reforms are blocked by rules and regulations emanating from the Ministry of Education at the national level. To summarize, compared to a similar position in the US, the salary is half as much, the teaching load is twice as high in practice, the administrative weight is orders of magnitude heavier, and the resulting stress is unbearable.
During my fourth year there, three faculty in my department had sick leaves, for independent reasons caused by stress and exhaustion. This served as a wake-up call for me. The following winter, I successfully applied to Ecole Polytechnique (one of the "grandes ecoles"), and that was the end of my stint as a professor at a French university. I have been there, I have seen what it was like, and... I have been vanquished. To any person who might be considering such a job, I can now repeat the advice that Philippe Flajolet gave me in 1997 when I told him that I was applying: "Don't do it."
Comments page (Usual comments link does not work properly, use this instead.)
Claire
3:33 PM #

Thursday, August 17, 2006

Guess the max

Posted by Claire Kenyon

On Friday I will be flying back to the East Coast. Here is a puzzle to keep blog readers occupied while I am traveling.
I write two different numbers, one on each hand. You choose one of my hands at random, I show you the number on that hand. You now guess whether the number you've seen is larger than the number you haven't seen. Find a strategy for guessing such that, no matter what two numbers I write, you have greater than a 50% chance of being correct. (Borrowed from there.)
What if I have three hands and at any time you can choose to either keep the number I show you or discard it and move on to choosing another hand?
Comments page (Usual comments link does not work properly, use this instead.)
Claire
9:00 PM #

Why do research?

Posted by Claire Kenyon

Why do we do research? What is our real source of gratification?
I remember the answer which Andy Yao gave me many years ago. When he discovers a new result, there is a moment, between the time when he finds the proof and when he shares it with others, during which he feels uplifted by the awareness that he knows something new, something that nobody else knows in the whole world. I guess it must be like reaching the top of a mountain after much effort, and realizing that you are the first person ever to have climbed it.
My own motivation (perhaps more at par with my abilities) is quite different. What I enjoy the most is working with other people. When two or three of us get together and focus on a particular problem, there is a time, when new insights start revealing themselves to us, during which ideas go back and forth and there is a strong sense of intellectual closeness while we are together building a new construction. This is what I strive for.
Here is what Gauss has to say on the topic: It is not knowledge, but the act of learning, not possession, but the act of getting there which generates the greatest satisfaction.
Comments page (Usual comments link does not work properly, use this instead.)
Claire
7:34 AM #

Wednesday, August 16, 2006

Using Mobius numbers for a lower bound

Posted by Claire Kenyon

I have occasionally seen some comments on this blog as to how one can never know too much math. To support this statement, here is an example of a beautiful application of math to proving lower bounds.
Given n numbers, the k-equal problem must decide whether there are k numbers which are equal. When k=2 this is the classic element distinctness problem, and when k>n/2 this is a classic exercise. What is the complexity of the problem for general k? In 1992 Bjorner, Lovasz and Yao proved a lower bound of at least a constant times n*log (2n /k). Here is an executive summary (summarized from Bjorner and Stanley's paper, A Combinatorial Miscellany).
From computational complexity to algebraic topology: Each equation x(i1)=x(i2)=...=x(ik) defines a (n-k+1) dimensional subspace. Removing all these subspaces defines a space M, and it can be proved that the complexity of the k-equal problem is at least logarithmic in b(M), the sum of the Betti numbers of M.
From algebraic topology to combinatorics: Let P(n,k) denote the partial order whose elements are the partitions of {1,2,...,n} whose parts all have size either equal to 1 greater than or equal to k, ordered by the "merging" partial order. A combinatorial formula of Goresky and MacPherson implies that b(M) is at least the absolute value of m(n,k), the value of the Mobius function of the set {1,2,...,n}.
Definition: Given a partial order with a bottom and a top element, the Mobius function is defined recursively by: m(bottom element)=1 and m(x) is the sum, over every y less than x, of -m(y).
Enumerative combinatorics: As it turns out, m(n,k+1) can be expressed in terms of the complex roots of the polynomial 1+x+x^2/2!+...+x^k/k! From this, for k fixed and n variable, one can prove that there is a subsequence of m(n,k) which grows quickly enough to prove the stated lower bound.
Comments page (Usual comments link does not work properly, use this instead.)
Claire
6:40 AM #

Tuesday, August 15, 2006

Refereeing: Go with your Guts, or Let Reason Rule?

Posted by Claire Kenyon

My usual way to review conference submissions is to ask myself a few standard questions:
What is the problem being studied? Is it motivated in a compelling manner, by either practical or theoretical considerations? New problems warrant more careful scrutiny.
What is the result? If there are several results, usually I only look at the main result and evaluate the paper based solely on its best result.
Is the proof clever or difficult? Can I identify the key idea, and is it novel?
Finally, I give the paper a bonus if it is particularly well-written and a big malus if it is particularly poorly written, especially if the authors are all well beyond their student years - I get impatient with them, and think to myself that they should know better.
At this point in my career, this is usually all fairly routine. However, as Daniel Dennett suggests: "Perhaps our approximation of a perfect Kantian faculty of practical reason falls so far short that our proud self-identification as moral agents is a delusion of grandeur. " I was recently given a paper to review for a conference, and something strange happened. Based on my usual criteria outlined above, I sent to the program committee a mild recommendation for rejection and promptly put the submission in the trash. But instead of instantly forgetting about it, I kept remembering bits and pieces of it and found myself trying to reconstruct parts of the proofs. After a couple of days, it dawned on me that, even though the submission did not pass the filter of my "objective" criteria, still, I was interested in it and actually liked it!
I wonder what one should do in that case. Should you trust your instinct, or obey your evaluation rules? Go with your Guts, or Let Reason Rule?

Comments page (Usual comments link does not work properly, use this instead.)
Claire
8:38 AM #

Monday, August 14, 2006

Gin and vermouth

Posted by Claire Kenyon

Here is a puzzle from Schelling's book, Micromotives and Macrobehavior:
You have a glass of gin and a glass of vermouth. You lift a tablespoon of gin and pour it into the vermouth. You then take a tablespoon of the liquid in the second glass, vermouth with some gin in it, and transfer it to the first glass. Which is now the greater quantity, vermouth in the gin glass or gin in the vermouth glass?
Comments page (Usual comments link does not work properly, use this instead.)
10:10 AM #

Sunday, August 13, 2006

Correlation Clustering

Posted by Claire Kenyon

Last year Ailon, Charikar and Newman designed a very simple algorithm for correlation clustering. Suppose you have a set S of n data items, and for each pair of items, you know whether they are similar or dissimilar. How do you partition S into clusters according to similarity? Ideally, any two similar items should be in the same cluster and any two dissimilar items should be in different clusters. This is not always possible: for example, with three items a,b,c, if a and b are similar, b and c are similar, but a and c are dissimilar, there is no way you can cluster them satisfactorily (call this an inconsistent triangle). In correlation clustering, one aims to find a clustering minimizing the number of disagreeing edges.
The algorithm is wonderfully simple: pick an item at random, form a cluster consisting of that item and of all the items which are similar to it, remove the items of that cluster from S, and recurse.
The analysis is wonderfully simple. If you just picked item a, you will create a disagreement on edge {b,c} exactly when triangle abc is inconsistent. For any inconsistent triangle abc, let A(ab,c) denote the event that a,b,c all stay together in S until a is the vertex chosen at random by the algorithm, and let p(bc,a) denote its probability. The expected cost of the algorithm is exactly the sum over inconsistent triangles abc of p(ab,c)+p(ac,b)+p(bc,a). So, if we write q(abc)=p(ab,c)=p(ac,b)=p(bc,a), the cost is 3 times the sum of q(.) over all inconsistent triangles.
Notice that A(ab,c) and A(ab,d) are disjoint events. Thus the sum over c of p(ab,c) is at most 1. So, q defines a fractional packing of inconsistent triangles, and any clustering will have cost at least equal to the sum of q(.) over all inconsistent triangles. This proves that the algorithm is a 3-approximation.
This result is perhaps not a great leap forward in our understanding of TCS in general, but it is a very beautiful illustration of linear programming duality, a little gem of simplicity and elegance that is a pleasure to look at.
Comments page(The usual comments link does not work properly.)
Claire
11:21 AM #

Saturday, August 12, 2006

Funding

Posted by Claire Kenyon

Hi, this is Claire Kenyon and I am the guest blogger while Lance is away. I have spent the last few weeks traveling and have heard many US academics express worries about possible pending money troubles. The precarious state of NSF funding is on everyone's mind. Like everybody else I know, I have sent a proposal in answer to NSF's last call for grant proposals in TCS, and I am now considering what the next step should be if it does not get funded. What alternative is there to NSF funding? I have asked this question to a few colleagues and have yet to hear a promising answer. However, I found the answer yesterday on my flight to Berkeley, reading the Kinsella best-seller, Confessions of a Shopaholic: "There are two solutions to money troubles. C.B., or M.M.M. -- Cut Back, or Make More Money." To know how to Cut Back, we can look at our less wealthy sister discipline, Math, for inspiration. For example, we could bypass conferences and submit our results directly to journals.
Comments page (Usual link does not work properly.)
12:22 PM #

Friday, August 11, 2006

Flying Away with No Water

Posted by Lance

Next week I am on vacation and off the Internet. Claire Kenyon will be your guest blogger.
I get to experience the new airline rules, no water, toothpaste, gels and liquids of most any kind. The US government is being a bit over reactive but they were only two possibilities

They can over react to the news and cut back restrictions later as they can more accurately understand the risk factors.
They can possibly under react where the world learns about a new method to attack planes and the US doesn't try to prevent that new threat.
At least the planes are still flying, the rest are just comfort issues.
11:42 AM #

Thursday, August 10, 2006

A Predictions Markets Mess

Posted by Lance

The prediction market exchange Tradesports have themselves a little controversy over North Korean missiles.
I have written about prediction (or information markets) before. Consider some future binary event like whether Hillary Clinton will be the democratic nominee for president in 2006. One can create a security 2008DEM.NOM.CLINTON that pays off $100 if Clinton wins the nomination and $0 if she doesn't. Then allow trading on the security including selling short. The price of the security will correspond to the probability that the event will occur, and studies have shown that these probabilities predict better, in general, than experts and polls. Tradesports has such a security on Clinton and the price as I write this for 2008DEM.NOM.CLINTON is 41.9 indicating Clinton has a 41.9% chance of winning the nomination.
Tradesports had another security N.KOREA.MISSILE.31JUL that would pay off if North Korea launces a test missle that leaves North Korean air space by July 31. As you might remember, North Korea did fire test missles on the fourth of July. So it seems like the security N.KOREA.MISSILE.31JUL should have paid off at $100.
Here's the rub. The fine details of the contract required that the US Department of Defense verify that the missiles left North Korean air space. Tradesports couldn't get the verification so they expired the security at $0.
Those who predicted the North Korean missile launch lost real money on a technicality which risks the accuracy of these markets. They no longer predict whether a launch occurs, just whether the DoD would acknowledge it.
More from Smart Money, the Freakonomics Blog and full details and opinions by Chris Masse.
10:42 AM #

Wednesday, August 09, 2006

Missile Season

Posted by Lance

Eldar Fischer reports from Haifa.
Truth be told, the beginning of the missile season was a surprise for us all. It is true that enough people can claim to have seen it coming, but there was nothing special or expected in the date it started. One day it was business as usual at the Technion and the next day it wasn't.
Haifa has it better than most of northern Israel. We need to stay indoors at all times, and go to the reinforced rooms when we hear the alarm several times a day (our faculty building has a couple of such rooms in every floor, as any post-1992 building is required to have in Israel). Haifa gets hit with actual missiles several times a week—my father told me that it is not unlike the air-raids on Tel-Aviv that he remembers from the 1948 independence war. There are cities to the north that have it much worse, in which life over ground has practically ceased.
All academic interaction with undergraduate students has stopped, as having a concentration of so many people under one roof is deemed to be an uncalculated risk. There will be much work to do when the aborted semester-end tests are resumed and shoe-horned into what is left of the schedule. For graduate student the decision is more personal. Some of them have joined the masses of Haifa residents that have left town (parking space in Haifa has never been so abundant), and others have stayed. A good many of the undergraduate and graduate students (including one of mine) have been called to active reserve military duty, and we all hope they will come back safely.
Faculty members have faced a decision similar to that of the graduate students. Some have taken their work elsewhere (August is considered a good month for academic visits and traveling also in peaceful years), and others like me have stayed. Research at the Technion has not stopped. Thinking is turning out to be possible also in varied settings, and where needed email is taking the place of personal communication. It is not the same as when the hallways were lively with people, but research is done and you can expect good things from the Technion in the upcoming conferences.
8:32 AM #

Tuesday, August 08, 2006

Confessions of a Quantum Computing Skeptic

Posted by Lance

Will we ever have useful quantum computers? Despite the "breakthroughs" we seem to have nearly every month, we are a long way off from controlling even a handful of quantum bits certainly not the tens of thousands of qbits one needs for any meaningful computation.
But I'm not a physicist or an engineer and suppose we can overcome these obstacles and actually build a working machine. Then I can imagine the following conversation in 2025:
Quantum People: We now have a working quantum computer.
Public: Yes after 30 years and 50 billion dollars in total funding. What can it do?
Q: It can simulate quantum systems.
P: I'm happy for you. What can it do for the rest of us?
Q: It can factor numbers quickly.
P: Yes, I know. We've had to change all of our security protocols because of your machine. Does factoring have any purpose other than to break codes?
Q: Not really. But we can use Grover's algorithm for general search problems.
P: That sounds great! So we can really solve traveling salesperson and scheduling problems much faster than before?
Q: Not exactly. The quadratic speed-up we get from Grover's algorithm isn't enough the offset the slow-down by using a quantum computer combined with error correction. But we can solve Pell's equation, approximate the Jones polynomial and a few other things very quickly.
P: Are those algorithms particularly useful?
Q: No.
P: They why did you build a quantum computer?
Q: Because we could.
11:26 AM #

Monday, August 07, 2006

Optimism and Patience

Posted by Lance

When looking for a long-term partner, you may have had a long string of failed dates, but you must remain optimistic that the next one will be "the one." You must also have patience to let a relationship develop before giving up and moving on.
The same advice holds for proving theorems. When trying to prove a difficult result, particularly a well-studied open question, it often seems some evil deity finds ways to foil your many proof attempts just as they almost seem to work. Don't give up. Remain optimistic that you can prove this theorem and keep the patience trying new approaches even as each approach gets cruelly shot down. Only when you've exhausted all of your ideas should you move on to the next result.
Over the years I have kept my optimism about proving a result, but I haven't had as much patience as earlier in my research career. Partly because as one gets older one gets more non-research responsibilities both at the university and in the community, though this is more an excuse than a reason. I also find it more difficult these days to focus on a single problem for hours or days at a time.
Let this be a lesson to young researchers. Don't worry that the older famous researchers have not solved the big open questions; most (but not all) do not have as much patience to focus on a problem and explore as many of the possible proof techniques as well as you can.
9:56 AM #

Thursday, August 03, 2006

Zero-Knowledge Sudoku

Posted by Lance

Victor has tried and failed to solve the latest Sudoku game and exclaims no solutions exists. His wife Paula has already solved the game. How does Paula convince Victor that a solution exists without giving the solution away?
A Sudoku game is a 9x9 board partially filled out with numbers 1-9.

9

2
3

8

4
1

4

5

6

1

7
6

2

1
9

8

2

5

4

2
9

5

8
3

2

The goal is to fill out the rest of the board with numbers 1-9 such that every row, column and the 3x3 sub-boxes all have exactly one of each digit in them.

1
9
7
6
8
2
3
4
5

6
8
5
3
4
1
9
7
2

4
3
2
7
9
5
8
6
1

4
1
8
7
6
3
2
5
9

5
6
9
8
2
4
7
1
3

2
7
3
5
1
9
6
8
4

9
2
6
5
7
1
8
3
4

4
3
7
2
9
8
1
5
6

1
5
8
3
4
6
9
2
7

Sudoku is an NP problem so Paula and Victor could reduce the problem to graph coloring and use the original zero-knowledge protocol for coloring. Or you can view Sudoku as a graph coloring problem. Here is a way for Paula can do a zero-knowledge proof on Sudoku directly, loosely based on the graph coloring protocol.
Paula goes to a different room than Victor and chooses a random permutation σ of {1,…,9} say σ(1)=2, σ(2)=8, σ(3)=6, σ(4)=5, σ(5)=4, σ(6)=9, σ(7)=1, σ(8)=7 and σ(9)=3. Paula then permutes the solution using σ as such.

2
3
1
9
7
8
6
5
4

9
7
4
6
5
2
3
1
8

5
6
8
1
3
4
7
9
2

5
2
7
1
9
6
8
4
3

4
9
3
7
8
5
1
2
6

8
1
6
4
2
3
9
7
5

3
8
9
4
1
2
7
6
5

5
6
1
8
3
7
2
4
9

2
4
7
6
5
9
3
8
1

Paula then puts each entry into a lockbox (which can be implemented using cryptographic assumptions) and gives the lockboxes to Victor.
Victor can make one of 28 choices.

Choose one of the rows.
Choose one of the columns.
Choose one of the sub-boxes.
See the permuted version of the original puzzle.
Paula then unlocks the appropriate boxes. If say Victor picked the third row Paula would reveal

6
5
4

3
1
8

7
9
2

Victor will accept if all of the digits in the row appear exactly once. Note that every possible permutation in the row will occur with equal probability over the choice of σ, so Victor learns nothing about the solution from this question.
If Victor picked the last choice Paula would reveal

3

8
6

7

5
2

5

4

9

2

1
9

8

2
3

7

8

4

5

8
3

4

7
6

8

Victor accepts if this is really a permutation of the original problem. Since the permutation σ is chosen at random again Victor learns nothing about the solution from this question.
Why should Victor now be convinced that a solution exists? If there was no solution, Paula could not find a permutation that causes Victor to accept for all of his 28 choices for the permuted puzzle is just the original puzzle in disguise. If Victor makes his choice at random then he will catch a cheating Paula with probability at least 1/28.
That still gives Paula a possible 27/28 chance of cheating. So repeat the protocol 150 times, each time Paula throws away the unused lock boxes and chooses a new permutation. Paula's chance of cheating in every round is at most (27/28)¹⁵⁰ < 0.5%.
Moni Naor gives a different protocol using scratch-off cards where Paula could never cheat Victor.
3:10 PM #

Wednesday, August 02, 2006

Fulkerson Prize

Posted by Lance

The winners of the 2006 Fulkerson Prize have been announced. The Fulkerson prize is given every three years to up to three papers in discrete mathematics.

Primes in P, Manindra Agrawal, Neeraj Kayal and Nitin Saxena
A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries, Mark Jerrum, Alistair Sinclair and Eric Vigoda.
Graph Minors. XX. Wagner's conjecture, Neil Robertson and Paul Seymour.
Great papers all. The Robertson-Seymour Theorem required twenty papers. Roughly it states that any graph property (like planarity) closed under edge contractions and edge and vertex deletions has a finite set of forbidden minors. This result has an interesting consequence that all such properties have a polynomial-time algorithm though there is no known method of constructing the algorithm from the property.
I disagree with Luca and Oded on awards. While theory is a team sport, we do like ways to recognize the very best work and individuals in our field. And awards get us talking about the best work. Even when we don't agree with the winners, the discussions that follow help us understand what we think is important.
By the end of the month we'll know the winners of the Fields Medal and the Nevanlinna prize. The excitement mounts.
12:37 PM #

Tuesday, August 01, 2006

Privacy

Posted by Lance

I have used Gmail extensively as my main email system for a couple of years now. I often get asked about letting Google have access to all my email. Is my email more secure on a machine run by Google or by the University of Chicago? Hint: Which one can my employer read without a court order?
Actually I don't care, I use Gmail because I like the interface and the ability to read my email on any browser on any internet-connected computer.
Computer scientists take as a given that everyone worries about privacy. But in fact, outside of computer scientists and a few other techophobes, most people don't. Google not only has my email but also my calendar and if they ever started Google Money, my financials as well. Nearly every major and most minor transactions I make leave an electronic trace. With the right passwords on the Internet you can see what products I buy, what books I read, what movies I rent. So what?
Best as I can