A natural function with very odd properties

Last time I posted some questions. Today I post the answer that I know.

1. Is there a subset of [0,1] that is uncountable and has measure 0?  YES- take the Cantor Set.  Many readers knew this.
2. Is there such a set that is natural? Some comments thought the Cantor Set was natural. I disagree, however
   this is a matter of opinion and taste.
3. Is there a function that is continuous everywhere and differential nowhere?  YES- take the Weierstrass Function.  Many readers knew this.
4. Is there such a function that is natural? Some think the Weierstrass Function is natural. I disagree because it was constructed for the sole reason to be continuous everywhere and differential nowhere.  But again, there are those who think it is natural and this is a matter of opinion.
5. Is there a function that has derivative 0 at almost every points of [0,1] even though it is strictly increasing?
   YES- take Cantor Functions,
   also known as the Devil's staircase. Some readers knew this.
6. Is there a natural such function? YES- and this was the motivation for the post. (I also didn't want to have the example I read about mentioned in the comments of the last post which is why I wanted all posts to be non-anonymous- so if I blocked one I could email the author WHY I blocked it.)

The function I will talk about came about because of a real problem having nothing to do with finding weird functions. Hence I think it is unambiguously natural.

I base my exposition on the exposition in
How to Gamble if you Must
by Kyle Siegrist. The original source is from the classic book Inequalities for Stochastic Processes: How to Gamble
if you must by Dubbins and Savage. Classic or not, unless that book is free online the future
will credit Siegrist with the result (even though Siegrist references Dubbins and Savage.)


Consider the following game: Let 0 < p < 0.5.
Let 0 ≤ x ≤ 1. We will view p as a probability and x as how
much money you start with.
You place a bet (which has to be ≤ what you have).
A coin is flipped with prob of WIN being p and of LOSS being 1-p.
If you win you double your bet. If you lose you lose your bet.
You repeat until you have 0 or you have 1.

You could play TIMIDLY: bet a fixed small amount every time.
This is analyzed. In the paper and is interesting.


You could play BOLDLY: if you have < 1/2 then bet all you have,
and if you have ≥ 1/2 then bet so that if you win you'll have 1
and can stop.


If you play BOLDLY then
what is the probability that you will end with 1?
We will fix p and let F(x) be the prob if you begin with x.
(We assume 0 ≤ x ≤ 1.)
F satisfies the following recurrence:

F(x) = pF(2x) if x ∈ [0,0.5]

F(x) = p + (1-p)F(2x-1) if x  ∈ [0.5,1].

F(0)=0, F(1)=1

This is enough to define F on all rationals between 0 and 1 (use the expansion in base 2).
Then use continuity to define F on all the rationals between 0 and 1.

The paper claims that F has derivative 0 at almost every point of [0,1]
even though its strictly increasing.
I leave this for the readers (translation into English: I don't know the proof).
However, I emailed the author who emailed me the following:

There are proofs in the book Probability and Measure by Patrick
Billingsley. In the third edition, it's Example 31.1 on page 407.  The fact
that F is continuous and strictly increasing on [0, 1] is fairly easy to
see, based on the definition of the underlying random variable.  The fact
that F has derivative 0 is not as easy to see intuitively--the proof is
more of a hard analysis type proof.

The paper assumes that money is continuous and out lives are indefinitely long.
Ekhad, Georgiadis, Zeilberger have written a paper
How to Gamble if you're in a Hurry
that looks at these problems from (to quote their abstract) a purely discrete, finistic, and computational viewpoint.

Six Questions about unnatrual and natural mathematical objects

Today (Monday) I pose some questions. In my next post (Tuesday) I will post the answers
that I know (some I do not). Some questions are a matter of opinion
in terms of what you consider natural.

1. Is there a subset of [0,1] that is uncountable and has measure 0?
2. Is there such a set that is natural?
3. Is there a function that is continuous everywhere and differential nowhere?
4. Is there such a function that is natural?
5. Is there a function that has derivative 0 at almost every points of [0,1] even though it is strictly increasing?
6. Is there a natural such function?

I request that all comments be NON-anonymous.  (I'll tell you why when I post the answers I know on Tuesday.)

The Combinatorics of Batman

(I wrote this post about a year ago but waited until the new Batman
movie came out to post it. I haven't seen the movie yet so
there may more possibilities to add to this.)

There have been many versions of the BATMAN story:
comic books (and within that there are several versions),
many movies, and a TV series.
This may lead to a COMBINATORICS question you can ask your class.

So how many ways can the BATMAN story go?
This is NOT A QUIZ- all of the answers are correct
for some version of BATMAN.

1) As a child Bruce Wayne saw his parents gunned down.  What were they doing before this happened?

 a) Watching the movie Zorro.
 b) Watching the movie The Lone Ranger.
 c) )Watching an Opera.

