When Words Get Stretched Beyond Their Original meaning

STORY ONE:

 On a Jeopardy rerun with Alex Trebek the question (actually the answer, given the shows format) was (I paraphrase)

Who resigned his commision in the US Army Air Force in April 1941 after President Roosevelt publicly rebuked him for his views?

The answer (actually the question--Why does Jeopardy do this answer-question thing, drives me nuts!) was

Charles Lindbergh.

Alex Trebek then said  Charles Lindberg's views on WW II were not politically correct.

This really struck me since Politically correct means, to quote Wikipedia:

a term used to describe language, policies, or measures that are intended to avoid offense of disadvantage to members of particular groups in society. 

Wikipedia also adds that the term is generally used pejoratively with an implication that these policies are excessive or unwarranted. 

 But Alex Trebek is using the term to mean  incorrect or perhaps incorrect given what we know now or if you think history is written by the winners, then perhaps incorrect since Germany lost the war.  But my point is that I really don't think the term  politically incorrect  makes sense here.

STORY TWO

More recently I heard an anti-masker say

We should not let some woke school board take the right to not wear a mask away from parents and children.

Independent of if you are anti-mask-mandates or pro-mask-mandates, this seems like a strange use of the word  woke  which means, to paraphrase Wikipedia:

Having an awareness of racial prejudice, gender prejudice, sexual orientation prejudice, and the past and current discrimination they have and do cause. 

I've seen it both positively and negatively.

The anti-masker's using of the term seems odd in that mask wearing is not a woke issue. Perhaps he should have said 

We should not let some Nazi school board take the right to not wear a mask away from parents and children.

The term  Nazi while not actually correct, conveys that the school board is authoritarian. However, he really could not use the term that since he was was a neo-Nazi and proud of it. That raises a question: what pejorative  term can a Neo-Nazi use when they want to say someone is  Authoritarian? I ask non-rhetoically. 

But I am getting off topic here- my real point is that the word woke is being used to mean Authoritarian which is not even close to its original meaning. 

MY POINT

The above are examples of how a word in English may change its definition over time, which is not really news, but I found the examples interesting since I saw the origin of these words.

BILL, THIS IS A COMPLEXITY BLOG! SO TALK ABOUT COMPLEXITY. OR MATH!

In math do words change their meaning over time? Yes. Here are a few

Function: at one time `function' implicitly means a function that occurs in nature. So only continous and perhaps diff functions qualified. 

Sets: probably similar.

Efficient: At one time this was an informal notion (Joe Kruskal's paper on MST (see here) is an example of that), then it seemed to be P or perhaps BPP. For some its linear or O(n log n) with a small constant. Rather than say the notion changed, its more like it was never that well defined in the first place, and still isn't. 

Constructive: The many diff definitions of this word could be a blog post of its own. In fact, I thought it was, but I could not find it. I did find lots of blog posts that use the word constructive in diff ways. 

Elementary: Also has many definitions, though they are closer together than for Constructive. This one I did do a post on here

Trusting Scientists

 A tweet that made me think.

If you think you don't trust scientists, you're mistaken. You trust scientists in a million different ways every time you step on a plane, or for that matter turn on your tap or open a can of beans. The fact that you're unaware of this doesn't mean it's not so.

— Paul Graham (@paulg) July 26, 2021

The point here is subtle. We don't get on a plane because we "trust scientists", rather we do so because of the strong safety record of commercial aviation. I knew some physicists who won't get on a commuter plane because they worry about the science. Never stopped me.

It is science that we trust to tell us why planes fly, or the water is our tap is (mostly) safe and healthy. I'm not a big fan of beans but not because of the science. Of course I trust science that created the vaccines.

It's not just science, but solid engineering and lots and lots of testing. 

Science isn't always right or consistent. When I was a kid not that long ago, we had nine planets in this solar system, dinosaurs were killed off by climate change and homosexuality was a mental illness. Science is fluid, updating as we learn with new data, models and experimentation. Science is at its best when it doesn't trust itself.

Sometimes people say trust in science to reinforce their beliefs. I've seen smart people say "Trust in the science" about whether vaccinated people should wear masks with completely different conclusions.

I'm a scientist, should you trust me? Let me quote another Paul G. 

“There’s a slightly humorous stereotype about computational complexity that says what we often end up doing is taking a problem that is solved a lot of the time in practice and proving that it’s actually very difficult,” said Goldberg.

The quote comes from a recent Quanta Magazine article about Paul's recent work with John Fearnley, Alexandros Hollender and Rahul Savani on the hardness of gradient descent. Even many NP-complete problems these days can often be solved in practice.

Let's end with the quote attributed to statistician George Box, "All models are wrong, but some are useful". Science gives us ways to understand the world and we need to both trust in the science but know the limitations of what it has to say.

What are the most important 46 papers in Computer Science? Harry Lewis has a book about them!

 (Disclosure:  Harry Lewis was my PhD advisor. For a blog post on  disclosures and bias see my post on that topic here.)

Harry Lewis has a book out: Ideas that Created the Future: Classic Papers in Computer Science

He picked out the 46 (why 46? Why not 46?) classic papers in computer science and, for each one, has a short article saying why its important, and then has the paper itself, though perhaps shortened (leave out the boring parts) or in some cases he has an excerpt of a book (e.g., The Mythical Man Month which is why I blogged about that book recently here).

Harry Lewis has blogged about his book here where he points to my review which is in SIGACT News. 

OR you an use my link to my review here. 

The list of 46 papers had some constraints, so if you wonder why isn't X there it might have hit one of those constraints.

1) No paper past 1980 (he had to stop somewhere).

2) He preferred short readable papers to long or unreadable ones (don't we all!). Before thinking `Gee why isn't paper X in the book' go read paper X. 

3) Some papers cost to much to get permission to reprint. My review points to one such paper that I found 5 links to on the web. 

4) We don't need X papers on topic Y.

Of more interest is some papers that you had not heard of but we can now see are important.

For more thought, read my review!

For even more information, buy the book!

Recognizing Faces

I sometimes have trouble recognizing faces, matching faces to people I've interacted with in the past. It's not a disease like prosopagnosia, I can certainly tell the difference between faces and have no trouble with people I work with directly. But if I haven't seen someone in a while, I may not recognize them or confuse them for someone else. It's especially bad out of context, say running into a professor in my campus on the streets of Frankfurt. It's gotten worse with age but I've had challenges my whole life.

I have my coping mechanisms. I start a conversation to get enough clues to figure out who I'm talking to. I'll google an image before I'm supposed to meet someone I haven't seen in a while. Sometimes I'll just say "Remind me how to pronounce your name again". Sometimes I'll just say something embarrassing thinking the person I'm talking to is someone else.

Name tags are useful, if it isn't obvious you are looking at them. Zoom has been great--everyone's name is just there. I worry that 18 months of zoom meetings means I've lost much of my coping ability, much the way I can no longer navigate by maps the way I used to.

