Still Typecasting from Dagstuhl

Lance: Bill, in our typecast earlier this week I said you were older than me. But 68? You don't look day over 66.

Bill: Neither do you. But seriously, why do you think I'm 68?

Lance: I just Google'd "How old is Bill Gasarch?"

Bill: Don't believe everything you read on the Internet. I'm really 58.

Lance: Prove it.

Bill: Here's my driver's license.

Lance: Bill you don't drive. And it literally says "NOT A DRIVER'S LICENSE" on the back. But it is an official State of Maryland Identification card stating that you were born in 1959. Are you saying I should trust the state of Maryland over Google?

Bill: Yes, because they pay my salary. Back to Dagstuhl. Let's talk about the talks. William Hoza gave a nice talk about hitting sets for L (deterministic small space) vs RL (randomized small space)  but when I asked him when will we prove L = RL he said not for fifty years. Grad students are not supposed to be that pessimistic.

Lance: You mean realistic. Though I'd guess more like 10-20 years. I wouldn't even be surprised if NL (nondeterministic log space) = L.

Arpita Korwar: I say 10-15 years.

Bill: Can we put that in the blog?

Lance: Too late. Bill I heard you were the stud muffin this week.

Bill: Yes, I talked about the muffin problem. Got a problem with that?

Lance: Needed milk. I saw this talk two years ago and now you have cool theorems. Who would've thought if you have 24 muffins and 11 people you can allocate 24/11 muffins and the smallest piece is 19/44, and that's the best possible for maximizing the smallest piece.

Bill: I can't believe you actually listened to the talk and didn't fall asleep.

Lance: zzzzzz. Did you say something?

Bill: Never mind. Eric Allender talked about the minimum circuit-size problem: Given a truth-table of a function f is there a circuit for f less that a given size w. The problem is frustrated, just consider the following theorem: if MCSP is NP-complete then EXP does not equal ZPP (exponential time in zero-error probabilistic polynomial-time).

Lance: Do you think EXP = ZPP?

Bill: No, the result only tells us it will be hard to prove MSCP is NP-complete without informing us whether or not it is NP-complete. Allender did show that under projections it isn't NP-complete (Editor's Note: I should have said log-time projections see Eric's comment. SAT and all your favorite NP-complete problems are complete under log-time projections). MSCP might be complete under poly-time reductions but not under weaker reductions.

Lance: Reminds me of the Kolmogorov random strings that are hard for the halting for Turing reductions but not under many-one reductions.

Bill: Everything reminds you of the Kolmogorov strings.

Lance: As they should.

Bill: I liked Michal Koucký's talk on Gray codes.

Lance: Shouldn't that be grey codes. We're not in the UK.

Bill: It's the color you moron. It's named after Frank Gray.

Lance: You are smarter than you look, not bad for a 68 year old. I missed Koucký's talk due to a sports injury, but he did catch me up later.

Bill: I never put Lance and sports in the same sentence before.

Lance: And I never put Bill and driving together. It's a new day for everything. Koucký showed how to easily compute the next element in the Gray code querying few bits as long as the alphabet size is of size 3.

Bill: Which contrasts Raskin's 2017 paper that shows with a binary alphabet you need to query at least half the bits.

Lance: Hey you stole my line.

Bill: That's not possible. You are editing this. I think this typecast has gone long enough. Take us out.

Lance: In a complex world, best to keep it simple.

Lance and Bill go to Dagstuhl: The Riemann Edition

Lance: Welcome to our typecast directly from Dagstuhl in Southwestern Germany for the 2018 edition of the seminar on Algebraic Methods in Computation Complexity. Say hi Bill.

Bill: Hi Bill. So Lance are you disappointed we didn't go to Heisenberg for the Michael Atiyah talk claiming a solution to the Riemann Hypothesis.

