Our Government at Work

Barring a surprise deal, the sequester goes into effect tomorrow. NSF Director (and soon to be CMU President) Subra Suresh announced a sequestration impact statement.

At NSF, the major impact of sequestration will be seen in reductions to the number of new research grants and cooperative agreements awarded in FY 2013. We anticipate that the total number of new research grants will be reduced by approximately 1,000. All continuing grant increments in FY 2013 will be awarded, as scheduled, and there will be no impact on existing NSF standard grants. It is also important to advise you that the Foundation is currently operating under a Continuing Resolution (CR) that will expire on March 27, 2013. 

Once the CR expires the whole NSF, and many other parts of government, will shut down. While I expect the sequestration to happen, most likely the CR will get extended.

Meanwhile last week the White House Office of Science and Technology Policy issued a memo that will require most federally funded research to be publicly available after a year. The NSF and other agencies have six months to produce a plan. According to Farnam Jahanian (NSF CISE head), the NSF will work with close consultation with academics and associations in developing its plan which may not be the same for each discipline. Purely speculating, I'm guessing something akin to what the NIH does by establishing an open repository of research papers and requiring funded researchers to post copies of their papers in that repository.

Enos, Oona, sqrt(3), and Aaronson

My darling does crossword puzzles and sometimes asks my help:

Darling: Bill, Slaughter in Cooperstown- whats the answer?

Bill: Enos. There was a serial murderer in a town named Cooper, and he always wrote on his victims Eternity's Not On Sale. So he got the nickname ENOS. Nobody ever figured out what that meant and he was never caught.

Darling: Another clue: Chaplin's wife

Bill: Oona. That's latin for minister's spouse. And in those days ministers were always men.

Darling. Okay. Another clue: Log man. Begins with an N.

Bill: Napier, a famous lumberjack.

Many of my readers know that, while the above answers are correct,
the reasoning behind them is fictional. In fact, the entire story is fictional.
But it IS true that when Darling sees those clues in crossword puzzles
she knows what the answer is without having any idea that Enos Slaughter is in
the Baseball Hall of Fame in Cooperstown, that Oona was the name of Charlie
Chaplin'sfourth and last wife, or that John Napier is regarded as having
invented logarithms (the history of such things is always murky).
She has MEMORIZED the answers (from years of doing crossword puzzles)
without really UNDERSTANDING the answers.

When I show my students the proof that sqrt(2) is irrational and ask
them to prove sqrt(3) is irrational, I often can't tell if they truly
understand the proof or are copying a template proof of sqrt(2).

Sometimes (and usually on harder problems) some small slip will
tell me that they are just copying since they didn't quite know
what to change. Or they may miscopy.

However, there is a deeper question here. If students memorizes the
template for the proof that sqrt(n) is irrational, and uses it correctly,
then do they understand or have they just memorized? The distinction can be
hard to discern and may not even exist. One real test is if they understand
why the same template fails on sqrt(4). For harder problems there may be
other ways to tell--- having to do with when the proof fails.

Incidentally, the reason the crossword clues above come up so often is
that the answers have many vowels in them. So, one way to immortality is
to be mildly famous and have a name with a large percentage of vowels.
Let see- gAsArch: 28% vowels not so good. fOrtnOw: The same (no wonder we coblog!),
also not so good. AArOnsOn: 50% WOW!! May his name adorn crossword puzzles for
many years to come!

Interruptions

I got a new toy this week, the Pebble watch which I got early because I pre-ordered donated to their Kickstarter campaign. It's a little buggy and the promised apps do not exist yet, but I'm already finding the watch extremely valuable because my email, texts and phone calls show up on my watch--much easier to check the watch than pull the phone from my pocket.

With Gmail smart labels and some additional filters, most of the email that reaches my inbox actually requires my attention at some point. But often I'm in a talk or a meeting. I've trained myself to ignore the buzz of my phone and now I can see I have to ignore the buzz of my watch as well--harder to do.

Our lives just get more interconnected. Some people I hear purposely disconnect themselves to get work done. I like to deal with issues as they arise and not let them pile up. But the trick is to remember that when you are in the midst of doing something best to ignore the interrupt than act upon it.

Are most lower bounds really upper bounds?