We have technological solutions but mostly unable to make use of them. Through the magic of machine learning, computers have gotten extremely good at recognizing faces. Nevertheless Google Googles actively prevented their one killer app, telling you who you were looking at, for privacy reasons. Perhaps they could limit it to people in your contacts with pictures you uploaded. It would only recognize people you already know.

I know I'm not alone, and I'm writing this post so others won't feel alone. And next time you see me and I look confused, remind me of your name.

Combing two posts: Blankface (Scott Aa) and Is Science Slowing Down? (Scott Al)

(I also posted this to the Less Wrong Website. At least I tried to- I don't quite know if or when it will appear there as its my first post there.) 

Some papers result from taking two papers and combining them. Perhaps nobody else had read both of them so you can say something new! Or (looking over this post) it may guide people to two really good papers, or in this case two really good posts. 

This blog will draw from two excellent blog posts.

Scott Aaronson  blogged on  his website Aug 2, 2021 about blankfaces, people who let stupid or undefined rules dictate what you can do  without apology (see his post for a better explanation). One example that struck me I quote

No, I never applied for that grant. I spend two hours struggling to log in to a web portal designed by the world's top blankfaces until I finally gave up in despair. 

Scott Alexander blogged  on LessWrong on Nov 26, 2018 about Is science slowing down? which answers with an emphatic yes. His point is science-per-researcher is much less than it used to be, and he has graphs and stats to prove it (see his post for the evidence and some speculation as to why this is) One of the reasons he gave struck me which I quote

Certain features of the modern academic system like undepaid PhD's, interminably long postdocs, endless grant writing drudgery, and clueless funders have lowered productivity. The 1930's academic system was ineed 25x more effective at getting researchers to actually do good research.

(A commenter reminded me that Scott Alexander himself dismisses this reason. I do not.) 

(I note that he gives other reasons as well, most notably for our field that the low hanging fruit is gone. Our lack of progress on P vs NP is likely that its a hard problem, rather than the reason above. Of course, if its solved tomorrow by an outsider without funding, I will happily be proven wrong.) 

Scott Alexander hits upon two types of blankfaces (without using the term).

Grant writing drudgery: the rules for how to submit get more and more detailed an onerous. This is  what Scott Aaronson was alluding to. There are other ways its drudgery as well. 

Clueless Funders: the people deciding who gets funded might not know the area (actually in my experience the grant I've reviews have been quite good and the problem is more not enough money to award all that are deserving.) 

SO I pose the following non-rhetorically as always

1) How big a factor is the slowing down of science that blankfaces get in the way?

2) What can we do about it?

Pole Vault Live Blogging

As I write this I'm watching the women's pole vault final in the Olympics. Of the 15 women who made the finals, only four remain after two heights.

To expand on my tweet, I find the pole vault the purest of the Olympic Sports. No electronic monitors and timers, no biased judges, no video review. No points deducted for bad form or failing to stick the landing. No disqualification for a false start or stepping over a line. Either you clear the bar without knocking it down, or you don't.

The high jump has similar properties, but just not as cool looking.

All four made the third height. Now onto 4.85 meters. An American, a Greek, a Brit and a Russian (sorry I meant member of the Russian Olympic Committee).

Back in the day, the TV coverage was rather limited. We'd only see the Americans and the medal winners with too much time spend on human interest backgrounds. Now in the streaming world I can watch every competitor. The good and the bad. Live as it happens.

The Russian Anzhelika Sidorova just cleared 4.85 on her first attempt. So did the Brit Holly Bradshaw and the American Katie Nageotte. The Greek Katerina Stefanidi missed her first attempt but decided to pass on the rest. All now go to 4.90 but Stefanidi only gets two attempts while the rest get three.

Stefanidi missed her first attempt at 4.90. She gets one attempt left.

Sidorova and Bradshaw fail to even reach the bar. Nageotte can't clear the bar.

Now the moment that means everything for Stefanidi. Her last attempt. Make it or the rest get the medals. Stefaidi fails to get a good plant and doesn't get into the air at all. Her Olympics are over.

Second attempt for the others. Sidorva and Bardshaw knock down the bar. Nageotte clears the bar, putting her in prime position. Go USA!

Imagine if we judged research papers this way. Either they get into a conference or they don't. Wait, that is they way they happen, although not always without biased judging.

Sidorova is passing on her last attempt at 4.90. Bradshaw goes for it but hits the bar. She has to settle for Bronze.

Bar is now at 4.95 meters. 

Sidorova gets only one attempt at 4.95. If she makes it, she takes the lead, if she misses, she gets the silver. 

Sidorova doesn't clear and the gold goes to the American Katie Nageotte! 

Just for excitement Nageotte is going for 5.01 meters, which would be her first over five meters in competition. In the men's pole vault, the Swede Armand Duplantis (great pole vault name!) easily won the gold. He moved the bar to 6.19 meters to break his own world record. Came all so close in his first attempt but failed to clear. 

Nageotte is just too excited winning the gold to focus enough to make a serious attempt at 5.01. Can't blame her.

Thus ends the best sport in the Olympics.

Do Four Colors Suffice?

(Guest Post by David Marcus)

Comment by Bill: Haken and Appel proved that all planar maps are 4-colorable. Or did they? David Marcus emailed me that its not quite true and I asked him to post on it, so here it is. The meta point is that math can be very subtle.

And now David Marcus's post:

Is the Four Color Map Theorem true?

It is commonly believed that the Four Color Map Theorem says that four colors suffice to color a planar map. While this is true for any map a non-mathematician would dream up, it is not true for maps a mathematician might dream up without some restriction on the regions that are allowed. This is shown in Hud Hudson's Four Colors Do Not Suffice which appeared in the American Math Monthly, Volume 110,  No. 5, May 2003, pages 417--423. 

Hudson's article is written in a very entertaining style. I recommend that you read it. He constructs a map consisting of six regions R1,...,R6.  Each region is bounded and path connected. There is a line segment B that is  in the boundary of all six regions.  So, six colors are needed, since all six regions share a common boundary. The construction is similar to the topologist's sine curve. For each i , the union of Ri and B is not path connected. Hudson also shows that for any n, there is a map that requires at least n colors.

Hudson thus disproves the following statement:

1)  Four colors are sufficient to color any map drawn in the plane or on a sphere so that no two regions with a common boundary line are colored with the same color.

Appel and Haken actually proved the following:

2) Four colors are sufficient to color any planar graph so that no two vertices connected by an edge are colored with the same color.

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.

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

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. 

I went to the ``debate'' about Program Verif and the Lipton-Demillo-Perlis paper

On Thursday June 17 I went to (on zoom- does that need to be added anymore?)

A Debate on Program Correctness

There was no subtitle but it could have been:

Have the points made in Social Processes and Proofs of Theorems and Programs by DeMillo, Lipton, Perlis, survived the test of time ? (Spoiler Alert: Yes.)

I found out about it from the Lipton-Regan blog here

The debaters were Richard DeMillo and Richard Lipton and the moderator was Harry Lewis (Alan Perlis passed away in 1990).  Calling it a debate is not correct since DeMillo and Lipton (and Lewis) all agree. (DeMillo and Lipton even have the same first name!)  The DLP paper is in Harry Lewis's collection Ideas that created the future.  The event  should have been advertised as a discussion. However, it was a good discussion so this is not a complaint.