Lance: I knew how fast I was going but I got lost going to Heisenberg. I think you mean the Heidelberg Laureate Forum a 100 miles from here. From what I heard we didn't miss much. For those who care here is the video, some twitter threads and the paper.

Bill: Too bad. When I first heard about the claim I was optimistic because (1) László Babai proved that graph isomorphism is in quasipolynomial-time at the age of 65 and (2) since Atiyah was retired he had all this time to work on it. Imagine Lance if you were retired and didn't have to teach or do administration, could you solve P vs NP? (This gets an LOL from Nutan Limaye)

Lance: I'll be too busy writing the great American novel. Before we leave this topic, don't forget about the rest of the Laureate Forum, loads of great talks from famous mathematicians and computer scientists. Why didn't they invite you Bill?

Bill: They did but I rather be at Dagstuhl with you to hear about lower bounds on matrix multiplication from Josh Alman. Oh, hi Josh I didn't see you there.

Josh: Happy to be here, it's my first Dagstuhl. I'm flying around the world from Boston via China to get here. Though my friends say it's not around the world if you stay in the Northern hemisphere. They are a lot of fun at parties. But not as much fun as matrix multiplication.

Bill: So Josh, what do you have to say about matrix multiplication. Is is quadratic time yet?

Josh: Not yet and we show all the current technique will fail.

Bill: Wouldn't Chris Umans disagree?

Kathryn Fenner: You shouldn't pick on Canadians [Ed note: Josh is from Toronto]. Pick on students from your own country.

Josh: (diplomatically) I think Chris Umans has a broader notion of what counts as known methods. There are some groups that aren't ruled out but we don't know how to use them.

Chris: Very well put. The distinction is between powers of a fixed group versus families of groups like symmetric groups. The later one seems like the best place to look.

Lance: Thanks Chris. Josh, what are your impressions of Dagstuhl so far?

Josh: I like the sun and grass. I wish it was easier to get here.

Lance: This is only the first day. You haven't even found the music room yet, past the white room, past the billiard room where Mr. Green was murdered with the candlestick. Oh hi Fred Green. Luckily Dr. Green is still alive. I remember my first Dagstuhl back in February of 1992.

Josh: Two months before I was born.

Lance: Way to make me feel old.

Bill: You are old.

Lance: You are older. Believe it or not six from that original 1992 meeting are here again this week: The two of us, Eric Allender, Vikaurum Arvind, Uwe Schöning and Jacobo Torán. Amazing how accents show up as we talk.

Bill: What did I sleep through this morning before Josh's talk?

Lance: Amnon Ta-Shma talked about his STOC 2017 best paper and Noga Ron-Zewi showed some new results on constructive list-decoding.

Bill: Let's do this again later in the week. Lance, takes us out.

Lance: In a complex world, best to keep it simple.

Why wasn't email built securely?

Recently I talked with Ehsan Hoque, one of the authors of the ACM Future of Computing Academy report that suggested "Peer reviewers should require that papers and proposals rigorously consider all reasonable broader impacts, both positive and negative." which I had satirized last May.

Ehsan said that "if email had sender authentication built in from the beginning then we wouldn't have the phishing problems we have today". Leaving aside whether this statement is fully true, why didn't we put sender authentication and encryption in the first email systems?

Email goes back to the 60's but I did get involved on the early side when I wrote an email system for Cornell in the early 80's. So let me take a crack at answering that question.

Of course there are the technical reasons. RSA was invented just a few years earlier and there were no production systems and the digital signatures needed for authentication were just a theory back then. The amount of overhead needed for encryption in time and bandwidth would have stopped email in its tracks back then.

But it's not like we said we wish we could have added encryption to email if we had the resources. BITNET which Cornell used and the ARPANET gateway only connected with other universities, government agencies and maybe some industrial research labs. We generally trusted each other and didn't expect anyone to fake email for the purpose of getting passwords. It's not like these emails could have links to fake login pages. We had no web back then.

