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

# Computational Complexity

Computational Complexity and other fun stuff in math and computer science from Lance Fortnow and Bill Gasarch

## Monday, May 25, 2020

## 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 here, here, 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.

## Tuesday, May 05, 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.

## Wednesday, April 29, 2020

### A Guest Blog on the Pandemic's affect on disability students

I asked my Grad Ramsey Theory class to email me about whatever thoughts they have on the pandemic that they want to share with the world, with the intend of making some of them into a blog post. I thought there would be several short thoughts for one post. And I may still do that post. But I got a FANTASTIC long answer from one Emily Mae Kaplitz. Normally I would ask to shorten or edit a guest post, but I didn't do that here since that might make it less authentic.

Here is Emily Kaplitz's email (with her enthusiastic permission)

--------------------------------------------------------------------------------------

Ok so this might be super ranty, (It definitely is.) but I think it is super important to bring up in a blog post written by an academic that will be probably read by other academics.

The students that are being most affected by this pandemic with online learning are disability students. As a disability student, we carefully cultivate the way that we learn best based off of years of trial and error. This is harder than anything else, we have to face in our lifetime. Most of the time disability students are left on the back burner and that statement is so much more prevalent right now. My friends brother is autistic. He is struggling so much right now because he is at home. Disability students learn what environment works best for them and at home is usually not the best place. We have to split our lives into different boxes that each have different tools to help us get our brains to focus and work well when we need them too. Disability students will rely on everything being planned out, so that they can succeed. Teachers and professors cannot understand the stress and strain that having to work at home puts on the student. Every time I go to another school, it is a struggle to figure out what new thing I need to add into the mix and what old thing I need to throw away. It's exhausting, but when I go from one school to another I at least know that the basics are the same. I sit in a classroom, the professors lecturer, and then I do work at home that is assigned to me. Changing to online changes that dynamic so much. A professor cannot see when a student is visibly struggling with a topic because we'll all behind computers. A neurotypical person might ask, "well why don't you just ask a question? Why don't you just let the professor know that you don't understand". Let me answer that simply. If all your life you've been silenced because of something that you cannot control, is your first reaction to speak out or to stay silent. It is so hard for disability students to ask a question after we've been labeled the dumb kid. Every time we ask a question, we always have the thought of: is this going to make me sound stupid. We've worked so hard to eliminate that word from our vocabulary and from others who will throw that word back at us. Disability students are being left in the hands of their parents and teachers/professors who do not understand us and our needs even if they try to or want to. It is so hard for us to explain what our normal is because we don't live your normal and therefore don't know the difference. Many disability students have their confidence slashed the moment they enter a classroom and realize that they are not like the other kids. Even more so because they don't understand why they aren't. Disability students are one of the most hard-working individuals when we have a cheerleader to cheer us on because it's hard. It's harder than anything anyone has to do. Because no one listens to you when you are stupid and no one cares for you if you're not easy to care for unless they are given a specific reason to. Fighting a losing battle every day is awful. Now imagine all of your weapons that you have carefully crafted over the years have been taken away and you are left defenseless. While we have things like ADS that are supposed to help support us, it's not enough. Just like putting a Band-Aid on an open infected wound will not be enough. Now more than ever we need to learn from this as academics. We need to learn that helping disability students does not only help disability students. It helps all students because all students learn differently. All students if given the chance can excel at any field that we put them in. We just have to figure out the best way to get that student to shine. That is one of the reasons why I am a PhD student right now. I saw in the tutoring center at my undergrad how many students came to me with so much frustration about something they are doing in class. Both students with disabilities and without. These students are constantly apologizing because they don't understand something. In one session by just changing the way that we talk about a subject the student was able to get it in less time than the professor taught it. I've had students come to me after an exam and tell me that the only reason they got the grade that they did was because in their head was my voice coaching them on a subject. We are not teaching optimally. We are teaching the way that it has been done for years and years and years and that is not the best way to teach. It might be the best way to teach the strongest links but really the link that matters the most is the weakest link that will snap under pressure because you can't pull a tractor with a broken link. Disability students think differently. Imagine how many impossible problems we can solve when we have people that think differently. But that's just my two cents as a disability student who is struggling and sees other disability students struggling every day. And really just wants to help all students succeed.

I blame any misspellings, grammar errors, and run on sentences on my speech to text and text to speech. This was a long email and if we were on tumblr, I would post a potato at the end. Since we aren't, I will leave this email with this. Thank you for taking the time to read this rant. Even if you don't include this in your blog post, I believe one person reading this has made the difference.

Thanks!

Emily Mae Kaplitz

Subscribe to:
Posts (Atom)