Monday, May 25, 2020

Oldest Living Baseball Players- can you estimate...

(The Baseball season is delayed or cancelled, so I post about baseball instead.)

This post is going to ask a question that you could look up on the web. But what fun with that be?

The following statements are true

1) Don Larsen, a professional baseball player who played from 1953 to 1967, is still alive. He is 90 years old (or perhaps 90 years young---I don't know the state of his health).  He was born Aug 7, 1929. He is best know for pitching a perfect game in the World Series in 1956, pitching for the Yankees. He played for several other teams as well, via trades (this was before free agency).
(CORRECTION- I wrote this post a while back, and Don Larsen has died since then.)

2) Whitey Ford, a professional baseball player who played from 1950 to 1967, is still alive. He is 91 years old (or perhaps 91 years young---I don't know the state of his health).  He was born Oct 21,  1928. He had many great seasons and is in the hall of fame. He played for the New York Yankees and no other team.

3) From 1900 (or so) until 1962 there were 16 professional baseball teams which had 25 people each. From 1962 until 1969 there were 20 teams which had 25 people each. There were also many minor league teams.

4) The youngest ballplayers are usually around 20. The oldest around 35. These are not exact numbers

SO here is my question: Try to estimate

1) How many LIVING  retired major league baseball players are there now who are older than Don Larsen?

2) How many LIVING retired major league baseball players are of an age between Don and Whitey?

3) How  many LIVING retired major league baseball players are older than Whitey Ford?

Give your REASONING for your answer.

Tuesday, May 19, 2020

Obit for Richard Dudley

Richard M. (Dick) Dudley died on Jan. 19, 2020 (NOT from Coronavirus).You can find obituaries for him  herehere, and here and an interview with him from 2019  here.

Professor Dudley worked in Probability and Statistics. His work is now
being used in Machine Learning. Here is a guest-post-obit by
David Marcus who had Prof. Dudley as his PhD Thesis Advisor.


Guest Blog Obit by David Marcus:

Dick was my thesis advisor at M.I.T. After I got my Ph.D. in 1983, I went
to work in industry, so did not work closely with him, as some of his other
students did. But, I enjoyed working with him very much in graduate school.

Dick was very precise. His lecture notes and articles (and later his books)
said exactly what needed to be said and didn't waste words. In his classes,
he always handed out complete lecture notes, thus letting you concentrate
on the material rather than having to take a lot of notes.

Dick was very organized, but his office had piles of papers and journal
articles everywhere. There is a picture here.

Before Dick was my advisor, I took his probability course. My orals were
going to be towards the end of the term, and I was going to use probability
as one of my two minor areas. So, I spent a lot of time studying the
material. Dick gave a final exam in the course. The final exam was unlike
any other final exam I ever took: The exam listed twelve areas that had
been covered in the course. The instructions said to pick ten and for each
area give the main definitions and theorems and, if you had time, prove the
theorems. Since I had been studying the material for my orals, I didn't
have much trouble, but if I hadn't been studying it for my orals, it would
have been quite a shock!(COMMENT FROM BILL: Sounds like a lazy way to make up an exam, though on this
level of may it works. I know of a prof whose final was

Make up 4 good questions for the final. Now Solve them.


Once Dick became my advisor, Dick and I had a regular weekly meeting. I'd
tell him what I'd figured out or what I'd found in a book or journal
article over the last week and we'd discuss it and he'd make suggestions.
At some point, I'd say I needed to think about it, and I'd leave. I never
did find out how long these meetings were supposed to last because I was
always the one to end them.(COMMENT FROM BILL: It's good someone ended them! Or else you might never
had graduated :-) )

