Covid Stats

A stat often quoted: About 97% of hospitalized coronavirus patients have not been vaccinated.  

People take this as proof that once vaccinated no worries. But I have so many challenges with this statistic.

• This statistic is down from 100% a year ago. Are vaccines working poorer now?
• There are likely correlations to those vaccinated and those who take precautions like mask wearing and social distancing, though I'm sure which way those correlations go.
• Those unvaccinated are more likely to be near others unvaccinated so more likely get infected and hospitalized.

Even though one shouldn't draw the conclusion from the statistic, that doesn't mean the conclusion is false. The gold standard are the double-blind vaccine trials which clearly showed the vaccines more efficient and safe. So get the vaccine, not that this blog post will convince those who have been making the conscious choice not to vaccinate to change their minds.

The other stat I found odd was that the life expectancy dropped 1.5 years in 2020. This doesn't mean on average we'll live 1.5 year less. Rather it means that someone who lives their whole life in 2020 conditions, widespread Covid without vaccines, would on average live 1.5 years less than someone who live their entire life in 2019 conditions pre-Covid.

Oddly enough if you made it to 2021 your life expectancy will probably increase (assuming you've been vaccinated). We made tremendous progress in understanding vaccine technology in 2020. Also people with conditions that could have limited their later life span were more likely to be fatal Covid victims, meaning those who are left would live longer.

I wish problems I have with computers really were my fault

 As you know, the website for out for a few days, as Lance explained here.

When I first could not get to the this blog  my thought was

OH, I must have changed some setting by accident. When Lance gets back (he was on vacation) he'll know how to fix it. Bad timing that it happened when he was gone, though prob not an accident- with him on vacation I was at the site more often and had more of a chance to screw things up. AND Lance will tell me what I did and I'll know to not do it again. And I will learn more about how this all works which will help me in the future!

When Lance got back we found out that NO Bill didn't do anything wrong. The blog site company  that we work with did an update and BLAH BLAH BLAH.  Reminds me of the theme behind the TV show Seinfeld: No Hugs, No Learning. At least no learning. I am not in the slightest more enlightened. 

Lance worked with them and YADA YADA YADA the problem is fixed, so I am very happy about that. 

On the one hand I wish it had been my fault so I would learn something.  On he other hand, if it was my fault would it have been as easy to fix? Would I really have learned something? 

When something does not work my protocol is

1) Turn the machine off and on again (e.g., log out and log in again). I want to say 

this works surprisingly often

but I doubt this surprises any of my readers, or is even news to them.

2) Spend at most 5 minutes trying to fix it myself . You will soon see that 5 minutes is a good choice for me.

3) Ask staff or Lance or Darling or my TA  (depending on the problem). 

4) They tell me to log off and log on again. When I tell them I already have they do something magical and it works again. I then ask them:

a) Could I have fixed this myself. 2/3 of the time the answer is no. They don't mean intellectually. They mean that I do not have access to what I need to fix it.

b) Did I do something wrong? I want to know so I won't do it again. about 99/100 times the answer is that I did nothing wrong (I don't recall that last time that I did).

Given a and b, I think 5 minutes is all the time I want to spend to try to fix it myself. 

Technical Difficulties

After returning from vacation last weekend (hello North Dakota--my 49th state visited), all sorts of odd problems arose. This blog stopped working, a P v NP paper was published on the ACM Transactions of Computing website and my personal emails were getting marked as spam. All is better, I hope.

Years ago I donated the URL computationalcomplexity.org to the Computational Complexity Conference, coincidentally held this past week, with the condition that I could continue to use the "blog" subdomain for this blog. Organizations continue but the people in them change, and when the website was "upgraded" on Saturday the pointers to make this blog work were left out. Thanks to Ashwin Nayak for getting it all straightened out and we're back online.

For the ToCT paper, a paper claiming to reduce 3-SAT to 2-SAT, and thus show P = NP, was originally rejected by the journal but a "disposition field" got inadvertently set to accept and wasn't caught until it showed up online. Editor-in-Chief Ryan O'Donnell quickly got on the case and ACM has removed the paper. P v NP remains as open as ever.

Fixing the email required me to learn far more about SPFs than I ever wanted to know.

By the way if anyone in Idaho wants to invite me to give a talk, I might be interested.

Political Intersections: Trump honors Antifa member who was shot dead by police

 1) Trump and other reps have said the following about the Jan 6 event at various times:

a) The Jan 6 event was freedom fighters who were fighting the noble fight to overturn a fraudulent election. Rah Rah!

b) The Jan 6 event was a peaceful protest to overturn a fraudulent election. 

c) The Jan 6 event was democrats trying to make republicans look bad.

d) The Jan 6 event was Antifa. (See here)

e) Ashli Babbitt (a protestor who was shot by police at the Jan 6 event) should have been honored by flying the flag at half-mast (see here) 

If we take the intersection of d and e we find that Trump wants to honor a member of Antifa who was shot by police. 

