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.