Instance Compression

Some announcements: FOCS Accepts, ITCS Call and ToC Special Issue for Rajeev Motwani

I'd like to highlight one of the new FOCS papers "New Limits to Classical and Quantum Instance Compression" by MIT student Andrew Drucker which solves a problem that has dogged me for a few years. Ignore the "Quantum" in the title, that's not the interesting part.

Consider the OR-SAT problem, given m formulas each of size n, is at least one of them satisfiable. In STOC 2008, Rahul Santhanam and I showed that if there is a reduction from OR-SAT to any language L with the property that the reduction reduces to instances of size polynomial in n (independent of m) then the polynomial-time hierarchy collapses. The question arose from parameterized complexity though it also has some applications to cryptography and PCPs.

Our techniques failed to get a similar result for AND-SAT, where we want to know if all of the formulas are satisfiable. Drucker settled the question, showing that a compression of AND-SAT (reducing to instances of size polynomial in n) also gives a similar collapse of the hierarchy. What impressed me the most was the ingenuity Drucker uses in his proof.

Drucker derives the following lemma about probability distributions based on a strong version of Fano's inequality. Let A be a set of strings, D a distribution over A and f any function that maps A^m to {0,1}^m-2. If you pick a y from D, with high probability there is an index i, such that the distributions f(D^m) and f(D^m) with the ith location replaced by y are statistically close.

Drucker combines this lemma with a minimax argument and a result of Sahai and Vadhan that characterizes Statistical Zero-Knowledge as determining whether two distributions are different from the circuits that generate them.

Sometimes people solve your open questions with a simple argument that makes you hit your head for not thinking of it yourself. Other times you just sit back amazed at the solution knowing there was no hope for you to find it. Drucker's paper definitely falls in that second category.

Transitions

On July 1 I officially move jobs from Northwestern to Georgia Tech, a change not just in location but in role as I become a department chair.

I'm proud by what we put together in my 4 1/2 years at Northwestern, a strong group at the intersection of CS and Economic theory with Jason Hartline, Nicole Immorlica and great connections with the economists at Kellogg, the Northwestern business school.


So why leave? I've been thinking about taking on a more leadership role at this point in my academic career and when Georgia Tech came calling it was impossible to turn it down. But all moves are bittersweet and I'll truly miss the atmosphere we put together at Northwestern.


Also in the CS community, on July 1 I pass the mantle of SIGACT chair to Paul Beame. In exchange I'm joining the CRA board on that date.

This is a week of many conferences, ICML in Edinburgh, LICS in Croatia, Women in Theory in Princeton and the blog's namesake Computational Complexity in Porto. Having attended the first 26 meetings of the Complexity conference I miss it for the first time. Bill is there and hopefully he'll come back with a full report.

Eric Allender remains the only person to have attended every Complexity conference. "I'll continue to go as long as they are fun", he remarked last week. May he have reason to go for many more years.

Which brings me to the saddest transition of them all. Manfred Kudlek, retired professor at Hamburg, passed away on the bus for the excursion to Betchley Park last Monday during the Computability in Europe conference. Manfred is well known as the only person to have attended all 38 ICALP conferences, the Warwick meeting next month will seem empty without him.

Alan Turing (1912-1954)

Today we celebrate the 100th anniversary of the birth of Alan Turing, remembering his incredible life and mourning his tragic death. Alan Turing simply asked how does a mathematician solve problems. He developed such a simple model, now called the Turing machine, that so perfectly captures computation and years later would be the right model to capture computational complexity.

Alan Turing did so much more, codebreaker, computer builder and developer of his test of intelligence, that he so richly deserves the title "father of computer science". But it is the Turing machine that gives us the right notion of computation, both formal and intuitive and the foundation for a whole new research field.

A week ago ACM honored Turing by bringing together 32 recipients of the Turing Award, the highest honor in computer science. An incredible retrospective on Turing's influence on computer science from those who best followed in Turing's footsteps. You can celebrate the day by watching the webcast. I recommend the panel sessions on the Turing Computation Model and the Algorithmic View of the Universe. Just seeing these great theorists on stage together is a treat.