Recently Daniel Apon (grad student of Jon Katz at UMCP, but he also hangs out with me) proved a LOWER BOUND by proving an UPPER BOUND. His paper is here. I have heard it said (I think by Avi W and Lane H) that MOST lower bounds are really upper bounds. Below I use the term Non-Alg Lower Bound for a lower bound that is NOT an algorithm. This is not a rigorous notion and the items below are up for debate.

1. Time Hier, Space Hier- Diagonalization. I would call that Non-Alg.
   
2. Cooks Theorem: this is an ALGORITHM to transform a Non Det TM and a string x to a Boolean Formula.
   
3. All reductions can be viewed as ALGORITHMS.
   
4. Parity not in AC0: The Yao-Hastad proof can be viewed as a non-alg lower bound for the depth 1 or 2, and then a randomized ALGORITHM to transform depth d to depth d-1.
   
5. Parity not in AC0[3]: This is a Non-Alg lower bounds--- you show that parity has some property (not being able to be approx by low degree polys) and then you show that AC0[3] cannot deal with this property.
   
6. Comm Complexity: The det lower bound on EQ is a Non-Alg lower bound. I think the randomized lower bound on DISJOINT is a Non-Alg lower bounds. Many others lower bounds are reductions to these two, and hence are algorithms.
   
7. Multiparty Comm Comp: I'll just mention one result: Chandra-Furst-Lipton's lower bounds on EXACT-N for k-player Number-on-Forehead. The lower bounds shows that if there is a protocol of t bits then some structure can be colored in a certain way. Then Ramsey Theory is used. Non-Alg Lower bound I think.
   
8. Decision Tree Complexity (Comparisons): The lower bounds on SORTING and MAX, are non-Alg lower bounds. The following leave-counting lower bound for
   2nd largest is sort-of a reduction to MAX but I still think its non-alg: First note that the lower bound for MAX is very strong- even the best case
   requires n-1 comps. Hence any DT for MAX has roughly 2^n-1 leaves.
   T is a DT for 2nd largest. For all i=1,...,n let T_i be the subtree where x_i WINS. This is a MAX tree for n-1 elements so has 2^n-2 leaves. All these sets of leaves are disjoint so T has n2^n-2 leaves.Hence T has height n+ log n + \Omega(1).)
   
9. Decision Tree Complexity (Other queries): Algebraic Queries, k-ary queries have all been studied.
   The Algebraic Queries lower bounds use number-of-component arguments and seem non-alg. Some of the k-ary query lower bounds use Ramsey Theory to reduce to the comparison case.
   
10. Branching programs and other models often reduce to comm complexity. Is that an algorithm.
    
11. Ryan Williams proof that NEXP is not in ACC is really, at its core, an algorithm that does slightly better than brute force.
    

My Final Opinion: The above is a random sample, but it seems to be that there are plenty of lower bounds that are non-alg lower bounds. However, as more and more lower bounds are known, more and more reductions will be used and hence there will be more algorithms.

Beauty and Science

Christopher Shea wrote a recent Chronicle Review article Is Scientific Truth Always Beautiful? I would argue the answer is yes, and it boils down to Occam's Razor that the simplest explanation that fits the available data is typically the best and there is a strong relationship between beauty and simplicity.

An ugly scientific theory would have a large number of parameters which will lead, in computer science terms, to overfitting the current state of the world and almost surely such a theory would be incorrect. So every scientific truth should be beautiful.

Now the converse doesn't hold. There are far more beautiful theories than correct ones. That's the beauty of the scientific method to help sort them out. As Einstein may have said, "Everything should be kept as simple as possible, but no simpler."

In mathematics, not all correct proofs are beautiful and not all beautiful proofs are correct. But if you believe Erdős, all correct theorems have beautiful proofs, all kept in The Book.

The Complexity-STOC Bonanza

STOC and Complexity are co-located June 1-7 in beautiful Palo Alto, California. Both conferences have just announced their accepted papers: STOC (with PDF links) and Complexity.

Both conferences will have student travel awards. Details coming soon to the respective web sites.

On a different topic, The 2014 Nevanlinna Prize committee is still accepting nomination until May 1, 2013.

Proving DFA-langs closed under concat and * without using equiv to NDFA's