Here are some things that came out of the discussion.

1) The main topic was the 1979 DeMillo-Lipton-Perlis paper (see here) that gave arguments why Proofs of Program correctness could not work.

An all-to-brief summary of the DLP paper: Some researchers are trying to set up frameworks for doing proofs that programs are correct, analogous to the certainty  we get with a proof of a Theorem in Mathematics. But proofs in Mathematics are, in reality, NOT that rigorous. Often details are left out or left to the reader. This is fine for mathematics (more on that later) but unacceptable for programs which need rather precise and rigorous proofs.

How do theorems in mathematics really get verified? By having enough people look at them and make sure they match intuitions, what DLP call A Social Process.  (NOTE FROM BILL: Papers that are not important do not get looked at so there may well be errors.)

2) The notion of proving-programs-correct was very seductive; however, the people who were trying to do this had a blind spot about how the analogy of proving-programs-correct and proving-theorem-correct differ.  In particular, a program is rather complicated and even stating carefully what you want to prove is difficult. By contrast, for most math statements, what you want to prove is clear. Note also that a program has lots of code (far more now than when DLP was written) and so much can happen that you cannot account for.

3) The DLP paper had a large effect on the field of program verification.  Funding for it was reduced and students were discouraged from going into it.

4) When DLP appeared DeMillo and Lipton were pre-tenure. Hence it took lots of courage to publish it. Alan Perlis had tenure and had already won a Turing award.  This did give DeMillo and Lipton some cover; however, it still took courage.

5) How did the Program Verification  Community deal with the objections in DLP?  DeMillo said that he looked at a large set of papers in the field, and very few even mentioned DLP. He recommends reading the book Mechanizing Proof: Computing, Risk, and Trust by David McKenzie see here.

6) So how can we be more certain that programs are correct?

a) Testing.

b) Modularize and test. Fix errors. Modularize  and test. Fix errors...

c) Try to isolate side effects.

d) More testing.

Some point to Model Checking, which could be considered very sophisticated testing, but that's used to verify circuits and perhaps low-level code, not programs. Model checking is a success story and note that Ed Clark, E. Allen Emerson, and Joseph Sifakis shared a (well deserved) Turing award for this work. But see next note.

6.5) An audience member pointed out that Program Verification people have won several Turing Awards

Dijkstra 1972

Floyd 1978 

Hoare 1980

Pnueli 1996

(Are there more?) 

so the field is alive and healthy. DeMillo responded that prizes for academic research are a poor measure of  success. 

7) Can computers themselves help with proofs of correctness? That is the only hope; however, there are scaling problems.

8) When DLP was written a program with 100,000 lines of code was considered large. Now we have programs with millions of lines of code. And now we have more concurrency. So the lessons of the DLP paper are probably more relevant now then they were then.

9) Since Program Verification does not seem to be used, how come we don't have a Software crisis?

a) We do! The Q+A mechanism at the meeting was terrible. 

b) We do! FILL IN YOUR OWN FAVORITE STORY OF BAD SOFTWARE.

c) See the answer to question 6.

10) SPECS are a problem. Tony Hoare once gave a talk where he proves that a program sorted correctly and then pointed out that if the program just output 0,...0 that would have also satisfied the SPEC since all that was required was that the output be sorted, not the (overlooked!) requirement that it be the same numbers as the input. So one needs to be careful!

11) Despite being a leader in the field, Tony Hoare has come to see the limitations of the Proofing-programs-correct approach to Software Verification.  His paper An Axiomatic basis for Computer Programming (1969)  (which is also in Harry Lewis's collection Ideas that Created the Future).

Much later, commenting on the paper,  Hoare says the following:

Ten years ago, researchers into formal methods (and I was the most mistaken among them) predicted that the programming world would embrace with gratitude every assistance promised by formalization to solve the problems of reliability that arise when programs get large and more safety-critical. Programs have now got very large and very critical--well beyond the scale which can be comfortably tackled by formal methods. There have been many problems and failures, but these have nearly always been attributable to inadequate analysis of requirements or inadequate management control. It has turned out that the world just does not suffer significantly from the kind of problem that our research was originally intended to solve.'

12) Richard Lipton told a story where he showed that the program in question satisfied the SPEC, but the SPEC was a tautology that any program would satisfy.  Again, one needs to be careful!

13) The test of time: Verifying large scale programs does not seem to be common in industry. Is industrial adaptation a fair measure? 

14) Harry Lewis's  book Ideas that created the future collects up, edits, and comments on 46 important papers in Computer Science (I reviewed it in the issue of SIGACT News that is in your mailbox---I will blog about it at a later time.) There are several papers in it about program verification, including DLP, Hoare's paper, and three papers by Dijkstra.