Today I have to privilege to celebrate Turing's legacy in Cambridge, England, where the Computability in Europe conference ends its meeting at King's College of Cambridge University. Turing was an undergraduate at King's College when he developed the computational model and wrote his truly classic paper. Everyone should read Chapter 9 where Turing gives an amazing argument why his model captures computation.

Thank you Alan. The world computes because of you.

The Ketchup Problem

MIT scientists are working on a bottle of ketchup where you CAN get out every last drop.  See here for details and some nice videos of the new bottle in action. This will be used on other products (like Mayonnaise) and will save much thrown away food every year! However, IF this had been around 45 years ago, then I might never have gone into Math!!! Why is that?

When I was 8 years old I had the following thought:

When ketchup is at the end of the bottle it drips very slowly.  It never stops dripping hence the number of drops is infinite.  Could I put an empty bottle of ketchup below it and catch all of those drops and hence never run out of ketchup?

When I was in college I came up with the following explanations:

1. NO: By the same reasoning there will never be an empty bottle of ketchup!
2. NO: Each drop is half the size of the previous one so even though this is an infinite series it converges.
3. NO: The time between drops doubles so it would take infinite time to fill up another bottle.

To this day I will NOT give up my conviction that the number of drops is infinite.  This ketchup problem may be the first time I saw a real world phenomena and made a math problem out of it. I blogged about other such problems here and here.
The ketchup problem so intrigued me that I became a math major. OR the fact that I thought of this problem indicates that I liked math and hence went into it. I would say its a chicken-and-egg thing but we need a new metaphor since
the chicken came first.

Other questions I thought of as a kid:

1. Why do people smoke tobacco if its so well known that its bad for them?  This one still puzzles me.
2. If, as the TV ads indicate, people want Margarine that tastes JUST LIKE BUTTER then why not just get butter? I NOW know that Margarine was cheaper back then (still is).
3. If, as the TV ads indicate, people want instant coffee that tastes JUST LIKE GROUND ROAST, why not just get ground roast? I had no idea what any of those terms meant as a kid. Why I cared is a mystery since I didn't drink coffee as an 8 year old (and I still don't).  I now deal with math terms i don't understand. Why I care is a mystery.
4. How is eating everything on my plate going to help the kids that are starving in Africa? Mom never quite answered that one.
5. How come whenever I see six kids playing together there are always either three that get along or three that don't get along?

Had I pursued the first three questions I would either be in sociology or advertising. Had I pursued the fourth question I might be in economics or politics. I have no idea what pursuing the fifth question would have lead to. Child Psychology? Party planning?