When I began working with Dick, he said he already had a full
load of students, but he would see if he had something I could work on. The
problem Dick came up with for me to work on was to construct a
counterexample to a theorem that Dick had published. Dick knew his
published proof was wrong, and had an idea of what a counterexample might
look like, so suggested I might be able to prove it was a counterexample.
In retrospect, this was perhaps a risky thesis problem for me since if the
student gets stuck, the professor can spend time figuring out how to do it.
But, in this case, presumably Dick had already put some effort into it
without success. Regardless, with Dick's guidance, I was able to prove it,
and soon after got my Ph.D.(COMMENT FROM BILL: Sounds risky since if Dick could not do it, maybe it's too hard.)

In 2003 there was a conference in honor of Dick's 65th birthday. All of his
ex-students were invited, and many of them attended. There was a day of
talks, and we all went out to dinner (Chinese food, if I recall correctly)
in the evening. At dinner, I asked Dick if any of his other students had
written a thesis that disproved one of his published theorems. He said I
was the only one.(COMMENT FROM BILL: Really good that not only was he okay with you disproving
his theorem, he encouraged you to!)

Thursday, May 14, 2020

Awesome Video from Women In Theory!

Below is an awesome video made by WIT (Women In Theory) on May 10, 2020 to celebrate the women in our field and in place of the Women in Theory Workshop that was supposed to take place
@Simons in June. ENJOY:

Monday, May 11, 2020

And the winners are ....

The Computational Complexity Conference has announced the accepted papers for the 2020 now virtual conference. Check them out!

Speaking of the complexity conference, my former PhD student Dieter van Melkebeek will receive the ACM SIGACT Distinguished Service award for his leadership in taking the conference independent. They grow up so fast! 

Robin Moser and Gábor Tardos will receive the Gödel Prize for their work giving a constructive proof of the Lovász Local Lemma, one of my truly favorite theorems as it gave a far stronger bound, a shockingly simple and efficient algorithm and an incredibly beautiful proof. Back in 2009 Moser gave my all-time favorite STOC talk on an early version of the paper. I (and others) sat amazed as his algorithm and proof came alive. During the talk I asked Eric Allender sitting next to me "Are we really seeing a Kolmogorov complexity proof of the Lovász Local Lemma?" Yes, we did.

Cynthia Dwork will receive the Knuth prize given for her life's work. The prize would be justified by her work on distributed computing alone but it is her leadership in formalizing Differential Privacy, one of the coolest concepts to come out of the theoretical computer science community this century, that will leave her mark in theory history. 

Thursday, May 07, 2020

Vidcast on Conferences

Bill and Lance have another socially-distanced vidcast, this time with Lance telling the story of two conferences (ACM Economics and Computation and the Game Theory Congress). As mentioned in the video the Game Theory Congress has been postponed to next year. Also mentioned in the video, for a limited time you can read Lance's book on P v NP on Project Muse.

Monday, May 04, 2020

Why is there no (d,n) grid for Hilbert's Tenth Problem?

Hilbert's 10th problem, in modern language is:

Find an algorithm that will, given a poly over Z in many variables, determine if it has a solution in Z.

This problem was proven undecidable through the work of Davis, Putnam, Robinson and then
Matiyasevich supplied the last crucial part of the proof.

Let H10(d,n) be the problem with degree d and n variables.

I had assumed that somewhere on the web would be a grid where the dth row, nth col has

U if  H10(d,n) is undecidable

D if H10(d,n) is decidable

? if the status of H10(d,n) was unknown.

I found no grid. I then collected up all the results I could find here

This lead to the (non-math) question: Why is there no grid out there? Here are my speculations.

1) Logicians worked on proving particular (d,n) are undecidable. They sought solutions in N. By contrast number theorists worked on proving particular (d,n) decidable. They sought solutions in Z.. Hence a grid would need to reconcile these two related problems.

2) Logicians and number theorists didn't talk to each other. Websites and books on Hilbert's Tenth problem do not mention any solvable cases of it.

3) There is a real dearth of positive results, so a grid would not be that interesting. Note that we do not even know if the following is decidable: given k in Z does there exists x,y,z in Z such that

x^3 +y^3+ z^3 = k. I blogged about that here

4) For an undecidable result for (d,n) if you make n small then all of the results make d very large.

For example

n=9, d= 1.6 x 10^{45}  is undecidable. The status of n=9, d=1.6 x 10^{45} -1 is unknown.

Hence the grid would be hard to draw.

Frankly I don't really want a grid. I really want a sense of what open problems might be solved. I think progress has gone in other directions- H10 over other domains. Oh well, I want to know about

n=9 and d=1.6 x 10^{45}-1. (parenthesis ambiguous but either way would be an advance.)

Friday, May 01, 2020

Predicting the Virus

As a complexity theorist I often find myself far more intrigued in what we cannot compute than what we can. 

In 2009 I posted on some predictions of the spread of the H1N1 virus which turned out to be off by two orders of magnitude. I wrote "I always worry that bad predictions from scientists make it harder to have the public trust us when we really need them to." Now we need them to.

We find ourselves bombarded with predictions from a variety of experts and even larger variety of mathematicians, computer scientists, physicists, engineers, economists and others who try to make their own predictions with no earlier experience in epidemiology. Many of these models give different predictions and even the best have proven significantly different than reality. We keep coming back to the George Box quote "All models are wrong, but some are useful."

So why do these models have so much trouble? The standard complaint of inaccurate and inconsistently collected data certainly holds. And if a prediction changes our behavior, we cannot fault the predictor for not continuing to be accurate.

There's another issue. You often here of a single event having a dramatic effect in a region--a soccer game in Italy, a funeral in Georgia, a Bar Mitzvah in New York. These events ricocheted, people infected attended other events that infected others. This becomes a complex process that simple network models can never get right. Plenty of soccer games, funerals and Bar Mitzvahs didn't spread the virus. If a region has hadn't a large number of cases and deaths is it because they did the right thing or just got lucky. Probably something in between but that makes it hard to generalize and learn from experience. We do know that less events means less infection but beyond that is less clear.

As countries and states decide how to open up and universities decide how to handle the fall semester, we need to rely on some sort of predictive models and the public's trust in them to move forward. We can't count on the accuracy of any model but which models are useful? We don't have much time to figure it out.