2) Who shot Bruce Wayne's parents?

 a) Joe Chill- a low level mugger.
 b) Joe Chill- hired by the mob since Thomas Wayne (Bruce Wayne's father) had once foiled a crime. The orders were to leave the boy alive so it would look like a low level mugging.
 c) The gangster who would later become the Joker.

3) Who was the Joker before he became the Joker?

 a) A completely innocent chemist-turned-comedian.  He was a good man but a bad comedian. He was just going to do one theft to make ends meet. Things went wrong and he fell into a batch of chemicals and became The Joker.  He is now a bad man but a good comedian.
 b) A gangster who was sleeping with his bosses girlfriend.  The boss arranged for him to be killed ,but nstead the gangster falls into a batch of chemicals and becomes The Joker.
 c) Hey, its just makeup. But he has scars which may have come from his father, himself, or who knows?
 d) There are surely other versions I do not know.  One could probably write a bad PhD on this topic.

NOTE: I don't think the Jokers name is known in any of the versions.
(Contrast: The Riddler's name is Edward Nigma.)

4) Where is the Joker now?

 a) In Arkam Asylum.
 b) Dead.
 c) Gee, he really seemed to die but we just know he'll turn up again.

5) Who is Two-face?

 a) Harvey Dent, the DA, who was a good man. During a court trial a criminal throws  acid on his face. Now half of his face is scared. This drove him insane and he is now a criminal.
 b) Harvey Dent, the DA, who was a good man. Dent and his girlfriend Rachel Dawes are kidnapped.Batman and Commissioner Gordan save him but (1) Rachel dies, and (2) Dent has his face half disfigured.This drives him mad.
 c) There are about 5 other people who took on this role. One of them was named Harvey Kent.   No relation to Clark Kent

6) Who else lives in Wayne Manor?

 a) Robin, Alfred the Butler, and Aunt Hariet.
 b) Robin and Alfred the Butler.
 c) Just Alfred the Butler.

7) How well do Batman and Superman get along?

 a) Superman is never mentioned.
 b) They get along.
 c) They don't get along.
 d) They REALLY don't get along!


This leads to a combinatorics question and a Batman question.
COMBINATORICS: Assuming that all of these options are independent, how many versions of the
Batman Legend could there be? This should be easy.
BATMAN: Of all of these, how many have actually been realized?
This might take a Batman scholar to figure out.
And I haven't even talked about Robin (nor will I).

There are also variants of the COMBINATORICS question if you disallow certain
combinations. For example, If Aunt Hariet exists then Superman does not.

I'm sure there are more options I don't know about.
If you know any, comment!

CCC12- post 4 of 4- Misc Info.

CCC 12 post 4 of 4.
The business meeting and other observations.

1. Programming committee info:
   
   1. There were 119 submissions of which 18 were junk (more on that later). This is pretty large- Paris 2009 had 113 submissions. The junk papers were not so much papers that claim they proved P=NP or P\ne NP; they were papers where it is hard to know what they are claiming. (Hmmm- there are valid papers that, after you go through all the definitions, its not clear what they are claiming.)
      
   2. 34 papers accepted. Second highest to Paris having 37. (In both Paris and this year there was no Rump Session- that could be why, no time for one.)
      
   3. Andrew Drucker won Best Student Paper award for Limitations of Lower-Bound Methods for the
      wire complexity of Boolean Operators.
      
   4. See Prog Comm Chair Slides for more information.
      
2. There were roughly 60 people at the conference. Here is a list of all attendance figures up through 2008 (if you know of the attendance in the later years let me know and I will add them).
   
3. Steering committee:
   
   1. Johan Hastad and Manindra Agrawal have been on the committee but their term has expired so they are now off of it.
      
   2. The steering committee put Madhu Sudan on.
      
   3. An election by people at the meeting put Venkat Guruswami on.
      
   4. Peter Bro Miltersen is stepping down as chair (his term expired) and Dieter is the new chair. Peter will stay on one more year (I think).
      