READERS- do you recall a math problem that you cared about as a kid that likely either inspired you to do math or indicated that you were interested in math? Note that you don't need to have SOLVED the problem as a kid- I am interested in your interests,
not your ability (note that I didn't any of my problem as a kid).

Name My Book

As many of you know I have been working on a non-technical popular science book on the P versus NP for a general audience. The book is mostly finished but the biggest challenge is finding a good title.

The current working title is

The Golden Ticket: P, NP and the Search for the Impossible

The “Golden Ticket” refers to beginning of the Roald Dahl book Charlie and the Chocolate Factory (and the two movies based on the book) where everyone is searching for a golden ticket to get a factory tour. But the publisher is worried that people will not understand the reference until they read the book.

Here are other possible titles some from me and many from the publisher.

• P vs NP: The Search for the Impossible
• Finding the Needle: P, NP and the Search for the Impossible
• The Road to Nerdvana: P, NP and the Search for the Impossible
• The Second Most Famous Equation: P=NP and the Search for the Impossible (the first being E = mc²)
• Can We Solve It? : P, NP and the Search for the Impossible
• The Ultimate Math Problem: P, NP and the Search for the Impossible
• How to Solve Everything and Why It's a Bad Idea: P, NP and the Search for the Impossible
• The Most Important Equation You Never Heard Of: P=NP and the Search for the Impossible
• The Answer to Everything
• Impossible Math: The search for the solution of P, NP
• One equation to rule them all: P, NP and the Search for the Impossible 
• One Way Math: P, NP, and the Search for the Impossible
• The Ultimate Puzzle: P,NP and the Search for the Answer to Everything
• The Golden Ticket: The Impossible Equation that Could Solve All Problems
• The Answer to Everything: The Ultimate Unsolvable Equation
• The Golden Ticket: The Ultimate Unsolvable Equation that Could Be The Answer to Everything 

Honestly I'm not loving (or hating) most of them. We decided to ask my readers, many of you are in the target audience for the book. Any of the titles above that you truly love (or hate)? Or do you have another suggestion? If we use your title, a free signed copy of the book will be yours.

Do 50-1 longshots in the Kentucky Derby ever come in?

(I delayed posting this until after The Belmont Stakes since I wanted to see if there would be a Triple Crown winner.
Alas, I'll have another was scratched. From what I've heard it was the right decision.)

Watching the Kentucky Derby my wife asked Do  50-1 shots every win? Since the Derby has been run 138 times it is likely that a 50-1 shot came in at least once.  That is, of course, if the odds were correctly figured.  Were they?

Essentially yes.  For the  ten longest longshots to win the derby I call a horse UNDERVALUED if they showed (came in 1st or 2nd or 3rd) in at least one of the other legs of the Triple Crown, and FLUKE if not. If there are other reason to say FLUKE I do so. Sometimes I say DON"T KNOW.

1. Donerail won in 1913 and was 91-1. (The longest long shot to win.) The prob that a 91-1 shot would NEVER come in after 138 races is (1 - 1/91)¹³⁸ which is roughly 0.217647740202952.  So while this is possible, it's more likely that such a long shot would come in. I could not find information on if Donerail ran in the Preakness or the Belmont Stakes.  Even though I don't know I'll say FLUKE with odds that long.
2. Mine that Bird won in 2009 and was 50.6-1 The prob that a 50.6-1 shot would NEVER come in after 138 races is (1 - 1/50.6)¹³⁸ which is roughly .0636355836570341.  Extremely unlikely, hence not at all surprising that such a horse won at some point, though surprising when it happens.  He finished second in the Preakness and third in the Belmont Stakes. UNDERVALUED!
3. Giacomo won in 2005 and was 50.3-1. Two horses that were roughly 50-1 have won the Derby.  I leave it to the reader to calculate the prob that only one 50-1 horse wins. I suspect that it is quite low, so having two of them win is reasonable.  He finished third in the Preakness and seventh in the Belmont Stakes. UNDERVALUED. I recall at the time thinking that betting he would show in the Belmont Stakes would be a sure thing. Alas, there is no such thing as a sure thing.
4. Gallahadion won in 1940 and was 35.2-1 (The website mislabels the picture as being from 2005 and misspelled the horses name by leaving out the a after the ll. What are the odds of that?) He finished third in the Preakness and did not show in the Belmont Stakes.  UNDERVALUED.
5. Charismatic won in 1999 and was 31.3-1.  He won the Preakness and came in third in the Belmont Stakes. UNDERVALUED!
6. Proud Clarion won in 1967 and was 30-1.  He finished third in the Preakness and Fourth in the Belmont Stakes. UNDERVALUED.
7. Exterminator won in 1918 and was 29.6-1.  Wikipedia has nothing on the Preakness or Belmont Stakes, so I assume he didn't run them. DON"T KNOW
8. Dark Star won in 1953 and was 24.9-1. A better name would have been Dark Horse. Was fifth in the Preakness possibly because he got injured running it, and that injury ended his career. DON"T KNOW.
9. Thunder Gulch won in 1995 and was 24.5-1. He came in third in the Preakness and won the Belmont Stakes. UNDERVALUED!
10. Stone Street won in 1908 and was 23.7-1.  Wikipedia does not have anything about his performance in the Preakness or the Belmont Stakes so I assume he didn't run in them. Wikipedia DOES report that his time, 2:15 1/5 is the slowest winner ever of the Derby. Based just on this I say FLUKE.
11. Animal Kingdom won in 2011 and was 20-1. He finished second in the Preakness and didn't show  in the Belmont Stakes (I could not find how well he did).  UNDERVALUED

Some comments:

1. To answer my wife's question- in 138 Derbies a 50-1 or better shot came in 3 times, which I think is about right, or at least not surprising. So they DO win.  Sometimes.
2. I was surprised that 5 of the 10 longest longshots were since 1999.  I would think people know more about racing now and so a real long shot is less likely. That may be the wrong way to think about it.
3. Should you bet on longshots? If you always bet x on the longest longshots in the Kentucky Derby, and (I have not checked this) The first, second, and third on the list above were the longest longshots when they ran, you would have roughly 190x - 135x = 55x dollars.
4. How do you tell if a long shots is undervalued (the odds should have been better) or a fluke (the odds were correct but something weird happened)? Here are three ways: (1) See how they did in the other two legs of the Triple Crown, (2) See their runtime in the Derby, or (3) for each race see if there were odd odd circumstances. For example, sometimes, it all depends if it rained last night.
5. By my measure there were six undervalued, two flukes, and two don't knows. I don't know if this means my measure is wrong.
6. Actually I'm GLAD that long shots sometimes come in. If not then they are being overvalued.  This is similar to why David Pennock wrote Why we're happy we got one prediction wrong on Super Tuesday. I saw his talk the same week as the Derby, and both jointly inspired this post. What are the odds of that?
7. I asked Dave Pennock about these issues and got two interesting thoughts from him:
   
   
   
   1. There is evidence racetrack odds are just about right (efficient) except with a slight "favorite-longshot bias" where favorites win a little too often and longshots not quite enough (people bet a little more than they should on longshots).
   2. It is an interesting hypothesis that odds should be less long with more information. I'm not sure that's true. With more information, the entropy of the distribution should go down, which intuitively might lead to longer long shots (and surer sure things)?
8. Dave also told me that there has been A LOT of work on this.  Here are some references:
   
   
   
   1. There is a whole edited volume on the subject: Efficiency of Racetrack Betting Markets
   2. Horse racing Testing the efficient markets model by Wayne W. Snyder.  J. of Finance, V. 33, No. 4, 1978.  pp. 1109--1118.
   3. Probability and utility estimates for racetrack bettors by Mukhtar M. Ali. J. of Political Economy, V. 85, No. 4, 1977, pp. 803--816.
   4. Utility analysis and group behavior: An empirical study by Martin Weitzman.  J. of Political Economy, V. 73, No. 1, 1865, pp. 18--26.
   5. Anomalies: Parimutuel betting markets: Racetracks and lotteries by Richard H. Thaler and William T. Ziemba.  J. of Economic Perspectives, V. 2, No 2, 1988, pp. 161--174.
   6. Gambling and rationality by Richard N. Rosett.  J. of Political Economy, V. 73 No. 6 pp. 595-607, 1965.
   7. Informed traders and price variations in the betting market for professional basketball games by John M. Gandar, William H. Dare, Craig R. Brown, and Richard A. Zuber.
   8. Information incorporation in online in-game sports betting markets by Sandip Debnath, David M. Pennock, Steve Lawrence, Eric J. Glover, and Lee Giles.  Proceedings of the Fourth Annual ACM Conference on Electronic Commerce, pages 258-259, 2003.
   9. How accurate do markets predict the outcome of an event? the Euro 2000 soccer championships experiment by Carsten Schmidt and Axel Werwatz.  Technical Report 09-2002, Max Planck Institute for Research into Economic Systems, 2002.
   10. Here are some fun books on the subject: Sharp Sports Betting by Wong and Calculates Bets by Skiena. I reviewed Skiena's book in my SIGACT NEWS book review column here.
   
   

Fortnoy's Complaint

During my daughter's 8th grade graduation last week, the teacher reading the names said "Molly Fortnoy...I mean Fortnow". I felt for Molly. When my name was first mentioned in a conference talk back in 1986 the speaker also said "Fortnoy". For the record my name is pronounced as it is spelled, like "He's going to the fort now".

I've been called Fortnoy many times from people in my generation or older. I put the blame on Philip Roth's book Portnoy's Complaint.

My father's birth name was Paul Fortunow. The name has Russian roots, possibly connected to Fortunoff. The 'u' in Fortunow is silent. Go ahead and try and pronounce Fortunow. You forgot the "u" was silent. So a couple of years before I was born (and before Portnoy's Complaint) my father changed his last name to Fortnow.