While teaching the Equiv of DFA, NDFA, Reg exps, I wanted to impress upon my students that the best way to show DFA-langs are closed under concat and * is to first prove DFA=NDFA and then show NDFA's closed under concat and * (which is easy). The question arises: CAN one PROVE that DFA-langs are closed under concat and star without using the equivalence to NDFA's? I emailed this informal question to Richard Beigel (my go-to guy for formal lang theory--- its a good thing he's not my go-to guy for Prog Langs since then I couldn't use go-to's.)

He emailed back the following sketches of proofs of closure that only use DFA's:

Closure under concat: states will be of the form (q,S) where q is a state of M1 and S is a set of states of M2. Start in (q0, {}) where q0 is the start state of M1. Each time a character is read advance q in M1 and advance each element of S in M2. Whenever q is an accepting state, insert M2's start set into S. Accept if S contains an accepting state of M2.

Closure under star: It is easy to modify a DFA so that the start state has no incoming edges. I'll assume that M is already in that form. State of the new machine will be a set S of states of M. Start in state {q0}. Each time a character is read, advance each state in S and then if S contains an accepting state of M insert q0 into S. Accept if S contains q0.

After complementing him on his answes I asked him him about proving Reg-exp-langs closed under complementation without using equiv to DFA's. He doesn't know how to do that, so I assume it can't be done. But is there a rigorous way to even state that?
~

Postdocs in Computer Science

Anita Jones is troubled by the growing number of postdocs in computer science, she uses "troubling" twice in the first paragraph of her CACM Viewpoint. But is it really a troubling trend or just a natural outgrowth of a maturing field?

Theoretical computer science leads computer science in having and even embracing a postdoc culture. Nearly every graduating PhD in theoretical computer science that remains in academia takes a postdoc position before taking an tenure-track job. If anything I hear theorists lamenting a drop in theory postdocs this year with the end of the Simons postdocs and CI fellows.

Postdocs give PhDs a chance to focus on research and strengthen them for the future job market. I initially started as a two-year assistant professor at Chicago, basically a teaching postdoc. If I didn't have that opportunity my research career would have died in its tracks.

What would happen if all postdoc funding was stopped. That would lead to more funding for graduate students most of whom would have to take a non-research career especially with no postdoc positions available. Hard to see how anyone wins.

Anita and I both agree that a successful postdoc experience requires strong mentorship and inclusiveness or otherwise the postdoc is just working in a vacuum. The CRA has put out a best practices memo, worth reading for both postdocs and the people who hire them.

The (il)logic of fandom

(UMCP is having an REU (Research Experience for Undergradutes) this summer on Combinatorial Algorithms Applied Research. If you are an ugrad, go to that site and see if you want to apply. If you are a faculty see if you want to recommend it to some students. Deadline to apply is Feb 15.)

The Sunday before the Superbowl I spotted this curious passage in THE WASHINGTON POST which I paraphrase.

Washington Redskins fans should root for the Baltimore Ravens in the Superbowl because the two teams share many fine qualities. Both have gritty defense, soft-spoken by shrewd head coaches, underrated quarterbacks craving validation on the big stage. Neither team is flashy or has big starts--- rather they are both greater than the sum of their parts.

I interpret this as assuming Sports fans pick who to root for in a logical manner. Something like I like quality X, this team has quality X, so I will root for them. Is that how sports fans act. If it was then sports fans would change who they root for often. They do not.

So what is the logic behind fandom? Why do people root for certain teams, likely for a lifetime. Is it rational?

1. Root root root for the home team, for it they don't win its a shame. Root for the team in the place you live NOW.
   
2. Root for your childhood team. I wonder if the Chicago Cubs has more fans across the country since one of the early cable channels WGN, is from Chicago and (I think) carries Cubs games--- so you can be a transplanted Chicagoan and still watch your team. As people move around alot loyalty to your home team may fade.
   
3. For College teams its common to root for the team that comes from the college you went to. This is less true for graduate school.
   
4. Fair weather fans root for the team that's winning. But it is more common to have a team (perhaps your home team) that you ignore unless they are winning. So you don't choose your team based on this, but you choose weather to care based on this.
   
5. The early NY Mets (early 1960's) were a terrible team but they had lots of fans. There was a loser-chic factor. The Chicago Cubs have also had that. This is rare or even nonexistent now. Everyone loves a winner.
   
6. Individual players may appeal to you. Tim Teabow got some attention because of his devout Christianity. But this is rare. Its more common to get attention for negative behavior. This is more a matter of rooting for a person rather than the team.
   
7. A while back some teams delayed getting any black players on them so they would still appeal to racist fans. This stopped once such teams just lost too much since they were not using that talent pool. Might someone root for or against a team because of the attitude or politics of the management? If some team took the profits and funded alternative energy for real would you root for them? What if they funded Ramsey Theory? What if they supported Same Sex marriage? I doubt a team would have a public opinion on an issue which may cause them to lose fans, though a player might.
   
8. A friend of yours is ON the team so you root for the team and your friend. This is rare. But if someone on the team is from your SCHOOL- you may have a certain affinity for that person and team even if you don't know them. Whenever I hear that some pro football player is from Harvard (where I went to graduate school) I at least notice this. Its rare.
   
9. In the Olympics one usually roots for their own country. What if (say) American offered the top Tennis player in the world (who was not an American) to become a citizen of the USA (and pay him for it) then he won the Gold Medal for American. (I think this is legal.) Would Americans be proud of that or feel that's not quite right? I suspect that this kind of thing will happen more often over time. While this may seem strange it already happens within a country. The NY Mets do not have more players from NY. Nor do the Baltimore Ravens have more players from Baltimore.
   
10. Jerry Seinfeld once commented that we LOVE this player if he's on OUR team but HATE him if he is on another team. What has changed? His uniform. So we are rooting for clothing.
    

Is there a logic to who a fan roots for or not? Is there a logic to being a sports fan?

Who do you write papers for?

Mitch Daniels, the former governor of Indiana and new president of Purdue, wrote an inaugural letter where he discusses many of the challenges of higher education. His lists several common attacks on universities and one caught my eye.

Too many professors are spending too much time "writing papers for each other," researching abstruse topics of no real utility and no real incremental contribution to human knowledge or understanding.

I write papers mainly for myself. I have my own opinions on what problems are important and where my interests and research strengths lie. One of the main draws of being a professor is having the freedom to choose our own research.

But we have to write for our peers as well. It's our peers that review and cite our papers and make decisions about grants and jobs. For the most part our peers are the only ones who read our papers.

In the end we write papers for society. Most of our papers taken individually add a small amount to human knowledge and are only of interest to fellow specialists. But taken together our research drives a field of inquiry allowing us to understand and take on new challenges. Even if we have trouble selling a specific theoretical computer science papers to a broader audience, taken as a whole theory helps us model and understand the power of computation and leads to smarter and faster algorithms on real world machines.

TCS online series- could this work?

Oded Regev, Anindya De and Thomas Vidick we are about to start an online TCS seminar series. See here for details, though I have the first few paragraphs below.

Its an interesting idea- we can't all get to conferences so this is a good way to get information out there. Wave of the future? We'll see how it goes.

Here is the first few paragraphs:

Ever wished you could attend that talk if only you didn't have to hike the Rockies, or swim across the Atlantic, to get there; if only it could have been scheduled the following week, because this week is finals; if only you could watch it from your desk, or for that matter directly from your bed?

Starting this semester TCS+ will solve all your worries. We are delighted to announce the initiation of a new series of *online* seminars in theoretical computer science. The seminars will be run using the hangout feature of Google+. The speaker and slides will be broadcast live as well as recorded and made available online. Anyone with a computer (and a decent browser) can watch; anyone with a webcam can join the live audience and participate.

Our goal is to make engaging talks accessible to the widest possible audience, ensuring a carbon-free dissemination of ideas across the globe.

We're still in beta, and we welcome any feedback from the community. There will undoubtedly be glitches at first, but we hope you'll bear with us and be as excited as we are at trying out the possibilities of this new medium.

Now for some more practical information:

Inauguration talk:

1. Speaker: Ronald de Wolf, CWI, Amsterdam.
   
2. Title: Exponential Lower Bounds for Polytopes in Combinatorial Optimization.
   
3. Source: Paper of the same name from STOC12 with Samuel Fiorini, Serge Massar,
   Sebastian Pokutta and Hans Raj Tiwary that won the best paper award.)
   

The End of a Useless Test

First a word from our sponsor: Mihalis Yannakakis is celebrating his 60th birthday this year and you are invited to the party.

From the Educational Testing Service:

The last administration of the GRE Computer Science Test will be in April 2013. The test will be discontinued after the April 2013 administration. Scores will continue to be reportable for five years.

Why is the Computer Science Test being discontinued?
Over the last several years, the number of individuals taking the Computer Science Test has declined significantly. Test volume will soon reach a point where ETS can no longer support the test psychometrically. As a result, the GRE Program has decided to discontinue the Computer Science Test. The test will be offered for the last time in April 2013

"Pyschometrically" just refers to the ability to measure abilities, mental traits and processes. Seems redundant in this context.

Bill tells me Maryland CS used to require a subject GRE but no longer does. Georgia Tech CS does not require a GRE. We have a separate PhD program in Algorithms, Combinatorics and Optimization that recommends the math subject test.

Computer Science is a broad field and can't be easily tested, psychometrically or otherwise, and the score of the subject test does not help us determine who will be a good grad student.

The regular GRE exam is not that much better. The quantitative can only help weed the weak students. The analytic score should be a good predictor but isn't. The verbal score, at least among Americans, oddly enough may have the best correlation to success in grad school, but not reliable enough to put much weight on it.

So how do I judge PhD candidates? Grades in CS and math courses taking into account the quality of the university, any undergraduate research, and the recommendation letters.

A New application of Ramsey Theory to a Geometry problem

All of the material summazized here is in a new paper by Gasarch and Zbarsky. You can find that paper here)