a) When Harry discussed including DLP some people said `You're going to include that!  Its a polemic, not a paper!'

b) When Harry teaches a course from this book (it must be an awesome class!) and asks the students at the end which papers they learned the most from, the top two are an excerpt from Fred Brooks The Mythical Man Month (see my post on Brook's work here ) and DLP.

c) I am hoping that this is just one of 46 talks with authors of the papers in his book.  I look forward to his interview with Aristotle, Leibnitz, Boole, Turing, ...

Collusion Rings

Grigory Yaroslavtsev now maintains the Theory Jobs Spreadsheet, a crowd-sourced listing of where your favorite CS theorists have taken new positions. Read his blog post for more info.

Michael Littman wrote a CACM Viewpoint on collusion rings designed to tilt the odds into getting papers into conferences. See also this post by T. N. Vijaykumar. I started to write a post on the topic but couldn't get it going so I asked the AI algorithm GPT-3 to write a guest post. Here is its story.

---

I have been part of a collusion ring and I know how it feels. I was a postdoc at the University of California, Berkeley, in the early 2000s when I first learned about the practice of “paper rings.” A paper ring is a group of researchers who agree to submit each other’s papers to conferences without disclosing this fact to the conference organizers. The idea is that if you have several submissions from the same conference, your chances of getting accepted are higher. The pressure to be part of such a ring can be immense. You are told that you need to publish or perish and that you need to get papers into top conferences. If you don’t play along, you will be left behind. I was lucky enough to have a mentor who warned me against being part of such rings. He told me that if I did not want my name on a paper, then I should not submit it to a conference. He also told me that if I did not want to be part of a paper ring, then I should not submit papers for others in the ring. He said that he would help me with my own research and that he would help me get my own papers into conferences. He was right: My own papers were accepted into conferences and they were published in journals.

I am now an associate professor at the University of Massachusetts Amherst and I have been on the other side of this issue as well. In 2012, I was asked by an editor at a top computer science conference to review a paper submitted by one of my students. The student had been part of a paper ring and had submitted his own paper along with those submitted by his collaborators in the ring. The editor told me that he had rejected the student’s paper because it was too similar to other papers submitted by members of the ring. However, he wanted me to review it so that he could reconsider accepting it for publication if I recommended doing so.

What should I do? Should I tell him about the paper ring? Should I recommend accepting the paper? Should I tell him that there is no way he should accept it? Should I tell him that he should reject it but then publish it anyway? What would you do? I decided not to tell him about the paper ring and not to recommend accepting the paper for publication. Instead, I told him that he should reject it but then publish it anyway because this would send a strong message about what we expect from our students and what we think about such practices. The editor agreed with my decision and published the student’s paper along with two other papers submitted by members of the same paper ring.

The student received his PhD degree but did not get any credit for his work on these three papers because they were considered as part of his dissertation work when he defended his thesis later that year. In retrospect, I think that my decision was wrong because it allowed these students to continue their unethical behavior without any consequences for them or their advisors (who were also part of this ring). But at least in this case, there were no negative consequences for anyone involved in this incident except for these students who did not get credit for their work on these three papers because they were considered as part of their dissertation work when they defended their thesis later that year.

Benny Chor (1956-2021)

Benny Chor passed away on June 10, 2021. Luca Trevisan had a blog post on the news.

We present a guest post on Benny Chor's life and works by Oded Goldreich. The post has many refs to papers. They will appear at the end with pointers to them.

---

Benny Chor was born on December 23rd 1956  and grew-up in Tel-Aviv, Israel. He studied Mathematics in the Hebrew University, receiving a B.Sc. in 1980 and an M.Sc. in 1981. He then switched to studying Computer Science at MIT, and graduated in 1985 with a PhD thesis titled

 Two Issues in Public Key Cryptography -- RSA Bit Security and a New Knapsack Type System

which received an ACM Distinguished Dissertation award. After post-doctoral periods at MIT and Harvard, he took a faculty position at the Computer Science Department of the Technion (1987-2001), and then at Tel-Aviv University, where he served as the chairman of the department for two years. He died on June 10th 2021, from a terminal disease.

Although Benny was a very articulated and verbal person, I find it impossible to describe his personality in words. The point is that words cannot capture the experience of interacting with him, which was always sheer fun. Still, I guess I should say something personal as a close friend of his. So I will just mention that he lived happily with Metsada, whom he met in the summer of 1981, and that they lovingly raised three kids: Arnon, Omer and Aya. Actually, let me also mention his life-long close relationship with his brother, Kobi.

Focusing on his contributions to science, I will confine myself to the areas of cryptography and randomized computation. Still, let me mention that in the mid 1990s, Benny's research interests gradually shifted to computational biology, but I will not review his contributions to that area, since it is very remote from my own expertise.

In my opinion, Benny's most important contribution to cryptography is the fundamental

paper on Verifiable Secret Sharing [CGMA].  Loosely speaking, Verifiable Secret Sharing

is a method to share a secret so that any majority of share-holders may reconstruct the

secret, whereas no minority may do so, and still each share-holder can verify that the

share that they got is a valid one.  This primitive had a tremendous impact on the

development of secure multi-party protocols, and almost all subsequent works in this

area utilize it.

Additional research milestones of Benny, in the area of Cryptography, include the proof

of the existence of a ``hard-core'' in the RSA and Rabin functions [BCS, ACGS], the

introduction and design of Private Information Retrieval (PIR) schemes [CGKS] (as well

as their computational counterparts [CG97]), and the introduction and design of

Tracing Traitor schemes [CFNP].  Each of these works deserves more than the foregoing

brief mention, yet I'm not even mentioning other important works like [CK].

Turning to the area of Randomized Computation, Benny's contributions span diverse areas

ranging from the manipulation of randomness to the use of randomness in complexity theory

and distributed computing.  In particular, his work on weak sources of randomness [CG88]

identified min-entropy (of the source) as the key parameter for randomness extraction and

presented a simple two-source extractor.  Distilling an aspect of [ACGS], his work on

pairwise-independent sampling [CG89] demonstrates the general applicability of this method. His works in distributed computing include a randomized Byzantine Agreement protocol [CC] that beats the deterministic bound without using unproven assumptions.  Lastly, let me just mention a couple of his complexity-theoretic works: [BCGL, CCGHHRR].

Benny was a superb teacher and a devoted graduate student adviser.  It is tempting to try

listing the numerous educational projects that he initiated, and his former students, but

these lists will be too long and the risk of a crucial omissions is too high.  So let me

end by expressing the feeling of loss that is shared by many in our community,

which adds to my personal sorrow.

Oded and Benny

Benny with his family's namesake (Chor = Bull)

[ACGS] Werner Alexi, Benny Chor, Oded Goldreich, Claus-Peter Schnorr:

RSA and Rabin Functions: Certain Parts are as Hard as the Whole.

SIAM J. Comput. 17(2): 194-209 (1988) LINK

[BCGL] Shai Ben-David, Benny Chor, Oded Goldreich, Michael Luby:

On the Theory of Average Case Complexity. J. Comput. Syst. Sci. 44(2): 193-219 (1992) LINK

[BCS] Michael Ben-Or, Benny Chor, Adi Shamir: On the Cryptographic Security of Single RSA Bits STOC 1983: 421-430. LINK

[CCGHHRR] Richard Chang, Benny Chor, Oded Goldreich, Juris Hartmanis, Johan Håstad, Desh Ranjan, Pankaj Rohatgi: The Random Oracle Hypothesis Is False.

J. Comput. Syst. Sci. 49(1): 24-39 (1994) LINK

[CC] Benny Chor, Brian A. Coan:

A Simple and Efficient Randomized Byzantine Agreement Algorithm.

IEEE Trans. Software Eng. 11(6): 531-539 (1985) LINK

[CFNP] Benny Chor, Amos Fiat, Moni Naor, Benny Pinkas:

Tracing traitors. IEEE Trans. Inf. Theory 46(3): 893-910 (2000) LINK

[CG97] Benny Chor, Niv Gilboa:

Computationally Private Information Retrieval. STOC 1997: 304-313 LINK

[CG88] Benny Chor, Oded Goldreich:

Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity.

SIAM J. Comput. 17(2): 230-261 (1988) LINK

[CG89] Benny Chor, Oded Goldreich:

On the power of two-point based sampling. J. Complex. 5(1): 96-106 (1989) LINK

[CGKS] Benny Chor, Oded Goldreich, Eyal Kushilevitz, Madhu Sudan:

Private Information Retrieval. J. ACM 45(6): 965-981 (1998) LINK

[CGMA] Benny Chor, Shafi Goldwasser, Silvio Micali, Baruch Awerbuch:

Verifiable Secret Sharing and Achieving Simultaneity in the Presence of Faults.

FOCS 1985: 383-395. LINK

[CK] Benny Chor, Eyal Kushilevitz:

A Zero-One Law for Boolean Privacy.  STOC 1989: 62-72. LINK

The Future of Faculty Hiring

Faculty hiring in computer science is a process long due for an overhaul. The pandemic certainly changed some of the dynamics moving most of the interviews online and saving a ton of money and time. Will this be the start of a fresh approach to recruiting?

A typical search in the past few years had some schools flying in 30-40 candidates, typically costing over a $1000 each and a full-time job for a staff member during the search. We'd justify the expense as small compared to the millions we'd invest in a faculty member throughout their career, but it is generally the largest discretionary expense for a CS department. It also gives advantages to rich departments over others.

During the pandemic all those interviews moved online and worked reasonably well at virtually no additional cost. Also no need to scrounge around to find faculty willing to skip family meals to have dinner with the candidates. And if a faculty had a conflict with a candidate on the interview day, they could schedule on a different day. There really is no reason to have all the meetings on the same day.

With the pandemic mostly behind us, will we go back to in-person interviews moving forward. I suspect the airport interview, where you fly out 20 or so candidates to have hour long interviews in a hotel near an airport with a search committee for an administrative position, will be the first to go completely virtual. 

Even for regular faculty interviews, there will be great pressure to reduce the number of in-person visits, perhaps to just the top candidates, or just the ones who have offers--make the "second visit" the only visit. Richer departments may find the expense worthwhile to make a bigger impression on the candidates and that will only expand the advantage of wealthier universities.

Times like this are the perfect opportunity for CS leadership to come in and give some sanity to the hiring process but I'm not holding my breath.

When do you use et al. as opposed to listing out the authors? First names? Middle initials? Jr?

 If I was refering to the paper with bibtex entry: 

@misc{BCDDL-2018,

  author    = {Jeffrey Bosboom and

               Spencer Congero and

               Erik D. Demaine and

               Martin L. Demaine and

               Jayson Lynch},

  title     = {Losing at Checkers is Hard},

  year      = {2018},

  note      = {\newline\url{http://arxiv.org/abs/1806.05657}},

}

(The paper is here.)

I would write 

Bosboom et al.~\cite{BCDDL-2018} proved that trying to lose at checkers (perhaps you are playing a child and want to keep up their self-esteem, or a Wookie and don't want your arms to be torn off your shoulders   (see here),  or a Wookie child) is hard. 

Why did I use et al. ? Because it would be a pain to write out all of those names. 

How many names does it take to make you write et al. ? Are there exceptions? 

I have not seen any discussion of this point on the web. So here are my rules of thumb and some questions.(CORRECTION- a commenter points out that this IS discussed on the web. Even so, you can comment on my thoughts or give your thoughts or whatever you like.) 

1) If  there are 3 or more people than use et al. Exception: If the three are VERY WELL KNOWN as a triple. E.g., the double play was Tinker to Evers to Chance. Well, that would not really come up since in baseball nobody ever says the double play was Tinker et al.  More relevant examples:

Aho, Hopcroft, and Ullman

Cormen, Leiserson, and Rivest, also known as CLR

The more recent edition is

Cormen, Leiserson, Rivest, and Stein. I have heard CLRS but I don't know if people WRITE all four names. 

Lenstra-Lenstra-Lovasz also usually mentions all three. 

2) If there is one name do not use et al.  unless that one person has a multiple personality disorder.

3) If there are 2 people it can be tricky and perhaps unfair. If the second one has a long name then I am tempted to use et al. For example

Lewis and Papadimitriou (If I mispelled Christos's name-- well- that's  the point!- to avoid spelling errors I want to use et al. )

Lampropoulos and Paraskevopoulou (the first one is UMCP new faculty!). After typing in the first name I would not be in the mood to type in the second. 

Similar if there are lots of accents in the name making it hard to type in LaTeX (though I have macros for some people like Erdos who come up a lot) then I might use et al. 

(ADDED LATER- some of the commenters object to my `rule' of leaving out the last name if its complicated. That is not really my rule- the point of this post was to get a discussion going about the issue, which I am happy to say has happened.) 