Foreigners usually have no trouble pronouncing my name. But once when I was checking in at the Frankfurt airport, the agents said something like "Here are your tickets Mr. Fornow". I said "Thanks but that's Fortnow". She responded  "If it was pronounced Fortnow there would be a 'u' after the 't'". I should have asked her where she was from. 

A new bound on 3-hypergraph Ramsey Number! Why wasn't it discovered earlier?

When a new result is first discovered one question to ask is Why wasn't it discovered earlier? We look at a result in Ramsey Theory from 2010 and speculate as to why it was not discovered earlier.

Let R(k) be the least n such that no matter how you 2-color the edges of the complete 3-hypergraph on R(k) vertices there will be a homogenous set of size k (that is, a set H of size k such that all 3-sets from H are the same color). R(k) is known to exist by Ramsey's theorem.

1. Ramsey's original proof (in 1930) gave astronomical tower-like bounds on R(k).
   
2. Erdos-Rado (1954) showed that R(k) is bounded by 2^24k.
   
3. Conlon-Fox-Sudakov (2010) showed that R(k) is bounded by 2^22k. (They did a lot more in their paper- they looked at asymmetric 3-Hypergraph Ramsey Numbers and developed a new framework for them.) See Hypergraph Ramsey Numbers on that page.)
   

Why are these results important?