But we did all receive an email from a law firm offering green card help. My first spam message. We had a mild panic but little did we guess that spam would nearly take down email at the turn of the century. Nor would we have guessed the solution would come from machine learning which kills nearly all spam and much of the phishing emails today.

I don't disagree with the report that we shouldn't think about the negative broader impacts, but the true impacts negative and positive are nearly impossible to predict. Computer Science works best when we experiment with ideas, get things working and fix problems as they arise. We can't let the fear of the future prevent us from getting there.

What is a Physicist? A Mathematician? A Computer Scientist?

 Scott Aaronson recently won the Tomassoni-Chisesi Prize in Physics (yeah Scott!).
In his post (here) about it he makes a passing comment:

I'm of course not a physicist

I won't disagree (does that mean I agree? Darn Logic!) but it raises the question of how we identify ourselves. How to answer the question:

Is X a Y?

(We will also consider why we care, if we do.)

Some criteria below. Note that I may say thinks like `Dijkstra is obviously a computer scientist'
but this is cheating since my point is that it may be hard to tell these things (though I think he is).

1) If X in a Y-dept then X is a Y. While often true, there are some problems: MIT CS is housed in Mathematics, some people change fields. Readers- if you know someone who is in dept X but really does Y, leave a comment. (CORRECTION- I really don't know how MIT is structured. I do know that the Math Dept has several people who I think of as Computer Scientists: Bonnie Burger,  Michael Goemans, Tom Leighton, Peter Shor, Michael Sipser. There may be others as well. The point being that I would not say `Sipers is a mathematician because he is in the MIT Math Dept')

2) If X got their degree in Y then they are Y. Again, people can change fields. Also, some of the older people in our field got degrees in Physics or Math since there was no CS (I am thinking Dijkstra-Physics, Knuth-Math). Even more recently there are cases. Andrew Child's degree is in Physics, but he did quantum computing. Readers- if you know someone who got there degree in X but is now donig Y, leave a comment.

3) Look at X's motivation. If Donald Knuth does hard math but he does it to better analyze algorithms, then he is a computer scientist. One problem -- some people don't know their own motivations, or it can be hard to tell. And people can get distracted into another field.

4) What does X call himself? Of course people can be wrong. The cranks he email me their proofs that R(5) is 40 (its not) think the are mathematicians. They are not- or are they? see next point

5) What X is interested in, ind. of if they are good at it or even know any. Not quite right- if an 8 year old  Bill Gasarch is interested in the Ketchup problem that does not make him a mathematician.

6) What X is working on right now. Fine but might change. And some work is hard to classify.

7) If you win an award in X, then you are an X. Some exceptions

Scott is a computer scientist who won the Tomassoni-Chisesi Physics Prize

Ed Witten is a Physicist who won the Fields Medal (Math)

John Nash is a mathematician who won a Nobel prize in Economics.

I want to make a full circle- so if you know other X won a prize in Y then leave a comment and
we'll see what kind of graph we get. Bipartite with people on one side and fields on the other.

8) What they can teach? Helpful in terms of hiring when you want to fill teaching needs.

Does any of this matter? We use terms like `mathematician' `physicist' `computer scientist' as shorthand for what someone is working on, so its good to know we have it right.

P = NP and Cancer

Often when the question comes to what happens if P = NP, one typically hears the response that it kills public-key cryptography. And it does. But that gives the impression that given the choice we would rather not have P = NP. Quite the opposite, P = NP would greatly benefit humanity from solving AI (by finding the smallest circuit consistent with the data) and curing cancer. I've said this before but never explained why.

Of course I don't have a mathematical proof that P = NP cures cancer. Nor would an efficient algorithm for SAT immediately give a cancer cure. But it could work as follows:

1. We need an appropriately shaped protein that would inhibit the cancer cells for a specific individual without harming the healthy cells. P = NP would help find these shapes perhaps just the DNA of the person and the type of cancer.
2. At this point we don't understand the process that takes a ACGT protein sequence and describes that shape that it forms. But it must be a simple process because it happens quickly. So we can use P = NP to find a small circuit that describes this process.
3. Use P = NP to find the protein sequence that the circuit from #2 will output the shape from #1.

We'll need an truly efficient algorithm for NP problems for this to work. A n⁵⁰ algorithm for SAT won't do the job. All this steps may happen whether or not P = NP but we'll need some new smart algorithmic ideas.

Please note this is just a thought exercise since I strongly believe that P ≠ NP. I do not want to give false hope to those with friends and loved ones with the disease. If you want to cure cancer your first step should not be "Prove P = NP". 

The Tenure system is broken but not in the way that you think (Anon Guest Post)

This is an ANON guest post. Even I don't know who it is! They emailed me asking if they
could post on this topic, I said I would need to see the post. I did and it was fine.

-----------------------------------------------------------------------------------------------------------------
I have written many tenure/promotion letters before. But this summer, I was especially inundated with requests. Thinking about my past experiences with such letters, I started to question their value.

For those unfamiliar with the process, let me explain. When someone is applying for a research job, they typically need to have recommendation letters sent on their behalf. Once someone is hired in
a tenure-track position, they then need to get additional letters each time they are promoted (in the US, this will typically occur when someone is granted tenure and again when they are promoted to full
professor).

Now, I know from experience that recommendation letters are scrutinized very carefully, and often contain useful nuggets of information. I am not questioning the value of such letters (though
they may have other problems). I am focusing here only on tenure/promotion letters.

Let me fill in a bit more detail about the tenure/promotion process,since it was a mystery to me before I started an academic position. (I should note that everything I say here is based only on how things are
done at my institution; I expect it does not differ much at other US universities, but it may be different in other countries.) First, the department makes a decision as to whether to put forward someone's
case for promotion. If they do, then a package is prepared that includes, among other things, the external recommendation letters I am talking about. After reviewing the candidate's package, the department holds an official vote; if positive, then the package is reviewed and
voted on by higher levels of administration until it is approved by the president of the university.

The external letters appear very important, and they are certainly discussed when the department votes on the candidate's case. However, I am not aware of any cases (in computer science) where someone who was put forward for tenure was denied tenure. (In contrast, I am aware of a very small number cases where a department declined to put someone forward for tenure. In such cases, no letters are ever
requested.) Perhaps more frustrating, this seems to be the case even when there are negative letters. In fact, I have written what I consider to be "negative" letters in the past only to see the candidate still get tenure.(To be clear, by academic standards a negative letter does not mean saying anything bad, it just means not effusively praising the candidate.) This makes be believe that these letters are simply being used as "checkboxes" rather than real sources of information to take into account during the decision-making process. Essentially, once a department has decided to put someone forward for promotion, they have effectively also decided to vote in favor of their promotion.

Letters take a long time to write, especially tenure/promotion letters, and especially when you are not intimately familiar with someone's work (even if they are in the same field). But if they are
basically ignored, maybe we can all save ourselves some time and just write boilerplate letters (in favor of tenure) instead?




Are Conferences Discriminatory?

Glencora Borradaile wrote a blog post in June about how conferences discriminate.

Let me spell it out. In order to really succeed in most areas of computer science, you need to publish conference papers and this, for the most part, means attendance at those conferences. But because of the institutional discrimination of border control laws and the individual discrimination that individuals face and the structural discrimination that others face, computer science discriminates based on nationality, gender identity, disability, and family status, just to name a few aspects of identity.

Suresh Venkatasubramanian follows up with a tweet storm (his words) echoing Glencora's points.

Is there structural (i.e not intentional or institutional) bias in how conferences operate? I.e is there a systematic and persistent disadvantage to certain groups from how conferences are structured? If we consider location, and groups = non-US people, then yes.

— Suresh Venkatasubramanian (@geomblog) July 6, 2018

