17x17: Paper that solved it available!/A contest inspired by it!/NPC result inspired by it!

Three new 17×17 items:

1. The paper (and some sequels) that SOLVED the 17×17 problem and the 17×18 problem are now available here. The first three papers are relevent.
   
2. There is a contest going on (it started Tuesday) INSPIRED by my 17×17 problem. In brief, they want to, for all c=2,3,4,...,21 have you find the largest n you can such that n×n can be c-colored without any monochromatic rectangles. See here for details. There is prize money! Do it for the fame AND the fortune! Deadline is Aug 31, 2012.
   
3. (I posted this before but got no comments, so I'll just say it again.) The problem of GIVEN a partially c-colored grid does there exist a way to extend it to a c-coloring of the entire grid, is NP-complete. See
   here.
   

Theory Jobs 2012

The theoretical computer science job market has mostly settled so time for the annual spring jobs posts. I set up a Google Spreadsheet that everyone can edit so we can crowd source who is going where next year.

The rules

• I set up several tabs (sheets), for faculty, industry, postdoc/visitors and students.
• People should be connected to theoretical computer science, broadly defined.
• Only add jobs that you are absolutely sure have been offered and accepted. This is not the place for speculation and rumors.
• You are welcome to add yourself, or people your department has hired.

This document will continue to grow as more jobs settle. So check it often.



Edit

STOC 2012- workshop and honored talks

I went to an enjoyed STOC this year. Today I talk about the workshops and the papers that either won awards or seem to be in the running. I may blog on other things, or expand on these, at a later point.

1. On Saturday there were two workshops, one on Computational Finance by Mike Kearns and one on the Unique Game Conjecture by Subhash Khot and others (sorry- I don't recall who the other speakers were, though they were quite good- in comments tell me and I'll add it. The program says Arora and Charikar, though they didn't speak. I assume they organized it.) (ADDED LATER- CLARIFICATION AND CORRECTION: There was a Comp Finance TUTORIAL that, when
   it was happening, was the only thing happending, and then later there were FOUR WORKSHOPS going on at the
   same time: Computational Sustainability, Algs for Dist and Streaming Data,
   Algs for Memory-Sensitive Computing, and Unique Game Conjecture.)
   
   1. Computational Finance: A distinguished theorist once told me that he is tired of working on problems nobody cares about so he will now work on Computational Finance. He gave a talk that began A Hedge Fund is a set of Boolean Formulas. By contrast Mike Kearns has actually worked with Lehman brothers (Is that why they were not bailed out? Unlikely.) on REAL questions that arise from Finance. The talk gave the needed background on finance and was excellent. One odd thing: I understood the entire thing. I am not bragging- I suspect that everyone who went did. If I was a snobbish pure math guy I would say Since I understood everything it couldn't have been any good. I of course feel the contrary way- it is WONDERFUL that I understood the whole thing. This is partially because he skipped details which is a good thing to skip. Slides are here.
      
   2. Unique Game Conjecture: For past work on this I can't do any better than Lipton's blog here, Khot's surveys and slides here. Khot's talk were a good review if you already knew the material and a good intro if you didn't. The other talks introduced a possible approach to disproving the conjecture. Very High Level View: There is an algorithm using the eight level of the Lasserre hierarchy of SDPs that MAY disprove the UQC. The usual counterexamples don't work. (I may not be stating this quite right.)
      Note that: (1) The community of people who study UGC seems to NOT have a consensu of whether its true or false.
      And those who think its TRUE or FALSE are not dogmatic. (2) It may be resolved before I do my next Poll. If not then I'll
      ask about it. (3) Even if its false it has lead to results of interest that do not assume it.
      
2. There were poster sessions for graduate students. In some ways these are better than talks since you can interact.
   (ADDED LATER- A commenter helpfully pointed out that the posters were NOT just for graduate students.)
   
3. Kasper Green Larsen won best Student Paper award and co-won Best paper award for The cell Probe Complexity of Dynamic Range Counting
   which proved better lower bounds in the cell probe model. The talk inspired me to read the earlier papers on this material.
   
4. Fiorini, Massar, Pokutta, Tiwary, de Wolf co-won best-paper award for Linear vs Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds. This paper seems to use Quantum Techniques to solve a classical problem.
   
5. Most of the time there were two tracks so there were two talks going on at the same time. There were five exceptions: the best student paper and the two best papers, and in addition three other papers (the numbers work out that way since the best student paper also co-won best paper award). I assume those three are being unofficially acknowledged as runners-up for best paper or some such (I do NOT have inside information). Those three papers were
   
   1. Julia Chozhoy's Routing in undirected graphs with constant congestion.
      
   2. Chan-Kleinberg-Shmoys Improving Christofides algorithm for the s-t path TSP For the METRIC TSP problem the best known upper bounds is STILL 3/2. WOW. There are some lower bounds (see On Approximation Lower Bounds for Tsp with Bounded Metrics for a list of them) but they are pretty weak-- (1+delta)OPT for some small values of delta. (Someone at the conference told me that better was known, like (4/3)OPT, but I have not been able to find it online- if someone can confirm please leave a comment.) This paper is NOT on the TSP, but on s-t-TSP. They give an upper bound of ((1+\sqrt{5})/2)OPT for this problem, breaking the bound of (5/3)OPT. I don't think any lower bounds are known on this problem. (Note that Euclidean TSP can be approximated arb well by the algorithms of Arora and Mitchell.)
      
   3. Virginia Vassilevska Williams Multiplying Matrices Faster Than Coppersmith-Winograd" has been discussed before in in this blog and also in a blog by Lipton. Virginia did not give the talk since she was close to giving birth (I don't know if she has yet). (Prediction: Ryan and Virginia's kid will prove NP is not in ACC₀ by improving the matrix mult bound. Title of the paper: Improving William's Lower Bound by Improving William's Upper Bound by Williams.)
      

STOC Business Meeting

Last night I ran my last STOC business meeting as SIGACT chair. It was a three-hour affair until the hotel staff kicked us out at midnight. Lots of highlights. I put many of the slides online if you want to see details.

We had a very large turnout for STOC, over 360 participants. Being in New York definitely helped as did posters and workshop sessions. There were 90 accepted papers out of 303 submitted.

There were two best paper winners:

• “Linear vs. Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds”  by Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary and Ronald de Wolf
• “The Cell Probe Complexity of Dynamic Range Counting,” by Kasper Green Larsen

Larsen also won the Danny Lewin best student paper award. There were three other papers considered strong enough to merit a single session talk.

Sampath Kannan won the SIGACT Distinguished Service Award for his work promoting theory at the National Science Foundation.

Both the SIGACT Distinguished Service Prize and the Knuth Award will be given annually for now because we have many excellent candidates for both. The Knuth Prize will be given in even years at FOCS and odd years at STOC.

SIGACT elections are still going on. Please vote if you are a SIGACT member and haven't done so.

Skipping ahead (so this doesn't become a three-hour post) FOCS 2012 is at Rutgers, ITCS 2013 in Berkeley, SODA 2013 in New Orleans, STOC 2013 in Palo Alto joint with Complexity and FOCS 2013 (and every two years thereafter) hosted by the new Simons Institute at Berkeley. 

2013 STOC PC chair Joan Feigenbaum described a new multi-tier structure experiment for her program committee. 

Finally László Babai led a discussion on ACM publication policies. More on that in a later post. 

Meetings/Conferences/Workshops/Seminars- whats in a name?

In June 11-14 will be a new workshop: Algorithmic Frontiers.




How many venues do we have for meetings?

1. What the call themselves:
   Meetings (e.g., MATHFEST), Conferences (e.g., STOC), Workshops (Barriers), Seminars (e.g., Dagstuhl), Tutorials, Lunches. More?
   (six options)
   
2. Criteria for getting a paper in: Refereed (e.g., STOC): lightly refereed (I think MATHFEST), unrefereed, talks-by-invite-only (Algorithmic Frontiers, Barriers)
   (four options)
   
3. Participants: Open (most)or by-invite-only (Dagstuhl and Bertinoro) (two options)
   
4. Size: This is more informal. However, CCC is small (100), STOC is larger (around 400), FCRC larger still, and Supercomputing is expecting 11,000. Medical conventions can get around 20,000.
   (five options, though could be more or less depending on your mood.)
   
5. Variety of activities: A venue can have any combination of the following: contributed talks (unrefereed), refereed talks (typical STOC), invited talks, rump sessions,
   tutorials, workshops, short courses. (128 combinations, though in reality only about 5 options actually happen, so I'll take it as 5)
   
6. Length: Number of days can be anything from 1 day to 2 months. However, I don't think all 60 options really exist. I've seen 1,2,3,4,5 days, 1 week, 2 weeks, 1 month, and 2 months. nine options.
   
7. Expense: Either expensive or VERY expensive.
   

So that would be 6x4x2x5x5x9x2. That's a lot! Of course its far far less since, for example, an invite-only gathering can only have invited talks. I would guess its more like 5 types. And some are inconsistent (e.g., STOC sometimes has tutorials and sometimes doesn't).

Algorithmic Frontiers seems to be a 4-day open workshop that has invited talks only. I don't know how big it will be but I would guess between 100 and 200.

Do the gatherings that we go to work? As my Software engineering friend Jim Purtilo often says If you don't know your goals you are not going to achieve them. So, what are the goals? Ultimately to help both us as individuals and us as a community in our research. The hope is we learn things and get inspired to work on problems. And these can be done by the formal talks in the ballroom and informal talks in the hallways. Does this happen? Yes. Is it cost effective (not just money but time)? Debatable, as this and other blogs have debated. Here are my experiences. What are yours?

1. DAGSTUHL SEMINARS. These are specialized one-week long meetings by
   invitation only. The talks need not be on the latest/greatest thing and hence are understandable. (I've been to DAGSTUHL- Complexity 3 times.)
   
2. Bertinoro is similar to Dagstuhl. I've been to the RATLOCC 2011 and
   RATLOCC 2009 which are on Ramsey Theory and Logic. Here there were even more talks
   that were surveys or historical-perhaps because math moves slower than computer science.
   If the talks were on the INTERSECTION Of Ramsey Theory and Logic then it would be too specialized.
   (I've worked in both, but not quite together.)
   As is, its a nice mix.
   But the main point- I understood the talks.
   
3. The Center for Intractability sponsors workshops which anyone can go to
   but the speakers are picked by them. I've been to one of the Barriers workshops and it was very good. The speakers have more time then at conferences,
   which is a plus. The Algorithmic Frontiers workshop seems to be in this model.
   
4. The last few CCC's and STOC's that I've gone to I have enjoyed and gotten stuff out of, but not as much as the smaller venues.
   Partly because the talks are shorter.
   which is a plus. The Algorithmic Frontiers workshop seems to be in this model.
   
5. MATHFEST is nice in that there is a VARIETY Of activities- workshops, seminar, tutorials, invited talks.
   Very large which is both good (that's why they can have all of these things and bad (I never met the same person twice).
   
6. One of my colleagues, Jeff Hollingsworth, is organizing SC12, Supercomputing 2012.
   This will have 11,000 people at it. The program committee has over 100 people
   on it. This seems... large. They seem to have a variety of activities
   so it more like MATHFEST.
   
7. Of course the talks are only part of the reason to go to these things. Even so, for me they are a big reason.
   

What venues to YOU get the most out of? Why or why not?

Gödel Prize

The ACM announced the 2012 Gödel Prize awardees, three seminal papers in algorithmic game theory. The prizes themselves will be presented at ICALP in Warwick in July.

Elias Koutsoupias and Christos H. Papadimitriou: Worst-case equilibria, Computer Science Review, 3(2): 65-69, 2009.

Tim Roughgarden and Éva Tardos: How Bad Is Selfish Routing?, Journal of the ACM, 49(2): 236-259, 2002.

Noam Nisan and Amir Ronen: Algorithmic Mechanism Design, Games and Economic Behavior 35: 166-196, 2001.

The first paper introduced the price of anarchy. The second applied price of anarchy to routing problems. The third applied algorithmic techniques and competitive analysis to auctions.

Congrats to all the winners.

Wall Street Complexity

There is much blame to go around for JPMorgan Chase's two billion dollar loss last week but part of that blame came back to us. In a New York Times web piece, How Moore’s Law Affects Wall St. Trading, Quentin Hardy argues

Faster, cheaper computing makes it possible to create more and better models for calculating cash movements, which can be turned into trading instruments. Areas like leasing, mortgages and project finance have exploded – as has the entire financial derivatives market — thanks to cheap computing...

Soon, it becomes nearly impossible to say what is going on where, and you get events like the 1998 blow-up at Long Term Capital Management, the creation and destruction of the subprime mortgage market in 2008 and perhaps even the “flash crash” in 2010. JPMorgan’s loss seems to be the latest in that series.

I've argued the dangers of reducing computational friction before. But here computational complexity comes in a different way. A derivative is just a function of current and future security prices. But a derivative complex enough can have a behavior that even its creator cannot understand. The Clay Math Institute offers a million dollars to settle "P v NP" but it cost Chase two billion.

So THATS why the 17x17 challenge was so hard. Or maybe not.

On November 30, 2009 I posted the famous 17x17 challenge:

(Paraphrase) Find a 4-coloring of the 17x17 grid that has
no monochromatic rectangles. For $289.00. It was solved in 2012
by Bernd Steinbach and Christian Posthoff (I posted about it
here
and will post their paper when they make it it is public, which should be soon.)
Even though it was solved, it seemed to be a hard problem.

On April 28, 2010 (before the problem was solved)
I wondered WHY it was so hard and posted the following question:

(Paraphrase) Consider the following problem:
Given (N,M,c,f) where f is a partial c-coloring of NxM,
can f be extended to a total c-coloring of NxM (without mono rectangles)?
Is this problem NP-complete?

Kevin Lawler emailed
me a sketch of a proof recently! So YES, it is NP-complete!
I cleaned it up, wrote it up, and put in a few other things, and the paper is
here.
(We will be posting to arXiv after we get comments from this blog.)

1. Does this really show why the 17x17 challenge was hard?
   Not really since the 17x17 challenge is just one instance.
   
2. Does this show that grid coloring problems are hard in general?
   Not really since the case we are really interesting in is where
   f is the empty function. While we do not believe this case is
   easy, we have not ruled this out.
   
3. What can we show about the algorithmic complexity?
   The problem is FPT. For fixed c its in time poly(N,M)+O(c^c4).
   

This is a problem for hardness-of-Ramseyian numbers in general. While it seems as if computing (say) Ramsey Numbers is hard, there is no real proof of this. Related problems have been studied by Marcus Shaefer here.
While this work is very interesting
it is NOT the same as showing that finding Ramsey Numbers is hard.I suspect that to prove such things we need a new framework for
lower bounds.

Paying to Publish

You proved a nice theorem, wrote up the paper and submitted it to a major computer science conference. Your paper was accepted! Congratulations. Now pay up.

An author of every paper accepted at a CS conferences is expected to present that paper at the conference. To do so requires at the least paying the registration fees, travel and lodging to go the the meeting. That can easily run one to three thousand dollars (or more) depending mostly on how far you need to travel.

You can use grant money for these expenses. Some conference offer support to those who need it, particularly students. CS departments will often help out if needed. Sometimes people pay out of their own pockets and, in any case, the funds come from limited pots that could have been used for other purposes.

In the "old days" this was less of a problem. There were only one or two conferences relevant to one's field and you were probably going to those conferences anyway. Now as the field has grown and it has been harder to get your papers published in the strongest conferences, you may find yourself traveling just to give the talk. Even many major conferences don't draw many attendees who don't have papers in the conference.

We haven't seen an outcry of these expenses, say compared to the outcry over the cost of digital library subscriptions. Perhaps we consider attending the conference a "reward" for getting published.

We could just eliminate the conferences and publish the proceedings and post videos of talks, made at the home institutions, saving the field huge amounts of money. Then we could actually choose to attend conferences to meet people in our field instead of just talking at them.

Note: Elchanan Mossel had a similar observation in a comment on a recent post.

Is it well known that we need to redefine well known?

A LONG time (so long ago I was a guest poster, not a co-blogger)
I posted
about how calling things that are on You-Tube rare is odd
since ITS ON YOU-TUBE! ANYONE in the world can look at it!
I now have a Contrasting thought: Can something be
well known if its not easily found on the web?

Last week I
posted
a proof that the intersection of a CFL and a REG lang
is CFL that did not use PDA's. I thought it was NOT new and indeed, the
comments politely gave me the proper reference.
So far, so good. But wait--- some of them called the proof Well Known.
Can a proof be well known if its not on the web?
The notion of a proof being well known has always been problematic
since one wonders what the scope is.

1. Addition
   being commutative is well known but might not
   to my 5-year old niece.
   Someone emailed me that I should take this opp to teach her
   about noncommutative algebras.
   
2. Binary search is well known but might not be known to my (then)
   8 year old great nephew.
   Some said I should use this opp to teach him logarithms.
   
3. Induction is a well known technique but it still puzzles some undergraduates.i
4. The poly vdw theorem
   is well known among mathematically inclined
   high school students in Maryland but
   is not even that well known among combinatorists.
   

The point really is well known to who?. But now with the web we can ask a more focused question: Can you find it easily? The proof I posted was not one that I found on the web. So here is what I want your thoughts on:

1. Should we redefine our definition of
   
2. If I were to make an article out of the three short notes on CFL's
   that I posted about, and submit to Math Archives,
   would that help the problem of what is easy to find
   or would it just clutter up Math Archives making things hard to find.
   (I would of course provide all references and make NO claim to
   originality.)
   
3. Should I post to Wikipedia?
   
4. Will the web ever replace
   asking someone who knows stuff?
   

Microsoft saves the Yahoo NY Researchers

I started working with David Pennock on prediction markets back when we both were at the NEC Research Institute in New Jersey a decade ago. After a major reorganization the dropped basic research from their mission, I went back to academics but David stayed in industry research first at Overture which soon was swallowed up by Yahoo. He ended up at Yahoo Research New York in a small but amazingly strong research lab including machine learning theorist John Langford and social scientist Duncan Watts. But with a new Yahoo CEO and Prabhakar Raghavan and Andrei Broder's departures for Google, it  became clear that the days of Yahoo research were numbered. 

Today Microsoft announced that they are hiring 13 researchers from the Yahoo lab including David, John and Duncan as they start a new Microsoft Research Lab in New York, initially led by Microsoft New England director Jennifer Chayes. Lots of nice coverage from the New York Times, All Things D,  blog posts from Jennifer and John, and a pictorial take from Chris Maase. Not the first time Microsoft has done something like this, Microsoft Research Silicon Valley got its start by hiring several researchers from the old Xerox PARC.

I'm happy the Yahoo researchers found a great home but I also mourn the loss of yet another company abandoning basic research in computer science.

Berkeley Wins the Simons

As reported today in the New York Times, the Simons Foundation has chosen U. C. Berkeley to host the new Simons Institute for the Theory of Computing, a $6,000,000/year center for studying core theoretical computer science and its applications to other disciplines. There will be 70 researchers (faculty, postdocs, grad students) at any given time affiliated with the Institute.

This will be a game changer for CS theory.