To be fair, Trump is entitled to change his mind. But I wonder- did he ever really think it was Antifa or was that a talking point? If he really thought so then  when did he change his mind? I ask non rhetorically---  NOT a `gotcha question'

(NOTE: I wrote this post a while back. Since then Trump and some other republicans are tending towards the Freedom Fighters narrative.) 

2) Vaccines:

a) Some people think that the vaccines are bad to take. I suspect they would give some (incorrect) health reasons, while the real reason may be political. (One reason is that the vaccine make you magnetic. That sounds awesome! Others think that there is a microchip in the vaccine so that Bill Gates can track our movements. Gee, Mark Zuckerberg can already do that. Some thing it will rewrite our DNA. A bio major I know  tells me that such people are confusing messenger RNA with DNA. Great- we can now have a nice conversation and point out where they are wrong.) 

b) Some people think we should NOT give vaccines to poor countries that need them, or to people in prison,  since Americans should have priority. (NOTE- from a purely health-viewpoint this is not correct since a pandemic does not respect boundaries- if there is an outbreak in a diff country or in a prison it will affect people not in those countries and not in prison.) 

Are there people who believe a and b? I ask non-rhetorically. 

I am not surprised when people hold contradictory thoughts in their heads, but these two cases just struck me as particularly strange. Not sure why.

 

Would you take this bet (Part 2) ?

 Recall from my last post (here)

I offer you the following bet: 

I will flip a coin.

If  HEADS you get 1 dollar and we end there.

If TAILS I flip again

If  HEADS you get 2 dollars and we end there.

If  TAILS I flip again

If HEADS you get 4 dollars and we end there.

If TAILS I flip again

The expected value is infinity.

Would you pay $1000 to play this game?

Everyone who responded said NO. Most gave reasons similar to what I have below. 

This is called The St Petersburg Paradox. Not sure it's a paradox, but it is odd. The concrete question of would you pay $1000 to play might be a paradox since most people would say NO even though the expected value is infinity.  See here for more background.

Shapley (see here) gives a good reason why you would not  pay $1000 to play the game, and also how much you should pay to play the game (spoiler alert: not much). I will summarize his argument and then add to it. 

1) Shapley's argument: Lets say the game goes for 40 rounds. Then you are owed 2^{40} dollars. 

The amount of money in the world is, according to this article around 1.2 quadrillion dollars  which is roughly 2^{40} dollars. 

So the expected value calculation has to be capped at (say) 40 rounds. This means you expect to get 20 dollars! So pay 19 to play. 

2) My angle which is very similar: at what point is more money not going to change your life at all? For me it is way less than 2^{40} dollars. Hence I would not pay 1000. Or even 20. 

Exercise: If you think the game will go at most R rounds and you only wand D dollars, how much should you pay to play? You can also juggle more parameters - the bias of the coin, how much they pay out when you win. 

Does Shapley's discussions  resolve the paradox? It depends on what you consider paradoxical. If the paradox is that people would NOT pay 1000 even though the expected value is infinity, then Shapley  resolves the paradox  by contrasting the real world to the math world. 

Would you take this bet (Part 1) ?

 I am going to present a well known paradox (I didn't know it until last week, but the source I read said it was well known) and ask your opinion in this post, and reveal my thoughts in my next post.

I don't want you to go to the web and find out about it, I want your natural thoughts. Of course I can't stop you, but note that I did not give the name of the paradox. 

Here it is:

I offer you the following bet: 

I will flip a coin.

If  HEADS you get 1 dollar and we end there.

If TAILS I flip again

If  HEADS you get 2 dollars and we end there.

If  TAILS I flip again

If HEADS you get 4 dollars and we end there.

If TAILS I flip again

etc. 

1) Expected value: 

Prob of getting 1 dollar is 1/2

Prob of getting 2 dollars is 1/2^2

Prob of getting 2^2 dollars is 1/2^3

etc

Hence the Expected Value is 

1/2 + 1/2 + 1/2 + ... = INFINITY

QUESTION: Would you pay $1000 to play the game?

Leave your answer in the comments and you may say whatever you want as well,

but I request you don't give the name of the paradox if you know it. 

Intersecting Classes

If you have two complexity classes that have complete sets, the intersection might not, for example NP ∩ co-NP. The world of total-function classes acts differently.

Christos Papadimitriou and others defined a number of classes based on finding solutions to problems where solutions are known to exists for some combinatorial reason. While TFNP, the set of all such problems, might not have complete sets, all the other classes are defined basically based on the complete search problem for the class, such as PLS, finding a local minimum. If you have two such classes A and B with complete search problems A and B define the search problem D as 

D(x,y): Find a solution to either A(x) or B(y)

D is complete for the intersection of A and B: First the problem D is in A since you can reduce the problem of finding a solution to either A or B to finding a solution to A. Likewise D is in B.

Suppose you have a problem Z in A∩B. Then since Z is in A and A is complete for A, finding a solution to Z(u) reduces a finding a solution of A(x) where x is easily computed from u. Likewise Z(u) reduces to finding a solution of B(y). So whatever solution D(x,y) gives you, it allows you to find a solution to Z(u). Thus D is complete for A∩B.

Some people nerd out to helicopters on mars. I nerd out to the complexity of complete sets. 

I learned about complete sets of intersections of total function classes from the talk by one of last week's STOC best paper awardees, The Complexity of Gradient Descent by John Fearnley, Paul W. Goldberg, Alexandros Hollender and Rahul Savani. The part above was well known but the paper goes much further.

Consider PPAD famously with Nash Equilibrium as a complete problem and PLS. PPAD ∩ PLS has complete sets by the argument above. But we can go further.

The class CLS is a variation of PLS where you find a local minimum in a continuous domain under some Lipschitz conditions and is known to sit in the intersection of PPAD and PLS. Fearnley et al. look at finding a minimum using gradient descent (the main tool for deep learning), and showing not only is it CLS-compete but complete for PPAD ∩ PLS. As a consequence CLS = PPAD ∩ PLS. Pretty cool stuff.