4. Future Conferences:
   
   1. 2013: the conference will be in Palo alto, ca, co-located with STOC June 1-4 STOC, June 4-7 CCC. I WILL BE THERE!
      
   2. 2014: the conference will be in Vancouver. Local arrangements chair Valentine Kabanets. There were no competing bids (are there ever?) I WILL BE THERE!
      
   3. 2015: Depends on if there is an FCRC and if we join it. In any case I WILL BE THERE! The Steering committee will decide these things later.
      
5. This year there were electronic proceedings (I think for the second time.) That's good, and I'm glad we don't have paper, but I would prefer if the proceedings were available on a public website before the conference (SODA has done that) or at least after (if it IS available and I missed that- leave an intelligent comment about it). On the other hand this might not matter much since most of the papers are available on line anyway.
   
6. My posts on the content of the conference didn't get many comments, nor did I think they would. I hope they were useful to you. Forcing myself to do it was very useful to me, and for that I thank you, the readers. (For abstracts of ALL of the papers without my opinions, see here and press on abstracts (not on the left column).
   
7. On my Honeymoon in 1991 I went on a cruise and we were cut off from ALL news. When we got back the first thing I heard was The crisis is over, the tanks are leaving Moscow. This was somewhat alarming. They were referring to the 1991 Soviet Coup d'etat attempt. By contrast, in 2012 in Portugal, I heard about the Supreme Court Decision on Health Care within an hour of when it happened. I missed the earlier incorrect accounts. Is it a good or bad that its harder to get away from news coverage? Lance posted on a related topic a while back
   
8. I was gone for a total of 20 days and did not check email once. (i had a vacation problem on.) I came home to 474 emails of which 20 needed to be responded to. None of them were crucial.
   

CCC 2012- Post 3 of probably 4

Post 3 of n on CCC 2012. I still don't know what n is.
I summarize the third and fourth day of the conference.
(The fourth day was only a half-day).

Thursday June 27 Morning Session:

1. Matrix Lie Algebra Isomorphism by Grochow. This paper was called (and the link above still uses the old name) Lie Algebra conjugacy. Some Isom problems for Lie Algebras are equivalent to Graph Isomorphism. In general Harder Math does not mean Harder Computationally.
   
2. On Sunflowers and Matrix Multiplication by Alon, Shpilka, Umans. Erdos-Rado made a conjectures about sunflowers. Coppersmith and Winograd made a conjecture in combinatorics which would, if true, yield a better Matrix Mult Alg. This paper shows (roughly) that if the ER-conj is true then the CW-conj is false. Neither conj sounds that intuitive to me so I don't know what to make of this.
   
3. Algebras of minimal multiplicative complexity by Blaser and Chokaev. I couldn't find a link- if you know one email it to me.
   
4. Invited Talk Prospects for Geometric Complexity Theory by Peter Burgisser. So what are the prospects? Mixed. I was happy to hear that there are people working on this, but the talk was not that optimistic.
   

Thursday June 27 Afternoon Session:

1. A Strong Direct Product Theorem for Quantum Query Complexity by Lee and Roland. Direct Product Conjectures say (roughly) that if a problem takes T blahs to do then doing k of them given to you all at once takes kT blahs to do. There are many of these depending on your interest. This paper shows shows something stronger: If you want to computer just the XOR of the k instances it will take roughly kT quantum queries. (That is not quite right- there are a lot of details I left out.)
   
2. A Strong Parallel Repetition Theorem for Projection Games on Expanders by Raz and Rosen. A parallel repetition theorem usually says that if the prob of (say) winning one game is p, then the prob of winning n games is pⁿ (That can't be quite right but that's the idea). The real question is how fast does the prob go down. This paper adds to our knowledge on this.
   
3. Share Conversion and Private Information Retrieval by Beimel, Ishai, Kushilevitz. I couldn't find an online version. If you know of one email the link please. The paper claims to unify and simplify PIR protocols!
   
4. Nondeterministic Circuit Lower Bounds from Mildly Derandomizing Arthur-Merlin Game by Aydinlioglu and van Melkebeek. There have been theorems along the lines of Lower bounds imply Derand. There have also been some (and this is one of them) along the lines of Derand implies Lower Bounds. As the author points out, when you first hear the result you may think one of two things: (1) GOOD NEWS- to get lower bounds, all I have to do is Derandomize! (2) BAD NEWS- to derandomize I HAVE to prove lower bounds, which are hard to prove. He claims a third interpretation of his paper- if you can derandomize then you can do so in a nice way
   
5. Hitting Set Generators for Sparse Polynomials over any Finite Fields by Lu. I could not find a link- if you know one email it to me.
   
