Grading policies during Covid-No easy answers

 Because of COVID  (my spellecheck says covid and Covid are not words, but COVID is) various schools have done various things to make school less traumatic. Students already have problems, either getting COVID or having their friends got family get it (I've had four relatives get it, and one died) . Some do not adjust to learning online.  Some do not have good computer connection to learn on line. So what is a good policy? Here are some things I have either seen schools do or heard that they might do.

1) Be more generous with Tuition-Refunds if a student has to withdraw. 

2) Be more generous with Housing-Refunds if a students comes to campus thinking it will be courses on campus and there are no courses on campus. Or if a student has to withdraw. 

3) Make the deadlines for dropping-without-a-W, or taking-it-pass-fail, later in the semester. 

4) Tell the teachers to `just teach them the bare min they need for the next course.'

5) Allow students to take courses P/F in their major and still allow them to count, so a student might get a D in Discrete Math and be able to go on in the major. 

6) How far to extend deadlines? How is this: extend deadline to make it P/F until the last day of classes (but before the final) and then after the final is given, the school changes its mind and says - OH, you can change to P/F now if you want to.

7) Allow either an absolute number (say 7) or a fraction (say 1/3) of the courses to be changed to P/F by the last day of class.

8) Combine 6 or 7 with saying NO- a D is an F for a P/F course. Perhaps only if its in the major, but that maybe hard to work out. since majors can change. Some schools do A-B-C-NO CREDIT, where the NC grade does not go into the GPA.

9) Give standard letter grades and tell the students to tough it out. Recall the following inspirational quotes

When the going gets tough, the tough go shopping

When the going gets tough, the tough take a nap

If at first you don't succeed, quit. Why make a damn fool of yourself. 

If at first you don't succeed, then skydiving is not for you. 

10) Decide later in the term what to do depending on who yells the loudest. 

11) Any combination of the above that makes sense, and even some that don't. 

On the one hand, there are students who are going through very hard times because of COVID and should be given a break. On the other hand, we want to give people a good education and give grades that are meaningful (the logic of how to give grades in normal times is another issue for another blog post). 

What is your school doing? Is it working? What does it mean to be working?

The problems I am talking about are first-world problems or even champagne-problems. I know there are people who have far worse problems then getting a bad grade or dropping courses.

PhDs and Green Cards

Joe Biden's immigration policy has some interesting policies for PhDs. 

Biden will exempt from any cap recent graduates of PhD programs in STEM fields in the U.S. who are poised to make some of the most important contributions to the world economy. Biden believes that foreign graduates of a U.S. doctoral program should be given a green card with their degree and that losing these highly trained workers to foreign economies is a disservice to our own economic competitiveness. 

Biden will submit an immigration plan to congress soon but it is not clear if the above will be in the bill, whether it will survive negotiations or even whether an immigration bill will be passed at all. 

Nevertheless I worry about the unintended consequences of this policy. It will encourage students to apply and come for a PhD who have no interest in research, but want the green card. It gives too much power to professors who may abuse their students who need the PhD. Conversely it will pressure professors and thesis committees to grant PhDs because there would be a big difference between graduating with a PhD and leaving early with a Masters. By making the PhD so valuable, we may devalue it.

The solution is to give green cards to Masters students as well. We shouldn't limit talented researchers and developers who can help the United States keep its technology edge. They don't take jobs away from Americans, but instead help create new ones.

Answers to the Prez Quiz, and some interesting history

I posted a presidential quiz (that is, a quiz about presidents, not a quiz that is so majestic it can be called presidential) on Thursday Jan 21.

Here is the link to the post: The Post

Here is the link to the quiz:The Prez Quiz

 I now post the answers here: The Prez Quiz Answers

Looking back at the quiz and some prior ones I realize that some questions are TRIVIA while others are not- that is- they tell us something interesting beyond the answer. Some thoughts on that: 

a) Asking who the oldest prez ever has to be better defined. But however you define it, the answer is Joltin Joe. I will ask it as Age-when-sworn-in, which for Joltin Joe is 78. Second is Trump who was 70 when sworn in.  INFO: Presidents seem to be getting older. Is this a trend or will 2024 and 2028 feature younger folks? I note that both VP's are in their 50's. 

b) Presidential first via xkcd; here

c) Between Nixon-Kennedy 1960 and Bush-Kerry 2004 EVERY election had one of he candidates being either a former or current Prez or Vice Prez.  (This was a question on the 2008 quiz, but since the streak is broken it is no longer as interesting.) INFO: It was hard to break into the prez business unless you were already somewhat known. Having said that, note that some of the non-VPs and non-Prezs DID win. 

d) Between 1948 and 2008 at least one of the candidates for Prez had served in the Military. How did they do? In many cases both served so I am not going to to a chart of how well the Military ones did. (This was a question on the 2012 quiz, but since the streak is broken it is no longer interesting.) INFO: At one time a lot of people were in the military. At one time a lot of people knew someone in the military. Now it seems like the military is rather far removed from civilians. 

e) Kennedy was our first Catholic Prez in 1960. Biden is our second one in 2020. My impression is that it was an issue for the Kennedy Campaign but not for the Biden campaign. Romney being a Mormon seems to have not been an issue in the General election, but some of the other candidates brought it up in the primaries. INFO: Religious bigotry within different denominations of Christianity is declining. 

f) Reagan was our first divorced Prez, in 1980. Trump was our second in 2016. It don't think it was  an issue for either one. INFO: We need to couple this with Rockefellers divorce being a problem for him getting the nomination in 1964. Peoples attitude on divorce has changed A LOT. 

Contrast: Knowing which president had a fictional street gang named after him  does not tell us anything about History .I will remove that question when I do the quiz in 2025. 

Alan Selman (1941-2021)

From a 1994 Dagstuhl Workshop. Selman is the one wearing a cap.

Alan Selman, one of the early leaders in structural complexity and the co-founder and first chair of what is now the Computational Complexity Conference, passed away this morning. He was one of the true greats in our field both for his research and his service.

Selman was a good colleague and a friend. I hosted his sabbatical at the University of Chicago in 1998 which produced a paper with Selman's student and my later postdoc Pavan Aduri. In Spring of 1999 Selman ran a NSF workshop in Chicago on Challenges for Theory of Computing.

In a desire to create a community of complexity theorists and foster publications of their results, Selman led the efforts to establish the Structure in Complexity Theory conference, first held in 1986 in Berkeley, California. As a student in Berkeley I attended that meeting and the next twenty-five. The conference would join the IEEE in 1987, in 1996 renamed the IEEE Conference and Computational Complexity and in 2015 drop from the IEEE to become the Computational Complexity Conference, still going strong. Alan served as the first conference chair and as PC co-chair of the first meeting. 

For all his service for the field, Selman received the ACM SIGACT Distinguished Service Award in 2002.

Selman joined University at Buffalo in 1990 to serve six years as department chair and then as a professor until he retired in 2014. Lane Hemaspaandra wrote a highly recommended appreciation for Selman and his research in honor of his retirement where he mentions some of Selman's research programs, including his seminal work on P-Selective sets, non-deterministic functions and his work with Joachim Grollman on one-way functions. Selman came down hard on anyone who got the wrong number of l's in Grollman, so we would often joking cite it as Grollman and Sellman or just Grollman et Al.

In my favorite Selman paper, in work with Hemaspaandra, Ashish Naik and Mitsu Ogihara, looks at witness reduction. If there is a set A in P such that for all satisfiable formula φ there is a unique satisfying assignment a of φ such that (φ,a) is in A then the polynomial-time hierarchy collapses. The more general question of whether NP=UP implies the polynomial-time hierarchy collapses remains open.

Also Selman's paper with Steve Homer giving an oracle where Σ₂^P-complete sets were isomorphic was instrumental to my own work on the isomorphism conjecture.

Bill wanted me to mention the Selman paper that most influenced him. Selman and Theodore Baker and gave the first oracle separating the second level of the polynomial-time hierarchy in 1979. It would take Yao and Håstad over five more years to get the whole hierarchy infinite relative to an oracle. The Baker-Selman proof could easily extend to show that AM games did not sit in Σ₂^P, a bit surprising as MA is in Σ₂^P.

In addition to his research, Selman wrote an introductory theory textbook with Homer as well as editor and co-editor of two editions of Complexity Theory Retrospective.

It would be no exaggeration to say the field of computational complexity and my own research within it would have been much different without Alan.

Alan drove a car with a "P NE NP" license plate. One day someone came up to him in a parking lot and said "Yes, but can you prove it?" Possibly the one thing in complexity he couldn't do.

Presidential Quiz: Three ways to take it

 Every four years around the time of the inaugural I post a presidential Quiz! I do that today, and I will post the answers on Monday.  I am tempted to joke that I am posting it AFTER Joltin Joe gets sworn in just in case something happens; however, I always posted it after the prez is sworn in. 

The quiz is here: quiz

 GRADING CRITERIA

33 questions, 3 points each, and 1 free point.

If the answer is a list of L elts and you get x correct, you get x/L points. If any are wrong then 0 points.

You can take the quiz one of three ways.

1) Take it WITHOUT using the web and see how many you can get right. Take 3 hours.

WARNING- its a hard quiz so this may not be fun. 

2) Take it and use the web and try to do it fast. Stop when you want. Your Score is as follows:

If  R is the number if points and  T be how many minutes you took,  your score is 

 (180R/T)+ 1.

If  you get all 33 right in 60 minutes then you get a 100. You could get more than 100 if you do it faster.

3) The answer key has all kinds of other information in it and is fun to read. So do not take the quiz and enjoy  reading the answers on Monday. That's what I did. 

I was curious if Joltin Joe would be sworn in by Joseph or Joe. I was routing for Joe so he would be the second president sworn in by his nickname (Jimmy Carter was the first--his real name is James). When I am sworn in as president I will use Bill and hence join the nickname-club. Lance does not have a nickname, so my veep will be sworn in by his actual name. Would we win? Is  America ready for a 2-Phd ticket? 

The Ethics Board

Back in 2014 I recommended a TCS ethics board mainly to deal with plagiarism and who should get credit for a result. It went the way of most suggestions I make in my blog, a quick road to nowhere. Bill asked "Does any other branch of CS have an ethics board? How have they worked?"

The NeurIPS conference created a such a board for the reviewing process, though with a broader mission.

We appointed an ethics advisor and invited a pool of 22 ethics reviewers (listed here) with expertise in fields such as AI policy, fairness and transparency, and ethics and machine learning. Reviewers could flag papers for ethical concerns, such as submissions with undue risk of harm or methods that might increase unfair bias through improper use of data, etc. Papers that received strong technical reviews yet were flagged for ethical reasons were assessed by the pool of ethics reviewers.

Thirteen papers met these criteria and received ethics reviews. Only four papers were rejected because of ethical considerations, after a thorough assessment that included the original technical reviewers, the area chair, the senior area chair and also the program chairs. Seven papers flagged for ethical concerns were conditionally accepted, meaning that the final decision is pending the assessment of the area chair once the camera ready version is submitted. Some of these papers require a thorough revision of the broader impact section to include a clearer discussion of potential risks and mitigations, and others require changes to the submission such as the removal of problematic datasets. Overall, we believe that the ethics review was a successful and important addition to the review process. Though only a small fraction of papers received detailed ethical assessments, the issues they presented were important and complex and deserved the extended consideration. In addition, we were very happy with the high quality of the assessments offered by the ethics reviewers, and the area chairs and senior area chairs also appreciated the additional feedback.

Without seeing the process I cannot say what criteria were used to reject the four papers. There could be legitimate reasons if the authors did violate professional ethics or even inadvertently based their results on biased data sets. But there's a fine line to rejecting papers because you don't like the outcome or the questions they ask. No easy answers here.

The ACM History Committee call for proposals looks wrong

 In November I (and prob everyone in the ACM) got an email that was a call for proposal from the ACM History committee. Here is a pointer to it. 

One of the passages in it just seems wrong to me:

This fellowship program is designed to support research and/or curatorial projects related to ACM's professional and educational activities and/or to ACM's rich institutional history including its organization, SIG activities, and conferences. 

I will give  examples of history projects that are interesting but do not fit the description. I challenge you to give me a history project that is interesting that does fit the bill. 

1) Compare and contrast how NP-completeness developed in America and in the USSR. For the USSR side it would be an expansion of  Trakhtenbrot's article here. OH, no good, Leonid Levin was not a member of the ACM.

2) Measure how various CS fields have changed by looking at the topics on the CALL FOR PAPERS for a conference. This would be a MASSIVE expansion of my blog post on how CCC call for papers, changed , see here. OH, I could only do ACM conferences. STOC but not FOCS. Okay, it makes perfect sense to study only ACM conference. Oh wait. IT MAKES NO SENSE WHATSOEVER.

3) When did mathematicians begin looking at P vs NP seriously? (e.g.,  In  The Handbook of Mathematical Logic from 1977 only one article mentions P vs NP: Michael Rabin's article on Decidable theories mentioned that even decidable theories may take a long time to decide and noted the importance of the P vs NP problem). How did MATH and CS  interact early on and now? This would need  one to look at math journals. How many of those are ACM? I would guess very few. 

4) When did engineers begin looking at P vs NP seriously, or even notice it? Same issue as the last item. 

5) Looking at how Programming lang design has changed one would have to only look at conference and journals that were ACM. And for those that were ACM but then dropped ACM you might only be able to use them up to the cutoff year. 

6) Which academic studies eventually lead to practical products people can use? This is a really broad topic so one could narrow it down to just academic studies that appeared in ACM journals or conferences. Is that a good way to narrow the focus? Spoiler alert: NO.

7) I recently filled out a survey about the future of theory and if it is insular (the topic of another post surely). Most of the questions were about ``STOC-FOCS'' The people who did the survey clearly do not care that one is ACM and one is IEEE. Does anyone? I ask non-rhetorically. 

Despite the capitol letters, I am not so much mad as puzzled. So I ask non-rhetorically: 

Q1) Did the ACM really mean for people to do history in a way where you can only use ACM materials? 

Q2) If no then please rewrite the Call for Proposals. 

Q3) If yes then give examples of studies that would be interesting. 

I am not asking to be snarky, I really want to know. And I note that interesting is subjective. 

(ADDED LATER- two historians who have worked with this kind of history left comments that indicate the grant is FINE with non-ACM stuff, so Q1 above seems to have the answer NO. Given that they should rewrite the call for proposal next time they do this. ALSO- the historians left pointers to VERY INTERESTING papers they wrote.) 

My Survey on Hilbert's 10th for particular (d,n) is ready for you to help me on!

 Hilbert's 10th problem is  (in modern terminology) to find an algorithm that will, given a poly 

p(x1,...,xn) in Z[x1,...,xn], determine if it has a solution in the integers. 

This was shown undecidable by the combined efforts of Davis-Putnam-Robinson and Matiyasevich. 

I posted here about the question of: For which (d,n) is H10 undecidable when restricted to degree d and number of vars n?

I was  invited to make an article out of the blog post and what I learned from the comments  for  the Algorithms column of BEATCS. That first draft is

here

Did I miss an important reference? (Note- I had meant to get out Matiyasevich's book on H10 but have been unable to because of the Pandemic, so if you have it my have stuff I need to know.) 

Did I misspell Matiyasevich? 

Did I say something stupid?

Please leave comments or email me directly if you have suggestions. 

Incidentally I am usually the one who is asking someone else to do an open problems column, a book review, a guest blog. Nice to be the askee instead of the asker for a change of pace.