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?"