6. Pseudorandom Generators for Read-Once ACC0 by Gavinsky, Lovett, and Srinivasan. Or see the talk on video from IAS.
   

Friday June 28 Morning Session

1. Non-Malleable Extractors with Short Seeds and Applications to Privacy Amplification by Cohen, Raz, and Segev. An extractor (informally) takes two strings and outputs a string that looks random. Strong Extractors and non-malleable extractors are stronger notions. Non-malleable extractors produce strings that look random, even to an adversary who is trying to make trouble. Hence they are good for Privacy Amplification. This paper has unconditional constructions of them!
   
2. Better Condensers and new extractors from Paravaresh-Vardy Codes by Ta-Shma and Umans I lose track of condensers vs extractors vs expanders vs dispersers.
   
3. List Decoding Barnes-Wall Lattices by Grigorescu and Peikert List decoding is when, instead of finding what a string decodes to, you find a small set of candidates, one of which is correct. What is a Barnes-Wall lattice? The paper does a good job on this. I wonder if the original paper by Barnes and Wall does as good a job?
   
4. Space-efficient algorithms for reachability in surface-embedded graph by Stolee and Vinodchandran. One of the consequences of there results is log-space algorithms for some graph-reachability problems. Maybe L=NL!
   
5. Space Complexity in Polynomial Calculus by Filmus, Lauria, Nordstrom , Thapen, Zewi. Proof complexity. While lower bounds on Resolution are well understood, what about more powerful proof systems? This paper is a good start on that.
   
6. Combinatorial PCPs with Short Proofs by Or Meir.
   I wish the PCP theorem itself had a short proof. Perhaps you can prove that it does.
   

CCC 2012: Post 2 of n

CC 2012. I still don't know what n is.
I summarize the second day of the conference.

Wednesday June 27 Morning Session:

1. A Satisfiable Algorithm and Average Case Hardness for Formulas over Full binary Basis
   by Seto and Tamaki.
   
2. Approximating AC
   by Beame, Impagliazzo, Srinivasan.
   
3. DNF Sparsification and Faster Deterministic Counting by Goplan, Meka, Reingold.
   

All three of the above papers solve a hard problem in slightly-better-than the usual worst case. All three of them (I think) want to use this to obtain lower bounds. (Recall that this is ultimately how Ryan got his lower bound- via an algorithm. I want to see a SODA paper that gets an algorithm via a lower bound.) Something bothers me about this. If we are getting algorithms that beat (albeit, just barely) brute force search, perhaps we should be yelling MAYBE P = NP instead of LETS USE THIS TO SHOW THAT P ≠ NP. Just a thought.

1. Invited talk Communication Complexity and Information Cost: Foundation and New Directions by Toniann Pitassi.
   This was an excellent talk. I didn't realize it was an hour long invited survey talk instead of a 20 minute long normal talk.
   I kept waiting for
   (a) her results, and (b) the talk to end, even though I was enjoying it.
   ADDED LATER: Toni emailed me her slides.
   They are
   here
   

Wednesday June 27 Afternoon Session:

1. Gaussian Noise Sensitivity and Fourier Tails by Kindler and O'Donnel. They first define a new kind of sensitivity Rotation Sensitivity They then show that this type of sensitivity is subadditive. This is used to obtain simple (or at least simpler) proofs of the the Gaussian Isoperimetric inequality in certain cases and a lower bound on approx max-cut of .8787 (not the best known, but very close and a simpler proof).
   
2. Junto-Symmetric Functions, Hypergraph Isomorphism, and Crunching by Fischer, Garcia-Soriano, Matsliah. Two Boolean functions are Isomorphic if they are the same up to a relabelling of the variables. Given two Boolean functions, can we tell if they are isomorphic? One way is to obtain the truth table for both of them and then see if some permutation of the variables makes them the same. Even if all we care about is queries, this seems like a lot. Can we do this in less queries? That is, we are asking Property Testing questions. What if we restrict them. Then what? Read the paper to find out!
   
3. Complexity lower bounds through Balanced Graph Properties by Moshkovitz.
   This looks hard! They mention Tensors!
   
4. Limitations of Lower-Bound Methods for the Wire Complexity of Boolean Operators by Andrew Drucker. First there were pathetic lower bounds on wire complexity. Then after what seemed like half a century, there were (just recently) some slightly less pathetic lower bounds. Even so, that was promising. This paper shows NO, don't get too excited. The new technique will not get better results. Gee Andy Drucker, couldn't you have let us dream just a bit longer. The most depressing talk I have every seen. (It was a GREAT talk and a GREAT result, but still depressing.)
   
