Tuesday, August 30, 2016

I have consulted four times. Really!

Those who know me know that I work on stuff that is not readily applied. Or perhaps not applied at all. Certainly my current state of knowledge does seem like it would be useful to  a company. Many theorists, at one time in their lives, were excellent programmers. (For example, Lance helped write a program that played Othello see here and an email system see here.) I have no such stories. I took ugrad compiler design and ugrad Operating Systems as a grad student (not at the same time!).
I was taking Operating systems and TAing Aut theory. Dave (I forget his last name) was taking Aut theory and TAing Operating systems. We both got B's which you can regard as either very good or very bad planning.

Anyway, I never was a programmer. Could I have been a good programmer? Irrelevant! Would real world experience have helped my research? Very hard to know, but prob yes.

Four times I have worked for a real world company of some sort (never for more than a two months) and I always wondered Gee, I don't know anything they would care about. But in all four cases they seem to like what I did for them.  Why?

For two of the four I signed an NDA (Non Disclosure Agreement) so I will need to talk in general terms.

1) I was hired to find out which of two ways to schedule jobs was better. I did some easy math, did some easy simulations, found out that it didn't matter much. I think they knew that, but having someone with a PhD tell them comforted them.

2) I was hired to find out why the Operating System was so slow. I had already had the course in OS but it didn't help at all. I did some easy math that identified some of the problems, but told them that they had a more overwhelming problem and what it was. I think they sort-of knew this, but I clarified it for them. AFTER the course I took a course in queuing theory since the job peaked my interest. If I had the course before the job it would  not have helped.

3) I was hired to do some statistical work. I wrote a report detailing the methods that I used, and then I used them. Everything I did was elementary statistics. The techniques were standard. But they really appreciated having it all laid out for them. Originality was not needed, just using known stuff.

4) A company working on SAT Solvers- I helped clear up some misconceptions they had.

I suspect that 3/4 of the people reading this blog could do 3/4 of the consulting I've done. What I learned from these experiences is

(1) just knowing math in a general sense may be all they need,

(2) you can pick up what you need,

(3) sometimes they just need someone with a degree to tell them what they already know.

In all four cases I was intrigued by having to solve a REAL problem as opposed to a CLEAN math problem.

Thursday, August 25, 2016

1956 Was a Fine Vintage

Bill sends me an email last week with the subject "Our field is getting old!" and talks about upcoming 60th birthday/retirement conferences he's invited to, all of which I've been invited to as well. Bill's subject line should have read "We're getting old."

Here's what's upcoming:
  • Avi Wigderson's 60th celebration before FOCS in New Jersey, October 5-8. Avi is a giant in computational complexity and the event has an amazing line-up of speakers.
  • Albert Meyer's retirement celebration at MIT, November 11. 
  • Rod Downey's 60th symposium in New Zealand, January 5-8.
  • Eric Allender and Michael Saks will have a joint 60th celebration at DIMACS in New Jersey, January 26-27.
Surely I've missed some. Feel free to add in the comments.

Theoretical computer science has a tradition of holding a symposium in honor of a 60th birthday, typically organized by the PhD students. I co-organized such a celebration for my advisor Michael Sipser two years ago. 60 is a good age, a time to look back but not quite the end of a career. 

Janos Simon giving toast to Juris Hartmanis (center).
The first 60th I attended was for Juris Hartmanis, one of the founders of computational complexity, back in 1988 at the 3rd Structure in Complexity Theory (now Computational Complexity Conference) meeting in DC. The conference announcement required everyone to wear a jacket and tie, the first and probably last time I will see a bunch of complexity theorists all dressed up.

Juris was also the first faculty retirement I attended in 2001 at Cornell. Retirement celebrations are generally organized by the department.

Many of the first generation of CS theorists from the 60's and 70's are hitting retirement age. The 1980s saw an explosion in CS theory PhDs and many of them turn 60 in the near future. Expects lots of celebrations, great speakers and remembering many great careers. 

Monday, August 22, 2016

Chrisitan Comment on the Jesus Wife Thing misses the important point

In 2012 a Professor of Divisinity at Harvard, Karen King, announced that she had a fragment that seemed to indicate that Jesus had a wife. It was later found to be fake.  The article that really showed it was a fake was in the Atlantic monthly here.  A Christian Publication called Breakpoint  told the story: here.

When I read a story about person X being proven wrong the question upper most in my mind is: how did X react?  If they retract then they still have my respect and can keep on doing whatever work they were doing. If they dig in their heels and insist they are still right, or that a minor fix will make the proof correct (more common in our area than in history) then they lose all my respect.

The tenth paragraph has the following:

Within days of the article’s publication, King admitted that the fragment is probably a forgery. Even more damaging, she told Sabar that “I haven’t engaged the provenance questions at all” and that she was “not particularly” interested in what he had discovered.

Dr. King should have been more careful and more curious (though hindsight is wonderful)  initially. However, her admitting it was probably a forgery (probably?) is ... okay. I wish she was more definite in her admission but... I've seen far worse.