Ryan Williams had a twitter thread defending conferences.

Because of where I live and work, I can collaborate with and see talks by many more people than the average person in my field. To me, conferences serve as a way of *leveling* that field, giving a venue where people from all over can benefit similarly.

— R. Ryan Williams (@rrwilliams) July 7, 2018

Not much difference these day between blog posts, tweet storms and twitter threads and I recommend you read through them all.

Much as I think conferences should not serve as publication venues, they do and should play a major role in connecting people within the community. We should do our best to mitigate the real concerns of Glencora and Suresh, create an environment that everyone feels comfortable, have travel support and child care to make it easier and have meetings in different countries so those with visa issues can still attend at times. But we cannot eliminate the conference without eliminating the community. Personal interactions matter.

The Rule of Threes/Astrology

On Aug 16, 2018 Aretha Franklin died. A famous singer.

On Aug 18 2018 Kofi Anan died. A famous politician.

On Aug 25, 2018 John McCain died. A famous politician.

On Aug 26, 2018 Neil Simon died, a famous playwright.

For 12 famous people who died between Aug 5 and Aug 26 see here (be careful- there are a few more on the list who died in August but a different year).

One could group those 12 into four sets of three and claim the rule of threes that celebrities die in threes. There was an episode of  30 Rock   where two celebrities had died and Tracy Jordan (a celeb) tried to kill a third one so he would not be a victim of the rule of threes. (see the short video clip: here.)

How would one actually test the rule of threes? We would need to define the rule carefully. I have below a well defined rule, with parameters you can set, and from that you could do data collection (this could be a project for a student though you would surely prove there is no such rule).

1. Decide on a definite time frame: T days. The deaths only count if they are within T days.
2. Define celebrity. This may be the hardest part. I'll start with they must have a Wikipedia page of length W and they must have over H  hits on Google. This may be hard to discern for people with common names or alternative spellings. You might also look into Friends on Facebook and  Followers on Twitter. A big problem with all of this is that if you want to do a study of old data, before there was Google, Wikipedia, Facebook, and Twitter, you will need other criteria (ask your grandparents what it was like in those days).
3. Decide whether or not to have a cutoff on age. You may decide that when Katherine Hepburn, Bob Hope, and Strom Thurmond died less than a month apart, at the ages of 96, 100, 100 this doesn't qualify. Hence you may say that the celebrities who die must be younger than Y  years.

I doubt anybody  will ever do the experiment--- those that believe its true (are there really such people?) have no interest in defining it carefully or testing it. And people who don't believe would not bother, partially because so few people believe it that its not worth debunking. But I wonder if a well thought out experiment might reveal something interesting. Also contrast the data to all deaths and see if there is a difference. For example, you might find that more celebs die in August then would be expected based on when all people die. Or that celebs live longer. Or shorter. Actually with enough p-hacking I am sure you could find something. But would you find something meaningful?

Astrology is in the same category- people who believe (there ARE such people!)  could do well defined experiments but have no interest in doing so. I doubt they would find anything of interest if they did. Here there are enough people who believe it in to be worth debunking, but would a well designed science experiment convince them that astrology does not have predictive powers? Has such been done?


I once DID do such an experiment to disprove a wild theory. In 2003 a cab driver once told me (1) there is no Gold in Fort Know, and Ian Fleming was trying to tell us this in the book Goldfinger,  (2)  Reagan was shot since he was going to tell,  (3) a small cohort of billionaires  runs the world. I challenged him-- if that is the case then how come in 1992 Bill Clinton beat George Bush, who was surely the billionaires  pick. He responded that Bill Clinton was a Rhodes Scholar and hence he is in-the-club. I challenged him- OKAY, predict who will get the Democratic Nomination in 2004. This was a well defined experiment (though only one data point) He would give me a prediction and I could test it. He smiled and said Wesley Clark was a Rhode Scholar. Oh well.