5. Limits on Alternation-Trading Proofs for Time-Space Lower Bounds Fortnow, Lipton, van Melkebeek, Viglas showed that any algorithm for SAT that uses log space must take at least time n^1.61 (the golden ratio). Since the golden ratio is a natural number (not literally) it was plausible that current techniques could not improve that. But Ryan Williams got n^c where c is 2cos(π/7) which is roughly 1.801. This can't possible be the best we can do since its just such a funny looking number. Ryan Williams wrote a program to try to fine tune the constants and do better but he couldn't do better. So he said NOBODY can do better!!!!. His advisor Manuel Blum believed him, but nobody else did. NOW he has shown, with help from Sam Buss, that NO, nobody can do better. I am impressed that he and Sam Buss were able to formalize what the technique was in a way that really does pin down ALL prior proofs. Had this paper been written first, there would only be one paper. This talk was NOT depressing since, being a new problem, I can believe that Ryan or Sam or someone can look at what the old techniques were and come up with some new ones and break the (I can't believe I am writing this) 2cos(π/7) barrier! And then what? A paper showing that that bound can't be improved, and then improve it. How far can this go? I've heard that really, really, we won't be able to show quadratic lower bounds. We'll see.
   
6. The Hardness of Being Private Common problem in crypto: Alice has x, Bob has y, they want to computer f(x,y) but they can't know anything about the other ones input accept what they can learn from their input and f(x,y). Are there any functions that people really want to compute like this? YES- the functions involved in a Vickrey Auction. In a Vickrey auction Bob and Alice bid x and y privately. The winner pays the LOSING bid. So if Alice bids 1000 and Bob bids 100, Alice gets to buy it for 100. Formally f(x,y) contains both WHO won and what they paid. The winner does know what the loser bid. But the loser should not know what the winner bid. This paper is about computing this function approximately-private in both the worst case and the average case. The most practical paper at the conference which isn't saying much. (Can the winner use Quantum Money?)
   

CCC12: Post 1 of n

(Post 1 of n on CCC 2012. I don't know how large n is yet.)

I will discuss the papers in the order they were presented.

June 26, 2012. Morning

1. Amplifying Circuit Lower Bounds Against Polynomial Time with Applications by Richard Lipton and Ryan Williams. Of course, what we mean by Applications may differ from what other people call applications. Here is one of the two main results:
   
   

   Let c,d ≥ 1 and e < 1 such that c < (1-e+d)/d. Either QBF is not solvable in time n^c or the Circuit Eval problem cannot be solved with circuits of size n^d and depth n^c.
   

   
   This is one of those odd results where its and OR of two things that we think are both true. But there are two unconditional lower bounds that can be derived from it:
   
   
   1. QBF does not have O(n^1.618)-time uniform circuits of depth n^o(1).
      
   2. For all ε > 0, QBF does not have O(n^{2- ε})-time uniform circuits of depth n^o(1).
      
   In his talk Ryan said that he needed the kind of complexity that only people like Dick Lipton still remember. (ADDED LATER: This is a misquote, see Ryan Williams comment below.)
2. Is the Valiant-Vazirani Isolation Lemma Improvable? By Holger Dell, Valentine Kabanets, Dieter van Melkebeek. Probably not. Oh well.
   
   
3. Parallel Approximation of min-max problems with application to classical and quantum zero-sum games by Gus Gutoski and Xiado Wu. In this paper they developed a better solution to a classical problem and then applied it to a quantum problem. I don't think this is common-- do you know of any other examples?
   
   
4. On the complexity of the Separable Hamiltonian Problem by Andre Chailoux and Or Sattah. (The first name is Or.). This paper looks hard!
   
   
5. Quantum Money with Classical Verification by Dimitry Gavinsky. Quantum Money is a funny topic in that it may be feasible in 100 years, but by then we will all have e-money.
   
   

Afternoon:

1. The Usefulness of Predicates by Per Austrin and Johan Hastad. There is an hour-long version of the talk done on a blackboard here.
   
   li> Reductions between Expansion Problems by Prasad Raghavendra, David Steurer, and Madhur Tulsiani. The authors claim that the Small Set Expansion Hypothesis (SSEH) is a natural hypothesis. (It has been discussed in earlier papers.) This paper shows that SSEH is equivalent to a subcase of UGC. The authors claim that SSEH is is the combinatorial heart of the UGC. WOW!
   
   
2. On Problems as Hard as CNFSAT by Marek Cygan, Holger Dell, Daniel Lokshantov, Daniel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabi, Magnus Wahlstrom, The Strong Exponential Time Hypothesis (SETH) states that for every ε > 0 there exists k such that k-SAT cannot be solved in time 2 ^{ε n} This paper assumes SETH and proves from it lower bounds on HITTING SET, SET SPLITTING, and NAE-SAT.
   
   
   
3. Testing List H-Homomorphisms A List H-Homomorphism is (informally) a homomorphism that satisfies given constraints. Given the constraints and given oracle access to an alleged hist H-Homomorphism, we want to determine if it IS one or is FAR FROM being one (if its not one but close we don't care.) As usual in property testing we are concerned with O(1) queries and sublinear queries. Both are characterized.
   
   
4. A Dichotomy for Real Weighted Holant Problems. by Sangxia Huang and Pinyan Lu. Recall that in Valiant's paper Accidental Algorithms he showed that for monotone planer 3-CNF formulas where each var appears twice (1) finding the number of solutions mod 2 is parity-P complete, but (2) finding the number of solutions mod 7 is in P. Since then there has been a wave of research trying to classify which counting problems are hard (likely complete somewhere) and which are on P. The paper by Huang and Lu is a big jump in this field.
   

North Carolina tries to legislate science

(I will post on CCC 2012 next week. I am still recovering from Jet Lag and going
through 472 emails that piled up on 2.5 weeks, of which 22 were relevent.)


You may have heard the story about the state of Indiana Pi bill:
In 1897 the state of Indiana wanted to legislate a value of pi.  Before reading the true story
I had heard the following:

1. They wanted to legislate pi=3 since the bible says that pi=3.  (The Bible does have a passage that seems to say pi=3, though that may not be the right interpretation.
   See here.)This version of the story puts them in a bad light.
2. They wanted to legislate pi=3 since this makes calculations easier.  They didn't really say pi=3, just that when measuring wheat in silos (or some such) everyone uses pi=3 to make everyones calcuations uniform and easy. (This was in the 1880's- they didn't have Wolframs Alpha).  This version of the story puts them in a good light.

Neither version is true. Look up the link to see what really happened.  Could this happen in America today?
On two issues it certainly could: Evolution and on Climate Change.

The North Carolina House has passed a law saying HOW to predict sea level rise rates.
The method they require predict less sea level rise then... anyone else. And only the
Division of Coastal management is allowed to put out such numbers.  So Independent scientists are not allowed to use... the scientific method.  (Not sure how they will enforce that.) See here for details.

Who wins, who loses?

1. Colbert gets a nice bit about it (which is how I learned about it): here
2. I get a blog out of it.
3. Scientists have to publish less, thus less trees get cut down, so the environment wins.
4. North Carolina looks more ridiculous than Indiana did back in 1897. But there are two differences-
   (1) North Carolina understood what the bill was saying and still passed it, Indiana did not.
   (2) North Carolina's bill has actual policy consequences, Indiana's pi-bill wouldn't have.
   

Fortunately the North Carolina Senate did not pass the bill so its not law. Yet.

Why is it called the Turing Award?

The ACM Turing Award represents the highest honor in the computing research community, the closest we have to a Nobel prize in computer science. In this centenary celebration of Alan Turing, it seems obvious that the award should be named after him.

But back in 1966 when Alan Perlis won the first Turing award, Turing's influence on the field was far less obvious. Turing's model had only a few years earlier found its way into computer science literature, still dominated by automata, parsing and circuits. In 1966, what is now the Foundations of Computer Science conference was just renamed Switching and Automata Theory from Switching Circuit Theory and Logical Design.

So why name the award after Turing back then? This question came up during one of the panel sessions at the ACM Turing Celebration where there were some vague guesses. I asked around during the breaks and nobody seemed to know. I even put the question to Turing biographer Andrew Hodges in Cambridge and he similarly didn't know.

The Knuth prize aside, most awards are named after people who have passed away. Back in 1966 there weren't very many dead computer scientists. Even among Turing's generation, Church, Post, Kleene, even Gödel were alive and kicking. Turing would have only been 54 had circumstances been different. John von Neumann died young from cancer in 1957 but wasn't thought of primarily as a computer scientist. There were also Charles Babbage and Ada Lovelace but I'm not sure they were in people's minds back then.

I'm guessing that Turing was just the default choice for the name of the award and the ACM just got extraordinarily lucky for picking the right person in spite of themselves.

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?
   

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.