Guest Post on ICS 2010 (1 of 3)

Innovations in Computer Science 2010 (post #1)

Guest post by Aaron Sterling

This is the first of three posts about ICS 2010, the much-discussed "concept conference," which took place at the Institute for Theoretical Computer Science (ITCS), Tsinghua University, Beijing, from January 5th-7th. I will provide my impressions in this post and one other, and Rahul Santhanam plans to contribute something as well.

First, I need to say that this was the best-run conference I have ever attended, and one of the best-organized events of any kind that I have ever participated in. The level of financial support for students and authors, the quality of food and lodging, and the remarkable closing ceremony (which included several music and dance acts, a Kung Fu demonstration, and -- my favorite -- a Face-Off performance) set a high bar for any other conference in the world. Local Arrangements Committee members don't often get mentioned in posts like these, but I believe the entire TCS community owes a debt of gratitude not just to PC Chair Andrew Yao, but also to Local Arrangements Chair Amy Yuexuan Wang, Conference Secretary Yuying Chang, and to everyone else who made this event happen. This feels like a turning point in the history of the field.

In the US, I have often gotten the impression that computer science departments and funding sources consider TCS to be of secondary importance. What a difference in Beijing! As a silly-yet-telling example, Sanjeev Arora told me that, for a conference in 2009, ITCS printed a sign in which the phrase "Theoretical Computer Science" appeared in the largest-size font ever. I believe the investment in theory on the part of the Chinese government and academia, contrasted to the malaise of departments in the United States, speaks volumes about the future, unless the United States changes direction significantly. I'll leave that topic to be discussed on a political blog, though. Suffice it to say, I think everyone was pleased to be treated like a first-class scientist, instead of like someone doing "impractical" things that are less worthy of support.

Perhaps the highlight of the technical program was the "derivatives paper," already covered at length by Richard Lipton and other bloggers, so I won't discuss it here. Many of the accepted papers were in algorithmic game theory, and I will limit myself to mentioning the two papers in that area I found the most exciting. These are "Bounding Rationality by Discounting Time" by Fortnow and Santhanam, and "Game Theory with Costly Computation: Formulation and Application to Protocol Security" by Halpern and Pass. Essentially, Halpern and Pass define a class of games with complexity functions attached, so it is possible to reason about concepts like equilibrium with respect to a particular measure of complexity. The Fortnow/Santhanam model embeds into this approach, as it considers one particular type of complexity function. On the other hand, the complexity function defined in Fortnow/Santhanam seems particularly natural, and they are able to obtain more specific results than Halpern/Pass, because they start with a less generalized model.

The conference started off with a bang: Benny Applebaum gave an excellent talk about cryptography obtained by using only local computation. This was "Cryptography by Cellular Automata or How Fast Can Complexity Emerge in Nature?" co-authored with Ishai and Kushilevitz. They constructed, for example, one-way functions with one step of cellular automata (i.e., after one step, it is computationally hard to invert the state of the system to the original state). As cellular automata can only communicate with their immediate neighbors, this has bearing on the parallel complexity of cryptography. One point that came up in discussion is that, unlike one-way functions, document signatures cannot be obtained by local computation only, because of the need to make global change to the output if a single bit of the input is changed.

The "Best Impromptu" Award goes to Avrim Blum, who, on three hours' notice, gave one of the most stimulating talks of the conference when he presented "A New Approach to Strongly Polynomial Linear Programming" by Barasz and Vempala, after the authors had a problem with their trip. The Barasz/Vempala concept is a hybrid of the Simplex Algorithm and the Interior Point Method for solving LP's. Rather than just trace the edges, or just go through the interior of the polytope, they take the weighted average of the "useful" edges near the current location, and follow the obtained "averaged" line until they hit another face in the polytope. It is unknown in general whether their algorithm runs in polynomial time, but it seems very interesting, because they have shown that, for each case for which Simplex runs in exponential time, their algorithm can solve that "hard case" in polynomial time. This is because their solution method is invariant under affine transformations of the problem statement, so it is robust even when the angles of the polytope are narrow, i.e., the constraints are very close to one another.

I will conclude this post by mentioning Bernard Chazelle's "Analytical Tools for Natural Algorithms." (Please see a previous guest post of mine, and comment 3 of that post by Chazelle, for some background.) His main philosophical message was: "Use algorithms to analyze algorithms" -- meaning that if one is trying to analyze the behavior of a nonlinear multi-agent system like ABC...Dx, where A,B,C, ... ,D are matrices whose identity depends on time and some kind of feedback loop, it is not helpful to consider the problem "just mathematically," by analyzing the operator ABC...D independent of x. Rather, one should consider the problem in the form A(B(C(Dx))), and design an algorithm to reason about this nested behavior. That algorithm can then (hopefully) be tweaked to prove similar results about related nonlinear multi-agent systems. To quote from his paper: "Theorems often have proofs that look like algorithms. But theorems are hard to generalize whereas algorithms are easy to modify. Therefore, if a complex system is too ill-structured to satisfy the requirements of a specific theorem, why not algorithmicize its proof and retool it as a suitable analytical device?"

In my next post, I'll sketch results from a few more papers, try to give some flavor of the discussion session at the end of the conference, and offer a few suggestions for the future. My apologies in advance to all the authors whose work I will be leaving out. Several attendees commented how accessible and well-presented the talks were -- and I noticed this too. (I think this was due in large part to the "call for concepts." Certainly when I prepared my own presentation, I felt motivated to communicate "high" concepts as well as I could, and I felt less pressure to include the Mandatory Scary Formula Slide(tm) to demonstrate my ability to perform rigorous research.) In any case, there is far more great material than I could possibly cover in two posts -- which is a very good problem for a new conference to have!

COLT and CCC

The COLT (Computational Learning Theory) call for papers is out. (Actually its been out since October but I was only recently emailed it.) For other information about COLT see here.
How do COLT and CCC relate to each other? (I use COLT for both the conference and the field. I use CCC for both the conference and the field.)

1. There are some results in COLT that are of interest to CCC and vice versa. But there is not much overlap. That is, the papers at COLT would be out-of-scope at CCC. And vice versa.
2. CCC has its original roots in computability theory. The basic notions of reductions and completeness were adapted from computability theory. COLT has some roots in Inductive Inference (computability-theoretic model of learning) but the connection is much weaker. The PAC model, and the other models, do not really take things from Inductive Inference and adapt them.
3. Both conferences used to have more of the Computability-theoretic material but it is faded in recent years.
4. Both fields use tools from discrete math; however, virtually all of Theoretical Computer Science uses discrete math.
5. COLT is co-located with ML (Machine Learning). They have done this before (I'm not sure how often.) COLT would like to be relevant to ML and probably is. CCC does not have a (more) applied field that it would like to be relevant to. CCC co-locating with STOC since there is a overlap in the people who want to go to both.

COLT is in Israel. Is this a good idea? A conference should be located in a place where the following occur.

1. There are people who normally can't go but now CAN go (e.g., CCC in Prague has 12(?) people from Prague, most of whom normally would have a hard time going). So- are there people in Israel who want to go? I would think yes since there is a strong theory community.
2. It is not too hard for the people who usually go to go. How hard will it be for Americans to get to Israel? For Europeans? I don't know.
3. The Guest Speakers (in this case Noga Alon and Noam Nissan) are close by thus saving on travel expenses. Actually, I had never thought of this one until I saw that they were the guest speakers.

DO NOT do this when choosing books for your class

When I took my first graduate course in complexity theory the professor had FOUR books on the REQUIRED FOR THE COURSE list. I bought all four. He said that

We may not use these books much but they will be good to have on your shelf if you go into theory.

I am the only one from that class who went into theory. One of them I have used (Hopcroft and Ullman's White Book). The other three I never touched and no longer have. I do not know what I did with them.

He was wrong, but for an interesting reason. Two of the books were on grubby Turing Machine stuff and models. (I don't recall what the third one was.) Things like constructing a universal Turing machine with 5 states. To be fair, theory was changing: Looking at grubby Turing Machine simulations was a dying field. Hence even a complexity theorist would not be served well by these books. We didn't even do this material in that class.

However, while I can be sympathetic that the prof didn't know that complexity theory was changing, asking students to buy FOUR books that are good to have on your shelf is a terrible idea.

Axioms: What should we believe?

Some misc thoughts on set theory inspired by yesterdays comments and other things.

1. Geometry: Use Euclidean Geometry when appropriate, for example if you are designing a bridge, use Riemannian geometry when looking at space time, and use geometries when they are appropriate. So there is no correct geometry, its more of a right tool for the right job thing. So far Set Theory does not seem to have a strong enough connection to the real world for this to make sense. I supposed you use ZFC when dealing with most of mathematics, but I doubt you would ever say something like: When dealing with Quantum Mechanics its best to assume AD. So what can you use to decide what axioms to use? You may decide what axioms to use based on your tastes. For example see this prior blog posting. This is good for an individual but will not really work for the whole community. For example, I happen to like AD since I like a world where the Banach Tarski paradox is false. But that's just me.
2. People concerned with these issues in the early 1900's were much more passionate then we are today. They had strong opinions on foundations and on non-constructive proofs. Mathematicians commonly carried firearms. We are far less passionate today on these issues. As an example, there are today people who study constructive proofs and prefer them, but I doubt anyone today would reject a theorem that was proven nonconstructively. Why the change of heart? Possibly Godel's theorem, but also the fact that people in different parts of math can't talk to each other so they can't argue.
3. Another axiom of interest: The existence of Inaccessible cardinals. MOTIVATION: Take omega. If |X| < omega then |powerset(X)| < omega. Does any other cardinal have this property? Why should omega be so unique? Kappa is an inaccessible cardinal is such that if |X| < Kappa then |powerset(X)| < Kappa. Do such cardinals exist? The existence of an inaccessible cardinal large than omega cannot be proven in ZFC. An inaccessible cardinal would be a model of ZFC and hence would prove that ZFC is consistent (omega does not prove ZFC consistent since no proper subset of omega is infinite). It is known that ZFC cannot prove its own consistency (I think that's true of any theory but there may be some conditions.)
4. Penelope Maddy has two nice articles on why mathematicians believe what they do: believing the axioms I believing the axioms II Also good to read: Shelah's Logical Dreams

Voting on Mathematical Truths: The Axiom of Det.

One of the founders of Conservapedia (a conservative alternative to Wikipedia) said the following on The Colbert Report:

There is an absolute truth. People don't vote on mathematical things like 2+2=4.

Given the source this quote may be ironic. However, this post is not about Conservapedia or Wikipedia. Its about voting on mathematical truths.

There is one kind of math where a vote might be appropriate. Some Set Theorists would like to resolve CH. We already know that this cannot be done in ZFC. So they want to add more axioms. What property should an axiom have? It should be obvious. It is unlikely that we will have new axioms of that type. How about that it be reasonable? Some set theorists think it is reasonable to remove FULL AC and add The Axiom of Determinacy (stated below). I want YOU to VOTE on if it is reasonable.

Definition: Let A be a subset of {0,1}^&omega. Let G_A be the following game: player I picks b₁ &isin {0,1}, then player II picks b₂ &isin {0,1}, then player I picks b₃ &isin {0,1}, etc. If the final sequence b₁ , b₂ , b₃ ... is in A then I wins. If not then II wins.

Definition: Let A be a subset of {0,1}^&omega. A is determined if either player I or II has a winning strategy for G_A.

The Axiom of Determinacy (AD): For all sets A that are subsets of {0,1}^&omega, A is determined.

1. AD is known to be true for A a Borel Set (Donald Martin proofed that).
2. AD contradicts the uncountable AC but implies the countable AC.
3. AD implies that every subset of the plane is measurable.
4. I don't think AD implies CH or not CH (are both AD + CH and AD + NOT(CH) known to have models?)
5. AD has a Wikipedia entry. This should not be taken as a sign that it is true of false. It should not even be taken as a sign that its well known. It just means someone put up an entry.
6. My wife thought AD was false in 1995 but true in 2005. I do not know what changed her mind. She is not a set theorist and had not thought about it in the intervening 10 years.
7. All finite games are determined so this is taking something true of finite games and assuming it is true for infinite games.

When you vote note that there is no right or wrong answer.

2009 Complexity Year in Review

We go all the way back to January for the paper of the year, Mark Braverman's Poly-logarithmic independence fools AC0 circuits. Runners up include the Moser-Tardos Constructive Proof of the Lovász Local Lemma (mostly for Robin Moser's great STOC talk) and Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay and John Watrous for QIP=PSPACE. Yet another great year for complexity.

We welcomed new bloggers Glencora Borradaile, Jon Katz, Harry Lewis, Richard Lipton, and Noam Nisan. And we have a new president who promises to restore science to its rightful place.

US Science funding in general and CS funding at the NSF in particular got a strong boost from the stimulus package and continues to be well funded in the new budget. Microsoft Research New England gobbles up Madhu Sudan and Boaz Barak. A new innovations conference starts next week and we explored barriers in August. Lots of postdoc jobs out there for theorists. If you are looking for a faculty job, well you might want to consider another postdoc. 

This year we started vidcasts and typecasts with special guests Molly Fortnow, Meena Mahajan, John Rogers, Rahul Santhanam, Chris Umans and Ryan Williams.

I had a fun year. My journal ACM Transactions on Computation Theory had its first two issues (submit your papers). I discovered Twitter. I became Theory Czar (SIGACT chair) with fellow blogger Michael Mitzenmacher as vice-chair. It's hard to complain about the powers-that-be when you are a power-that-is. I had two CACM articles Time for Computer Science to Grow Up and The Status of the P versus NP Problem, another year and the problem is still open. I just started a 3-month blog sabbatical to turn the latter CACM article into a book for the masses, though I can't resist the Year in Review post. Thanks to Bill for keeping the blog going.

We remember Rajeev Motwani, Amir Pnueli, Jack Schwartz, Imre Simon and Ray Solomonoff.

Thanks to our guest posters and contributors: Michele Budinich, Hans Courant, Dave Doty, Sorelle Friedler, Samir Khuller, Clyde Kruskal, Joe Kruskal, Bill Kahn, Michael Lucas, Lucy Moser, Ryan O'Donnell, Tal Rabin, Rahul Santhanam, Janos Simon, Aaron Sterling, Vijay Vazirani and Lenore Zuck.

Have a great New Years. Bill will be back next week and I'll be posting regularly again in March starting in Columbus. 

How to tell how good a TV show is

(This is my last blog of the year. Lance will interrupt his blog sabbatical to do an END OF THE YEAR blog later.)

The TV show MONK recently finished its 8th and final season. My wife and I are big fans and have seasons 1-7 on DVD (and we will get 8). But this post is not about Monk. Its about the question: How to determine how good a TV show is? I am sure that whatever I say here may apply to other problems.

First assign to each episode a number between 1 and 10 depending on how much you liked it. (This could be the hardest part of the method.) Let t be a parameter to be picked later. t stands for threshold. If your criteria is How likely is it that an episode is OUTSTANDING? then you would pick t large, perhaps 9. If your criteria is How likely is it that an episode DOES NOT SUCK? then you would pick t small, perhaps 2. Some of the methods use t, some do not.

There are many different ways to do this. We give a few of them:

1. The mean or median of all of the episodes.
2. The probability that a randomly chosen episode is rated above t. (Could also get into prob that it is within one standard deviation from t.)
3. The probability that a randomly chosen disc has an episode rated above t.
4. The probability that a randomly chosen disc has fraction f of its episodes rated above t.
5. Rate each disc in the DVD set for the entire season. The mean or median of all of these ratings.
6. The mean or median of the best season.
7. The mean or median of the worst season.

There are others as well. But the question really is, given a set of numbers grouped in a natural way (in this case roughly 8 sets of 16 numbers, and each set of 16 in groups of 4) how do you judge the quality?
For those who are fans of the show MONK here are my choices for OUTSTANDING and UNWATCHABLE episodes: here

What is an explicit Construction?

The Prob method (usually credited to Erdos) was once considered quite novel: You show something exists but you don't show how to construct it! An early example was lower bounds on the Ramsey Numbers: You can prove that there exists a 2-coloring of the edges of K_n with no monochromatic k-cliques where n=2^k/2, and the proof does not give a way to construct the coloring! When Joel Spencer wrote his first book on The Probabilistic Method (appeared in 1974) this kind of argument was still considered novel. Now they are quite common. Such arguments were (and still are) called Nonconstructive. However, at the time, the term was not defined rigorously.

Of course, once you know that such a coloring exists, it is easy to find one by just looking at all possibly colorings. Hence this use of nonconstructive proofs would not be an issue for logicians.

Many of the early prob method arguments actually showed that most colorings have the property you want. Hence they would lead to randomized polynomial time algorithms. With this in mind, here is one possible definition that seems to cover what Erdos and company were thinking informally:

Definition: A coloring of an object X is constructive if it can be obtained in time polynomial in the size of X.

Is this a good definition? Now that we think P=BPP, or at least that BPP is a good notion of feasible, perhaps we should call randomized algorithms constructive. Moser and Tardos think so since there paper entitled A constructive proof of the General Lovasz Local Lemma has a randomized algorithm.

Here is a history of the prob method as applied to lower bounds on VDW numbers (see here for definitions and some of the proofs). Let W(k) be the least number such that, no matter how you 2-color {1,...,W(k)}, there will be a monochromatic arithmetic sequence of length k.

1. W(k) &ge sqrt(k)2^(k-1)/2 is an easy application of the Prob Method. The proof is so easy that I could not find it written down anywhere, so I wrote it down in the paper pointed to above.
2. W(k) &ge sqrt(k)2^(k-1)/2 can be proved constructively by the method of conditional expectations. This is also so easy that I could not find it written down anywhere. So I wrote it down myself in the paper pointed to above.
3. Berlekamp showed that, if p is prime, then W(p) &ge p2^p constructively. (I prove a slightly weaker result in the paper linked to above.) (Berlekamp's original paper can be found on my website of VDW papers: here.)
4. Using the Local Lovasz Lemma one can show that W(p)&ge 2^k/ek. This proof is nonconstructive and does not yield and almost-all result, so it cannot be turned into a randomized algorithm.
5. Moser and Tardos (above link) (and later Beigel with a different proof) showed that the LLL can always be made to yield a prob algorithm. Hence they have a randomized algorithm to obtain a 2-coloring of {1,...,2^k/ek} with no mono k-AP's. This is not a constructive algorithm in the way that Erdos or Spencer might accept, though it does yield a feasible algorithm.
6. Chandrasekaran, Goyal, Haeupler in the paper Deterministic algorithms for the Lovasz Local Lemma have a deterministic version of the LLL with slightly worse bounds. From their paper one can obtain: W(k) &ge 2^{k/(1+&epsilon)} via a poly algorithm.

A hard problem inspired by an easy problem

The following problem was problem 1 (the easy one) on the Maryland Math Competition 2009 (I will later report on how the students did on it).

1. Show that for every set of three integers we can find two of them whose average is an integer.
2. Show that for every set of five integers we can find three of them whose average is an integer.

I am sure that most of my readers can do this problem. Here is a generalization. I do not know if it is true.

(Conjecture) For all k, every set of 2k-1 integers, there exists k of them whose average is an integer.

1. The UMCP competition asked for the k=2 and k=3 cases of the conjecture. They are true and easy.
2. I have done the k=4 case. It was tedious but not hard.
3. I think I have done the k=5 case but it was alot of cases so I may have missed one.

SO, is the conjecture true or not? I have asked around and people who should know don't seem to, so I throw it open to the blogosphere.

What I hope happens: Someone posts a nice proof.

What would also be okay: Someone posts a counterexample.

Guest Post- Women in Theory Workshop

(Tal Rabin requested to post this so I am doing so. This post is essentially her email, so call it a guest post.)

There will be a Women In Theory workshop for female graduate students in theoretical computer science in Princeton on June 19-23, 2010(see here) Tell all of the female students in your department about this workshop.

The workshop will have first-rate technical content and we also hope that it will help encourage female researchers and perhaps in the long run increase the unfortunately low number of women in our field. We will supply rooms and food for the participants, and will probably also be able to cover at least part if not all of their travel expenses - please let us know if that will be an issue. There may be a nominal registration fee.

The format will be similar to the WIT 2008 workshop. You can view information on that workshop at: here and view a video of WIT08 at: here.

For any questions, please email WomenInTheory2010@gmail.com . The deadline to apply is February 1st, 2010.

Mild Request for Guest Posters.

(Deadline to submit a paper to CCC is Dec 15. Depending on when you read this that could be today or in the past.)

As you all know from Lance's last post, Lance is taking a Blog Sabbatical. I will try to have 4-posts-a-week. But not holidays (I may define what a holiday is- like a week when I only have 3 posts I may declare Friday to be a holiday: no-post-day.)

This blog has always been generous about Guest Posts. Mostly people who wanted to guest post did so. More common is the following kind of exchange:

READER: You should do a post on Davenport-Schnitzel Sequences!

LANCE OR BILL: I've got a better idea, why don't you write one and we'll edit it and post it.

READER: Uh. Hmmm. Uh.... never mind.

Now that Lance is on Blog Sabbatical and I still WANT to get something up 4-times-a-week. I offer the following: IF you want to guest post then let me know and we'll see what makes sense. Rather than merely accepting Guest Posts, I am now ASKING for them. If I don't get any guest bloggers then I'll be singing this song:

CCC deadline Dec 15, 2009! (not factorial)

Submissions to 25th CCC are due TOMORROW! (Actually it could be TOMORROW, TODAY, or IN THE PAST depending on when you read this.) Should you submit?

1. If you have a paper all set to go, with proofs complete, that is in scope and interesting, then you certainly COULD submit. Whether you should depends on other factors.
2. If this is the first you've heard of the deadline then you probably shouldn't RUSH to get it done in time. However, some people work well that way. Not only am I not one of those people, I don't understand those people.
3. This year STOC and CCC are back-to-back in Boston. That's my favorite arrangement- the advantage of FCRC (STOC and CCC in the same place) without the disadvantage (too big!). Hence, submit, accept, or not, I think you should GOTO STOC and CCC if circumstances permit.
4. Should you look at who is on the committee and based on that decide if it will get in? I tend to ignore the committee. So many papers are subrefereed. Trying to figure out which conference will be better for you based on the committee is too hard to deduce. Better to go for SCOPE- is your paper a complexity paper or not? Also, if for some reason a STOC or FOCS paper is better for your resume you can submit there; however, you can then end up with NO conferences for a while and resubmit later and and and...
5. If you submit then make sure to get your submission spellchecked and proofread before you submit.

A Blog Sabbatical

With the end of the fall quarter I will take a break from the blog for a few months. This is not another End, just a chance to move my creative juices in another endeavor, to expand my CACM article into a book to spread the gospel of P v. NP to an even larger audience.

Bill will continue to post though not as often as we did together. I will post as needed for "really important stuff" and will continue to feed my Twitter with the less important but occasionally interesting/insightful/humorous stuff. 

I will return to blogging in mid-March with the start of Northwestern's spring quarter. I need the blog as I teach to keep my sanity. By then I should have written enough of the book to get past the point of no return. Maybe I'll even share some of it with you.

P.S. If any of you have good suggestions for publishers, let me know.

Whats your Game Mr. Bond? Nim?

BILL: Clyde is teaching a graduate course titled Games, Game Theory, and the Theory of Games. He tells me that there are basically eight kinds of games governed by three 2-valued parameters. (1) 2-player or multi-player, (2) complete information or incomplete information, (3) luck or no luck. For example Chess or Nim are 2-player, no hidden information, no luck (I won't quibble about the coin toss to see who goes first.) There are natural examples of most of the combinations. The one I have the most trouble with is multiplayer with no hidden information and no luck. (Clyde is NOT as dogmatic as the above indicates. One other aspect I've left out for this post is that some games are impartial and some are not.)

DARLING: Here is a multiplayer game with no luck and no hidden information: pick up sticks.

BILL: For Clyde's class that not a game.

DARLING: Why not? Its alot more fun than NIM!

Help me answer my darling. What makes something a game rather than a sport? Not sure pick-up-sticks is a sport either.

Lets try to get NATURAL examples of each category: One issue- the terms are not that well defined so you may disagree with some of these. We break it into two basic categories (for a better picture of the results goto here.)

1) Complete Information

1. 2-player, no luck. Go, Chess, Nim: Nim has had some nice math associated to it. Chess and Go have inspired very nice computer techniques (was alpha-beta pruning developed for chess originally?). There are some recent techniques for GO which I will talk about in a later posting.
2. 2-player, some luck: Backgammon, Can't Stop (a natural game but not that well known). Sorry! (that's not be apologizing, that's the game Sorry!). Parcheesi.
3. Multiplayer, no luck: Chinese Checkers. I do not know of ANY other examples.
4. Multiplayer, luck: Monopoly (and similar games).

2) Incomplete Information

1. 2-player, no luck. Stratego, Battleship: These are debatable. In fact, it may that that if defined carefully this combination is impossible.
2. 2-player, luck: Gin and most 2-player card game.
3. Multiplayer, no luck: Clue where each player only moves 5 squares per turn, so dice needed. One of Clyde's students families plays it this way, hence it is a natural game.
4. Multiplayer, luck: Poker. Most multiplayer card games.

QUESTION: Many games are hard via complexity theory. For example, GO and CHESS are EXPTIME complete (see here). Do these results tell us things about real games?

Is posting about 17x17 problem BAD FOR ACADEMIA?

(The 17x17 problem has gotten far wider attention than I imagined--- Brian Hayes posted it on his website: here, and its also here and here. The last website is odd in that it mentions my co-authors as also putting up the money, which is not true.)

(UPDATE- 17x17 and even 18x18 was solved. See my arXiv paper on grid colorng and/or Feb 8, 2012 post.)


(Reminder: NYU-IBM-COLUMBIA-THEORY DAY: see here.)

Anon 9 on comments on 17x17 post writes about my 17x17 post:

This is just like when teachers ask their students to model or code parts of a system that will be used in the teachers own research eventually. this is really bad for academia in general. Never again propose such things, please.

I will take this comment as the starting point in an intellectually honest discussion. I reply to it after this paragraph. I then URGE the poster to reply with either: (1) Yes, GASARCH you are correct, or (2) Yes, GASARCH you are correct, but its still bad for academia because ..., or (3) No, GASARCH you are wrong because ... . Doing either would be intellectually honest. Doing neither would be intellectually dishonest. You need not use capitals or use my phrases, but you get the idea.

1. When a teacher assigns students to write code for a system the students are forced to do it in order to get a good grade. I am not forcing anyone to work on the 17x17 challenge.
2. When a teacher assigns students to write code for a system and the students do not get a co-authorship then this could be bad (this might depend on the situation). I stated explicitly that whoever cracks 17x17 can publish it themselves, or, if they do enough other stuff, with me. In any case the terms are out in the open. Also note that whatever I do will get much scrutiny because I posted it on a public blog rather than a private classroom.
3. When a teacher assigns students to write code for a system the students might get nothing for his efforts. If a student cracks my problem they will get $289.00. If they try and fail they may learn things of interest (to be fair, this may be true for student-code-writer as well).
4. The 17x17 challenge has already stimulated discussion on three blog and might get some people interested on the math end (Ramsey Theory) or the computer end. How is this bad for academia?
5. As Michael pointed out what I am doing is similar to what Erdos did, though my problem is not deep mathematics. Do you think that when Erdos offered money for problems, this was bad?
6. If I had posted about the problem WITHOUT the cash prize would you still object to it? (One point: if I offered it without a cash prize I would have asked to RESOLVE the problem rather than to GIVE ME a verifiable coloring). If I had offered ALOT MORE money would you object? Is it a U-shaped curve: offer either less than 10 or more than 2000 and you are okay with it? I am not being funny--- I look forward to your intelligent to comment on this.)

Dequantification

After a talk on derandomization at Midwest Theory Day, someone asked if those techniques could also be used in quantum computing. 

In classical randomness under reasonable assumptions we can create a polynomial in m sized set S number of strings of length m such that every circuit of size m will accept with roughly the same probability whether we draw the input uniformly from S or from all strings of length m. Can we have an analog for quantum? 

There are many good parallels between probabilistic computing and quantum computing. Both seem to allow an exponential number of possible computations in parallel combined in a limited way. Probabilistic computation is essentially multiplying exponentially large stochastic matrices and quantum computing is multiplying exponentially large unitary (or just orthogonal) matrices.

If a quantum algorithm uses classical randomness, one can replace that randomness with measurements of appropriate qbits. So classical randomness does not give any additional power to quantum computation.

But could one use some hardness assumptions to remove the quantumness from a quantum computation leaving a deterministic algorithm? It's not clear we can pull out the quantumness and even if we could quantumness and randomness just work differently. Quantum algorithms get their power from interference, allowing adding positive and negative amplitudes causing cancellation, something very difficult to simulate probabilistically or with any form of psuedorandom generator.

In short no hope for dequantification. You'll just have to build that quantum computer if you want to run those quantum algorithms.

Complexity Vidcast 3

Quick announcement: If you are a student who wants to go to SODA but doesn't have the funds, click here.

I had forgotten we did this. Here's a video of my daughter Molly interviewing Bill and I about complexity our third Vidcast filmed last October before our Dagstuhl trip.

The Probability of P=NP

Dean Foster asked me for a probability that P=NP. Now P=NP is not a probabilistic event, either P=NP or P≠NP (if it's independent it's still equal or unequal in whatever model of set theory we happen to live in). So I responded that I was highly confident that Prob(P=NP)=0.

Not good enough for Dean, a professor in the Wharton statistics department, who said "But you aren't willing to give a number? Good Bayesians / Game Theorists have to bet on everything!"

A good Bayesian puts a probability p on every future event E where one would be indifferent to taking a small bet that pays off 1-p if the event is true and loses p if the event is false. 

As a computational complexity theorist we tend not to be Bayesians, rather look at worst-case performance under that assumption that everyone is working against us. But I've been talking with economists a bit recently so lets take the Bayesian approach.

Richard Lipton asked if one would bet their life that P≠NP. In some sense I have since the vast majority of my research becomes trivial or uninteresting if P=NP. But how much one bets isn't really the right question since that involves taking risk into account as well as beliefs. 

So what odds do I give? The problem is that I could only bet conditional on P v. NP being solved in some reasonable amount of time which would alter my beliefs since a proof that P=NP requires only an algorithm but a proof that P≠NP requires showing no algorithm can work. And the no trade theorem comes into play: If someone were to offer me a bet on P v. NP, I'd secretly suspect that they knew an algorithm or a proof I hadn't seen yet. But suppose that I could make a bet against a magical oracle would reveal the correct answer once a bet is made.

Still I can't in my heart give a positive probability to P=NP. So the probability of P=NP is zero, but in the measure theory sense that because an event has probability zero it doesn't mean it can't happen, only that it won't.

Congrats to new ACM fellows

Congrats to ALL of the ACM Fellows which were annouced here.

There are several theorists among them. I could try to list them or count them; however, the term theorist is not that well defined so I'll pass.

I wonder if any of them could use an additional $289.00...

17x17: Comments on your comments

One of the comments on my last post, the 17x17 post, inquired if I am also interested in the other unknown grids (NOW just 17x18, 18x18,21x12, 22x10). I AM. In fact, Brad Larson emailed me a 4-coloring of 21x10. Here it is. He does not get $289.00 but he does get my eternal gratitude. (ADDED LATER: BRAD LATER GOT A 4-COL OF 21x11. I ADDED IT TO THE LINK THAT GAVE THE 21x10 COLORING. I WILL SOON UPDATE MY LAST POST ABOUT POSSIBLE OBSTRUCTION SETS, AND MY CHART.) (ADDED EVEN LATER: BRAD GOT A 4-COL OF 22x10 ALSO.)

(UPDATE- 17x17 WAS solved, as was 18x18. See my arXiv paper on grid coloring and/or my post on Feb 8, 2012).


One of my former high school students emailed me because he was excited that my 17x17 posting was picked up by another blogger: here Is that worth being excited about? Will it make me a celebrity? Will it get me on THE COLBERT REPORT or THE DAILY SHOW? I doubt it.

Many readers commented on my last post. These comments have lead to two corrections- my chart had typos, and the paper had a typo in an equation. The other objections raised were (I think) incorrect; however, I could be wrong. In THIS post I will answer all of the questions in the last post. If there are remaining questions, please post.

1. The typos in the chart were fixed. THANKS for the corrections.
2. The equation that Aaron Sterling pointed out was incorrect had a typo. THANKS Aaron. That should be fixed soon.
3. The Obstruction set raised alot of questions. OBS_c is NOT the set of all non-c-colorable grids. It is the set of all MINIMAL non-c-colorable grids. More precise: if nxm is in OBS_c then nxm is NOT c-colorable but both (n-1)xm and nx(m-1) are c-colorable.
4. Sky thinks 9,10,11 are in conflict. I corrected the chart so that may no longer be an issue, but if it is, please comment.
5. Grid coloring is not related to coloring planar graphs. Grid coloring problems can be rephrased at hypergraph coloring problems. I doubt this is helpful, but I could be wrong.
6. Why $289.00? Because 17x17=289. I originally thought I would offer $2.89 but Lance pointed out that that might not be enough to generate interest. Then I thought $28.90, but Lance again thought that would not get people interested. $289.00 seems just about right to get people interested but not break the bank of Gasarch. The person who won't give away the answer fo $289.00--- will you take $2.89 instead? How about $28.90?
7. dut asks if the 74-sized Rect Free Subset is the smallest there is, or could there be one of sized 73. Actually we could just take out one element and get a 73-sized Rect Free Subset. I think dut meant to ask: in a 4-coloring do we know a number x such that no color appears less than x times? YES. Lets say (and this is true but probably can be improved) that there is no Rect Fres set of sized 80 of 17x17. Then the smallest possible number of times a color can appear can easily be lower bounded. li> One of the Anon posits that its impossible since this person thinks you can't have a 73-sized Rect Free Set. Alas, my original post had a 74-sized Rect Free Set. In fact, thats why I think you CAN 4-color 17x17. I look at it as a barrier result: All of the techniques to show a grid can't be c-colored used rect free sets. Hence 17x17 (and the others) will not be able to be proven not 4-colorable using our techniques. Hence new techniques are needed. Not quite as impressive as Oracles, Natural Proofs, or Algebraization.
8. Scott claims that my claims are riddled with errors. Scott- please either point out an error or post that you are mistaken. Clearly the CHART was riddled with errors, but has been corrected.
9. I agree with commenter after David Benson who would like to know what David Benson did. David Benson- please elaborate so we can see what you did and if its right.