1. An improvement on the 3-hypergraph Ramsey numbers automatically gives an improvement in the a-hypergraph Ramsey numbers for any a ≥ 3.
   
2. There is an exponential gap between the upper and lower bounds of R(k) and all of the a-hypergraph Ramsey numbers. Hence any improvement may be a key to closing that gap.
   

I have (with Andy Parrish and Sandow Sanai) celebrated the result of CFS with a survey of bounds on the 3-hypergraph Ramsey Numbers here. Proofs and intuitions and historical context of the results enumerated above are in our survey. (If you read it and have corrections please email them to us- we plan to put it on arXiv next week.) The techniques in this paper did not depend on any mathematics unknown to Erdos or Rado (or others) in 1954. (This is in contrast to, say, Conlon's paper A New Upper Bound on Diagonal Ramsey Numbers which uses quasi random graphs- a technique and technology unknown in 1954.) So why didn't someone else prove the result earlier? Our speculations may apply to other results that are proven with techniques that were already known.

1. The CFS paper develops a framework for upper bounds on asymmetric 3-Hypergraph Ramsey numbers that involving a game (not a FUN game, but a game). This framework is used to prove many things. If all you want is the bound on R(k) then you don't need the framework and you get a proof that, IN HINDSIGHT, gives you the bound in a way that Erdos-Rado could have done. That's alot of HINDSIGHT. (Our Survey gives the stripped down proof of just that result, without their game framework.)
   
2. Not that many people worked on it. Hence that individual people didn't get it is not surprising. Perhaps Erdos-Rado was happy enough to get the bound from tower to merely 2^24k. More generally--- if an entire community is looking at a problem then the question Why wasn't it found earlier? may have a global answer. If its just a few people, it could just be local things like After working on this problem she switched to Computable Algebraic Topology.
   
3. CFS are very very clever. This is another HINDSIGHT argument- AFTER its done it looks easy.
   

Other reasons that might apply in other cases, though not to the case at hand:

1. Timing and Luck should not be underestimated. A paraphrase from The Honors Class: Hilbert's Problems and their Solvers, the chapter on Hilbert's 10th problem, page 112:
   

   All of these people, Robinson, Davis, Putnam, others had been reading Number Theory books full of obscure facts. Matiyasevich had just read the third edition of Nikolia Vorob'ev's ``popular book'' Fibonacci Numbers. In that book, published in 1969, there was a new result about the divisibility of Fibonacci numbers. Matiyasevich used it to prove If F(n)² divides F(m) then F(n)divides m. This allowed him to solve Hilbert's 10th problem (building on work of Davis-Putnam-Robinson). Robinson had read that book, but not the third edition!

   With the web is this more or less likely to happen? I ask nonrhetorically. (The spelling I give for Matiyasevich is the one given in the book. I have seen different spellings.)
   
2. Everyone thought the negation was true. This was one reason why NL=coNL was proven as late as it was.
   
3. The problem itself wasn't looked at earlier. Some of the Time-Space tradeoffs for SAT may be in this category.
   
4. A groupthink sets in and people are all thinking the same way. Laszlo Babai noted this concern in his 1990 article Email and the unexpected power of interaction where he writes:
   

   But will the diversity of thought that now exists be preserved in an era when intellectual fashions are dictated by the strongest? Shall we see more Levins and Razborovs come out of the Kolmogorov school, bringing in so prominently different, yet profoundly relevant ideas?

   He was referring to email, but the tendency of groupthink may be even more of a tendency with the web. (Levins and Razborovs, not Levin's and Razborov's, is how it appears in the original article.)
   

SO, READERS- your turn! Leave comments on results that, once proven, the question arose Why wasn't this proven earlier? and speculate as to why. You need not write a survey of the area.

Mihai Pătraşcu (1982-2012)

Update: Visit the Memorial Website

Mihai Pătraşcu passed away Tuesday after a bout with brain cancer. Even though he hadn't reached his 30th birthday, he had already produced a number of major achievements in the algorithmic community. The theoretical computer science community lost one of its brightest young stars.

During STOC, Yevgeniy Dodis arranged to have Mihai at the business meeting while we announced him as a co-winner of the EAPresburger award which Mihai will receive posthumously at ICALP next month. The standing ovation that followed made for the most emotional moment I have ever seen at an academic conference.

We asked Mohammad Taghi Hajiaghayi to write some personal thoughts on Mihai:

Last night I heard the very sad news that Mihai Pătraşcu has passed away at the age of 29. Though I knew about his cancer from 1.5 years ago and several steps that he took to fight the cancer still the news was quite shocking to me. Mihai's carreer was short but very productive with his lots of great papers in e.g., STOC, FOCS, and SODA.


Indeed Mihai is the second close friend of mine and a bright star researcher from my MIT times that I missed in the recent years (the first one was Misha Alekhnovich who died in 2006 in a white-water kayaking accident in Russia).


I became familiar with Mihai since 2002 when he joined MIT. He was interested in working on date structure with Erik Demaine who was my Ph.D. advisor as well. As a result, I got know him much better esp. since both of us had common experiences in IOI (International Olympiad in Informatics). One of Mihai's early ground-breaking papers is

Erik D. Demaine, Dion Harmon, John Iacono, Mihai Patrascu: Dynamic Optimality - Almost. FOCS 2004: 484-490

In this paper, an O(lg lg n)-competitive online binary search tree is given which improves upon the best previous competitive ratio of O(lg n). This was the first major progress on Sleator and Tarjans dynamic optimality conjecture of 1985 that O(1)-competitive binary search trees exist. Indeed Mihai could formulate the O(1)-competitive conjecture as an approximation factor of some algorithm and we worked together for some time to prove the conjecture (that so far we could not:)). This was my first research experience with Mihai. Since then we always have talked about research (but we never had a joint paper).


