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

# Computational Complexity

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

## Thursday, July 29, 2021

### Covid Stats

## Sunday, July 25, 2021

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

## Friday, July 23, 2021

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

## Sunday, July 18, 2021

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

## Sunday, July 11, 2021

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

## Tuesday, July 06, 2021

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

## Thursday, July 01, 2021

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

## Sunday, June 27, 2021

### Someone thinks I am a fine artist! Why?

A while back I got an email asking me to submit to a Fine Arts Journal. Why me? Here are some possibilities:

1) They were impressed with my play:

**Sure he created the universe, but would he get Tenure?** (see here) which did get into a play-writing contest and was performed (one of the actresses scolded me since I took a slot from *a real* *playwrigh*t).

2) They were impressed with my **Daria Fan Fiction** (see the four entries here labelled as Daria Fan Fiction).

3) They were impressed with my play **JFK: The Final chapter** (see here). Unlikely since this was rejected by a play writing contest and is not well known (as opposed to my other works in the fine arts which are well known?)

4) They were impressed with my collection of satires of Nobel Laureate Bob Dylan (here) .

5) They were impressed with some subset of (a) complexityblog, (b) Problems with a Point, (c) Mathematical Muffin Morsels, and (d) Bounded Queries in Recursion Theory. Or maybe just having 3 books on amazon is their threshold. If it's complexityblog then Lance and I should co-author something for them.

6) It is a vanity-journal where you pay to publish. So why email me who (a) is not an artist, (b) is not a fine artist, and most important (3) **does not think of himself as a fine artist**. The PRO of emailing me or people like me is they cast a wide net. The CON is--- there is no CON! It costs nothing to email me, and emailing me does not affect their credibility. That still raises the question of how they got my name.

7) Could it be a phishing? If I click on something in the email would they get my credit card number? Their email begins *Dear Professor* not *Dear Professor Gasarch. * So they know I am a professor. Then again, I have known of ugrads who get emails that begin *Dear Professor*. (The emails to HS student Naveen and ugrad Nichole in the story I tell here were addressed to *Dear Professor.) *

8) They mistook me for my parents who, in 1973, put together an anthology of short stories titled *Fiction:The Universal elements*, for a Freshman Comp course my mom taught, see here. I note that their book ranks around 18,000,000, so even that explanation is unlikely. Actually the rank changes a lot- it was 12,000,000 this morning. Still, not what one would call a best seller. It's fun to see what is doing better: *Bounded Queries in Recursion Theory (currently at around rank 6.000.000) * or *Fiction: The Universal Elements.*

If I ever get one of these emails from a History Journal I will submit my Satirical *Ramsey Theory and the History of Pre-Christian England: An Example of Interdisciplinary Research* (see here) just to see what happens- but I will stop short of paying-to-publish. Or maybe I will pay-to-publish so that the next time I try to fool a class with it I can point to a seemingly real journal which has the article.