----------

There are other issues along these lines: when to include the first name (when there is more than one person with that last name, e.g. Ryan Williams and Virginia  Vassilevska Williams), when to use middle initials (in the rare case where there is someone with the same first and last name- Michael  J. Fox added the J and uses it since there was an actor named Michael Fox.)

I will soon give a quote from a math paper that amused me, but first some context.  The problem of determining if a poly in n variables over Z has an integer solution is called E(n). By the solution to Hilbert's 10th problem we know that there exists n such that E(n) is undecidable. E(9) is undecidable, but the status of E(8) is unknown (as of May 2021) and has been since the early 1980's. 

Here is the quote (from here).

Can we replace 9 by a smaller number? It is believed so. In fact, A. Baker, Matiyasevich and J.Robinson  even conjectured that E(3) is undecidable over N.

Note that Baker and Robinson get their first initial but Matiyasevich does not.

I suspect that they use J. Robinson since there is another mathematician with last name Robinson: Rafael Robinson who was Julia's Robinson's husband (to my younger readers--- there was a time when a women who got married took her husband's last name). There is at least one other Math-Robinson: Robert W Robinson. I do not think he is closely related. 

Baker: I do not know of another mathematician named Baker. I tried Google, but the Bakers  I found were   not in the right time frame. I also kept finding hits to an anecdote about Poincare and a man whose profession was a baker (see here though its later in that blog post). However, I suspect there was another mathematician named Baker which is why the author uses the first initial.  Its possible the author did not want to confuse Alan  Baker with Theodore Baker, one of the authors of Baker-Gill-Solovay that showed there were oracles that made P = NP and others that made P NE NP.  But somehow, that just doesn't seem right to me. I suspect there is only one mathematician with last name Matijsavic. 

Thomas Alva Edison named his son Thomas Alva Edison Jr.  This was a bad idea but not for reasons of authorship, see here.

What happened to self-driving cars?

In 2014, I wrote a blog post about a fake company Elfdrive.

With a near record-setting investment announced last week, the self-driving car service Elfdrive is the hottest, most valuable technology start-up on the planet. It is also one of the most controversial.

The company, which has been the target of protests across Europe this week, has been accused of a reckless attitude toward safety, of price-gouging its customers, of putting existing cabbies out of work and of evading regulation. And it has been called trivial. In The New Yorker last year, George Packer huffed that Elfdrive typified Silicon Valley’s newfound focus on “solving all the problems of being 20 years old, with cash on hand.”

It is impossible to say whether Elfdrive is worth the $117 billion its investors believe it to be; like any start-up, it could fail. But for all its flaws, Elfdrive is anything but trivial. It could well transform transportation the way Amazon has altered shopping — by using slick, user-friendly software and mountains of data to completely reshape an existing market, ultimately making many modes of urban transportation cheaper, more flexible and more widely accessible to people across the income spectrum.

It was a spoof on Uber but now it looks more like Tesla, expect that Tesla's market value is over half a trillion, about six times larger than General Motors.

The post was really about self-driving cars which I thought at the time would be commonplace by 2020. We are mostly there but there are issues of silent communication between drivers or between a driver and a pedestrian on who goes first that's hard to duplicate for a self-driving car. There is the paradox that if we make a car that will always stop if someone runs in front of it, then some people will run in front of it.

There is also the man-bites-dog problem. Any person killed by a self-driving car will be a major news item while the person killed by a human-driven car while you've been reading this post will never be reported.

We'll get to self-driving cars eventually, it just won't be all at once. We're already have basically self-driving cars on highways and in many other roads as well. As the technology improves and people see that it's safe at some point people will say, "So why do we even need the steering wheel anymore?"

What is a natural question? Who should decide?

(Thanks to Timothy Chow for inspiring this post.)

My survey on Hilbert's Tenth Problem(see  here) is about variants of the problem. One of them is as follows: 

For which degrees d and number-of-vars n, is Hilbert's tenth problem decidable? undecidable? unknown? 

 I wondered why there was not a website with this information. More generally, the problem didn't seem to be getting much attention. (My survey does report on the attention it has gotten.) 

I got several emails telling me it was the wrong question. I didn't quite know what they meant until Timothy Chow emailed me the following eloquent explanation:

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

One reason there isn't already a website of the type you envision is that from a number-theoretic (or decidability) point of view, parameterization by  degree and number of variables is not as natural as it might seem at first glance. The most fruitful lines of research have been geometric, and so geometric concepts such as smoothness, dimension, and genus are more natural than, say, degree. A nice survey by a number theorist is the book Rational Points on Varieties by Bjorn Poonen. Much of it is highly technical; however, reading the preface is very enlightening. Roughly speaking, the current state of the art is that there is really only one known way to prove that a system of Diophantine equations has no rational solution.

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

AGAINST THE NUMBER THEORISTS VIEWPOINT:

1) ALICE: Why are you looking for your keys under the lamppost instead of where you dropped them?

   BOB: The light is better here.