In general Mihai and I were close friends and talked about all things. For example some times the people asked me about Mihai's personality especially because of some posts in his blog that were a bit controversial. I always told them Mihai is a very nice guy to work or chat with and those posts are indeed some concerns that everyone has in this mind, but Mihai is just brave enough to mention them loudly in his blog for the hope of some changes in the way that our community think (and anyone else including myself may agree or disagree with them).


After Mihai's graduation with Ph.D. from MIT which was only for 2 years (the same was true for Misha Alekhnovich), he applied for lots of places and got several very good offers. I was one of the people who encouraged him to join AT&T research labs, the place that I was there at that time. Finally Mihai decided to decline several faculty offers and join AT&T esp. to work with Mikkel Thorup (before joining AT&T he went as a Raviv Postdoctoral Fellow to IBM Almaden for one year). He has also chosen AT&T because of its place near to NYC that was good for his wife's career. As a result since July 2009, I was very happy to have Mihai, a star researcher, as my colleague at AT&T research labs and we talked more about everything during the past years. For example, later I wanted to teach hashing in my Introduction to Algorithms course at UMD; I asked Mihai and he gave me a very good overview about the field including an overview of his recent ground-breaking paper on simple tabulation hashing.


I first knew about Mihai's cancer in Feb 2011. At that time he was taking chemo before a brain surgery in March 2011. Just a day after the surgery he sent an email to David Johnson from the hospital that he already recovered and started thinking about his research problems. After this surgery, doctors, Mihai, and all of us at AT&T were very hopeful that the bad days for Mihai have been passed and Mihai will recover fully and produce lots of papers again:). Indeed everything was fine since then and Mihai even applied for faculty positions in Fall 2011 (he always considered his AT&T (industry) position as a long-term post-doc position). He asked for my opinion about his research statement and I was happy to give him some comments (esp. since I was also a person who first took the path of the industry and then academia). Again everything was fine until mid Jan 2012 that Mihai understood the cancer is back. Unfortunately this time the cancer was very strong and in a week or two he went to a wheelchair from a completely healthy position. I saw him several times at AT&T recently (when I visited there) and I always was very sad to see him on a wheelchair. To my mind, the best good news for Mihai since January 2012 was the fact that Mihai was selected as a co-winner of the 2012 EATCS Presburger Young Scientist Award for his ground-breaking work on data structure lower-bounds. He was very happy about it as he posted in his blog about it as well.


