Lance Fortnow's Blog, page 126

Rise of the Engineer

I rarely watch TV commercials anymore but its NFL playoff time and during a game last weekend, the following Ford commercial 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:



They would rather I print it out then they print it out.

Having the paper serves as a reminder to do it (my psychological point.)

The want to have more trees cut down, hasten global warming, since that way the planet may die before the final.

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.

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.)

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:



2012: Obama vs Romney: Obama has 2 daughters, Romney has 5 sons. Winner: Obama (the one with the daughter)

1948: Dewey vs Truman: Dewey had 2 sons. Truman had 1 daughter. Winner: Truman (the one with the daughter)

1944: Dewey vs Roosevelt: Dewey had 2 sons. Roosevelt had 1 daughter and 5 sons. Winner: Roosevelt (the one with the daughter)

1940: Roosevelt vs Wilkie: Roosevelt had 1 daughter and 5 sons. Wilkie had 1 son. Winner: Roosevelt (the one with the daughter)

1932: Hoover vs Roosevelt: Hoover had 2 sons. Roosevelt had 1 daughter and 5 sons. Winner: Roosevelt (the one with the daughter)

1928: Hoover vs Smith: Hoover had 2 sons. Smith had 2 daughters and 3 sons. Winner: Hoover (the one without a daughter)

1924: Davis vs Coolidge: Coolidge had 2 sons. Davis had a daughter Winner: Coolidge (the one without a daughter)

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.

2012: Obama vs Romney: Obama has 2 daughters, Romney has 5 sons. Winner: Obama*

2008: Obama vs McCain: Obama has 2 daughters, McCain has 2 sons, 2 daughters. Winner: Obama.

2004: Bush vs Kerry: Bush has 2 daughters. Kerry has 2 daughters and 3 step-sons. Winner: Bush.

2000: Bush vs Gore: Bush has 2 daughters. Gore has 3 daughters and 1 son. Winner: Bush.

1996: Clinton vs Dole: Clinton has 1 daughter. Dole has 1 daughter. Winner: Clinton.

1992: Bush vs Clinton: Bush has 2 daughters and 4 sons. Clinton has 1 daughter. Winner: Clinton.

1988: Bush vs Dukakis: Bush has 2 daughters and 4 sons. Dukakis has 2 daughters and 1 son. Winner: Bush.

1984: Mondale vs Reagan: Mondale has 1 daughter and 1 son. Reagan has 2 daughters and 2 sons. Winner: Reagan.

1980: Carter vs Reagan: Carter has 1 daughter and 3 sons. Reagan has 2 daughters and 2 sons. Winner: Reagan.

1976: Carter vs Ford: Carter has 1 daughter and 3 sons. Ford has 1 daughter and 3 sons. Winner: Carter.

1972: McGovern vs Nixon: McGovern has 4 daughters and 1 son. Nixon had 2 daughters. Winner: Nixon.

1968: Humphrey vs Nixon: Humphrey had 1 daughter and 2 sons. Nixon had 2 daughters. Winner: Nixon.

1964: Goldwater vs Johnson: Goldwater had 2 daughters and 2 sons. Johnson had 2 daughters. Winner: Johnson

1960: Kennedy vs Nixon: Kennedy had 1 daughter and 2 sons. Nixon had 2 daughters Winner: Kennedy

1956: Eisenhower vs Stevenson: Eisenhower had 2 sons. Stevenson had 3 sons. Winner: Eisenhower.

1952: Eisenhower vs Stevenson: Eisenhower had 2 sons. Stevenson had 3 sons. Winner: Eisenhower.

1948: Dewey vs Truman: Dewey had 2 sons. Truman had 1 daughter. Winner: Truman*

1944: Dewey vs Roosevelt: Dewey had 2 sons. Roosevelt had 1 daughter and 5 sons. Winner: Roosevelt*

1940: Roosevelt vs Wilkie: Roosevelt had 1 daughter and 5 sons. Wilkie had 1 son. Winner: Roosevelt*

1936: Landon vs Roosevelt: Landon had 2 daughters. Roosevelt had 1 daughter and 5 sons. Winner: Roosevelt.

1932: Hoover vs Roosevelt: Hoover had 2 sons. Roosevelt had 1 daughter and 5 sons. Winner: Roosevelt*

1928: Hoover vs Smith: Hoover had 2 sons. Smith had 2 daughters and 3 sons. Winner: Hoover**

1924: Davis vs Coolidge: Davis had 1 daughter. Coolidge had 2 sons. Winner: Coolidge**

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,


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.

