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. 

Complexity Year in Review 2020

For the result of the year we go to all the way back to the "before times".

MIP*=RE by Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright and Henry Yuen

A follow up to last year's runner up NEEXP in MIP*, the new paper shows how to prove everything computable and beyond to a polytime verifier with two provers who cannot communicate but share entangled quantum bits. The result had a bit of a scare but fixed up this fall.

Honorary mention goes to beating the Christofides-Serdyukov approximation for traveling salesman by Anna R. Karlin, Nathan Klein and Shayan Oveis Gharan. Nathan got his start in Bill's REU program.

Of course when we think back at 2020 it won't be the theorems but the pandemic, a divisive election and racial reckoning. The word of the year for academia is "virtual", virtual teaching, virtual research collaborations, virtual talks, virtual conferences, virtual panels and virtual job visits. For the most part the the pandemic hasn't really created new trends but accelerated trends already in place. Given the far lower costs in terms of time, money and the environment, how much of "virtual" will remain post-corona?

Bill's published a new book on muffin problems, his second book in two years. I started a new College of Computing. 

We remember Lars Arge, Ed Clarke, John Conway, Richard Dudley, Stanley Eisenstat, Ron Graham, Richard Guy, Katherine Johnson, Vaughn Jones, James Randi, Arianna Rosenbluth, Joy Thomas, Robin Thomas, Alex Trebek, Boris Tsirelson and Paul Young. 

Thanks to our guest posters Gorjan Alagic, Andrew Childs, Tom Goldstein, Daniel Gottsman, Clyde Kruskal and Jon Katz, Antoine Amarilli, Thomas Colcombet, Hugo Férée and Thomas Schwentick, Steve Butler, Varsha Dani, Evangelos Georgiadis and Emily Kaplitz.

In 2021 we will likely see the end of the pandemic and most definitely see the 50th anniversary of P versus NP. Hope for a successful and healthy year for all. 

Slowest Sorting Algorithms

Radu Gigore tweeted "People are obsessed with finding the best algorithms. What about the worst?" So here's a Christmas gift that keeps giving, the slowest of sorting algorithms. 

Before you read on, try to think of the slowest sorting algorithm. No fair spinning its wheels, sleeping or doing unrelated tasks. It should always make progress towards sorting. 

Here are some examples, in particular bogosort that generates all permutations until it finds a sorted one. Takes n! time on average.

But we can do much worse. The following redicusort algorithm I got from Stuart Kurtz back in the 90's.

Generate all permutations and then sort those permutations. The sort of the original permutation will be first on the list.

The running time depends on the sorting algorithm you use after generating the permutations.

If you use bubblesort you get a (n!)² time algorithm.

If you use bogosort you get a (n!)! bound.

What if you just call redicusort recursively? The algorithm will never end. If you want to guarantee termination you need to bound the depth of the recursion. Choose something like an Ackermann function to get a sorting algorithm that always makes progress but not primitively recursive. In general you can get a sorting algorithm that takes longer than any fixed computable function.

Dr Jill Biden

(I was helped on this post by Gorjan Alagic, Andrew Childs,  Tom Goldstein, Daniel Gottsman, Clyde Kruskal,  Jon Katz. I emailed them for their thoughts on the issue and some of those thoughts are embedded in the post. ) 

The First First Lady to have a college degree was Lucy Hayes (Rutherford B Hayes was Prez 1876-1880). Nickname: Lemonade Lucy since she did not serve alcohol. 

Trivia: who was the last first lady to not have a college degree? I'll answer that one at the end of this post. 

The First First Lady to keep her day job was Abigail Fillmore who was a teacher. (Millard Fillmore was Prez in 1850-1852. He became prez  after Zachary Taylor died in office) . 

In recent times it is  uncommon for a first lady to have a day job. So much so that it was notable when Elizabeth Dole said that if her husband (Bob Dole) won in 1996 she would keep her job at the Red Cross. 

For other first lady firsts  see here.

Jill Biden is the First First Lady to have a PhD. (ADDED LATER- one of the comments pointed out that she has an Ed. D, Doctor of Education.)   She says she will keep her day job as a professor.  Four other First ladies had advanced degrees: Pat Nixon (MS in Education), Laura Bush (MS in Library Science), Hillary Clinton (Law degree), Michelle Obama (Law degree). If I missed any, let me know. 

The WSJ had an op-ed  that said Jill Biden should not call herself `Dr'.  Inspired by that, here are thoughts on the use of the word `Dr'

1) At the 1986 Structures Conference (now Complexity Conference ) Lane Hemachandra (now Lane Hemaspaandra) gave a talk. He had just gotten his PhD a few weeks ago, so he was introduced as `DOCTOR Lane Hemchandra' Gee, most of the talks were by people with PhD's but were not introduced as such.

2) Most people I know within academia do not call themselves Dr since it sounds pretentious. However, speaking in public about an issue one might want to use `Dr' to signal that you...know stuff. However, it would be odd for a PhD in (say) linguistics to claim he knows a lot about (say) politics. It has been said: an Intellectual is someone who is an expert in one field and pontificates in another field. 

3) Does the general public think of DOCTOR as Medical Doctor? Probably yes. There are some exceptions: Dr. Martin Luther King and Dr. Henry Kissinger. Also, I think it is  more common in Psychology, pharmacy, education, and counseling to call yourself `Doctor'  

4) The article also criticized her PhD (in education, about community colleges) as `useless' . If that's the reason to not call her doctor than I shudder to think what the WSJ would think of degrees in, say, set theory with an emphasis on Large Cardinals. GEE, you can't call yourself  DOCTOR since your degree is on Ramsey Cardinals. OH, now they found an application, so now you CAN call yourself DOCTOR. OH, the application is to extending the Canonical Ramsey Theory from Polish spaces  to meta- compact  cardinals, so we can't call you DOCTOR after all. Do we really want to go down this path? 

5) I ask all of the following non-rhetorically:  Did the author read her PhD thesis? Is he qualified to judge it? Did he (as one should do) look at her entire body of work to judge her? What point is he trying to make anyway? 

6) Should Dr. Who call themselves a doctor? Are they  a medical doctor? PhD? If so, in what? Is `Who' part of their name? For other TV and movie tropes about the use of the word doctor, see here.

7) I avoid saying I am a doctor since people will then ask me about the medical condition.

I avoid saying I am a computer scientist since people will then ask me how to help them with their Facebook privacy settings. 

I avoid saying I am a mathematician since people will ask me to help their daughter with her trigonometry. 

8) The answer to my trivia question: The last first lady to not have a college degree: Melania Trump. She went to college for a year and then left. The one before her was Barbara Bush who also went for a year and then left. 

ADDED LATER: Many supervillians who don't have a PhD or an MD call themselves `Doctor', see here. Why no outrage about this? Because (1) they are fictional, and (2) imagine the scenario: Not only does Dr. Doom want to take over the world, he also doesn't even have a PhD or an MD!

ADDED LATER: Where does Dr. Pepper fit into this?