2) I can imagine the following conversation:

BILL: I want to know about what happens with degree 3, and number of variables 3.

MATHPERSON: That's the wrong question you moron. The real question is what happens for fixed length of cohomology subchains.

BILL: Why is that more natural?

MATHPERSON: Because that is what we can solve. And besides, I've had 10 papers on it.

FOR THE NUMBER THEORISTS VIEWPOINT

1) They are working on really hard problems so it is natural to gravitate towards those that can be solved.

2) I suspect that the math that comes out of studying classes of equations based on smoothness, dimension, genus is more interesting than what comes out of degree and number of vars. Or at least it has been so far. 

META QUESTION

Who gets to decide what problems are natural?

People outside the field (me in this case) are asking the kind of questions that a layperson would ask and there is some merit to that.

People inside the field KNOW STUFF and hence their opinion of what's interesting to study has some merit. But they can also mistake `I cannot solve X' for `X is not interesting'

Does the university matter?

As we come out of a pandemic with online teaching and research collaborations, how much do we actually need the university?

Theoretical research in computer science, math and elsewhere it hardly slowed down with everyone hunkered down at home, and when it did it was more because of supervising kids with their on-line learning than being away from the university. Collaborating with those around the world was basically the same as collaborating with your colleagues on campus.

Many courses, especially the larger ones, worked about as well on-line as they do in person.

The pandemic is accelerating changes already in place. Before say 1960, the fastest travel for the masses was on train and boats and fast communication limited to expensive phone calls. You needed strong colleagues, a strong library and a strong support staff to be a successful academic. Traveling to meet colleagues and attend conferences was a luxury that few could do often.

The 60's gave us air travel though it wasn't until the 90's that we could readily send academic papers electronically. It's really only recently that we have the infrastructure to allow high-quality teaching and research collaboration online.

Suppose universities now just disappeared. Professors would be free agents, supported by grants and tuition from students taking their on-line courses and consulting. Students would pick and choose courses from the best instructors, their "transcript" being recorded on a blockchain-like database. PhD students would be more of an apprenticeship, a low salary in exchange for personalized mentoring from a professor. 

For the experimental sciences, there would be a set of national labs that professors could join.

Startups would create apps to enable all these things, professors would just become yet another piece of the gig economy. Superstar academics can pull in large salaries, the rest would struggle to make a decent wage--not that different from actors and musicians. 

Don't worry, universities aren't going anywhere soon. Or are they?

Emerging from the Pandemic

The City of Chicago yesterday agreed with the latest CDC guidelines that those of us fully vaccinated no longer have to wear masks in most settings. Lollapalooza, the big Chicago music festival, will be held in full capacity this summer. There are still some restrictions but barring any surprise setbacks should be mostly gone by the Fourth of July.

It's not appropriate to call the pandemic over. Too many countries are suffering and lack good access to vaccines or strong health care. But in most of the US vaccinations are readily available and it really feels like we are putting the pandemic in the past.

Variants that beat the vaccines could emerge. Vaccines could become ineffective over time. Too many still need to be vaccinated and too many don't want to do so. Typically problems start small and quickly get big by exponential growth but likely with enough warning if we need boosters or extra precautions. And all those who cut in line to get shots early are now my canaries for the effects wearing off.

What will this post-pandemic world look like? Continued virtual meetings from people who don't want to spend the 10-15 minutes to get across campus or to come to campus at all. A bigger move to casual dress, even in the corporate world. No more snow days. Changes in ways we won't expect. 

We all have our different attitudes but I'm ready to move on. Time to start the "after times".

Why do countries and companies invest their own money (or is it?) in Quantum Computing (Non-Rhetorical)

 There have been some recent blog posts by Scott (see here) and Lance (see here)  about the hype for SHORT TERM APPLICATIONS of Quantum Computing, which they both object to. 

I have a question that has been touched on but I want to get it more out there.

PREAMBLE TO QUESTION:  The following scenarios, while distasteful, do make sense: 

a) A researcher on their grants exaggerates or even out-right lies about the applications of their work. 

b) A journalist in their articles exaggerates or even out-right lies about the applications of the science they are covering.

c) A company exaggerates or even out-right lies about the applications of their project to a venture capitalist or other kind of investor. 

QUESTION: 

Why does a company or country invest THEIR OWN MONEY into Quantum Computing which is unlikely to have a short term profit or benefit? Presumably they hire honest scientists to tell them the limits of the applications in the short term. 

ANSWERS I HAVE GOTTEN FROM ASKING THIS

1) QC might be able to do something cool and profitable, like factoring, or simulating physics quantum experiments or something else, in the short term. Quantum Crypto is already happening, and that's a close cousin of Quantum Computing. 

2) QC might be able to do something cool and profitable (like in (1)) in the long term, and both companies and countries think they will be around for a long time. (For a list of America's 10 oldest companies see here.) 

3) The company or country is in this for the long term, not for a practical project, but because they realize that doing GOOD SCIENCE is of a general benefit (this might make more sense for a country than a company). And funding Quantum Computing is great for science. 

4) Bait and Switch: The company claims they are doing Quantum to attract very smart people to work with them, and then have those smart people do something else.

5) (this is a variant of 1) While Quantum Computing may not have any short term applications, there will be classical applications INSPIRED by it (this has already happened, see here).

6) Some of these companies make money by applying for GRANTS to do QC, so its NOT their money. In fact, they are using QC to  GET money.

7) For a country its not the leaders money, its that Taxpayer's money- though that still leaves the question of why spend Taxpayer money on this and not on something else.

8) For a company its not their money- its Venture Capitalists  and others (though for a big company like Google I would think it IS their money). 

9) The scientists advising the company or country are giving them bad (or at least self-serving) advice so that those scientists can profit- and do good science. So this is a variant of (3) but without the company or country knowing it. 

10) In some countries and companies group-think sets in, so if the leader (who perhaps is not a scientist) thinks intuitively that QC is good, the scientists who work for them, who know better, choose to not speak up, or else they would lose their jobs...or worse. 

11) For countries this could be like going to the moon: Country A wants to beat Country B to the moon for bragging rights. Scientists get to do good research even if they don't care about bragging rights. 

12) (similar to 11 but for a company) If a company does great work on QC then it is good publicity for that company. 

13) Some variant of the greater fool theory. If so, will there be a bubble? A bail-out? 

Cryptocurrency, Blockchains and NFTs

 I first wrote about bitcoin in this blog ten years ago after I gave a lecture in a cryptography class I taught at Northwestern. Two years later I had a follow-up post, noting the price moved from $3 to $1000 with a market cap of about $11 Billion. My brother who thought they were a scam back then has since become a cryptocurrency convert. The bitcoin market cap is now over a trillion dollars and other cryptocurrencies are not far behind. No longer can we view cryptocurrencies as simply a neat exercise in applied cryptography now that it has serious value.

The main uses of cryptocurrencies are for speculation or illegal activities, such as drug sales, ransoms, money laundering and tax evasion. Sure you can buy a Tesla with bitcoins but that's more of a gimmick. Cryptocurrency spending is simply too slow, expensive and volatile right now to replace other methods of electronic payment. 

Non-fungible tokens (NFTs) truly puzzle me. They are just a digital certificate of authentication. What could you do with them you couldn't do with docusign? Collectibles of publicly available digital goods is a fad already fading.

I'm not a fan of a fiat currency governed by strict rules not under governmental control. Bad things could happen. However thinking of cryptocurrencies and the blockchain technology that underlies them have brought up real needs for our digital world.

• An easy way to pay online without significant fees, expenses or energy consumption.
• An easy and cheap way to transfer money between different countries.
• A distributed database to allow tracking of supply chains, credentials and financial transactions for example. I see less a need to make these databases decentralized.
• A need, for some, to have a digital replacement for the anonymity of cash.
• People need something to believe in once they have given up believing in religion and a functioning democracy. 

Don't change your investing habits based on anything I write in this post. Speculation and illegal activities are powerful forces. Or it could all collapse. Make your bets, or don't.

Note: Since I wrote this post yesterday, Elon Musk tweeted that Tesla will no longer accept bitcoins, and the bitcoin market cap has dropped below a trillion.

Trump, Facebook, and ComplexityBlog

 I care about the Facebook decision to ban Trump, but I do not have a strong opinion about it. I have heard arguments on both sides now, from up and down, and still somehow... I don't know how I feel. So instead of posting my opinion I post other opinions and my opinion of them.

1) Facebook is a private company. If they want to have liberal bias or a free for all or whatever then  it is not the governments place to interfere. If enough people don't like what they see then they will lose customers. The invisible hand of the market will regulate it enough. Libertarians and honest small-gov republicans might believe this. On a personal level, I don't want someone else telling Lance and I that we can't block some comment; however, for now, more people use Facebook then read Complexity Blog. 

2) Facebook is a private company but they need to follow standard business practices of having their uses sign an agreement and stick to it. Since the user signed the agreement, Facebook need only stick to that agreement. This is problematic in that (1) if the agreement is not that rigorous then Facebook can be arbitrary and capricious, but (2) if the agreement is to rigorous then people can game the system. Imagine if Lance and me had  rule that you could not use profanity in the comments. Then someone could comment 

People who think P vs NP is ind of ZFC can go Fortnow themselves. They are so full of Gasarch.

 (Something like this was the subplot of an episode of The Good Fight)

3) Facebook is so big that it has an obligation to let many voices be heard, within reason. This could lead to contradictions and confusions:

a) Facebook cannot ban political actors. What is a political actor? (Jon Voight is pro-trump and Dwayne ``The Rock'' Johnson is anti-trump, but that's not what I mean.) High level people in the two main parties qualify (how high level?). IMHO third parties (Libertarian and Green come to mind) need the most protection since they don't have as many other ways to get out their message and they are serious. (I wonder if Libertarians would object to the Government  forcing Facebook to not ban them). What about the Surprise Party or the Birthday Party (which did have a platform see here). And what about people running for Mayors of small towns (much easier to do now with Facebook)? Should just running be enough to ban banning? 

b) Facebook can ban posts that are a threat to public health and safety. I am thinking of anti-vaxers and insurrectionists, though I am always wary of making them free speech martyrs. 

c) Fortunately a and b above have never conflicted. But they could. I can imagine a president who has lost an election urging his followers to storm the capitol. Then what should Facebook do?  (ADDED LATER- A commenter points to a case where a and b conflicted that is not the obvious case.) 

4) Facebook is so big that it has an obligation to block posts that put people in danger. This may have some of the same problems as point 3---who decides? 

5)  Facebook is so big and controls so much of the discourse that it should be heavily regulated (perhaps like a utility).  This has some of the same problems as above- who decides how to regulate it and how?

6) As a country we want to encourage free speech and a diversity of viewpoints. There are times when blocking someone from posting may be better for free speech then letting them talk. When? When that person is advocating nonsensical views that stifle the public discussion. But I am talking about what the country should want. What do they want? What does Facebook want? Does either entity even know what they want? These are all ill defined questions. 

7) Facebook is a monopoly so use Anti-Trust laws on it. Anti-Trust was originally intended to protect the consumer from price-gouging. Since Facebook is free this would require a new interpretation of antitrust. Judicial activism? The Justices solving a problem that the elected branches of government are currently unable to solve? Is that a bad precedent? What does it mean to break up Facebook anyway--- its a network and hence breaking it up probably doesn't make sense (maybe use MaxCut). 

(ADDED LATER- a commenter pointed out that anti-trust is NOT just for consumer protection, but also about market manipulation to kill small innovators.) 

8) Lets say that Facebook and Society and the Government and... whoever, finally agree on some sort of standards. Then we're done! Not so fast. Facebook is so vast that it would be hard to monitor everything. 

9) As a side note- because Facebook and Twitter have banned or tagged some kinds of speech or even some people, there have been some alternative platforms set up. They always claim that they are PRO FREE SPEECH. Do liberals post on those sites? Do those sights  ban anyone? Do they have SOME rules of discourse? I ask non rhetorically. 

Negotiations

So you got an offer to be an assistant professor in the computer science department at Prestigious U. Congratulations! 

Time to negotiate your offer with the chair. Don't be nervous. This shouldn't be adversarial. Both of you have the same goal in mind--for you to come to Prestigious and be successful. 

Let's discuss the different aspects of each package.

Research 

Funds for supporting your research such as equipment, graduate student support, travel and postdocs. Here you should explain what you need to be successful. This will vary by subdiscipline, a systems researcher will need more equipment and students than a theorist. Keep in mind the university is giving you funds for 2-4 years to start your research, after which you are expected to fund your own research via grants.

I don't recommend taking on a postdoc right at the start of your first academic appointment. Postdocs require good mentoring while you need to spend the first year getting your research up and running. If you do ask for postdoc money, ask to have a flexible start time.

Many departments give course reductions to get your research going. I'd suggest asking to spend your first semester teaching a graduate topics course based on your thesis research to pick up some PhD students followed by a semester with no classes to get you research program going.

Salary

This includes actual salary, which is also the base for future raises, and summer salary in the first couple of years. Feel free to ask for more salary, but often these numbers are fixed for new assistant professors. There is more give if you take an academic job later in your career. You could also say something like, "Well if you can't give me more salary maybe you could give me another semester of grad student support?"

Partner

It seems 80% of the time, a job candidate has a partner that needs accommodating. Don't wait until the end of negotiations, bring it up early. The more time we have, the better we can help. Doesn't matter what job they want--we know people and we know people who know people.

Thesis

Many schools won't hire you as an assistant professor if you haven't finished your thesis. Has to do with college rankings work. Don't worry--they will generally give you some other role with the same package until you finish. This might delay your tenure clock though.

Delayed start time

A January start is usually fine with good reason but if you weren't planning to start until the fall of 2022 why are you on the market this year? If you do get the department to hold a position for you, remember you are also making a commitment--this is not an opportunity to try again for something better.

Overall

You may not get all that you want after a negotiation--don't take it personally. You shouldn't necessarily choose the place that gives you the biggest package. It's far more important in the long run that you pick a place where you can best succeed both professionally and personally, and the package is just a small piece of that puzzle.

The Mythical Man-Month, Hen-Day, and Cat-Minute (Fred Brooks Turned 90)

 (Added later: Fred Brooks passed away on November 7, 2022, at the age of 90.)

The Mythical Man-Month is a great book which talks about the (obvious in retrospect) fact that putting more people on a project may slow it down. It was by Fred Brooks who turned 90 in April (he is still alive). It's a good read. I actually read it many years ago when I exchanged books with a Software Engineer I was dating- She lent me The Mythical Man Month which I found interesting, and I lent her What is the name of this book by Smullyan which she found amusing. Did this exchange of books help our relationship? We have now been married for many years, though its not clear if we can trace this to the exchange of books OR to the fact that she had KNUTH Volumes 1 and 3, and I had KNUTH Volume 2. 

 Fred Brooks: You have my thanks and of course Happy Birthday!

When I read The Mythical Man-Month  I was reminded of a math problem I heard as a kid: 

If a hen-and-half lays an egg-and-a-half in a day-and-a-half then how many eggs can seven hen lay in seven days? 

My answer: if (3/2) hens lay (3/2) eggs in (3/2) days then that's 2/3 of an egg per hen-day, so the answer is 

49* 2/3 = 32 and 2/3 eggs.

It did not bother me one whit that (1) you can't have 2/3 of an egg, and (2) Just like adding more people might slow down a project, adding more hens might end up being a bad idea-- especially if they are all crowded into the same chicken-coop and hence don't feel much like laying eggs.

Who was the first person to note that adding more people or hens might be a bad idea? I do not know, but here is an amusing, yet realistic, article by Mark Twain on what I would call The mythical cat-minute. My advisor Harry Lewis send it to me in the midst of an email exchange about The Mythical Man-Month. He got it from a student of his, Larry Denenberg. Here it is: 

CATS AND RATS

The following piece first appeared in ``The Monthly Packet'' of February
1880 and is reprinted in _The_Magic_of_Lewis_Carroll_, edited by John
Fisher, Bramhall House, 1973.


   If 6 cats kill 6 rats in 6 minutes, how many will be needed to kill
   100 rats in 50 minutes?

   This is a good example of a phenomenon that often occurs in working
   problems in double proportion; the answer looks all right at first, but,
   when we come to test it, we find that, owing to peculiar circumstances in
   the case, the solution is either impossible or else indefinite, and needing
   further data.  The 'peculiar circumstance' here is that fractional cats or
   rats are excluded from consideration, and in consequence of this the
   solution is, as we shall see, indefinite.

   The solution, by the ordinary rules of Double Proportion, is 12 cats.
   [Steps of Carroll's solution, in the notation of his time, omitted.]

   But when we come to trace the history of this sanguinary scene through all
   its horrid details, we find that at the end of 48 minutes 96 rats are dead,
   and that there remain 4 live rats and 2 minutes to kill them in: the
   question is, can this be done?

   Now there are at least *four* different ways in which the original feat,
   of 6 cats killing 6 rats in 6 minutes, may be achieved.  For the sake of
   clearness let us tabulate them:
      A.  All 6 cats are needed to kill a rat; and this they do in one minute,
          the other rats standing meekly by, waiting for their turn.
      B.  3 cats are needed to kill a rat, and they do it in 2 minutes.
      C.  2 cats are needed, and do it in 3 minutes.
      D.  Each cat kills a rat all by itself, and takes 6 minutes to do it.

   In cases A and B it is clear that the 12 cats (who are assumed to come
   quite fresh from their 48 minutes of slaughter) can finish the affair in
   the required time; but, in case C, it can only be done by supposing that 2
   cats could kill two-thirds of a rat in 2 minutes; and in case D, by
   supposing that a cat could kill one-third of a rat in two minutes.  Neither
   supposition is warranted by the data; nor could the fractional rats (even
   if endowed with equal vitality) be fairly assigned to the different cats.
   For my part, if I were a cat in case D, and did not find my claws in good
   working order, I should certainly prefer to have my one-third-rat cut off
   from the tail end.

   In cases C and D, then, it is clear that we must provide extra cat-power.
   In case C *less* than 2 extra cats would be of no use.  If 2 were supplied,
   and if they began killing their 4 rats at the beginning of the time, they
   would finish them in 12 minutes, and have 36 minutes to spare, during which
   they might weep, like Alexander, because there were not 12 more rats to
   kill.  In case D, one extra cat would suffice; it would kill its 4 rats in
   24 minutes, and have 26 minutes to spare, during which it could have killed
   another 4.  But in neither case could any use be made of the last 2
   minutes, except to half-kill rats---a barbarity we need not take into
   consideration.

   To sum up our results.  If the 6 cats kill the 6 rats by method A or B,
   the answer is 12; if by method C, 14; if by method D, 13.

   This, then, is an instance of a solution made `indefinite' by the
   circumstances of the case.  If an instance of the `impossible' be desired,
   take the following: `If a cat can kill a rat in a minute, how many would be
   needed to kill it in the thousandth part of a second?'  The *mathematical*
   answer, of course, is `60,000,' and no doubt less than this would *not*
   suffice; but would 60,000 suffice?  I doubt it very much.  I fancy that at
   least 50,000 of the cats would never even see the rat, or have any idea of
   what was going on.

   Or take this: `If a cat can kill a rat in a minute, how long would it be
   killing 60,000 rats?'  Ah, how long, indeed!  My private opinion is that
   the rats would kill the cat.