At the end I pray that Mihai's soul rests in peace and the research area of data structure lower-bounds in which he had several ground-breaking works becomes more prosperous due to his work.

Which Books to Keep?

Moving is an excuse to go through your possessions and weed out what you don't need anymore. Over my professional life I've collected two large bookcases full of CS, Math and Econ books and all the STOC, FOCS and Complexity proceedings from 1986 until they stopped publishing proceedings a couple of years ago. I also have a surprisingly large collection of complexity Ph.D. theses.

What do I move and what do I toss or give away? All the proceedings are now on-line. Maybe keep STOC 1987, my first conference paper? How many different editions of Li and Vitanyi's Kolmogorov tome do I need? How many Introduction to Theory textbooks? Publishers send them to me since it is the one undergraduate class I have consistently taught. I use Sipser, partly because he was my Ph.D. advisor, but mostly because it's a great book.

One approach is to toss everything. As some of my students say, if it's not on the web it can't be of much value. But I can't imagine life without some of the classics. When I want to prove something NP-complete, I still start by finding the closest related problem in Garey & Johnson to reduce from. For that one needs to skim through their list of problems. I have yet to see a good way to skim electronically.

I'm not a luddite. I do all my pleasure reading on the Kindle and read and mark up PDFs on my iPad. But when it comes to math books, we still haven't found a good replacement for paper. 

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?