Goodstein Sequences (Its his 100th birthday!)

LANCE: Bill, on Dec 15, 2012 it will be

Reuben Goodstein's

100th birthday.



BILL: Is he still alive? Will there be a conference in his honor? Free Food? Cake?



LANCE: No, no, and no. But you could blog about Goodstein sequences. (thinking: or they could just look it up here).



BILL: That is a Goodstein idea. You have a Goodstein sequence of good ideas.



I first define a sequence that is not a Goodstein sequence but will be good for education. Let n be a number. Say let n=42 Base 10. We then decrease the number by 1 but increase the base by one. We keep doing this. We get



42 base 10 = 42 base 10

41 base 11 = 45 base 10

40 base 12 = 48 base 10

3E base 13 = 50 base 10 (E stands for Eleven)

3T base 14 = 52 base 10 (T stands for Ten)

39 base 15 = 54 base 10


The sequence looks like its increasing. But note that it eventually gets to

30 base 24 = 72 base 10

2(23) base 25 = 73 base 10 (the ``units digit'' is 23)

2(22) base 26 = 74 base 10


OH MY. Its still increasing. But note that it eventually gets to

20 base 48 base 10 = 96 base 10

1(47) base 49 = 96 base 10

1(48) base 50 = 98 base 10

1(47) base 51 = 98 base 10


It seems to be at 98 for a while. Indeed we eventually get to

11 base 97 = 98 base 10

10 base 98 = 98 base 10

0(97) base 99 = 97 base 10


And from there on it it goes to 0.
Given n, how many iterations do you need to get to 0?
This function grows rather fast, but not THAT fast.
To prove that it goes to 0 you need (I think) an induction on an omega-squared ordering.

The true Goodstein sequences initially write the number in base 10 but
also writes the exponents in base 10 and does that as far as it can:


4 x 102 x 104 + 8 x 103 + 7 x 102 + 8 x 102 x 101 + 3 x 100




(This is called Hereditary 10 notation.) At each iteration we subtract 1 and then turn all of the 10's into 11's. More generally we write the number in base b and the exp in base b... etc and then subtract 1 and make all of the b's into b+1's. This sequence also goes down to 0. NOW how long does it take to goto 0. The function is not primitive recursive. Also, the theorem that states the sequence eventually goes to 0, cannot be proven in Peano Arithmetic.



I use Goodstein sequences as an example of a natural (one can debate that) function that is not primitive recursive. Ackermann's function comes up more often (lots more often) but is harder to initially motivate.



So Reuben Goodstein, wherever you are, I salute you!

The Fiscal Cliff

Unless the republicans and democrats get a deal before year's end, the country will head over the so-called "Fiscal Cliff" including a budget sequestration that will cause automatic cuts to most federal agencies. This will be a disaster for science, grants will be delayed or not awarded, perhaps even spending freezes on current funds. University presidents have banded together in my old state and new to drive this point home.



Don't panic too much about the fiscal cliff, which will be short lived if it happens at all. But the consequence may lead to deep short or long term budget cuts in science. If charitable deductions are eliminated, that can be a large hit on university endowments. Pell grants might also be in play. 




On the other hand, science and education has its friends in Washington, starting with Barack Obama. So maybe the whole fiscal mess will work out just fine for us and we can go back to worrying whether universities will be decimated by MOOCs. 

Book review column

(I am a bit behind on posting links to my book review column- this blog post is about the Third (of four) for the year 2012, and the fourth of four has already appeared. I'll post that one later.)



My second-to-last book review column can be found here. The file pointed to does NOT include the BOOKS I NEED REVIEWED since that has changed. For that go here.



The column has an editorial! In a book review column for CS theory books?! It is an editorial against the high prices of books and the fact that many books are NOT online. These are well known problems, so what of it? I could say why the publishers are at fault, but frankly, I don't know the economics of the book market. So instead I recommend the community to do the following:



Only buy books used or at a cheaper than list price (you probably already do this).

If you write a book then insist that the contract allow for it to be online for free. This is not as outlandish as it sounds: (1) Blown to Bits by Abelson, Ledeen, Lewis (which I reviewed in this Column) is a book for a wide audience--- it is a popular book about computers and society. Even so, it is available online for free here. (2) Some book companies of Math and Science books allow the author to have the book free on line.

When assigning a course textbook allow them to get earlier editions that are usually far far cheaper. There is no reason to insist they get the most recent edition.


Also of interest with regard to all of this- the Kistsaeung vs Wiley case:
here