Computational Complexity and other fun stuff in math and computer science from Lance Fortnow and Bill Gasarch
Monday, June 29, 2020
Can you name a famous living Chemist? Can anyone?
I was re-watching the Greatest-of-all-time Jeopardy championship and the following happen (I paraphrase)
----------------------
Alex Trebek: The category is Chemistry and we have a special guest reading the clues.
Darling: I wonder who that will be.
Bill: Hmm. I assume some famous chemist.
------------------------
So who was it? Bryan Cranston, the actor who PLAYED chemist Walter White on Breaking Bad.
Why couldn't they get a famous living chemist to read the clues?
My guess: there are no famous living chemists.
The number of famous living scientists is fairly short and they are often known for things that are not quite their science. Some are famous because the popularize science (deGrasse Tyson, Dawkins) or because of something unusual about their life (Hawkings when he was alive) or for something else entirely that they did (Ted Kaczynski). Are any famous for the actual work that they do in the science?
Andrew Wiles was famous for a brief time, and even made People Magazine's 25 most intriguing people of the year list in the early 1990's (after he solved Fermat's Last Theorem). So he was famous but it was short lived.
Terry Tao was on the Colbert Report (see here) after he won the Fields Medal, the MacAuthor Genius award, and the Breakthrough prize. And even that fame was short lived.
I looked at the web page of Nobel Prize winners, here.
The only Chemistry Nobel's I recognized were Marie Curie, Irene Joilet-Curie (Marie's Daughter), and Erst Rutherford.
The only Physics Nobel's I recognized were
Richard Feynman,
Eugene Wigner (for writing about The unreasonable effectiveness of mathematics in the natural sciences),
Richard Hofstadter (since he was the father of Douglas H and an uncle of Leonard H)
Andrew Geim (since he won both an Ig-Noble prize and a Nobel prize, see here)
Wolfgang Pauli (I've heard the term `Pauli Principle" though I did not know what it was until I looked it up while preparing this blog. I prob still don't really know what it means.)
Enrico Fermi
Erwin Schrodinger
Paul Dirac
Robert Millikan
Albert Einstein
Max Karl Ernest Ludwig Planck (I thought his last name was `Institute')
Johannes Diderik van der Waals
Pierre Curie
Marie Curie
So, some questions:
a) Am I wrong? Are there famous living chemists I never heard of? Are there any famous living scientists who are famous for their work in science?
b) If I am right then was there ever a time when there were famous scientists?
c) If there was such a time, what changed?
(I ask all of this non-rhetorically and with no agenda to push.)
Monday, June 22, 2020
Winner of Ramsey Meme Contest
My REU program had a Ramsey Meme Contest.
The winner was Saadiq Shaik with this entry:
I Don't Always...
I challenge my readers to come up with other Ramsey Memes! or Complexity Memes! or point me to some that are already out there.
The winner was Saadiq Shaik with this entry:
I Don't Always...
I challenge my readers to come up with other Ramsey Memes! or Complexity Memes! or point me to some that are already out there.
Thursday, June 18, 2020
On Chain Letters and Pandemics
Guest post by Varsha Dani.
My 11-year-old child received a letter in the mail. "Send a book to the first person named," it said, "then move everyone's name up the list, add your own name and send copies of the letter to six friends. In a few weeks you will receive 36 books from all over the world!". Wow. When I first encountered chain letters in the mid eighties, it was postcards, but even then it hadn't taken me in. Since then I hadn't seen one of these in a long time, but I guess with a lot of people suddenly at home for extended periods, people crave both entertainment and a connection to others.
What's wrong with chain letters? Well quite apart from the fact that they are illegal, even a child can comprehend that the number of books (or postcards or other gifts) received must equal the number sent, and that for every participant who does get a rich reward, there will be many who get nothing.
But there is another kind of chain communication going around. It is an email, asking the recipient to send a poem or meditation to somebody, and later they will receive many communications of the same sort. How endearing. Poetry. Sweetness and Light. No get-rich-quick pyramid schemes here. What's wrong with that?
Of course, it depends on what one means by "wrong". Maybe you like exchanging poetry with strangers. Maybe you don't find it onerous or wish that your spam filter would weed it out. But let's leave aside those issues and look at the math alone. You send the email to two friends, each of whom forwards it to two of their friends and so on. So the number of people the email reaches ostensibly doubles every step. Exponential growth. But in fact that is not what the graph of human connections looks like. Instead, what happens is that the sets of friends overlap, so that after a while the growth stops being exponential and tapers down.
Where else have we seen something like that? Oh, right. The pandemic. The virus jumps from infected people to the people they meet, and from them to the people they meet and so on. Initially, that's exponential growth fof new cases, but after a while it tapers off, forms a peak and then starts to decrease. Why? Because eventually there is overlap in the sets of people that each infected person is "trying" (unintentionally) to infect, and a newly infected person who got the virus from one or many previously infected people is still just one newly infected person.
So the chain letter spreads just like a virus. Indeed if one were to, somewhat fancifully, think of the chain letter as an independent entity whose goal is to self-replicate, then it looks even more like a virus, and, like a virus, it can only achieve its self-replication goal through the help of a host. But here's a way in which it is not like a virus. Once one has got the virus and recovered, one (hopefully) does not get it again. Not so the chain letter, of which one may get many copies over time! So maybe you will get some gifts or poetry, but you will likely also get more requests for them!
So what's wrong with the poetry chain email? It depends on your perspective. To those of you who are wistfully waiting for that Poem from a Stranger, I dedicate the following to you.
An open letter to my 2n dearest friends:
A letter came for me today
It promised wondrous ends
If only I would forward it
To just two other friends.
If they in turn should send it on
to two more that they know,
the goodwill that we're sending out
would grow and grow and grow.
Is this as pleasant as it seems?
Alas, dear friends, it's not.
This exponential growth can lead
To quite a sticky spot.
Friends of friends of friends of mine
May very well be linked
The further that the letters go.
These folks are not distinct!
Ensuring there's no overlap
Is a logistic* pain.
As you will see, when you receive
That letter yet again.
So while you're stuck at home this year
And pacing in your room.
Pick up the phone and make a call
Or see your friends on Zoom.
Your real thoughts would make me smile.
Chain letters are a con.
Do everyone a favor and
Don't send that letter on!
--------------
Monday, June 15, 2020
Presentations of Diffie-Helman leave out how to find g
When I first taught Diffie Helman I read the following
1) Alice and Bob agree on p a prime and g a generator
2) Alice picks a, sends g^a to Bob, Bob picks b, sends g^b to Alice
3) Alice computes (g^b)^a and Bob computes (g^a)^b so they both have g^{ab}
I knew how to find a prime- pick a number of length n (perhaps make sure the last digit is not even) and test for primality, if not then try again, you'll get one soon enough. I did not know how to find g. I had thought you first find p, and then given p you find g. I then figured out that you make actually pick p to be a safe prime, so q=(p-1)/2 is a prime, and then just pick random g and test them via computing g^2 and g^q: if neither is 1 then g is a generator. You will find a generator soon enough.
That was all fine. But how come my source didn't say how to find g.?You need to know that to run the algorithm. That was years ago. Then I wondered how common it is for an explanation to not say how to find g. So I Googled ``Diffie-Helman'' I only record those that had some technical content to them, and were not about other DH such as Elliptic Curves.
0) The Original DH paper Page 34: alpha is a fixed primitive element of GF(alpha). No mention of how to find either the prime q or the prim root alpha.
1) Wikiepdia: ... protocol uses the mult group of integers mod p, where p is a prime and g is a prim root mod p. NO mention of how they find p or g.
2) Wolfram's MathWorld: They agree on two prime numbers g and p, where p is large and g is a prim root mod p. In practice it is good to choose p such that (p-1)/2 is also prime. They mention (p-1)/2 but not for the reason I give. (There are algorithms for Discrete Log that do well if (p-1)/2 has many factors.)
3) Comparatech: Alice and Bob start out by deciding two numbers p and g. No mention of how to find p or g.
4) Searchsecurity Won't bother quoting, but more of the same, no mention of how to find p or g.
5) The Secret Security Wiki Alice and Bob agree on p and g.
6) Science Direct More of the same.
7) Notes from a UCLA Crypto Course YEAH! They say how to find g.
8) Brilliant (yes that really is the name of this site) Brilliant? Not brilliant enough to realize you need to say how to find p and g.
9) OpenSSL Hard to tell. Their intuitive explanation leaves it out, but they have details below and code that might have it.
I looked at a few more but it was the same story.
This is NOT a RANT or even a complaint, but its a question:
Why do so few expositions of DH mention how to find p,g? You really need to do that if you really want to DO DH.
Speculation
1) Some of the above are for the laymen and hence can not get into that. But some are not.
2) Some of them are for advanced audiences who would know how to do it. Even so, how to find the generator really needs to be mentioned.
3) Goldilocks: Some papers are for the layman who would not notice the gap, and some papers are for the expert who can fill in the gap themselves, so no paper in between. I do not believe that.
4) The oddest of the above is that the original paper did not say how to find g.
1) Alice and Bob agree on p a prime and g a generator
2) Alice picks a, sends g^a to Bob, Bob picks b, sends g^b to Alice
3) Alice computes (g^b)^a and Bob computes (g^a)^b so they both have g^{ab}
I knew how to find a prime- pick a number of length n (perhaps make sure the last digit is not even) and test for primality, if not then try again, you'll get one soon enough. I did not know how to find g. I had thought you first find p, and then given p you find g. I then figured out that you make actually pick p to be a safe prime, so q=(p-1)/2 is a prime, and then just pick random g and test them via computing g^2 and g^q: if neither is 1 then g is a generator. You will find a generator soon enough.
That was all fine. But how come my source didn't say how to find g.?You need to know that to run the algorithm. That was years ago. Then I wondered how common it is for an explanation to not say how to find g. So I Googled ``Diffie-Helman'' I only record those that had some technical content to them, and were not about other DH such as Elliptic Curves.
0) The Original DH paper Page 34: alpha is a fixed primitive element of GF(alpha). No mention of how to find either the prime q or the prim root alpha.
1) Wikiepdia: ... protocol uses the mult group of integers mod p, where p is a prime and g is a prim root mod p. NO mention of how they find p or g.
2) Wolfram's MathWorld: They agree on two prime numbers g and p, where p is large and g is a prim root mod p. In practice it is good to choose p such that (p-1)/2 is also prime. They mention (p-1)/2 but not for the reason I give. (There are algorithms for Discrete Log that do well if (p-1)/2 has many factors.)
3) Comparatech: Alice and Bob start out by deciding two numbers p and g. No mention of how to find p or g.
4) Searchsecurity Won't bother quoting, but more of the same, no mention of how to find p or g.
5) The Secret Security Wiki Alice and Bob agree on p and g.
6) Science Direct More of the same.
7) Notes from a UCLA Crypto Course YEAH! They say how to find g.
8) Brilliant (yes that really is the name of this site) Brilliant? Not brilliant enough to realize you need to say how to find p and g.
9) OpenSSL Hard to tell. Their intuitive explanation leaves it out, but they have details below and code that might have it.
I looked at a few more but it was the same story.
This is NOT a RANT or even a complaint, but its a question:
Why do so few expositions of DH mention how to find p,g? You really need to do that if you really want to DO DH.
Speculation
1) Some of the above are for the laymen and hence can not get into that. But some are not.
2) Some of them are for advanced audiences who would know how to do it. Even so, how to find the generator really needs to be mentioned.
3) Goldilocks: Some papers are for the layman who would not notice the gap, and some papers are for the expert who can fill in the gap themselves, so no paper in between. I do not believe that.
4) The oddest of the above is that the original paper did not say how to find g.
Monday, June 08, 2020
The Committee for the Adv. of TCS- workshop coming up SOON!
(Posted by request from Jelani Nelson.)
The Committee for the Advancement of Theoretical Computer Science (CATCS)
is organizing a Visioning workshop. The primary objective of the workshop
is for TCS participants to brainstorm directions and talking points for TCS
program managers at funding agencies to advocate for theory funding.
There was some question of whether or not it would run this summer, but
YES, it is going to run.
If you are interested then reply (at the link below) by June 15.
This is SOON so click that link SOON.
The time commitment is 4-5 hours during the week of July 20-July 24 for
most participants, or roughly 10 hours for those who are willing to
volunteer to be group leaders.
The link to sign up is:
Tuesday, June 02, 2020
How to handle grades during the Pandemic
In March many Colleges sent students home and the rest of the semester was online. This was quite disruptive for the students. Schools, quite reasonably, wanted to make it less traumatic for students.
So what to do about grades? There are two issues. I state the options I have heard.
ISSUE ONE If P/F How to Got About it?
1) Grade as usual.
2) Make all classes P/F.
PRO: Much less pressure on students.
CON: Might be demoralizing for the good students.
3) Make all classes P/F but allow students to opt for letter grades BUT they must decide before the last day of class. Hence teachers must post cutoffs before the final is graded
CON: Complicated and puts (a) teachers in an awkward position of having to post cutoffs before the final, and (b) puts students in an awkward position of having to predict how well they would do.
CON: A student can blow off a final knowing they will still get a D (passing) in the course.
PRO: Good students can still get their A's
CAVEAT: A transcript might look very strange. Say I was looking at a graduate school applicant and I see
Operating Systems: A
Theory of Computation: P
I would likely assume that the Theory course the student got a C. And that might be unfair.
3) Make all classes P/F but allow students to opt for letter grades AFTER seeing their letter grades.
PRO: Less complicated an awkard
PRO: A students blah blah
CAVEAT above still applies.
ISSUE TWO If P/F what about a D in the major
At UMCP COMP SCI (and I expect other depts)
a D is a passing grade for the University
but
a D is not a passing grade for the Major.
So if a s CS Major gets a D in Discrete Math that does not count for the major--- they have to take it over again.
But if classes are P/F what do do about that.
Options
1) Students have to take classes in their major for a letter grade.
CON: The whole point of the P/F is to relieve pressure on the students in these hard times.
PRO: None.
2) Students taking a course in their major who get a D will still get a P on the transcript but will be told that they have to take the class over again.
3) Do nothing, but tell the students
IF you got a D in a course in your major and you are taking a sequel, STUDY HARD OVER THE SUMMER!
4) Do nothing, but tell the teachers
Students in the Fall may have a weak background. Just teach the bare minimum of what they need for the major.
(Could do both 3 and 4)
SO- what is your school doing and how is it working?
So what to do about grades? There are two issues. I state the options I have heard.
ISSUE ONE If P/F How to Got About it?
1) Grade as usual.
2) Make all classes P/F.
PRO: Much less pressure on students.
CON: Might be demoralizing for the good students.
3) Make all classes P/F but allow students to opt for letter grades BUT they must decide before the last day of class. Hence teachers must post cutoffs before the final is graded
CON: Complicated and puts (a) teachers in an awkward position of having to post cutoffs before the final, and (b) puts students in an awkward position of having to predict how well they would do.
CON: A student can blow off a final knowing they will still get a D (passing) in the course.
PRO: Good students can still get their A's
CAVEAT: A transcript might look very strange. Say I was looking at a graduate school applicant and I see
Operating Systems: A
Theory of Computation: P
I would likely assume that the Theory course the student got a C. And that might be unfair.
3) Make all classes P/F but allow students to opt for letter grades AFTER seeing their letter grades.
PRO: Less complicated an awkard
PRO: A students blah blah
CAVEAT above still applies.
ISSUE TWO If P/F what about a D in the major
At UMCP COMP SCI (and I expect other depts)
a D is a passing grade for the University
but
a D is not a passing grade for the Major.
So if a s CS Major gets a D in Discrete Math that does not count for the major--- they have to take it over again.
But if classes are P/F what do do about that.
Options
1) Students have to take classes in their major for a letter grade.
CON: The whole point of the P/F is to relieve pressure on the students in these hard times.
PRO: None.
2) Students taking a course in their major who get a D will still get a P on the transcript but will be told that they have to take the class over again.
3) Do nothing, but tell the students
IF you got a D in a course in your major and you are taking a sequel, STUDY HARD OVER THE SUMMER!
4) Do nothing, but tell the teachers
Students in the Fall may have a weak background. Just teach the bare minimum of what they need for the major.
(Could do both 3 and 4)
SO- what is your school doing and how is it working?