Consider the following problem:

1. Let {p1,...,pn} be a subset of distinct points in R^d. We think of d ≤ n. How big is the largest subset X of points such that all of the distances determined by pairs of elements of X are different? Let h(d,n) be the min size of X. That is, we always have a set X of size h(d,n) with all distances between points different.
   
2. Assume that no three of the original points are collinear. How big is the largest subset X of points such that all of the areas determined by triples of points in X are different? Let g(d,n) be the min size of X. That is, we always have a set X of size g(d,n) with all triangle-areas of different sizes.
   

(This is NOT the Erdos Distance problem where you are given n points and want to know the min number of diff distances you have.) What is know about the problem posed?

1. The case of d=1 is known h(1,n)=Θ(sqrt(n)).
   
2. Erdos said somewhat mysterioulsy (I paraphrase)
   

   It is easy to see that there are constants ep(d) such that h(d) ≥ n^ep(d). (BILL: Frankly- I do not find it easy to see.)

   Aside from that, not much was known.
   

Until now. Gasarch and Zbarsky have shown the following (roughly)

1. h(d,n) ≥ Ω(n^1/(6d)).
   
2. g(2,n) ≥ Ω((log log n)^1/2901).
   
3. g(3,n) ≥ Ω((log log n)^1/27804).
   