A good scholar will admit when they are wrong. A good scholar will look at the evidence and be prepared to change their minds.

Does Breakpoint itself do this when discussing homosexuality or evolution or global warming. I leave that to the reader.

However, my major point is that the difference between a serious scientist and a crank is what one does when confronted with evidence that you are wrong.

Thursday, August 18, 2016

Predicting in Changing Environments

The New York Times yesterday ran a story connecting climate change to the Louisiana flooding.
The National Weather Service reports that parts of Louisiana have received as much as 31 inches of rain in the last week, a number Dr. Easterling called “pretty staggering,” and one that exceeds an amount of precipitation that his center predicts will occur once every thousand years in the area.
Dr. Easterling said that those sorts of estimates were predicated on the idea that the climate was stable, a principle that has become outdated.
The third National Climate Assessment, released in 2014 by the United States Global Change Research Program, showed that “the amount of rain falling in very heavy precipitation events” had been significantly above average since 1991.
However, the research did not identify the South as one of the areas of greatest concern; the increase was found to be greatest in the Northeast, Midwest and Upper Great Plains regions of the United States.
In short climate change means our old prediction models of the weather no longer apply. On top of that, new models that tried to take into account climate change predicted heavier rains but not in that area of the country.

The weather is hardly the only predictions gone bad this year. From Nate Cohn's What I Got Wrong About Donald Trump
Did he have a 1 percent chance to win when he descended the escalator of Trump Tower last June? Twenty percent? Or should we have known all along?
Was Mr. Trump’s [republican nomination] victory a black swan, the electoral equivalent of World War I or the Depression: an unlikely event with complex causes, some understood at the time but others overlooked, that came together in unexpected ways to produce a result that no one could have reasonably anticipated?
Or did we simply underestimate Mr. Trump from the start? Did we discount him because we assumed that voters would never nominate a reality-TV star for president, let alone a provocateur with iconoclastic policy views like his? Did we put too much stock in “the party decides,” a theory about the role of party elites in influencing the outcome of the primary process?
The answer, as best I can tell, is all of the above.
I do think we — and specifically, I — underestimated Mr. Trump. There were bad assumptions, misinterpretations of the data, and missed connections all along the way.
We also had bad predictions on Brexit and one factor in the 2008 financial crisis was a heavy reliance on historical patterns of housing prices.

We have at our fingertips incredible prediction tools from machine learning models to prediction markets. Not all things change, our models trained to recognize cat pictures will continue to recognize cat pictures for a long time running. But as we continue to rely more and more on data driven predictions and decisions, be prepared for more and more surprises as underlying changes in the environmental, political and financial climates can pull the rug out from under us.

Monday, August 15, 2016

Is the examiner being pedantic? Whats really going on here?

The following are two real conversations.  For each one: (1) Is the examiner correct?, and
(2) Where and when do you think this conversation took place?

I give the answers below so you may want to read, stop and think, and then read on.


EXAMINER: What is the definition of a circle?

STUDENT: The set of points equidistant from a given point.

EXAMINER:  Wrong! It is the set of ALL points equidistant from to a given point.


EXAMINER: What is the definition of a circle?

STUDENT:  It is the set of all points equidistant from a given point.

EXAMINER: WRONG! You did not specify that the distance is nonzero.

AN ANSWER I HAVE HEARD FROM SOME NON-MATHEMATICIANS: Since math people are  pedantic and formal to an absurd level the examiner is correct.

REAL ANSWER: Nobody in math would be that pedantic.  In the old USSR, entrance exams for
Moscow State University were rigged so that Jewish students could not pass.  The following is a quote from

Bella Abramovna Subbbotovskaya and the Jewish People's university, By G. Szpiro. Notices of the AMS Vol 54,  . 1326--1330. Article is here

The first story in it happened to Edward Frenkel when he was a 16-year-old taking the oral entrance exam to Moscow State University in 1984, recounted in his book Love and Mathematics, which I reviewed here.

Jews -- or applicants with Jewish-sounding names -- were singled out for special treatment.  On one occasion a candidate was failed for answering the question what is the definition of a circle with
 the set of points equidistant to a give point. The correct answer, the examiner said, was the set of all points equidistant to a given point.  On another occasion an answer to the same question was deemed incorrect because the candidate had failed to stipulate that the distance had to be nonzero.

A different technique used on the entrance exams was to give Jewish students problems that had simple solutions which were extremely difficult to find.  The simplicity of the solution made appeals and complaints difficult.  Some of these problems and their history is in this article:

Killer Problems by Tanya Khovanova and Alexey Radul, The American Mathematical Monthly ,Vol 119, pp. 815--829.Article is here (link is to arxiv version where title is Jewish Problems.)

This is of course apalling; however, I have another issue to raise. Not allowing some part of your population to contribute  is just... idiotic. What I really want to know is why did they do this when it so clearly worked against their interests. How would an intelligent defender of this system defend it? By intelligent I mean someone who knows that Jews are not FILL IN ANY FALSE NEGATIVE BELIEF ABOUT JEWS.  By intelligent I also  mean someone who actually sees the downside. In other words, how would they fill in the following sentence:

The downside is that people who are talented in math and other fields do not get to contribute to our society, but the upside is FILL IN THE BLANK.

For more information on this, but not really an answer to my question, see the Wikipedia entry on anti-semitism in Russia here.

Thursday, August 11, 2016

Robin Hanson's Ems

Robin Hanson an economist at George Mason and author of the Overcoming Bias blog, has a new book The Age of Em: Work, Love and Life when Robots Rule the Earth. Em stands for brain emulation, a computerized version of a human brain processes including consciousness, all the wants, desires and faults of a human brain. An em can be created by copying from a human brain or another em, it can be stored and restored, slightly tweaked and can run faster or slower depending on the power consumption. Reminds me a bit of the cookies in the White Christmas episode of Black Mirror. Hanson also talks about clans, the collection of all the ems that descend from a particular human.

The book has two distinct parts. The first gives a plausible physical and social explanation as to how and why the em world will come to be. Hanson gives the odds of such a world developing at one in a thousand. I put the odds much lower, especially since we have no true understanding of consciousness. For example if consciousness requires quantum entanglement, we would have no hope of copying into an em without destroying the old em (or human) it came from. More likely I expect we would have em-like machines that can perform a number of human-like tasks but won't have any true consciousness. Nevertheless I'd acknowledge that Hanson's world is at least possible given our current knowledge of the brain.

I enjoyed more Hanson's discussion about the world of the ems given that they exist. Hanson takes a science, as opposed to a science fiction, approach to the topic, carefully thinking about how ems would work as a clan, how they interact politically, socially and economically. You can see the variety of topics in the table of contents on the book's website. For example, Hanson argues that it makes economic sense to have ems split off as "spurs" to do more menial tasks in parallel in exchange for a short working life, as short as a few minutes, and a long retirement, with the retirement in a slower low-powered mode. Hanson has done some strong research and advocating for prediction markets (we even have a joint paper on the topic) that there is no surprise that markets show up as a decision making systems for ems.

I don't agree with all of Hanson's conclusions, in particular he expects a certain rationality from ems that we don't often see in humans, and if ems are just human emulations, they may not want a short life and long retirement. Perhaps this book isn't about ems and robots at all, but about Hanson's vision of human-like creatures as true economic beings as he espouses in his blog. Not sure it is a world I'd like to be a part of, but it's a fascinating world nevertheless.

Sunday, August 07, 2016

A Game Theory Conference! That sounds like fun!

Bill: Lance just came back from Games, a conference on Game Theory.

Darling: That sound like fun! From what you tell me there is some nice math behind
Monopoly(see here for a paper on Monopoly as a Markov Process), Risk (see here for a paper on using Markov chains in the game Risk. Was Markov a game player?) and other FUN games.

Bill: Uh, I don't think they talked much about those kinds of games.

Darling: Darn. Did they talk about those really boring math games like Dup-Spoiler games, those games that AD is about, Gale-Stewart Games, Banach-Mazur games, Martingales, Pebble games, Communication complexity games. Oh, and Combinatorial games like NIM which can be sort of fun.Or did they talk about computers that play Chess and similar games? Or did they have talks on things like Chess being EXPTIME complete. Or did they talk about the Unique Game Conjecture.

Bill: Most of the talks were about setting up a system so that all players acting in their own best interest is also good for the system. Like an auction system where it is a players best interest to bid what they actually think the item is worth.

Darling: So there are no Games at a Game Theory conference?

Bill: There were a few papers on Poker, but that's it.

Darling: They should change the name of the field.

Bill:  Lance tells me that Ehud Kalai has suggested  Game Science. 

Darling: So long as the word Game is in the title they should have fun games there. Oh well.

Wednesday, August 03, 2016

Seymour Papert (1928-2016)

Seymour Papert, the great AI pioneer, passed away Sunday at the age of 88. In the theory community we best know him for his 1969 book Perceptrons with Marvin Minsky, who died earlier this year. In that book they show that a perceptron (what we now call a weighted threshold function) cannot compute parity, one of the first examples of a circuit lower bound.

In the summer of 1982 I worked a a computer camp in Los Olivos, California and we taught the kids programming with the Logo programming language, a simple functional language co-created by Papert and Wally Feurzeig. In Logo you controlled a virtual turtle that carried a pen and you could give simple instructions like raising and lowering the pen, moving forward and backward and turning. With simple functions one could create complex diagrams, like the one above. Normally you would see the diagrams on a screen but we also had a physical electronic turtle that would move and draw on a sheet of paper. The kids loved it since they could see the results of their programs as a picture while they learn programming functions and recursion without realizing it.

You can play with Logo at Turtle Academy  Logo set the stage for control of actors in many other computer languages designed for children including the tasks for the popular Hour of Code.

Let's raise our turtle pens to honor Papert and the many that he brought into the world of computing.