We believe these results are new. They were obtained using variants of the Canonical Ramsey Theorem, originally due to Erdos and Rado, and some geometric lemmas.

Rise of the Engineer

I rarely watch TV commercials anymore but its NFL playoff time and during a game last weekend, the Ford commercial showing how a liftgate can be opened by waving a foot caught my eye.

When not showing pictures of feet, this commercial focuses on an engineer by face and name, Vince Mahe, one of four engineers featured in Ford Escape commercials.

Vince Mahe, the engineer behind the hands-free liftgate, was born in France and moved to the United States when he was 10. All around the world, Mahe noticed people often have their hands full. So Mahe and team engineered a way for people to open the liftgate of the all-new Escape with a simple kicking motion under the rear bumper.

There is also a series of new IBM commercials (can't find the videos online) where an IBM researcher walks into the frame of a commercial and says something like "I'm so-and-so and I'm an IBMer helping you analyze data to target your customers".

Wasn't long ago that companies hid their scientists and engineers, only selling the product. We're seeing a new time where engineers and scientists tackling societal problems, big and small, are more forefront and center. Not since the 60's has it been this cool to be a geek.

paperfree?- we are not there yet

Last time I taught I had to decide if I would HAND OUT the HW or just say its posted (NOTE- I post it in any case.) This may seem old fashion but I think there is some psychological value to actually giving someone a piece of paper with HW 8 on the top of it. I also thought that perhaps my students would think this a strange notion and certainly my youngest great nephew and niece (both 6) will never see an assignment on paper. My classes were of sizes 40 and 20, so this is not a burden on copying (I do go paperless for my class of size bigger than 70).

I asked around and asked the class. Much to my surprise about 3/4 in each class wanted paper. Why? Speculation:

1. They would rather I print it out then they print it out.
   
2. Having the paper serves as a reminder to do it (my psychological point.)
   
3. The want to have more trees cut down, hasten global warming, since that way the planet may die before the final.
   
4. The youth of today are not quite as PAPER FREE as we think.
   

I also asked the students Do you think that in 10 years the students will prefer just posting the HW? Only half thought so, which surprised me. I think that the paperless society is coming at us much faster than that; however, I am also surprised its not here yet. So that semester I mostly gave out paper HW. But there was something else wrong with this scheme, and in the future I won't be doing it.

1. I copied 40 HW's and only 30 people show up for class- so that really is a waste. I assigned 12 HWs, so that's 120 sheets of paper wasted. (CAVEAT- not totally wasted- I print out other papers on the backs when I can.)
   
2. There were a few times when I gave out the HW, taught a lesson, then realized I wanted to ask something different. BETTER to make up MOST of the HW before the lesson, but then adjust it and post after the lesson.
   

My question for you: are your classes COMPLETELY paperless at this point? PROS and CONS? Also, when will this post seem quaint and odd? I thought it already was, but my students reaction says otherwise.

Slow Science

You likely have not heard about the Slow Science manifesto. They don't blog. They don't tweet. They give a broken link to their Facebook Page which has no posts. But they do have a point.

Science needs time to think. Science needs time to read, and time to fail. Science does not always know what it might be at right now. Science develops unsteadily, with jerky moves and unpredictable leaps forward—at the same time, however, it creeps about on a very slow time scale, for which there must be room and to which justice must be done.

Computer Science is inherently a fast discipline. Technology changes quickly and if you don't publish quickly your research may become irrelevant. We created a culture with conferences and deadlines that push us, even those of us on more theoretical end, to finish our projects quickly and publish the best we have at the next due date.

But we need to step back and take a while to view the great challenges we have in computing. Issues like privacy, big data, the Internet of things and cloud computing need time to really think of the right approach, not just short term projects. In computational complexity we have grand challenges in understanding the power of efficient computation but too often we just tweak a model to eke out another publication.

Andrew Wiles solved Fermat's last theorem by toiling on the problem by himself for several years right before the Internet revolution. Will we see a slow science success again in this new age?

Do daughtered candidates to better- Look at the Data!

Someone in my election night party predicted Obama because:

Ever since women got the right to vote (1920) if one candidate has a daughter and one does not, then the one with the daughter won. This is because they know how to talk to women. Note that Obama has two daughters while Romney has 5 sons.

With Wikipedia and the web one can actually try to VERIFY the alleged FACT that daughtered candidates beat non-daughtered. If it was true then it would be much harder to verify the conjecture as to WHY its true. The full data is below but in a nutshell: From 1920 to 2012 there were 24 election. In EIGHT of them one candidate was daughtered and the other not. In FIVE of those the daughtered one won. Is this statistically significant? NO. It would take far more trials to determine if daughtered candidates do better. And even then one can note things like Roosevelt going for his third and fourth term was unstoppable so I don't think his having a daughter put him over the top. Also, times change. We will surely one day have a female candidate so that might change the dynamic as well. The problem with trends- once you figure them out they may no longer hold.

When doing a study like this you often find OTHER data of interest: ALL of the prez candidates since 1920 had children (Harding's child was a step-son but regarded Harding as his father, hence so do I.) I then looked up prez's without kids (I didn't look at candidates--- too much work) George Washington had step kids who regarded him as their father as well as the father of our country. James Madison, James Polk, James Buchanan (our only bachelor prez) didn't have kids. Of the SIX presidents named James (the others are James Monroe, James Garfield, and James Carter) THREE of them didn't have kids! Odd but NOT stat sig.

Lessons to draw from this--- (1) Don't believe everything you hear at election parties. (2) It's harder to make false claims at parties with Wikipedia and the Web around to verify (though political candidates seem to get away with it), (3) Daughtered is now a word. (4) Things that sound intuitively reasonable may still be false (5) If you look into claims that are false you may find other things of interest.

Here are the EIGHT:

1. 2012: Obama vs Romney: Obama has 2 daughters, Romney has 5 sons. Winner: Obama (the one with the daughter)
   
2. 1948: Dewey vs Truman: Dewey had 2 sons. Truman had 1 daughter. Winner: Truman (the one with the daughter)
   
3. 1944: Dewey vs Roosevelt: Dewey had 2 sons. Roosevelt had 1 daughter and 5 sons. Winner: Roosevelt (the one with the daughter)
   
4. 1940: Roosevelt vs Wilkie: Roosevelt had 1 daughter and 5 sons. Wilkie had 1 son. Winner: Roosevelt (the one with the daughter)
   
5. 1932: Hoover vs Roosevelt: Hoover had 2 sons. Roosevelt had 1 daughter and 5 sons. Winner: Roosevelt (the one with the daughter)
   
6. 1928: Hoover vs Smith: Hoover had 2 sons. Smith had 2 daughters and 3 sons. Winner: Hoover (the one without a daughter)
   
7. 1924: Davis vs Coolidge: Coolidge had 2 sons. Davis had a daughter Winner: Coolidge (the one without a daughter)
   
8. 1920: Cox vs Harding: Cox had 2 sons and 2 daughters, Harding had one step-son.
   Winner: Harding (the one without a daughter)
   

Here is the full data. A * means that it was daughtered vs non-daughtered and daughtered won. ** means it was daughtered vs non-daughtered and the non-daughtered won.

1. 2012: Obama vs Romney: Obama has 2 daughters, Romney has 5 sons. Winner: Obama*
   
2. 2008: Obama vs McCain: Obama has 2 daughters, McCain has 2 sons, 2 daughters. Winner: Obama.
   
3. 2004: Bush vs Kerry: Bush has 2 daughters. Kerry has 2 daughters and 3 step-sons. Winner: Bush.
   
4. 2000: Bush vs Gore: Bush has 2 daughters. Gore has 3 daughters and 1 son. Winner: Bush.
   
5. 1996: Clinton vs Dole: Clinton has 1 daughter. Dole has 1 daughter. Winner: Clinton.
   
6. 1992: Bush vs Clinton: Bush has 2 daughters and 4 sons. Clinton has 1 daughter. Winner: Clinton.
   
7. 1988: Bush vs Dukakis: Bush has 2 daughters and 4 sons. Dukakis has 2 daughters and 1 son. Winner: Bush.
   
8. 1984: Mondale vs Reagan: Mondale has 1 daughter and 1 son. Reagan has 2 daughters and 2 sons. Winner: Reagan.
   
9. 1980: Carter vs Reagan: Carter has 1 daughter and 3 sons. Reagan has 2 daughters and 2 sons. Winner: Reagan.
   
10. 1976: Carter vs Ford: Carter has 1 daughter and 3 sons. Ford has 1 daughter and 3 sons. Winner: Carter.
    
11. 1972: McGovern vs Nixon: McGovern has 4 daughters and 1 son. Nixon had 2 daughters. Winner: Nixon.
    
12. 1968: Humphrey vs Nixon: Humphrey had 1 daughter and 2 sons. Nixon had 2 daughters. Winner: Nixon.
    
13. 1964: Goldwater vs Johnson: Goldwater had 2 daughters and 2 sons. Johnson had 2 daughters. Winner: Johnson
    
14. 1960: Kennedy vs Nixon: Kennedy had 1 daughter and 2 sons. Nixon had 2 daughters Winner: Kennedy
    
15. 1956: Eisenhower vs Stevenson: Eisenhower had 2 sons. Stevenson had 3 sons. Winner: Eisenhower.
    
16. 1952: Eisenhower vs Stevenson: Eisenhower had 2 sons. Stevenson had 3 sons. Winner: Eisenhower.
    
17. 1948: Dewey vs Truman: Dewey had 2 sons. Truman had 1 daughter. Winner: Truman*
    
18. 1944: Dewey vs Roosevelt: Dewey had 2 sons. Roosevelt had 1 daughter and 5 sons. Winner: Roosevelt*
    
19. 1940: Roosevelt vs Wilkie: Roosevelt had 1 daughter and 5 sons. Wilkie had 1 son. Winner: Roosevelt*
    
20. 1936: Landon vs Roosevelt: Landon had 2 daughters. Roosevelt had 1 daughter and 5 sons. Winner: Roosevelt.
    
21. 1932: Hoover vs Roosevelt: Hoover had 2 sons. Roosevelt had 1 daughter and 5 sons. Winner: Roosevelt*
    
22. 1928: Hoover vs Smith: Hoover had 2 sons. Smith had 2 daughters and 3 sons. Winner: Hoover**
    
23. 1924: Davis vs Coolidge: Davis had 1 daughter. Coolidge had 2 sons. Winner: Coolidge**
    
24. 1920: Cox vs Harding: Cox had 2 sons and 2 daughters. Harding had 1 step son. Winner: Harding**
    

Erdős and Turing

Only nine months separate the births of two very influential mathematicians, Paul Erdős and Alan Turing, whose centenaries we celebrate this year and last. That's where the similarities end. Turing used philosophical ideas to create models and questions that help us shape the important problems in computer science. Erdős solved combinatorial problems and developed tools and techniques in the process that the rest of us rely on. Turing generally worked alone and Erdős famously "opened up his brain" to so many that we measure our research distance to him. Turing tragically died young nine year before I was born. Erdős lived twice as long as Turing, I've met Erdős and seen him speak. We connect Turing to World War II where he helped break German codes. We connect Erdős to the Cold War that challenged travel between his native Hungary and America.

Turing's work gets celebrated in the broad computer science and logic communities. ACM's highest honor is named after Turing and we just finished a year's worth of activities in his honor. Erdős is a deity in the combinatorics community and gets his centennial conference (in Hungary of course). The most influential Erdős prizes are the ones he gave out for solving his open questions.

You've likely heard much of Turing's life over the past year. For 2013 go read an Erdős biography like The Man Who Loved Only Numbers and learn about another life well lived.

2012 Complexity Year in Review

As we turn our thoughts from Turing to Erdős, a look back at the complexity year that was. Written with help from co-blogger Bill Gasarch.

The complexity result of the year goes to Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary and Ronald de Wolf for their paper Linear vs Semidefinte Extended Formualtions: Exponential Separation and Strong Lower Bounds (ArXiv version). It is easy to show that TSP can be expressed as an exponentially sized Linear Program (LP). In 1987 Swart tried to show that TSP could be solved with a poly sized LP. While his attempt was not successful it did inspire Yannakakis to look at the issue of how large an LP for TSP has to be.He showed in 1988 that any symmetric LP for TSP had to be exponential size. (Swart had used symmetric LP's).

What about assymetric LP's? This has been open UNTIL NOW! The paper above proves that any LP formulation of TSP requires an exponential sized LP. They use communication complexity and techniques that were inspired by quantum computing.

Runners Up

• Sam Buss and Ryan Williams for their limits on the time-space tradeoffs for Satisfiability. 
• Paul Beam, Christopher Beck and Russell Impagliazzo for Time-space tradeoffs in resolution: superpolynomial lower bounds for superlinear space
• Tsuyoshi Ito and Thomas Vidick: MIP with entangled provers still contains NEXP

And don't forget the solution to Bill's 17x17 problem.

News and trends: The new Simons Institute for the Theory of Computing at Berkeley, the great exodus of Yahoo! researchers mostly to Google and Microsoft, the near death of Florida computer science (anyone want to be chair?), and the rise of the MOOCs. 

We remember Dick de Bruijn, Tom Cover, Mihai Pătraşcu, Ernst Specker and David Waltz, not to mention Neil Armstrong and Ray Bradbury

Thanks to our guest posters Bernard Chazelle, Yoav Freund, Andrew Goldberg, Mohammad Taghi Hajiaghayi, William Heisel, Lane Hemaspaandra, John Purtilo, Janos Simon and Vijay Vazirani.

Enjoy 2013 and remember that when living in a complex world, best to keep it simple. And try not to fall off that fiscal cliff.

Flash Fill

Sometimes it just takes a simple new feature in a popular piece of software to remind us how computer science just does cool stuff.

Excel 2013 has a new feature, Flash Fill, where you can reformat data by giving an example or two. If you have a column of names like

Manuel Blum
Steve Cook
Juris Hartmanis
Richard Karp
Donald Knuth


You can start a column to the right and type
Blum, M.
Cook, S.
and the rest of the table gets filled in automatically.

Flash Fill is based on a 2011 POPL paper by Sumit Gulwani (later a CACM highlight). It's been explained to me as applying machine learning to binary decision diagrams.

Flash Fill allows a user to manipulate data without having to write macros or Perl scripts. Someone with no technical background can use Flash Fill and enjoy the CS goodness inside without even knowing it is there.